Search

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.

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.

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.

Finite-state automata are important components in information retrieval and natural language processing software. A recursive automaton is the most compact representation of the acyclic deterministic finite-state automata. It is based on merging not only the equivalent states but also the identical substructures in an automaton. The LZ trie variant is the state-of-the-art in automata compression regarding space, but the time needed for its construction was, until now, quadratic, which has made it impractical for large inputs. In this paper, we present the first algorithm for LZ trie construction that runs in effectively linear time thereby making it an attractive choice for finite-state automata implementation. We achieve this goal by adding a new functionality to the enhanced suffix array data structure. We present two variants of the construction procedure - an optimal method regarding the final size and a method that sacrifices some compression for low intermediate memory usage. We have made the implementation of our algorithms available in an open source software package LzLex.Copyright © 2014 John Wiley & Sons, Ltd.

We revisit the problem of deciding by means of a finite automaton whether a string is uniquely decodable from its bigram counts. An efficient algorithm for constructing a polynomial-size Nondeterministic Finite Automaton (NFA) that decides unique decodability is given. This NFA may be simulated efficiently in time and space. Conversely, we show that the minimum deterministic finite automaton for deciding unique decodability has exponentially many states in alphabet size, and compute the correct order of magnitude of the exponent.

Recent studies on fuzzy automata are influenced by algebraic techniques to tackle issues like reduction, minimization and their languages. Fuzzy automaton homomorphism is one such majorally discussed technique. This paper is concerned with the group of (weak) fuzzy automaton automorphisms and constructions of all (weak) fuzzy automaton automorphisms over arbitrary fuzzy automaton. It is shown that (1) every arbitrary fuzzy automaton is decomposed into distinct primaries, (2) primaries are maximal singly generated fuzzy automata and (3) every weak fuzzy automaton homomorphism on an arbitrary fuzzy automaton is uniquely determined into weak fuzzy automaton homomorphisms on all its primaries. Therefore, the discussion begun over strongly connected fuzzy automaton and continue constructions as well as characterizations of (weak) fuzzy automaton homomorphisms, isomorphisms, endomorphisms and automorphisms sequentially over perfect fuzzy automaton, singly generated fuzzy automaton and primaries of fuzzy automaton. Finally, it is obtained that the group of weak fuzzy automaton automorphisms and its cardinality over arbitrary fuzzy automaton.

Every regular expression can be transformed into a Nondeterministic Finite Automaton (NFA) with or without  transitions. A well known algorithm called subset construction technique is used for conversion of NFA into DFA. In this paper, initially, the construction of the position automaton is given for the same. Also, the algorithm to convert this Position Automaton into DFA using subset construction technique is discussed. AMS MSC2010 Certification: 68Q45, 68Q70

It is proved that for each nondeterministic ordinal automaton there exists a deterministic ordinal automaton which is equivalent to the original one for all countable ordinals. An upper bound for the number of states of the deterministic automaton is double exponential in the number of states of the nondeterministic automaton.

Deep packet inspection, in which packet payloads are matched against a large set of patterns, is an important algorithm in many networking applications. Nondeterministic Finite Automaton (NFA) and Deterministic Finite Automaton (DFA) are the basis of existing algorithms. However, both NFA and DFA are not ideal for real-world rule sets: NFA has the minimum storage, but the maximum memory bandwidth; while DFA has the minimum memory bandwidth, but the maximum storage. Specifically, NFA and DFA cannot handle the presence of character sets, wildcards, and repetitions of character sets or wildcards in real-world rule sets. In this paper, we propose and evaluate a dual Finite Automaton (dual FA) to address these shortcomings. The dual FA consists of a linear finite automaton (LFA) and an extended deterministic finite automaton (EDFA). The LFA is simple to implement, and it provides an alternative approach to handle the repetition of character sets and wildcards (which could otherwise cause the state explosion problem in a DFA) without increasing memory bandwidth. We evaluate the automaton in real-world rule sets using different synthetic payload streams. The results show that dual FA can reduce the number of states up to five orders of magnitude while their memory bandwidth is close to minimum.

