Blogs (9) >>
SPLASH 2016
Sun 30 October - Fri 4 November 2016 Amsterdam, Netherlands
Sun 30 Oct 2016 10:30 - 10:55 at Matterhorn 1 - Second Session

Minimal acyclic deterministic finite automata (MADFAs) are frequently used to represent dictionaries, i.e. finite sets of finite words, in e.g. spell checkers, network security, packet filtering applications, and other tools. Given the size of such dictionaries, which may run into millions of words, their efficient construction is a critical issue. Acyclic Deterministic Finite Automata (ADFAs) consist of a set of states, one of them being a start state, and one or more of them being final states; and labeled transitions between states. They are deterministic, i.e. each state has at most one out-transition for a specific label; and they are acyclic, i.e. as their name says, no cycles occur. An ADFA is a MADFA if no other ADFA with fewer states accepts the same set of words. This makes MADFAs an excellent data structure to store large finite word sets like dictionaries. As a result, quite some research has gone into MADFA construction algorithms, and a number of different ones, with different characteristics, have been developed [1]. Yet no coherent implementation covering all these algorithm variants existed. In this talk, we report on our experience implementing these algorithms in a coherent Java-based toolkit, and on initial empirical performance results obtained.

[1] B. W. Watson. Constructing Minimal Acyclic Deterministic Finite Automata. PhD thesis, University of Pretoria, 2010.

Sun 30 Oct

parsing2016
10:30 - 12:10: Parsing@SLE - Second Session at Matterhorn 1
parsing2016147781980000010:30 - 10:55
Talk
parsing2016147782130000010:55 - 11:20
Talk
File Attached
parsing2016147782280000011:20 - 11:45
Talk
File Attached
parsing2016147782430000011:45 - 12:10
Demonstration
File Attached