Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their conceptual extension is the non-deterministic finite automata which also have plenty of applications. In this article, we study these models through the lens of succinct data structures where our ultimate goal is to encode these mathematical objects using information-theoretically optimal number of bits along with supporting queries on them efficiently. Towards this goal, we first design a succinct data structure for representing any deterministic finite automaton @math having @math states over a @math -letter alphabet @math using @math bits of space, which can determine, given an input string @math over @math , whether @math accepts @math in @math time, using constant words of working space. When the input deterministic finite automaton is acyclic, not only we can improve the above space-bound significantly to @math bits, we also obtain optimal query time for string acceptance checking. More specifically, using our succinct representation, we can check if a given input string @math can be accepted by the acyclic deterministic finite automaton using time proportional to the length of @math , hence, the optimal query time. We also exhibit a succinct data structure for representing a non-deterministic finite automaton @math having @math states over a @math -letter alphabet @math using @math bits of space, such that given an input string @math , we can decide whether @math accepts @math efficiently in @math time. Finally, we also provide time and space-efficient algorithms for performing several standard operations such as union, intersection, and complement on the languages accepted by deterministic finite automata.
For DFA and NFA, other than the basic structure that is mentioned in the introduction, there exists many extensions variations in the literature, for example, two-way finite automata, B " u chi automata and many more. Researchers generally study the properties, limitations and applications of these mathematical structures. One such line of study that is particularly relevant to us for this paper is the research on counting DFAs and NFAs. Since the fifties there are plenty of attempts in exactly counting the number of DFAs and NFAs with @math states over the alphabet @math , and the state-of-the-art result is due to @cite_12 for DFAs and @cite_3 for NFAs respectively. We refer the readers to the survery (and the references therein) of Domaratzki @cite_4 for more details. Basically, from these results, we can deduce the information theoretic lower bounds on the number of bits required to represent any DFA or NFA. Then we augment these lower bounds by designing data structures whose size matches the lower bounds, hence consuming optimal space, along with capable of executing algorithms efficiently using this succinct representation, and this is the main contribution of this paper.
@cite_3 @cite_4 @cite_12
2169680978 2912788251 2260314326 1966773178
We present techniques to parallelize membership tests for Deterministic Finite Automata (DFAs). Our method searches arbitrary regular expressions by matching multiple bytes in parallel using speculation. We partition the input string into chunks, match chunks in parallel, and combine the matching results. Our parallel matching algorithm exploits structural DFA properties to minimize the speculative overhead. Unlike previous approaches, our speculation is failure-free, i.e., (1) sequential semantics are maintained, and (2) speed-downs are avoided altogether. On architectures with a SIMD gather-operation for indexed memory loads, our matching operation is fully vectorized. The proposed load-balancing scheme uses an off-line profiling step to determine the matching capacity of each participating processor. Based on matching capacities, DFA matches are load-balanced on inhomogeneous parallel architectures such as cloud computing environments. We evaluated our speculative DFA membership test for a representative set of benchmarks from the Perl-compatible Regular Expression (PCRE) library and the PROSITE protein database. Evaluation was conducted on a 4 CPU (40 cores) shared-memory node of the Intel Academic Program Manycore Testing Lab (Intel MTL), on the Intel AVX2 SDE simulator for 8-way fully vectorized SIMD execution, and on a 20-node (288 cores) cluster on the Amazon EC2 computing cloud. Obtained speedups are on the order of @math O 1 + | P | - 1 | Q | · ? , where @math | P | denotes the number of processors or SIMD units, @math | Q | denotes the number of DFA states, and @math 0 < ? ≤ 1 represents a statically computed DFA property. For all observed cases, we found that @math 0.02 < ? < 0.47 . Actual speedups range from 2.3 @math × to 38.8 @math × for up to 512 DFA states for PCRE, and between 1.3 @math × and 19.9 @math × for up to 1,288 DFA states for PROSITE on a 40-core MTL node. Speedups on the EC2 computing cloud range from 5.0 @math × to 65.8 @math × for PCRE, and from 5.0 @math × to 138.5 @math × for PROSITE. Speedups of our C-based DFA matcher over the Perl-based ScanProsite scan tool range from 559.3 @math × to 15079.7 @math × on a 40-core MTL node. We show the scalability of our approach for input-sizes of up to 10 GB. Inference of deterministic finite automata (DFA) finds a wide range of important practical applications. In recent years, the use of SAT and SMT solvers for the minimum size DFA inference problem (MinDFA) enabled significant performance improvements. Nevertheless, there are many problems that are simply too difficult to solve to optimality with existing technologies. One fundamental difficulty of the MinDFA problem is the size of the search space. Moreover, another fundamental drawback of these approaches is the encoding size. This paper develops novel compact encodings for Symmetry Breaking of SAT-based approaches to MinDFA. The proposed encodings are shown to perform comparably in practice with the most efficient, but also significantly larger, symmetry breaking encodings. Deterministic finite automata DFA have long served as a fundamental computational model in the study of theoretical computer science, and the problem of learning a DFA from given input data is a classic topic in computational learning theory. In this paper we study the learnability of a random DFA and propose a computationally efficient algorithm for learning and recovering a random DFA from uniform input strings and state information in the statistical query model. A random DFA is uniformly generated: for each state-symbol pair @math , we choose a state @math with replacement uniformly and independently at random and let @math , where Q is the state space, @math is the alphabet and @math is the transition function. The given data are string-state pairs x,i¾?q where x is a string drawn uniformly at random and q is the state of the DFA reached on input x starting from the start state @math . A theoretical guarantee on the maximum absolute error of the algorithm in the statistical query model is presented. Extensive experiments demonstrate the efficiency and accuracy of the algorithm. There are two principal methods for turning regular expressions into NFA's — one due to McNaughton and Yamada and another due to Thompson. Unfortunately, both have drawbacks. Given a regular expression R of length r and with s occurrences of alphabet symbols, Chang and Paige (1992) and Bruggemann-Klein (1993) gave Θ(m + r) time and O(r) space algorithms to produce a Θ(m) space representation of McNaughton and Yamada's NFA with s + 1 states and m transitions. The problem with this NFA is that m = Θ(s2) in the worst case. Thompson's method takes Θ(r) time and space to construct a Θ(r) space NFA with Θ(r) states and Θ(r) transitions. The problem with this NFA is that r can be arbitrarily larger than s. We overcome drawbacks of both methods with a Θ(r) time Θ(s) space algorithm to construct an O(s) space representation of McNaughton and Yamada's NFA. Given any set V of NFA states, our representation can be used to compute the set U of states one transition away from the states in V in optimal time O(¦V¦ + ¦U¦). McNaughton and Yamada's NFA requires Θ(¦V¦ × ¦U¦) time in the worst case. Using Thompson's NFA, the equivalent calculation requires Θ(r) time in the worst case. Comparative benchmarks show that an implementation of our method outperforms implementations of competing methods with respect to time for NFA construction, NFA accepting testing, and NFA-to-DFA conversion by subset construction. Throughout this paper program transformations are used to design algorithms and derive programs. A transformation of special importance is a form of finite differencing used previously by Douglas Smith to improve the efficiency of functional programs.