Hyper-minimization of deterministic finite automata (DFA) is a recently introduced state reduction technique that allows a finite change in the recognized language. A generalization of this lossy compression method to the weighted setting over semifields is presented, which allows the recognized weighted language to differ for finitely many input strings. First, the structure of hyper-minimal deterministic weighted finite automata is characterized in a similar way as in classical weighted minimization and unweighted hyper-minimization. Second, an efficient hyper-minimization algorithm, which runs in time [Formula: see text], is derived from this characterization. Third, the closure properties of canonical regular languages, which are languages recognized by hyper-minimal DFA, are investigated. Finally, some recent results in the area of hyper-minimization are recalled.

We exhibit the construction of a deterministic automaton that, given k > 0, recognizes the (regular) language of k-differentiable words. Our approach follows a scheme of Crochemore et al. based on minimal forbidden words. We extend this construction to the case of C\infinity-words, i.e., words differentiable arbitrary many times. We thus obtain an infinite automaton for representing the set of C\infinity-words. We derive a classification of C\infinity-words induced by the structure of the automaton. Then, we introduce a new framework for dealing with \infinity-words, based on a three letter alphabet. This allows us to define a compacted version of the automaton, that we use to prove that every C\infinity-word admits a repetition in C\infinity whose length is polynomially bounded., Comment: Accepted for publication

We present schemes of deterministic finite automata such that, for every nontrivial automaton A resulting from the scheme with n states, the state complexity of the mirror image of the language L(A) equals 2n. The construction leads to cases, where the increase in complexity is maximal in the transition from nondeterministic devices to deterministic ones. We also discuss the crucial importance of the size of the alphabet and present some open problems.

In an earlier paper, the author used derivatives to construct a deterministic automaton recognizing the language defined by an ω-regular expression. The construction was related to a determinization method invented by Safra. This paper describes a new construction, inspired by Piterman's improvement to Safra's method. It produces an automaton with fewer states. In addition, the presentation and proofs are simplified by going via a nondeterministic automaton having derivatives as states.

Deterministic finite automata (DFAs) are constructed for various purposes in computational biology. Little attention, however, has been given to the efficient construction of minimal DFAs. In this article, we define simple non-deterministic finite automata (NFAs) and prove that the standard subset construction transforms NFAs of this type into minimal DFAs. Furthermore, we show how simple NFAs can be constructed from two types of pattern popular in bioinformatics, namely (sets of) generalized strings and (generalized) strings with a Hamming neighborhood.

A number α, in the range from n to 2n, is magic for n with respect to a given alphabet size s, if there is no minimal nondeterministic finite automaton of n states and s input symbols whose equivalent minimal deterministic finite automaton has α states. We show that in the case of a ternary alphabet, there are no magic numbers. For all n and α satisfying n ⩽ α ⩽ 2n, we define an n-state nondeterministic finite automaton with a three-letter input alphabet that requires exactly α deterministic states.

This paper introduces a compiler technology based approach to model and simulate finite automata for pedagogical purposes. The compiler technology helps to define a language to formally model finite automata and to develop a toolkit to simulate them efficiently. The language is called Finite Automaton Description Language (FADL) and the toolkit is based on it. A fast single-pass compiler is used to compile a finite automaton defined in FADL. Then an interpreter is used to simulate the working of the compiled finite automaton for any input string. The nondeterminism of a Nondeterministic Finite Automaton (NFA) is simulated using backtracking. A tool to view the transition diagram of the finite automaton is provided. A Deterministic Finite Automaton (DFA) can be additionally compiled using an optimizing compiler that also minimizes the number of states. Tools for converting an NFA to a DFA and for converting a DFA to a Turing machine are also provided. A preliminary testing of the toolkit has been performed in which the participating students observed that the toolkit is an interesting teaching tool and it helped them to acquire a better perception about finite automata. © 2010 Wiley Periodicals, Inc. Comput Appl Eng Educ 21: 467–474, 2013

In this paper we consider algorithms which allow one to combine several states of a nondeterministic finite automaton into one state. Along with the algorithms for combining states, we adduce one more algorithm for the equivalent transformation of a non-deterministic finite automaton, namely, an algorithm for adding cycles. Problems under consideration imply the development of robust computer programs.

We present a tight time-hierarchy theorem for nondeterministic cellular automata by using a recursive padding argument. It is shown that, if t2(n) is a time-constructible function and t2(n) grows faster than t1(n + 1), then there exists a language which can be accepted by a t2(n)-time nondeterministic cellular automaton but not by any t1(n)-time nondeterministic cellular automaton.

