Search

Every language recognized by a non-deterministic finite automaton can be recognized by a deterministic automaton, at the cost of a potential increase of the number of states, which in the worst case can go from n states to 2ⁿ states. In this article, we investigate this classical result in a probabilistic setting where we take a deterministic automaton with n states uniformly at random and add just one random transition. These automata are almost deterministic in the sense that only one state has a non-deterministic choice when reading an input letter. In our model each state has a fixed probability to be final. We prove that for any d ≥ 1, with non-negligible probability the minimal (deterministic) automaton of the language recognized by such an automaton has more than n^d states; as a byproduct, the expected size of its minimal automaton grows faster than any polynomial. Our result also holds when each state is final with some probability that depends on n, as long as it is not too close to 0 and 1, at distance at least Ω(1/√n) to be precise, therefore allowing models with a sublinear number of final states in expectation., LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 19:1-19:14

In this paper, we propose a canonization method for fuzzy automata, i.e., a determinization method that is able to return a minimal fuzzy deterministic automaton equivalent to the original fuzzy automaton. The canonization method is derived from the well-known Brzozowski's algorithm for ordinary nondeterministic automata. For a given fuzzy automaton A, we prove that the construction M ˆ ( r ( N ( r ( A ) ) ) ) returns a minimal fuzzy deterministic automaton equivalent to A. In that construction, r ( . ) represents the reversal of a fuzzy automaton, N ( . ) is the determinization of a fuzzy automaton based on fuzzy accessible subset construction, and M ˆ ( . ) is the determinization of a fuzzy automaton via factorization of fuzzy states which also includes a simple reduction of a particular case of proportional fuzzy states. The method is accomplished for fuzzy automata with membership values over the Godel structure (also called max-min fuzzy automata). These fuzzy automata are always determinizable and have been proved useful in practical applications.

A translated finite automaton (TFA) results from a translation of a deterministic finite automaton (DFA). A translation is based on a mapping from the alphabet of the DFA to a new alphabet, where each symbol in the original alphabet is substituted with a symbol in the new alphabet. When this substitution generates a nondeterministic automaton, the TFA may need to be determinized into an equivalent DFA. Determinization of TFAs may be useful in a variety of domains, specifically in model-based diagnosis of discrete-event systems, where large TFAs constructed by model-based reasoning are processed to perform knowledge compilation. Since, in computation time, the classical Subset Construction determinization algorithm may be less than optimal when applied to large TFAs, a conservative algorithm is proposed, called Embedded Subset Construction. This alternative algorithm updates the TFA based on the mapping of the alphabet rather than building a new DFA from scratch. This way, in contrast with Subset Construction, which performs an exhaustive processing of the TFA to be determinized, the portion of the TFA that does not require determinization is not processed. Embedded Subset Construction is sound and complete, thereby yielding a DFA that is identical to the DFA generated by Subset Construction. The benefit of using Embedded Subset Construction largely depends on the portion of the TFA that actually requires determinization. Experimental results indicate the viability of Embedded Subset Construction, especially so when large TFAs are affected by small portions of nondeterminism.

Deterministic Finite Automaton (DFA) is widely employed in performing fast regular expression matching for numerous network applications. However, constructing DFA recognizing a set of regular expressions is time-consuming especially when the set is huge. In this paper, an improved approach is introduced to accelerate DFA construction based on the hierarchical merging method. The experiments demonstrate that the improved approach proposed in this paper performs about 1.6 to 3.4 times faster than the original hierarchical merging method, and 120 to 1500 times faster than the classical subset construction algorithm.

A mutating finite automaton (MFA) is a nondeterministic finite automaton (NFA) which changes its morphology over discrete time by a sequence of mutations, one mutation at each time instant. A mutation involves the insertion and/or removal of a set of states and/or transitions. This results in a sequence of NFAs, one mutated NFA for each mutation. Some application domains, including model-based diagnosis and monitoring of active systems in artificial intelligence and model-based testing in software engineering, require online determinization of MFAs. Determinizing an MFA online means generating a deterministic finite automaton (DFA) as soon as a mutation occurs, which is equivalent to the mutated NFA. Since the classical Subset Construction determinization algorithm may be inadequate for MFAs, a conservative algorithm is proposed, called Subset Restructuring, that generates the new DFA by restructuring the previous DFA based on the mutation occurred, instead of building it from scratch. Experimental results indicate the effectiveness of the approach, especially so when large MFAs change in time by small mutations.

