Search

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.

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.

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.

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.

This article describes an improvement of the brute force determinization algorithm in the case of homogeneous nondeterministic finite automata (NFAs), as well as its application to pattern matching. Brute force determinization with limited memory may provide a partially determinized automaton, but its bounded complexity makes it a safe procedure contrary to the classical subset construction. Actually, our algorithm is inspired by both recent results of Champarnaud concerning the subset automaton of a homogeneous NFA and the algorithm recently designed by Navarro and Raffinot to implement the brute force determinization of the Glushkov NFA of a regular pattern. Our algorithm significantly improves Navarro–Raffinot's one since it has an average exponentially smaller memory requirement for a given level of determinization, which, considering a bounded memory, implies a quadratically smaller parsing time. This algorithm has been implemented in CCP software (http://www.univ-rouen.fr/LIFAR/aia/ccp.html). Tests ...

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.

This paper continues the discussion of teaching nondeterminism (see [6]) where we presented a didactic approach introducing the notion of nondeterministic automata. Although in this paper we use the same methodology we have to face up to new didactic challenges. Namely, teaching the subset construction requires answers to the question how can CAS be used in teaching the different phases of mathematical problem solving so that we can reach higher cognitive efficiency.

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.

The functional behaviour of a reactive system can be modelled by an IOLTS (input output labelled transition system). However when the system is observed asynchronously (i.e., remotely through some medium), the apparent (or asynchronous) behaviour is different from its actual functional behaviour. Specifically, each trace of input output events executed by a system can appear distorted in infinite number of ways. Given a finite state IOLTS M describing the actual behaviour of a system, [7] shows how to define a corresponding infinite state IOLTS [M] describing the asynchronous behaviour of the same system. So defined, the resulting [M] is non-deterministic. Since [M] is also infinite state, it is not possible to convert it into its deterministic equivalent [M]D by the standard subset construction method. To this end, our first contribution in this paper is to show how to define an infinite state deterministic IOLTS [M]D from the given M. The states of M and [M]D bear correspondence such that if we distinguish some states of M as accept states, then we can have corresponding accept states in [M]D. Our second contribution is about reachability analysis. In particular, we prove how to determine whether a given state of [M]D leads to some accept state. This result assumes importance because of the infinite size of [M]D. After proving these fundamental results, we shift the discussion to the theory underlying conformance testing. The center of discussion is a test generation tool called TGV. We finally show how these results can be used to build a TGV-like approach for generating test cases for an asynchronously communicating system.

Part 2: Regular Contributions; International audience; 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 finite V -algebras and a category of finite structured sets and relations. By instantiating this to different varieties we recover three well-studied canonical nfas (the átomaton, the jiromaton and the minimal xor automaton) and obtain a new canonical nfa called the distromaton. We prove that each of these nfas is minimal relative to a suitable measure, and give conditions for state-minimality. Our approach is coalgebraic, exhibiting additional structure and universal properties.

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.

We introduce a new class of groups with solvable word problem, namely groups specified by a confluent set of short-lex-reducing Knuth–Bendix rules which form a regular language. This simultaneously generalizes short-lex-automatic groups and groups with a finite confluent set of short-lex-reducing rules. We describe a computer program which looks for such a set of rules in an arbitrary finitely presented group. Our main theorem is that our computer program finds the set of rules, if it exists, given enough time and space. (This is an optimistic description of our result — for the more pessimistic details, see the body of the paper.) The set of rules is embodied in a finite state automaton in two variables. A central feature of our program is an operation, which we call welding, used to combine existing rules with new rules as they are found. Welding can be defined on arbitrary finite state automata, and we investigate this operation in abstract, proving that it can be considered as a process which takes as input one regular language and outputs another regular language. In our programs we need to convert several nondeterministic finite state automata to deterministic versions accepting the same language. We show how to improve somewhat on the standard subset construction, due to special features in our case. We axiomatize these special features, in the hope that these improvements can be used in other applications. The Knuth–Bendix process normally spends most of its time in reduction, so its efficiency depends on doing reduction quickly. Standard data structures for doing this can become very large, ultimately limiting the set of presentations of groups which can be so analyzed. We are able to give a method for rapid reduction using our much smaller two variable automaton, encoding the (usually infinite) regular language of rules found so far. Time taken for reduction in a given group is a small constant times the time taken for reduction in the best schemes known (see [5]), which is not too bad since we are reducing with respect to an infinite set of rules, whereas known schemes use a finite set of rules. We hope that the method described here might lead to the computation of automatic structures in groups for which this is currently infeasible. Some proofs have been omitted from this paper in the interests of brevity. Full details are provided in [4].

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.