We show that for all integers n and α such that n ⩽ α ⩽ 2n, there exists a minimal nondeterministic finite automaton of n states with a four-letter input alphabet whose equivalent minimal deterministic finite automaton has exactly α states. It follows that in the case of a four-letter alphabet, there are no "magic numbers", i.e., the holes in the hierarchy. This improves a similar result obtained by Geffert for a growing alphabet of size n + 2.

The automaton programming technology is a modern Russian development, which is actively studied and supported by a number of Russian research groups. In the automaton approach to the program design and construction, the program is divided into two—systemindependent and system-dependent—parts. The former part implements logic of the program and is given by a system of the interacting Moore‐Mealy automata. The design of each automaton consists in the creation of a link scheme describing its interface and a transition graph determining its behavior by a verbal description of the desired automaton (declaration of purposes). Given these two documents, a program module corresponding to the automaton can formally and isomorphically be constructed (after which its system-dependent part can be implemented). The automaton programming does not depend on

We present the first (polynomial-time) algorithm for reducing a given deterministic finite state automaton (DFA) into a hyper-minimized DFA, which may have fewer states than the classically minimized DFA. The price we pay is that the language recognized by the new machine can differ from the original on a finite number of inputs. These hyper-minimized automata are optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs. With small modifications, the construction works also for finite state transducers producing outputs. Within a class of finitely differing languages, the hyper-minimized automaton is not necessarily unique. There may exist several non-isomorphic machines using the minimum number of states, each accepting a separate language finitely-different from the original one. We will show that there are large structural similarities among all these smallest automata.

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.

We introduce and study three notions of typeness for automata on infinite words. For an acceptance-condition class γ (that is, γ is weak, Büchi, co-Büchi, Rabin, or Streett), deterministic γ-typeness asks for the existence of an equivalent γ-automaton on the same deterministic structure, nondeterministic γ-typeness asks for the existence of an equivalent γ-automaton on the same structure, and γ-powerset-typeness asks for the existence of an equivalent γ-automaton on the (deterministic) powerset structure – one obtained by applying the subset construction. The notions are helpful in studying the complexity and complication of translations between the various classes of automata. For example, we prove that deterministic Büchi automata are co-Büchi type; it follows that a translation from deterministic Büchi to deterministic co-Büchi automata, when exists, involves no blow up. On the other hand, we prove that nondeterministic Büchi automata are not co-Büchi type; it follows that a translation from a nondeterministic Büchi to nondeterministic co-Büchi automata, when exists, should be more complicated than just redefining the acceptance condition. As a third example, by proving that nondeterministic co-Büchi automata are Büchi-powerset type, we show that a translation of nondeterministic co-Büchi to deterministic Büchi automata, when exists, can be done applying the subset construction. We give a complete picture of typeness for the weak, Büchi, co-Büchi, Rabin, and Streett acceptance conditions, and discuss its usefulness.

We consider control questions for finite automata viewed as input/output systems. In particular, we find estimates of the minimal number of states of an automaton able to control a given automaton. We prove that, on average, feedback closed-loop control automata do not have fewer states than open-loop control automata when the control objective is to steer the controlled automaton to a target state. We compare our approach to other ways of formalizing of formalizing analogous control objectives.

We present a tableau-based algorithm for obtaining a Buchi automaton from a formula in Dynamic Linear Time Temporal Logic (DLTL), a logic which extends LTL by indexing the until operator with regular programs. The construction of the states of the automaton is similar to the standard construction for LTL, but a different technique must be used to verify the fulfillment of until formulas. The resulting automaton is a Buchi automaton rather than a generalized one. The construction can be done on-the-fly, while checking for the emptiness of the automaton. We also extend the construction to the Product Version of DLTL.

Our aim is to enumerate all NFAs (nondeterministic finite automata) that recognize a given regular language [Formula: see text]. More precisely, we produce a set 𝔸 of automata such that each automaton A recognizing [Formula: see text] appears in 𝔸 up to the merging of some states and the addition of some transitions, that is, there is a surjective morphism that maps A onto an automaton of 𝔸. We provide a common theoretical framework, based on morphism properties, to previous works of Kameda and Weiner (1970), and of Sengoku (1992), whose issue is the minimization of NFAs. Our paper gives two incomparable enumeration techniques. Both proceed by enumerating a specific class of grid covers of the automaton map. The first one is related to the canonical automaton introduced by Carrez. The second one is based on new outcomes related to the relationship between grid covers and their projections.