In this work we present the algorithms to produce deterministic finite automaton (DFA) for extended operators in regular expressions like intersection, subtraction and complement. The method like “overriding” of the source NFA(NFA not defined) with subset construction rules is used. The past work described only the algorithm for AND-operator (or intersection of regular languages); in this paper the construction for the MINUS-operator (and complement) is shown.

Given a strong bimonoid P, we introduce three different behaviors of a weighted finite automaton over P (called a P − valued finite automaton), named the initial object semantics, final object semantics and run semantics. We define four forms for a P − valued nondeterministic finite automaton ( P − NFA) and three forms for a P − valued deterministic finite automaton ( P − DFA). Under the above-mentioned semantics, the equivalence and differences among the four forms of P − NFAs are discussed and the equivalence among the three forms of P − DFAs are given. Moreover, we show that some equivalence depends on right distributivity or left distributivity, or even requires P to degenerate into a semiring.

Let $S$ be a string of length $n$ with characters from an alphabet of size $\sigma$. The \emph{subsequence automaton} of $S$ (often called the \emph{directed acyclic subsequence graph}) is the minimal deterministic finite automaton accepting all subsequences of $S$. A straightforward construction shows that the size (number of states and transitions) of the subsequence automaton is $O(n\sigma)$ and that this bound is asymptotically optimal. In this paper, we consider subsequence automata with \emph{default transitions}, that is, special transitions to be taken only if none of the regular transitions match the current character, and which do not consume the current character. We show that with default transitions, much smaller subsequence automata are possible, and provide a full trade-off between the size of the automaton and the \emph{delay}, i.e., the maximum number of consecutive default transitions followed before consuming a character. Specifically, given any integer parameter $k$, $1 < k \leq \sigma$, we present a subsequence automaton with default transitions of size $O(nk\log_{k}\sigma)$ and delay $O(\log_k \sigma)$. Hence, with $k = 2$ we obtain an automaton of size $O(n \log \sigma)$ and delay $O(\log \sigma)$. On the other extreme, with $k = \sigma$, we obtain an automaton of size $O(n \sigma)$ and delay $O(1)$, thus matching the bound for the standard subsequence automaton construction. Finally, we generalize the result to multiple strings. The key component of our result is a novel hierarchical automata construction of independent interest., Comment: Corrected typos

The classical subset construction for non-deterministic automata can be generalized to other side-effects captured by a monad. The key insight is that both the state space of the determinized automaton and its semantics---languages over an alphabet---have a common algebraic structure: they are Eilenberg-Moore algebras for the powerset monad. In this paper we study the reverse question to determinization. We will present a construction to associate succinct automata to languages based on different algebraic structures. For instance, for classical regular languages the construction will transform a deterministic automaton into a non-deterministic one, where the states represent the join-irreducibles of the language accepted by a (potentially) larger deterministic automaton. Other examples will yield alternating automata, automata with symmetries, CABA-structured automata, and weighted automata.

For each regular language L we describe a family of canonical nondeterministic acceptors (nfas). Their construction follows a uniform recipe: build the minimal dfa for L in a locally finite variety V , and apply an equivalence between the category of finite V -algebras and a suitable category of finite structured sets and relations. By instantiating this to different varieties, we recover three well-studied canonical nfas: V = boolean algebras yields the atomaton of Brzozowski and Tamm, V = semilattices yields the jiromaton of Denis, Lemay and Terlutte, and V = Z 2 -vector spaces yields the minimal xor automaton of Vuillemin and Gama. Moreover, we obtain a new canonical nfa called the distromaton by taking V = distributive lattices. Each of these nfas is shown to be minimal relative to a suitable measure, and we derive sufficient conditions for their state-minimality. Our approach is coalgebraic, exhibiting additional structure and universal properties of the canonical nfas.

