Implementation and Application of Automata

Much work has been done to obtain classes of picture languages that would correspond to the classes of the Chomsky hierarchy for string languages, and finally the class REC of recognizable picture languages has been agreed on as the class that corresponds to the ‘regular string languages.’ This class has several nice characterizations in terms of regular expressions, tiling automata, and on-line tesselation automata, and it has nice closure properties, but it also has two main drawbacks: all its characterizations are highly nondeterministic in nature, and it contains languages that are NP-complete. Consequentially, various deterministic subclasses of REC have been defined. Mainly, however, these definitions are quite complex, and it is not clear which of the resulting classes should be considered as ‘the’ class of deterministic recognizable picture languages. Here we present some recent developments obtained in a research project that aims at finding a deterministic model of a two-dimensional automaton that has the following desirable properties:

In the course of the project, several types of two-dimensional automata have been defined and investigated. Here these types of automata and the classes of picture languages accepted by them are compared to each other and to the classes REC and DREC, and their closure properties and algorithmic properties are considered.

The investigation of automata and languages defined over a one letter alphabet shows interesting differences with respect to the case of alphabets with at least two letters. Probably, the oldest example emphasizing one of these differences is the collapse of the classes of regular and context-free languages in the unary case (Ginsburg and Rice, 1962). Many differences have been proved concerning the state costs of the simulations between different variants of unary finite state automata (Chrobak, 1986, Mereghetti and Pighizzini, 2001). We present an overview of those results. Because important connections with fundamental questions in space complexity, we give emphasis to unary two-way automata. Furthermore, we discuss unary versions of other computational models, as one-way and two-way pushdown automata, even extended with auxiliary workspace, and multi-head automata.

Cellular Automata (CA) as bio-inspired parallel computational models of self-reproducing organisms can capture the essential features of systems where global behavior arises from the collective effect of simple components which interact locally. In this aspect, CAs have been considered as a fine candidate to model pedestrian behavior and crowd dynamics in a fine manner. In specific, for crowd modeling, the CA models show evidence of a macroscopic nature with microscopic extensions, i.e. they provide adequate details in the description of human behavior and interaction, whilst they retain the computational cost at low levels. In this paper several CA models for crowd evacuation taking into consideration different modeling principles, like potential fields techniques, obstacle avoidance, follow-the-leader principles, grouping theory, etc. will be presented in an attempt to accomplish efficient crowd evacuation simulation. Moreover, an integrated system based on CAs that operates as an anticipative crowd management tool in cases of medium density crowd evacuation for indoor and outdoor environments is also shown, and its results different real world cases and different environments prove its efficiency. Finally, robot guided evacuation with the help of CAs is also presented. Quite recently, an evacuation system was proposed, based on an accurate CA model capable of assessing the human behavior during emergency situations takes advantage of the simulation output to provide sufficient information to a mobile robotic guide, which in turn guides people towards a less congestive exit at a time.

The notion of linear finite transducer (LFT) plays a crucial role in a family of cryptosystems introduced in the 80’s and 90’s. However, as far as we know, no study was ever conducted to count and enumerate these transducers, which is essential to verify if the size of the key space, of the aforementioned systems, is large enough to prevent an exhaustive search attack. In this paper, we determine the cardinal of the equivalence classes on the set of the LFTs with a given size. This result is sufficient to get an approximate value, by random sampling, for the number of non-equivalent injective LFTs, and subsequently for the size of the key space. We introduce a notion of canonical LFT, give a method to verify if two LFTs are equivalent, and prove that every LFT has exactly one equivalent canonical LFT. We then show how this canonical LFT allows us to calculate the size of each equivalence class on the set of the LFTs with the same number of states.

We consider the model of one-way automata with quantum and classical states (qcfas) introduced in [23]. We show, by a direct approach, that qcfas with isolated cut-point accept regular languages only, thus characterizing their computational power. Moreover, we give a size lower bound for qcfas accepting regular languages, and we explicitly build qcfas accepting the word quotients and inverse homomorphic images of languages accepted by given qcfas with isolated cut-point, maintaining the same cut-point, isolation, and polynomially increasing the size.

