Narrow Results

It is shown that a two-way deterministic finite automaton (2DFA) with $n$ states over an alphabet $\mathrm{\Sigma }$ can be transformed to an equivalent one-way automaton (1DFA) with $\left|\mathrm{\Sigma }\right|\cdot \phi (n)+1$ states, where $\phi (n)={max}_{k=1}^{n-1}{k}^{n-k+1}=n^{n-\frac{nlnlnn}{lnn}+O(\frac{n}{lnn})}$. This reflects the fact that, by keeping the last processed symbol $a$ in memory, the simulating 1DFA can remember one of $k$ states in which the automaton moves by $a$ to the right, and a function that maps $n-k$ states moving to the left to $k$ states moving to the right; cf. ca. $n^n$ functions in the classical construction. A close lower bound of $\phi (n)$ states is established using a 2-symbol alphabet, with witness languages defined by direction-determinate 2DFA. The same lower bound is also achieved with witness languages defined by sweeping 2DFA, at the expense of using a 5-symbol alphabet. In addition, the complexity of transforming a sweeping or a direction-determinate 2DFA to a 1DFA is shown to be exactly $\phi (n)$.

We introduce a certain restriction of weighted automata over the rationals, called image-binary automata. We show that such automata accept the regular languages, can be exponentially more succinct than corresponding NFAs, and allow for polynomial complementation, union, and intersection. This compares favourably with unambiguous automata whose complementation requires a superpolynomial state blowup. We also study an infinite-word version, image-binary Büchi automata. We show that such automata are amenable to probabilistic model checking, similarly to unambiguous Büchi automata. We provide algorithms to translate $k$-ambiguous Büchi automata to image-binary Büchi automata, leading to model-checking algorithms with optimal computational complexity.

The partial derivative automaton (${{𝒜}}_{\mathrm{\text{PD}}}$) is an elegant simulation of a regular expression. Although it is, in general, smaller than the position automaton (${{𝒜}}_{\mathrm{\text{POS}}}$), the algorithms that build ${{𝒜}}_{\mathrm{\text{PD}}}$ in quadratic worst-case time first compute ${{𝒜}}_{\mathrm{\text{POS}}}$. Asymptotically, and on average for the uniform distribution, the size of ${{𝒜}}_{\mathrm{\text{PD}}}$ is half the size of ${{𝒜}}_{\mathrm{\text{POS}}}$, being both linear on the size of the expression. We address the construction of ${{𝒜}}_{\mathrm{\text{PD}}}$ efficiently, on average, avoiding the computation of ${{𝒜}}_{\mathrm{\text{POS}}}$. The expression and the set of its partial derivatives are represented by a directed acyclic graph with shared common subexpressions. We develop an algorithm for building ${{𝒜}}_{\mathrm{\text{PD}}}$s from expressions in strong star normal form of size $n$ that runs, on average, in time that asymptotically behaves as $n^{3/2}\sqrt[4]{\mathrm{\text{log}}(n)}$, and space as $n^{3/2}/{(\mathrm{\text{log}}n)}^{3/4}$. Empirical results corroborate its good practical performance.

We consider general computational models: one-way and two-way finite automata, and logarithmic space Turing machines, all equipped with an auxiliary data structure (ADS). The definition of an ADS is based on the language of protocols of work with the ADS. We describe the connection of automata-based models with “Balloon automata” that are another general formalization of automata equipped with an ADS presented by Hopcroft and Ullman in 1967. This definition establishes the connection between the non-emptiness problem for one-way automata with ADS, languages recognizable by nondeterministic log-space Turing machines equipped with the same ADS, and a regular realizability problem (NRR) for the language of ADS’ protocols. The NRR problem is to verify whether the regular language on the input has a non-empty intersection with the language of protocols. The computational complexity of these problems (and languages) is the same up to log-space reductions.

${ℒ}\subseteq {\{0,1\}}^{\ast }$ is a binary coded unary regular language, if there exists a unary regular language ${{ℒ}}^{\prime }\subseteq {\{a\}}^{\ast }$ such that $a^x$ is in ${{ℒ}}^{\prime }$ if and only if the binary representation of $x$ is in ${ℒ}$. If a unary language ${{ℒ}}^{\prime }$ is accepted by a minimal deterministic finite automaton (DFA) ${{𝒜}}^{\prime }$ with $n$ states, then its binary coded version ${ℒ}$ is regular and can be accepted by a DFA ${𝒜}$ using at most $n$ states, but at least $1+\lceil logn\rceil$ states. There are witness languages matching these upper and lower bounds exactly, for each $n$.