The paper proposes an emerging evolutionary and swarm-based intelligent water drops algorithm for email spam classification. The proposed algorithm is used along with the machine learning classification technique known as naive Bayes classifier. The intelligent water drops algorithm is used for feature subset construction, and naive Bayes classifier is applied over the subset to classify the email as spam or not spam. The result of the hybrid method is compared with other evolutionary algorithm used with machine learning classifiers. The proposed algorithm outperforms the other hybrid algorithms.

Deterministic finite automata (DFA) is widely employed in regular expression matching for content-aware applications, such as protocol identification, NIDS, load balancing, traffic billing, etc. Subset construction is the most time-consuming process when converting regular expressions to the corresponding DFA, which brings a great challenge for fast update application scenarios. Subset construction mainly consists of subset computation and subset comparison. The subset comparison is efficiently processed with the trie tree structure, but the subset computation still remains inefficient for the massive and repetitive memory accesses of NFA state transitions. Through the theoretical analysis and the example demonstration, we prove that the inefficiency mainly originates from the traditional list structures for the NFA state transitions. Then, we proposed two improved data structures for the NFA state transitions, namely the ordered list structure and the ordered array structure. These structures leverage the alphabetical order of the transitions to avoid the huge irrelevant memory accesses during subset computation. Experiments on practical rule sets demonstrate that the subset computation procedure achieves a speedup of 6x to 8x and the total DFA generation achieves a speedup of 2x to 4x.

Finite automata are exploited in several domains, including language processing, artificial intelligence, automatic control, and software engineering. Let \({\mathcal {N}}\) be a nondeterministic finite automaton (NFA) and \({\mathcal {D}}\) the deterministic finite automaton (DFA) equivalent to \({\mathcal {N}}\). Assume to decrement \({\mathcal {N}}\) by \(\varDelta {\mathcal {N}}\), thus obtaining the decremented NFA \({\mathcal {N}}' = {\mathcal {N}}\setminus \varDelta {\mathcal {N}}\), where some states and/or transitions are missing. Consider determinizing \({\mathcal {N}}'\). Instead of determinizing \({\mathcal {N}}'\) from scratch using the classical Subset Construction algorithm, we propose Decremental Subset Construction, an algorithm which generates the DFA \({\mathcal {D}}'\) equivalent to \({\mathcal {N}}'\) by updating \({\mathcal {D}}\) based on \({\mathcal {N}}\) and \(\varDelta {\mathcal {N}}\). This way, only the actions necessary to transform \({\mathcal {D}}\) into \({\mathcal {D}}'\) are applied. Although evidence from worst-case complexity analysis indicates that Decremental Subset Construction is not better than Subset Construction, in practice, when \({\mathcal {N}}\) is large and \(\varDelta {{\mathcal {N}}}\) relatively small, Decremental Subset Construction may outperform Subset Construction significantly.

Refinement checking answers the question on whether an implementation model is a refinement of a specification model, which is of great value for system verification. Some refinement relationships, e.g., trace refinement and failures/divergence refinement, have been recognized for different verification purposes. In general, refinement checking algorithms often rely on subset construction, which incurs in the state space explosion problem. Recently the anti-chain based approach has been suggested for trace refinement checking, and the results show a significant improvement. In this paper, we investigate the problems of applying the anti-chain approach to timed refinement checking (a timed implementation vs. a timed or untimed specification) and probabilistic refinement checking (a probabilistic implementation vs. a non-probabilistic specification), and show that the state space can be reduced considerably by employing the anti-chain approach. All the algorithms have been integrated into the model checking tool PAT, and the experiments have been conducted to show the efficiency of the application of anti-chains.

For the past time a number of algorithms were presented to produce a deterministic finite automaton (DFA) for the regular expression. These algorithms could be divided into what they used as an initial data from which to produce DFA. The method to produce DFA from non-deterministic finite automaton (NFA) by a subset construction could be generalized for extended regular expressions, including intersection, negation and subtraction of the regular languages. In this article the modified algorithm of subset construction is presented; this algorithm produces a unigram DFA for the regular expression with extensions (specifically AND-operator). General Terms Pattern Recognition; Finite Automata; Algorithms.