International audience; The main result is a finite-state version of the Kraft-McMillan theorem characterizing the generating sequence of a k-ary regular tree. The proof uses a new contruction called the multiset construction which is a version with multiplicities of the well-known subset construction of automata theory

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.

We propose a practical technique to compile pattern-matching of prioritised overlapping patterns in equational languages to an minimal deterministic left-to-right matching automaton. First, we present a method to construct a tree matching automaton for such patterns. The automaton obtained allows pattern-matching to be performed without any backtracking. Although this automaton is efficient since it avoids symbol re-examination, it can only achieve this at the cost of increased space requirements. Such space requirements could be minimised by using a dag automaton that shares all the isomorphic subautomata which are duplicated in a tree automaton. We design an efficient method to identify such subautomata and avoid their construction while generating the dag automaton. This is achieved without constructing the tree automaton first.

Infinite behavior of nondeterministic finite-state automata running over infinite trees or more generally over elements of an arbitrary algebraic structure is characterized by a calculus of fixed point terms interpreted in powerset algebras. These terms involve the least and greatest fixed point operators and disjunction as the only logical operation. A tight correspondence is established between a hierarchy of Rabin indices of automata and a hierarchy induced by alternation of the least and greatest fixed point operators. It is shown that, in the powerset algebra of trees constructed from a set of functional symbols, the fixed point hierarchy is infinite unless all the symbols are unary (i.e. trees are words). It is also shown that an interpretation of a closed fixed point term in any powerset algebra can be factorized through the interpretation of this term in the powerset algebra of trees, from which it is deduced that the question whether a term denotes always ∅ can be answered in polynomial time.

We show how to turn a regular expression R of length r into an O(s) space representation of McNaughton and Yamada's NFA, where s is the number of occurrences of alphabet symbols in R, and s + 1 is the number of NFA states. The standard adjacency list representation of McNaughton and Yamada's NFA takes up 1 + 2s + $s\sp2$ space in the worst case. The adjacency list representation of the NFA produced by Thompson takes up between 2r and 6r space, where r can be arbitrarily larger than s. Given any subset V of states in McNaughton and Yamada's NFA, our representation can be used to compute the set U of states one transition away from the states in V in optimal time O($\vert V\vert + \vert U\vert$). McNaughton and Yamada's NFA requires $\Theta$($\vert V\vert \times \vert U\vert$) time in the worst case. Using Thompson's NFA, the equivalent calculation requires $\Theta$(r) time in the worst case. An implementation of our NFA representation confirms that it takes up an order of magnitude less space than McNaughton and Yamada's machine. An implementation to produce a DFA from our NFA representation by subset construction shows linear and quadratic speedups over subset construction starting from both Thompson's and McNaughton and Yamada's NFA's. It also shows that the DFA produced from our NFA is as much as one order of magnitude smaller than DFA's constructed from the two other NFA's. An UNIX egrep compatible software called cgrep based on our NFA representation is implemented. A benchmark shows that cgrep is dramatically faster than both UNIX egrep and GNU e?grep. Throughout this thesis the importance of syntax is stressed in the design of our algorithms. In particular, we exploit a method of program improvement in which costly repeated calculations can be avoided by establishing and maintaining program invariants. This method of symbolic finite differencing has been used previously by Douglas Smith to derive efficient functional programs.

We show that Safra's determinization ofω-automata with Streett (strong fairness) acceptance condition also gives memoryless winning strategies in infinite games, for the player whose acceptance condition is the complement of the Streett condition. Both determinization and memorylessness are essential parts of known proofs of Rabin's tree automata complementation lemma. Also, from Safra's determinization construction, along with its memoryless winning strategy extension, a single exponential complementation of Streett tree automata follows. A different single exponential construction and proof first appeared in [N. Klarlund (1992), Progress measures, immediate determinacy, and a subset construction for tree automata,in“Proceedings, 7th IEEE Symposium on Logics in Computer Science”].

Austinat, Diekert, Hertrampf, and Petersen [2] proved that every language L that is (m,n)-recognizable by a deterministic frequency automaton such that m > n/2 can be recognized by a deterministic finite automaton as well. First, the size of deterministic frequency automata and of deterministic finite automata recognizing the same language is compared. Then approximations of a language are considered, where a language L′ is called an approximation of a language L if L′ differs from L in only a finite number of strings. We prove that if a deterministic frequency automaton has k states and (m,n)-recognizes a language L, where m > n/2, then there is a language L′ approximating L such that L′ can be recognized by a deterministic finite automaton with no more than k states.