We continue the study of the shuffle of individual words, and the problem of decomposing a finite automaton into the shuffle on words. There is a known polynomial time algorithm to decide whether the shuffle of two words is a subset of the language accepted by a deterministic finite automaton [5]. In this paper, we consider the converse problem of determining whether or not the language accepted by a deterministic finite automaton is a subset of the shuffle of two words. We provide a polynomial time algorithm to decide whether the language accepted by a deterministic finite automaton is a subset of the shuffle of two words, for the special case when the skeletons of the two words are of fixed length. Therefore, for this special case, we can decide equality in polynomial time as well. However, we then show that this problem is coNP-Complete in general, as conjectured in [2].

Partial words are sequences of characters from an alphabet in which some positions may be marked with a “hole” symbol, ⋄. We can create a ⋄-substitution mapping this symbol to a subset of the alphabet, so that applying such a substitution to a partial word results in a set of full words (ones without holes). This setup allows us to compress regular languages into smaller partial languages. Deterministic finite automata for such partial languages, referred to as ⋄-DFAs, employ a limited non-determinism that can allow them to have lower state complexity than the minimal DFAs for the corresponding full languages. Our paper focuses on algorithms for the construction of minimal partial languages, associated with some ⋄-substitution, as well as approximation algorithms for the construction of minimal ⋄-DFAs.

We search for the largest syntactic semigroup of a star-free language having n left quotients; equivalently, we look for the largest transition semigroup of an aperiodic finite automaton with n states.

We first introduce unitary semigroups generated by transformations that change only one state. In particular, we study complete unitary semigroups which have a special structure, and we show that each maximal unitary semigroup is complete. For \(n \geqslant 4\) there exists a complete unitary semigroup that is larger than any aperiodic semigroup known to date.

We then present even larger aperiodic semigroups, generated by transformations that map a non-empty subset of states to a single state; we call such transformations and semigroups semiconstant. In particular, we examine semiconstant tree semigroups which have a structure based on full binary trees. The semiconstant tree semigroups are at present the best candidates for largest aperiodic semigroups.

We show that the upper bound (n − k)·2 ⁿ  + k·2 ^n − 1 on the state complexity of the square of a regular language recognized by an n-state deterministic finite automaton with k final states is tight in the ternary case for every k with 1 ≤ k ≤ n − 2. Using this result, we are able to define a language that is hard for the square operation on languages accepted by alternating finite automata. In the unary case, the known upper bound for square is 2n − 1, and we prove that each value in the range from 1 to 2n − 1 may be attained by the state complexity of the square of a unary language with state complexity n whenever n ≥ 5.

A two-way deterministic finite state automaton with one counter (2D1CA) is a fundamental computational model that has been examined in many different aspects since sixties, but we know little about its power in the case of unary languages. Up to our knowledge, the only known unary nonregular languages recognized by 2D1CAs are those formed by strings having exponential length, where the exponents form some trivial unary regular language. In this paper, we present some non-trivial subsets of these languages. By using the input head as a second counter, we present simulations of two-way deterministic finite automata with linearly bounded counters and linear–space Turing machines. We also show how a fixed-size quantum register can help to simplify some of these languages. Finally, we compare unary 2D1CAs with two–counter machines and provide some insights about the limits of their computational power.

We present a type system for automata and rational expressions, expressive enough to encompass weighted automata and transducers in a single coherent formalism. The system allows to express useful properties about the applicability of operations including binary heterogeneous functions over automata.

We consider a restricted variant of the prefix-suffix duplication operation, called bounded prefix-suffix duplication. It consists in the iterative duplication of a prefix or suffix, whose length is bounded by a constant, of a given word. We give a sufficient condition for the closure under bounded prefix-suffix duplication of a class of languages. Consequently, the class of regular languages is closed under bounded prefix-suffix duplication; furthermore, we propose an algorithm deciding whether a regular language is a finite k-prefix-suffix duplication language. An efficient algorithm solving the membership problem for the k-prefix-suffix duplication of a language is also presented. Finally, we define the k-prefix-suffix duplication distance between two words, extend it to languages and show how it can be computed for regular languages.

In this paper, we study tree automata recognizing labeled multidigraphs. We define that a labeled multidigraph is accepted by a tree automaton if and only if the graph has a spanning tree accepted by the tree automaton. We call this automaton a spanning tree automaton. The membership problem of labeled multidigraphs for a spanning tree automaton is NP-complete because the Hamiltonian path problem can be easily reduced to it. However, it will be shown that the membership problem is solvable in linear time for graphs of bounded tree-width.

We present several series of synchronizing automata with multiple parameters, generalizing previously known results. Let p and q be two arbitrary co-prime positive integers, q > p. We describe reset thresholds of the colorings of primitive digraphs with exactly one cycle of length p and one cycle of length q. Also, we study reset thresholds of the colorings of primitive digraphs with exactly one cycle of length q and two cycles of length p.