Display Omitted A hybrid finite automaton is proposed with deterministic and nondeterministic parts.The hybrid FA is capable of inspecting multiple characters in parallel.The space required by the finite automata is efficient when scales up.The transitions number increases almost linearly to the number of multi-character.A configurable multi-stage architecture can implement the hybrid finite automaton. The throughput of a string-matching engine can be multiplied up by inspecting multiple characters in parallel. However, the space that is required to implement a matching engine that can process multiple characters in every cycle grows dramatically with the number of characters to be processed in parallel. This paper presents a hybrid finite automaton (FA) that has deterministic and nondeterministic finite automaton (NFA and DFA) parts and is based on the Aho-Corasick algorithm, for inspecting multiple characters in parallel while maintaining favorable space utilization. In the presented approach, the number of multi-character transitions increases almost linearly with respect to the number of characters to be inspected in parallel. This paper also proposes a multi-stage architecture for implementing the hybrid FA. Since this multi-stage architecture has deterministic stages, configurable features can be introduced into it for processing various keyword sets by simply updating the configuration. The experimental results of the implementation of the multi-stage architecture on FPGAs for 8-character transitions reveal a 4.3 Gbps throughput with a 67MHz clock, and the results obtained when the configurable architecture with two-stage pipelines was implemented in ASICs reveal a 7.9 Gbps throughput with a 123MHz clock.

Network intrusion detection and prevention systems commonly use regular expression (RE) signatures to represent individual security threats. While the corresponding deterministic finite state automata (DFA) for any one RE is typically small, the DFA that corresponds to the entire set of REs is usually too large to be constructed or deployed. To address this issue, a variety of alternative automata implementations that compress the size of the final automaton have been proposed such as extended finite automata (XFA) and delayed input DFA (D2 FA). The resulting final automata are typically much smaller than the corresponding DFA. However, the previously proposed automata construction algorithms do suffer from some drawbacks. First, most employ a "Union then Minimize" framework where the automata for each RE are first joined before minimization occurs. This leads to an expensive nondeterministic finite automata (NFA) to DFA subset construction on a relatively large NFA. Second, most construct the corresponding large DFA as an intermediate step. In some cases, this DFA is so large that the final automaton cannot be constructed even though the final automaton is small enough to be deployed. In this paper, we propose a "Minimize then Union" framework for constructing compact alternative automata focusing on the D2 FA. We show that we can construct an almost optimal final D2 FA with small intermediate parsers. The key to our approach is a space-and time-efficient routine for merging two compact D2 FA into a compact D2 FA. In our experiments, our algorithm runs on average 155 times faster and uses 1500 times less memory than previous algorithms. For example, we are able to construct a D2 FA with over 80 000 000 states using only 1 GB of main memory in only 77 min.

Deterministic finite automatons (DFAs) and nondeterministic finite automatons (NFAs) are two typical automatons used in the network intrusion detection system. Although they both perform regular expression matching, they have quite different performance and memory usage properties. DFAs provide fast and deterministic matching performance but suffer from the well-known state explosion problem. NFAs are compact, but their matching performance is unpredictable and with no worst case guarantee. In this paper, we propose a new automaton representation of regular expressions, called tunable finite automaton (TFA), to deal with the DFAs' state explosion problem and the NFAs' unpredictable performance problem. Different from a DFA, which has only one active state, a TFA allows multiple concurrent active states. Thus, the total number of states required by the TFA to track the matching status is much smaller than that required by the DFA. Different from an NFA, a TFA guarantees that the number of concurrent active states is bounded by a bound factor b that can be tuned during the construction of the TFA according to the needs of the application for speed and storage. Simulation results based on regular expression rule sets from Snort and Bro show that, with only two concurrent active states, a TFA can achieve significant reductions in the number of states and memory usage, e.g., a 98% reduction in the number of states and a 95% reduction in memory space.

Regular expression matching is the state of the art in signature based intrusion detection systems. A regular expression matching algorithm used in intrusion detection systems is expected to process data at a speed linear in size of the incoming data and also to be able to run on network devices with limited memory. Traditional DFA and NFA based algorithms fail to meet either of these two requirements. The existing techniques try to either modify a DFA or a NFA, or combine both these to find a trade off between speed and memory requirements. The idea we propose in this paper is orthogonal to existing techniques. We propose a new approach to store a finite automaton in memory which otherwise is stored as a transition table. Our approach can be used by existing algorithms to further reduce the memory requirements with a minimal increase in the processing speed.