In this paper, Nondeterministic Buchi Automata (NBA) are equivalently transformed as a new kind of deterministic omega automata, Deterministic Partitioned Automata (DPA). Different from the existing automata, at most three different transitions may occur between two states of a DPA. This leads to a determinization construction of NBA with smaller state complexity but larger transition complexity. Compared with the existing determinization constructions of NBA, the new one is intuitive and easily implementable since it is completely based on subset construction. In addition, we have proved that both nondeterministic and deterministic partitioned automata share the same expressive power with NBA.

International audience; We study the number of states of the minimal automaton of the mirror of a rational language recognized by a random deterministic automaton with n states. We prove that, for any d > 0, the probability that this number of states is greater than nd tends to 1 as n tends to infinity. As a consequence, the generic and average complexities of Brzozowski minimization algorithm are super-polynomial for the uniform distribution on deterministic automata.

A non-functional requirement for model-based diagnosis of active systems is efficient determinization of acyclic automata. In literature, determinization of finite automata is performed by the Subset Construction algorithm SC: given a nondeterministic automaton N, an equivalent deterministic automaton D is generated, with each state in D being a subset of states in N. However, SC is conceived for monolithic determinization, when N is completely specified. By contrast, monitoring-based diagnosis of active systems requires incremental determinization. We consider the Incremental Determinization Problem for finite acyclic automata: after extending the acyclic automaton N to N' by ΔN by new transitions and, possibly, new states, we require N' to be determinized into D' based on D and ΔN. Although this problem can be naively solved by applying SC to N' thereby disregarding both D and ΔN, this solution is bound to lead to poor performances, as it does not exploit the incremental nature of N'. Therefore, an incremental algorithm is proposed, called ISCA, which extends D into D' based on ΔN, rather than starting from scratch the determinization of N'. ISCA is a general-purpose algorithm. Evidence from experiments indicates that, in time, ISCA is significantly more efficient than SC in solving incremental determinization problems.

For a finite automaton, regardless whether it is deterministic or nondeterministic, Brzozowski's minimization algorithm computes the equivalent minimal deterministic finite automaton by applying reversal and power-set construction twice. Although this is an exponential algorithm because of the power-set construction, it performs well in experimental studies compared to efficient O(nlogn) minimization algorithms. Here we show how to slightly enhance Brzozowski's minimization algorithm by some sort of reachability information so that it can be applied to the following automata models: deterministic cover automata, almost equivalent deterministic finite state machines, and k-similar automata.

International audience; A lot of computing tools are often used for analyzing DNA se- quences like trees, automata, dictionaries, every one being re- served for a particular problem. A. Blumer and al. have proposed a more general computing tool : the smaller automaton recogniz- ing the subwords of a text (DAWG). In this paper we propose the concept of "weighted factors au- tomaton" producing every occurrence of any factor. Its transi- tions are labeled by the read letter and weighted by the set of the indices of the factors beginnings. The factors are obtained by concatenating the read letters and the indices of the factors begin- nings are obtained by computing the intersection of the weight- ing sets, when advancing from the initial state to a final state. We think that this automaton can be more easily processed than DAWG and we present a comparison between DAWG and our automaton: the set of the factors beginnings indices and the fac- tors frequency are more easily obtained by our automaton and the restriction of our automaton to the factors of length k maintains the automaton structure, when DAWG cannot be eas- ily restricted. The applications are numerous: By selecting factors of length 1 , we obtain the coding regions, factors of length 3 , we obtain the expression level of some gene. The "weighted factors au- tomaton" allows us to find matches of pattern, to study homol- ogy, FASTA and BLAST algorithms being significantly simplified.

The Rabin index of a regular language of infinite words is the minimum number of accepting pairs used in any deterministic Rabin automaton recognizing this language. We show that the Rabin index of a language given by a Muller automaton withnstates andmaccepting sets is computable in timeO(m2nc) wherecis the cardinality of the alphabet.

Two nondeterministic finite automata (NFAs) are said to be path equivalent if each string is accepted by the two automata via the same number of computation paths. In this paper we show the following. 1. (1) The path equivalence problem for NFAs without λ-cycles is solvable not only in polynomial sequential time but also in O(log2(n)) parallel time using a polynomial number of processors, where n is the total number of states in two NFAs. 2. (2) The path equivalence problem for NFAs with λ-cycles is PSPACE-complete, hence decidable.

We first give a method for simulating, in the case of Buchi, an alternating automaton by a usual nondeterministic one. Then, to make the satisfiability problem of Linear Propositional Temporal Logic (LPTL) use this result, we give a method for translating any formula of this logic into an equivalent Buchi alternating automaton.