New applications of finite automata, such as computational linguistics and asynchronous circuit simulation, can require automata of millions or even billions of states. All known construction methods (in particular, the most effective reachability-based ones that save memory, such as the subset construction, and simultaneously minimizing constructions, such as Brzozowski's) have intermediate memory usage much larger than the final automaton, thereby restricting the maximum size of the automata which can be built. In this paper, I present a reachability-based optimization which can be used in most of these construction algorithms to reduce the intermediate memory requirements. The optimization is presented in conjunction with an easily understood (and implemented) canonical automaton construction algorithm.

We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language L is accepted by a Las Vegas automaton having r states such that the probability for a definite answer to occur is at least p , then r ≥ np , where n is the number of the states of the minimal deterministic automaton accepting L . Earlier this result has been obtained in [2] by using a reduction to one-way Las Vegas communication protocols , but here we give a direct proof based on information theory.

The aim of this paper is to compare three efficient representations of the position automaton of a regular expression: the Thompson ∊-automaton, the [Formula: see text]-structure and the ℱ-structure, an optimization of the [Formula: see text]-structure. These representations are linear w.r.t. the size s of the expression, since their construction is in O(s) space and time, as well as the computation of the set δ(X,a) of the targets of the transitions by a of any subset X of states. The comparison is based on the evaluation of the number of edges of the underlying graphs respectively created by the construction step or visited by the computation of a set δ(X,a).

Pattern-matching is a fundamental feature in many applications such as functional programming, logic programming, theorem proving, term rewriting and rule-based expert systems. Usually, patterns are pre-processed into a deterministic finite automaton. Using such an automaton allows one to determine the matched pattern(s) by a single scan of the input term. The matching automaton is typically based on left-to-right traversal of patterns. With ambiguous patterns a subject term may be an instance of more than one pattern. To select the pattern to use, a priority rule is usually engaged. The pre-processing of the patterns adds new patterns which are instances of the original ones. When the original patterns are ambiguous, some of the instances supplied may be irrelevant for the matching process. They may cause an unnecessary increase in the space requirements of the automaton and may also reduce the time efficiency of the matching process. Here, we devise a new pre-processing operation that recognises and avoids such irrelevant instances and hence improves space and time requirements for the matching automaton.

In this paper the concept of substitution property (SP) partition for a finite fuzzy automaton is formulated, and the quotient automaton with respect to an SP partition is defined. The state minimization problem for such automata by using the method of quotient machines is solved.

A cover-automaton A of a finite language L⊆Σ ∗ is a finite deterministic automaton (DFA) that accepts all words in L and possibly other words that are longer than any word in L . A minimal deterministic finite cover automaton (DFCA) of a finite language L usually has a smaller size than a minimal DFA that accept L . Thus, cover automata can be used to reduce the size of the representations of finite languages in practice. In this paper, we describe an efficient algorithm that, for a given DFA accepting a finite language, constructs a minimal deterministic finite cover-automaton of the language. We also give algorithms for the boolean operations on deterministic cover automata, i.e., on the finite languages they represent.

The aim of this paper is to investigate how subset construction performs on specific families of automata. A new upper bound on the number of states of the subset-automaton is established in the case of homogeneous automata. The complexity of the two basic steps of subset construction, i.e. the computation of deterministic transitions and the set equality tests, is examined depending on whether the nondeterministic automaton is an unrestricted one, an homogeneous one, a position one or a ZPC-structure, which is an implicit construction for a position automaton. Copyright 2001 Elsevier Science B.V.

We prove that every regular expression of size n can be converted into an equivalent nondeterministic ε-free finite automaton (NFA) with O(n(logn)2) transitions in time O(n2logn). The best previously known conversions result in NFAs of worst-case size Θ(n2). We complement our result by proving an almost matching lower bound. We exhibit a sequence of regular expressions of size O(n) and show the number of transitions required in equivalent NFAs is Ω(nlogn). This also proves there does not exist a linear-size conversion from regular expressions to NFAs.

A method for construction of an automaton (an acceptor) from a first-order logical formula is proposed. The method is similar to the tableau method and can be considered as modification and improvement of it.

It is shown that if α is an integer which can be expressed as 2k or 2k+1 for some integer 0⩽k⩽n/2−2, then there exist nondeterministic finite automata with n states whose equivalent deterministic finite automata need exactly 2n−α states.

The paper discusses the problem of determinizing finite-state automata containing large numbers of ε-moves. Experiments with finite-state approximations of natural language grammars often give rise to very large automata with a very large number of ε-moves. The paper identifies and compares a number of subset construction algorithms that treat ε-moves. Experiments have been performed which indicate that the algorithms differ considerably in practice, both with respect to the size of the resulting deterministic automaton, and with respect to practical efficiency. Furthermore, the experiments suggest that the average number of ε-moves per state can be used to predict which algorithm is likely to be the fastest for a given input automaton.

We survey three applications that use finite automata to specify behaviors of concurrent processes in general, and asynchronous circuits in particular. The applications are: verification of concurrent processes, liveness properties, and delay insensitivity of asynchronous networks. In all three cases, we start with a common model of a nondeterministic finite automaton, and then add certain application-specific features. Typically, the added features involve separating the alphabet or the state set of the automaton into several disjoint subsets. For each application we provide the motivation, describe the type of automaton used, define the most important operations, and state some of the key results. For process verification, we describe a BDD-based tool that implements the respective automata and operations.

We consider the problem of storing a set S⊂Σkas a deterministic finite automaton (DFA). We show that inserting a new string σ∈Σk or deleting a string from the set S represented as a minimized DFA can be done in expected time O(k|Σ|), while preserving the minimality of the DFA. The method can be applied to reduce the memory requirements of model checkers that are based on explicit state enumeration. As an example, we discuss an implementation of the method for the model checker Spin.

A deterministic automaton recognizing a given ω -regular language is constructed from an ω -regular expression with the help of derivatives. The construction is related to Safra's algorithm, in about the same way as the classical derivative method is related to the subset construction.

There are three classical algorithms to compute a finite automaton from a regular expression. The Brzozowski algorithm yields a deterministic automaton, the Glushkov algorithm a nondeterministic one, and the general step by step method generally yields a NFA with e-transitions. Berry and Sethi have adapted Brzozowski's algorithm to compute the Glushkov automaton of an expression. We describe a variant of the step by step construction which associates standard and trim automata to regular languages. We show that the automaton constructed by the variant and the Glushkov automaton (computed by Berry-Sethi algorithm) are isomorphic.

Given a timed Buechi automaton G, we present a simplified procedure for computing the untimed language accepted by G, provided certain restrictions are made on the queries along the edges of G. The untimed language accepted by G is given as the language accepted by a Muller automaton. This finite automaton has fewer states than the Buechi automaton Untime(G) defined by Alur and Dill. Essentially in order to test acceptance of a word by G is only necessary to consider clock valuations that map all clocks to integers. Associated properties of the defined good sets of clock valuations are given.

The algorithmic approach to the design of fault-detection experiments for testing of control devices requires a mathematical model that describes the behavior of the tested device and its reference model. A finite automaton usually provides a suitable mathematical model. The classical problem assumes that the reference model and the tested device behave as a deterministic f'mite automaton (in what follows, we use the term "automaton" for a deterministic f'mite automaton). The class of faults is limited to faults that do not increase the number of automaton states. It is also assumed that the experimenter has direct access to the inputs and outputs of the device being tested. The construction of multiple fault-detection experiments assumes the existence of an input symbol that allows the model automaton to return from any state to some fixed (initial) state. This special symbol remains a reset symbol under all faults [1]. Recent studies use a nondeterministic automaton (nd-automaton) as a reference model for testing. In particular, an ndautomaton is used to construct test cases that check computer network protocols for conformity [2-4]. It has been shown [5] that if the output of the device being tested is observable only on the output of another device, then a fault,detection experiment also can be constructed using a nondeterministic model. The construction of a fault-detection experiment usually focuses mainly on the design of input sequences. The set of admissible output responses is identified with the entire set of model output sequences. In this article we analyze the possibility of reducing the length of the fault-detection experiment by reducing the set of admissible output responses. The article is organized as follows. Section 1 introduces the main def'mitions and notation. Section 2 describes the possibility of reducing the admissible set of output sequences in a fault-detection experiment. Section 3 provides necessary and sufficient conditions for the realization of a nondeterministic automaton by a deterministic automaton. We examine the conditions that permit passing from the nd-automaton P to an nd-automaton P,~ with fewer states and fewer output responses. The set of automata realizing P is identical with the set of automata realizing P~.. We can thus construct a fault~etection experiment for the nd-automaton P based on the nd-automaton P~.. This possibility is illustrated in Section 4.