More precisely, if ${{𝒜}}^{\prime }$ uses $\sigma \ge 0$ states in the initial segment and $\mu \cdot 2^{\ell }$ states in the loop, where $\mu$ is odd and $\ell \ge 0$, then the minimal ${𝒜}$ for ${ℒ}$ consists of a preamble with at most $\sigma$ but at least $max\{1,1+\lceil log\sigma \rceil -\ell \}$ states, except for $\sigma =0$ with no preamble, and a kernel with at most $\mu \cdot 2^{\ell }$ but at least $\mu +\ell$ states. Also these lower bounds are matched exactly by witness languages, for each $\sigma ,\mu ,\ell$. If the length of the loop is fixed, the size of the preamble is bounded by $O(\sigma /log\sigma )$.

The conversion in the opposite way is not always granted: there are binary regular languages the unary versions of which are not even context free.

The conversion of a unary nondeterministic finite automaton (NFA) to a binary NFA uses $O(n^2)$ states and introduces a binary version of Chrobak normal form.

We investigate the complexity of basic regular operations on languages represented by Boolean and alternating finite automata. We get tight upper bounds $m+n$ and $m+n+1$ for union, intersection, and difference, $2^m+n$ and $2^m+n+1$ for concatenation, $2^n+n$ and $2^n+n+1$ for square, $m$ and $m+1$ for left quotient, $2^m$ and $2^m+1$ for right quotient. We also show that in both models, the complexity of complementation and symmetric difference is $n$ and $m+n$, respectively, while the complexity of star and reversal is $2^n$. All our witnesses are described over a unary or binary alphabets, and whenever we use a binary alphabet, it is always optimal. We also show that the tight upper bound for the conversion of alternating finite automata into nondeterministic finite automata with a unique initial state is $2^n+1$. Some of our results provide answers to open problems stated by Fellah et al. [5].

We present a new generic ∊-removal algorithm for weighted automata and transducers defined over a semiring. The algorithm can be used with any semiring covered by our framework and works with any queue discipline adopted. It can be used in particular in the case of unweighted automata and transducers and weighted automata and transducers defined over the tropical semiring. It is based on a general shortest-distance algorithm that we briefly describe. We give a full description of the algorithm including its pseudocode and its running time complexity, discuss the more efficient case of acyclic automata, an on-the-fly implementation of the algorithm and an approximation algorithm in the case of the semirings not covered by our framework. We illustrate the use of the algorithm with several semirings. We also describe an input ∊-normalization algorithm for weighted transducers based on the general shortest-distance algorithm. The algorithm, which works with all semirings covered by our framework, admits an on-the-fly implementation.

In this paper we give the cost, in terms of states, of some basic operations (union, intersection, concatenation, and Kleene star) on regular languages in the unary case (where the alphabet contains only one symbol). These costs are given by explicitly determining the number of states in the noncyclic and cyclic parts of the resulting automata. Furthermore, we prove that our bounds are optimal. We also present an interesting connection to Jacobsthal's function from number theory.

We consider the problem of labeling a directed multigraph so that it becomes a synchronized finite automaton, as an ultimate goal to solve the famous Road Coloring Conjecture, cf. [1,2]. We introduce a relabeling method which can be used for a large class of automata to improve their 'degree of synchronization'. This allows, for example, to formulate the conjecture in several equivalent ways.

We show that it is undecidable whether or not two finite substitutions are equivalent on the fixed regular language ab*c. This gives an unexpected answer to a question proposed in 1985 by Culik II and Karhumäki. At the same time it can be seen as the final result in a series of undecidability results for finite transducers initiated in 1968 by Griffiths. An application to systems of equations over finite languages is given.

One of the new approaches to data classification uses prefix codes and finite state automata as representations of prefix codes. A prefix code is a (possibly infinite) set of strings such that no string is a prefix of another one. An important task driven by the need for the efficient storage of such automata in memory is the decomposition (in the sense of formal languages concatenation) of prefix codes into prime factors. We investigate properties of such prefix code decompositions. A prime decomposition is a decomposition of a prefix code into a concatenation of nontrivial prime prefix codes. A prefix code is prime if it cannot be decomposed into at least two nontrivial prefix codes. In the paper a linear time algorithm is designed which finds the prime decomposition F₁F₂…F_k of a regular prefix code F given by its minimal deterministic automaton. Our results are especially interesting for infinite regular prefix codes.

