Search

A counting finite-state automaton is a nondeterministic finite-state automaton which, on an input over its input alphabet, (magically) writes in binary the number of accepting computations on the input. We examine the complexity of computing the counting function of an NFA, and the complexity of recognizing its range as a set of binary strings. We also consider the pumping behavior of counting finite-state automata. The class of functions computed by counting NFA's (1) includes a class of functions computed by deterministic finite-state transducers; (2) is contained in the class of functions computed by polynomially time- and linearly space-bounded Turing transducers; (3) includes a function whose range is the composite numbers.

We will continue here the study of finite automata behavior, or periodic events, with a presentation of Kleene’s (1956) characterization of these events. In chapter 3 we have already seen a proof of one half of this result, namely, the class P k of periodic events contains all finite subsets of N k , is closed under the Boolean operators, and is closed under the “regular” operators dot and star. Transition systems, also called nondeterministic automata, were introduced by Myhill (1957) to give another, and very elegant, proof of this fact. He noticed that the closure under ∪, · , * is quite obvious for behaviors of finite transition systems, and he used the subset construction to show that these behaviors are no more general than those of finite automata. This matter is contained in sections 4.1, 4.2, and 4.3.

Let a partial deterministic finite automaton be a DFA in which each state need not have a transition edge for each letter of the alphabet. We demonstrate that the minimal partial DFA for the set of all subwords of a given word w, |w| > 2, has at most 2|w| − 2 states and 3|w| − 4 transition edges, independently of the alphabet size. We give an algorithm to build this minimal partial DFA from the input w on-line in linear time.

Publisher Summary This chapter focuses on the recognizers (Rabin-Scott automata). A deterministic automaton is a special case of a nondeterministic one; hence, a set of tapes recognized by a deterministic automaton is recognized by a nondeterministic one. The chapter also shows that the opposite is also true. Various theorems are proved in the chapter. Various examples of regular and non-regular sets are presented. A reduced automaton is one which has no proper homomorphic images, provided that its input set is held constant. Every semiautomaton with more than one state has a proper homomorphic image: the one-state semi-automaton. The regular sets corresponding to an automaton and to its homomorphic image are equal.

This publication is the author's master's thesis. It treats the following problem: If one takes a ''Chomsky-automaton'' (i. e. a finite state automaton, a push-down automaton, a linear bounded automaton or a Turing Machine) and equips it with output one obtains the corresponding translator. Define the graph of a translator as the set of pairs (x, y) where input x belongs to the language accepted by the automaton and y is the ouput produced while processing x . How can such graphs be characterized ?A characterization is given for all Chomsky types in terms of pair grammars generating the graphs as well as in terms of homomorphic images of a language of corresponding type. The publication was intended to be used as material in connection with a course on automata theory and hence it contains proofs of theorems appearing elsewhere in the literature.

Any finite tree automaton (or regular type) can be used to construct an abstract interpretation of a logic program, by first determinising and completing the automaton to get a pre-interpretation of the language of the program. This has been shown to be a flexible and practical approach to building a variety of analyses, both generic (such as mode analysis) and program-specific (with respect to a type describing some particular property of interest). Previous work demonstrated the approach using pre-interpretations over small domains. In this paper we present techniques that allow the method to be applied to more complex pre-interpretations and larger programs. There are two main techniques presented: the first is a novel algorithm for determinising finite tree automata, yielding a compact “product” form of the transitions of the result automaton, that is often orders of magnitude smaller than an explicit representation of the automaton. Secondly, it is shown how this form (which is a representation of a pre-interpretation) can then be input directly to a BDD-based analyser of Datalog programs. We demonstrate through experiments that much more complex analyses become feasible.

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 investigate a model of self-assembling finite automata. An automaton is assembled on demand during its computation from copies out of a finite set of items. These items are pieces of a finite automaton which are connected to the already assembled automaton by identifying states. Depending on the allowed number of such interface states, the degree, infinite hierarchies of properly included language families are shown. The presented model is a natural and unified generalization of regular and context-free languages since degrees one and two are characterizing the finite and pushdown automata, respectively. Moreover, by means of different closure properties nondeterministic and deterministic language families are separated., Journal of Automata, Languages and Combinatorics, Volume 14, Number 1, 2009, 75-92

A classical construction of Aho and Corasick solves the pattern matching problem for a finite set of words X in linear time, where the size of the input X is the sum of the lengths of its elements. It produces an automaton that recognizes A*X, where A is a finite alphabet, but which is generally not minimal. As an alternative to classical minimization algorithms, which yields a ${\mathcal O}(n\log n)$ solution to the problem, we propose a linear pseudo-minimization algorithm specific to Aho-Corasick automata, which produces an automaton whose size is between the size of the input automaton and the one of its associated minimal automaton. Moreover this algorithm generically computes the minimal automaton: for a large variety of natural distributions the probability that the output is the minimal automaton of A*X tends to one as the size of X tends to infinity.

Part 1: Cross-Domain Conference and Workshop on Multidisciplinary Research and Practice for Information Systems (CD-ARES 2014): Knowledge Management; International audience; Some application domains, including monitoring of active systems in artificial intelligence and model-based mutation testing in software engineering, require determinization of finite automata to be performed incrementally. To this end, an algorithm called Incremental Subset Construction (ISC) was proposed a few years ago. However, this algorithm was recently discovered to be incorrect is some instance problems. The incorrect behavior of ISC originates when the redirection of a transition causes a portion of the automaton to be disconnected from the initial state. This misbehavior is disturbing in two ways: portions of the resulting automaton are disconnected and, as such, useless; moreover, a considerable amount of computation is possibly wasted for processing these disconnected parts. To make ISC sound, a metrics-based technique is proposed in this paper, where the distance between states is exploited in order to guarantee the connection of the automaton, thereby allowing ISC to achieve soundness. Experimental results show that, besides being effective, the proposed technique is efficient too.