We propose a novel approach for coping with alternating quantification as the main source of nonelementary complexity of deciding WS1S formulae. Our approach is applicable within the state-of-the-art automata-based WS1S decision procedure implemented, e.g. in MONA. The way in which the standard decision procedure processes quantifiers involves determinization, with its worst case exponential complexity, for every quantifier alternation in the prefix of a formula. Our algorithm avoids building the deterministic automata---instead, it constructs only those of their states needed for (dis)proving validity of the formula. It uses a symbolic representation of the states, which have a deeply nested structure stemming from the repeated implicit subset construction, and prunes the search space by a nested subsumption relation, a generalization of the one used by the so-called antichain algorithms for handling nondeterministic automata. We have obtained encouraging experimental results, in some cases outperforming MONA by several orders of magnitude., Comment: Accepted to TACAS'15

We propose a novel approach for coping with alternating quantification as the main source of nonelementary complexity of deciding WS1S formulae. Our approach is applicable within the state-of-the-art automata-based WS1S decision procedure implemented, e.g. in MONA. The way in which the standard decision procedure processes quantifiers involves determinization, with its worst case exponential complexity, for every quantifier alternation in the prefix of ai¾?formula. Our algorithm avoids building the deterministic automata--instead, it constructs only those of their states needed for disproving validity of the formula. It uses a symbolic representation of the states, which have a deeply nested structure stemming from the repeated implicit subset construction, and prunes the search space by a nested subsumption relation, a generalization of the one used by the so-called antichain algorithms for handling nondeterministic automata. We have obtained encouraging experimental results, in some cases outperforming MONA by several orders of magnitude.

Hereditarily finite (HF) set theory provides a standard universe of sets, but with no infinite sets. Its utility is demonstrated through a formalisation of the theory of regular languages and finite automata, including the Myhill-Nerode theorem and Brzozowski’s minimisation algorithm. The states of an automaton are HF sets, possibly constructed by product, sum, powerset and similar operations.

We propose to harness Angluin’s \(L^*\) algorithm for learning a deterministic finite automaton that describes the possible scenarios under which a given program error occurs. The alphabet of this automaton is given by the user (for instance, a subset of the function call sites or branches), and hence the automaton describes a user-defined abstraction of those scenarios. More generally, the same technique can be used for visualising the behavior of a program or parts thereof. This can be used, for example, for visually comparing different versions of a program, by presenting an automaton for the behavior in the symmetric difference between them, or for assisting in merging several development branches. We present initial experiments that demonstrate the power of an abstract visual representation of errors and of program segments.

Recently there have been increasing research interests on regular expression matching for its widely application in network systems to recognize predefined signatures in suspicious network traffic. Deterministic Finite Automaton (DFA) is the basic data structure for regular expression matching. Though DFA satisfies the need of real-time processing of network traffic in on-line systems, the construction of DFA is very time-consuming that prevents it from being applied on large sets of signature. In this article, we propose two approaches to parallelize the traditional sequential subset construction algorithm, which is used to convert a non-deterministic finite automaton (NFA) to an equivalent DFA, in order to accelerate DFA construction. The first proposed algorithm PRW is based on fine-grained locks on shared data structures to ensure multiple worker threads construct a DFA in parallel safely. The second proposed algorithm ARW splits the read and write accesses on shared data structures, and distributes the read operations and write operations to the multi-thread stage and the single-thread stage respectively. Experiment demonstrates the efficiency of our algorithms on real signatures of open source systems, and the speed-up ratio of PRW and ARW is up to 1.72 and 2.71 respectively with 4 worker threads.

Various string matching problems can be solved by means of a deterministic finite automaton (DFA) or a non-deterministic finite automaton (NFA). In non-oblivious cases, DFAs are often preferred for their run-time efficiency despite larger sizes. In oblivious cases, however, the inevitable computation and communication costs associated with the automaton size are more favorable to NFAs. We propose oblivious protocols for NFA evaluation based on homomorphic encryption and demonstrate that our method can be orders of magnitude faster than DFA-based methods, making it applicable to real-life scenarios, such as privacy-preserving detection of viral infection using genomic data.