We present a technique based on the construction of finite automata to prove termination of string rewriting systems. Using this technique the tools Matchbox and TORPA are able to prove termination of particular string rewriting systems completely automatically for which termination was considered to be very hard until recently.

In this paper, we study the tradeoffs in descriptional complexity of NFA (nondeterministic finite automata) of various amounts of ambiguity. We say that two classes of NFA are separated if one class can be exponentially more succinct in descriptional sizes than the other. New results are given for separating DFA (deterministic finite automata) from UFA (unambiguous finite automata), UFA from MDFA (DFA with multiple initial states) and UFA from FNA (finitely ambiguous NFA). We present a family of regular languages that we conjecture to be a good candidate for separating FNA from LNA (linearly ambiguous NFA).

The aim of this work is to provide a model for the dynamic implementation of finite automata for enhanced performance. Investigations have shown that hardcoded finite automata outperforms the traditional table-driven implementation up to some threshold. Moreover, the kind of string being recognized plays a major role in the overall processing speed of the string recognizer. Various experiments are depicted to show when the advantages of using hardcoding as basis for implementing finite automata (instead of using the classical table-driven approach) become manifest. The model, a dynamic algorithm that combines both hardcoding and table-driven is introduced.

Extended finite automata are finite state automata equipped with the additional ability to apply an operation on the currently remaining input word, depending on the current state. Hybrid extended finite automata can choose from a finite set of such operations. In this paper, five word operations are taken into consideration which always yield letter-equivalent results, namely reversal and shift operations. The computational power of those machines is investigated, locating the corresponding families of languages in the Chomsky hierarchy. Furthermore, different types of hybrid extended finite automata, defined by the set of operations they are allowed to apply, are compared with each other, demonstrating that there exist dependencies and independencies between the input manipulating operations.

Our aim is to present an efficient algorithm that checks whether a binary regular language is geometrical or not, based on specific properties of its minimal deterministic automaton. Geometrical languages have been introduced in the framework of off-line temporal validation of real-time softwares. Actually, validation can be achieved through both a model based on regular languages and a model based on discrete geometry. Geometrical languages are intended to develop a link between these two models. The regular case is of practical interest regarding to implementation features, which motivates the design of an efficient geometricity test addressing the family of regular languages.

We summarize results on the complexity of regular(-like) expressions and tour a fragment of the literature. In particular we focus on the descriptional complexity of the conversion of regular expressions to equivalent finite automata and vice versa, to the computational complexity of problems on regular-like expressions such as, e.g., membership, inequivalence, and non-emptiness of complement, and finally on the operation problem measuring the required size for transforming expressions with additional language operations (built-in or not) into equivalent ordinary regular expressions.

In this paper, we study the state complexities of two particular combinations of operations: catenation combined with union and catenation combined with intersection. We show that the state complexity of the former combined operation is considerably less than the mathematical composition of the state complexities of catenation and union, while the state complexity of the latter one is equal to the mathematical composition of the state complexities of catenation and intersection.

The hairpin completion is an operation on formal languages which is inspired by the hairpin formation in biochemistry. Hairpin formations occur naturally within DNA-computing. It has been known that the hairpin completion of a regular language is linear context-free, but not regular, in general. However, for some time it is was open whether the regularity of the hairpin completion of a regular language is decidable. In 2009 this decidability problem has been solved positively in [5] by providing a polynomial time algorithm. In this paper we improve the complexity bound by showing that the decision problem is actually NL-complete. This complexity bound holds for both, the one-sided and the two-sided hairpin completions.

We investigate the magic number problem, that is, the question whether there exists a minimal n-state nondeterministic finite automaton (NFA) whose equivalent minimal deterministic finite automaton (DFA) has α states, for all n and α satisfying n ≤ α ≤ 2ⁿ. A number α not satisfying this condition is called a magic number (for n). It was shown that no magic numbers exist for general regular languages, whereas trivial and non-trivial magic numbers for unary regular languages were identified. We obtain similar results for automata accepting subregular languages like, for example, star-free languages, prefix-, suffix-, and infix-closed languages, and prefix-, suffix-, and infix-free languages, showing that there are only trivial magic numbers, when they exist. For finite languages we obtain some partial results showing that certain numbers are non-magic.