We prove new decidability and undecidability results concerning the finite-ambiguity problem in acceptors, and the finite-valuedness and lossiness problems in transducers. The acceptors and transducers we study have infinite memory.

We study the Kleene closure operation on regular and prefix-free languages. Using an alphabet of size 2n, we get the contiguous range from 1 to 3/4·2 ⁿ of complexities of the Kleene closure of regular languages accepted by minimal n-state deterministic finite automata. In the case of prefix-free languages, the Kleene closure may attain just three possible complexities n − 2, n − 1, and n.

We study the NFA reductions by invariant equivalences. It is well-known that the NFA minimization problem is PSPACE-complete. Therefore, there have been approaches to reduce the size of NFAs in low polynomial time by computing invariant equivalence and merging the states within same equivalence class. Here we consider the nondeterminism reduction of NFAs by invariant equivalences. We, in particular, show that the left-invariant equivalence is more useful than the right-invariant equivalence for reducing NFA nondeterminism. We also present experimental evidence for showing that NFA reduction by left-invariant equivalence achieves the better reduction of nondeterminism than right-invariant equivalence.

We show that the only analytic functions computable by finite state transducers in sofic Möbius number systems are Möbius transformations.

Minimization of nondeterministic finite automata (NFA) is a hard problem (PSPACE-complete). Bisimulations are then an attractive alternative for reducing the size of NFAs, as even bisimilarity (the largest bisimulation) is almost linear using the Paige and Tarjan algorithm. NFAs obtained from regular expressions (REs) can have the number of states linear with respect to the size of the REs and conversion methods from REs to equivalent NFAs can produce NFAs without or with transitions labelled with the empty word (ε-NFA). The standard conversion without ε-transitions is the position automaton, \(\mathcal{A}_{pos}\). Other conversions, such as partial derivative automata (\(\mathcal{A}_{pd}\)) or follow automata (\(\mathcal{A}_{f}\)), were proven to be quotients of the position automata (by some bisimulations). Recent experimental results suggested that for REs in (normalized) star normal form the position bisimilarity almost coincide with the \(\mathcal{A}_{pd}\) automaton. Our goal is to have a better characterization of \(\mathcal{A}_{pd}\) automata and their relation with the bisimilarity of the position automata. In this paper, we consider \(\mathcal{A}_{pd}\) automata for regular expressions without Kleene star and establish under which conditions they are isomorphic to the bisimilarity of \(\mathcal{A}_{pos}\).

The expressive power of regularity-preserving multi bottom-up tree transducers (mbot) is investigated. These mbot have very attractive theoretical and algorithmic properties. However, their expressive power is not well understood. It is proved that despite the restriction their power still exceeds that of composition chains of linear extended top-down tree transducers with regular look-ahead (xtop ^R), which are a natural super-class of stsg. In particular, topicalization can be modeled by such mbot, whereas composition chains of xtop ^R cannot implement it. However, the inverse of topicalization cannot be implemented by any mbot. An interesting, promising, and widely applicable proof technique is used to prove those statements.

In this paper, we consider weighted synchronous context-free tree grammars and identify a certain syntactic restriction of these grammars. We suggest a new weighted tree transducer formalism and prove that the transformations of the restricted grammars are precisely those of the linear and nondeleting instances of these transducers.

We introduce weighted variable automata over infinite alphabets and commutative and idempotent semirings. We prove that the class of their behaviors is closed under sum, and under scalar, Hadamard, Cauchy, and shuffle product, as well as star operation. Furthermore, we consider rational series over infinite alphabets and we state a Kleene-Schützenberger theorem.

We construct zero-error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded-error probabilistic finite automata (PFAs). Here is a summary of our results:

Pairwise Rational Kernels (PRKs) are the combination of pairwise kernels, which handle similarities between two pairs of entities, and rational kernels, which are based on finite-state transducer for manipulating sequence data. PRKs have been already used in bioinformatics problems, such as metabolic network prediction, to reduce computational costs in terms of storage and processing.

In this paper, we propose new Pairwise Rational Kernels based on automaton and transducer operations. In this case, we define new operations over pairs of automata to obtain new rational kernels. We develop experiments using these new PRKs to predict metabolic networks. As a result, we obtain better accuracy and execution times when we compare them with previous kernels.