We introduce a notion of partial derivative of a regular expression and apply it to finite automaton constructions. The notion is a generalization of the known notion of word derivative due to Brzozowski: partial derivatives are related to non-deterministic finite automata (NFA's) in the same natural way as derivatives are related to deterministic ones (DFA's). We give a constructive definition of partial derivatives and prove several facts, in particular: 1.(1) any derivative of a regular expression r can be represented by a finite set of partial derivatives of r;2.(2) the set of all partial derivatives of r is finite and its cardinality is less than or equal to one plus the number of occurrences of letters from A appearing in r;3.(3) any partial derivative of r is either a regular unit, or a subterm of r, or a concatenation of several such subterms. These theoretical results lead us to a new algorithm for turning regular expressions into relatively small NFA's and allow us to provide certain improvements to Brzozowski's algorithm for constructing DFA's. We also report on a prototype implementation of our NFA construction and present several examples.

In this paper we present two algorithms for building lexicons in Directed Acyclic Word-Graphs (DAWGs). The two algorithms, one for deterministic and the other for non-deterministic DAWGs, can be used instead of the traditional subset construction method. Although the proposed algorithms do not produce the optimal DAWG (i.e., the one with the minimum number of states), they are simple, fast and able to build the DAWG incrementally, as new words are added to the lexicon. Thus, building large lexicons in a DAWG structure becomes an easy task, even for a modest computer.

Modeling the morphological structure of natural languages in terms of a nondeterministic finite-state automaton is shown to be inadequate in its handling of some common natural language phenomena. We show that a two-tape nondeterministic automaton is capable of handling these phenomena. The modeling is improved by the specification of a new type of automaton, the preset two-head automaton, which we argue is equivalent in expressive power to a linear context-free grammar. We discuss the operation of a parser which implements the improved model.

The present article is a continuation of a series of studies on functional synthesis of automata from their logical specifications. A specification language L based on the logic of one-place predicates interpreted on the set of integers has been described. A specification S in this language defines the class K(S) of equivalent nondeterministic automata. If S is treated as a specification of deterministic automata, then the class of all automata satisfying the specification S is identical with the class of all determinizations of any automaton from K(S). The problem of functional synthesis of a deterministic automaton specified in the language L involves constructing a procedural representation of the automaton (i.e., a representation in terms of states and transition and output functions) that satisfies the original specification. It thus includes the construction of one or several determinizations of an automaton from the class K(S). The last problem can be solved either on the procedural level (i.e., the level of the automaton graph) by constructing a procedural representation of an automation from K(S) or on the logical level (i.e., the level of formulas in the language L). In this article, we propose a solution of the problem based on the methodology ofmore » verification design of automaton. An essential feature of this methodology is that all transformations of the automaton being designed (except the construction of a procedural representation of the automaton) are carried out on the level of specification language formulas. This permits using logic methods to verify the correctness of the applied by the designer in the process of design. The problem is accordingly formulated as follows: given the specification S, constructed a specification S such that K(S{sup *}) is a class of equivalent deterministic automata that are determinizations of automata from K(S).« less

In order to keep up with the demand for solutions to problems with ever-increasing data sets, both academia and industry have embraced commodity computer clusters with locally attached disks or SANs as an inexpensive alternative to supercomputers. With the advent of tools for parallel disks programming, such as MapReduce, STXXL and Roomy --- that allow the developer to focus on higher-level algorithms --- the programmer productivity for memory-intensive programs has increased many-fold. However, such parallel tools were primarily targeted at iterative programs.We propose a programming model for migrating recursive RAM-based legacy algorithms to parallel disks. Many memory-intensive symbolic algebra algorithms are most easily expressed as recursive algorithms. In this case, the programming challenge is multiplied, since the developer must re-structure such an algorithm with two criteria in mind: converting a naturally recursive algorithm into an iterative algorithm, while simultaneously exposing any potential data parallelism (as needed for parallel disks).This model alleviates the large effort going into the design phase of an external memory algorithm. Research in this area over the past 10 years has focused on per-problem solutions, without providing much insight into the connection between legacy algorithms and out-of-core algorithms. Our method shows how legacy algorithms employing recursion and non-streaming memory access can be more easily translated into efficient parallel disk-based algorithms.We demonstrate the ideas on a largest computation of its kind: the determinization via subset construction and minimization of very large nondeterministic finite set automata (NFA). To our knowledge, this is the largest subset construction reported in the literature. Determinization for large NFA has long been a large computational hurdle in the study of permutation classes defined by token passing networks. The programming model was used to design and implement an efficient NFA determinization algorithm that solves the next stage in analyzing token passing networks representing two stacks in series.