Search

The present paper is devoted to traversing a maze by a collective of automata. This part of automata theory gave rise to a fairly wide range of diverse problems ([1], [2]), including those related to problems of the theory of computational complexity and probability theory. It turns out that the consideration of complicated algebraic objects, such as Burnside groups, can be interesting in this context. In the paper, we show that the Cayley graph a finitely generated group cannot be traversed by a collective of automata if and only if the group is infinite and its every element is periodic.

Deterministic finite automata are one of the simplest and most practical models of computation studied in automata theory. Their conceptual extension is the non-deterministic finite automata which also have plenty of applications. In this article, we study these models through the lens of succinct data structures where our ultimate goal is to encode these mathematical objects using information-theoretically optimal number of bits along with supporting queries on them efficiently. Towards this goal, we first design a succinct data structure for representing any deterministic finite automaton $\mathcal{D}$ having $n$ states over a $\sigma$-letter alphabet $\Sigma$ using $(\sigma-1) n\log n + O(n \log \sigma)$ bits of space, which can determine, given an input string $x$ over $\Sigma$, whether $\mathcal{D}$ accepts $x$ in $O(|x| \log \sigma)$ time, using constant words of working space. When the input deterministic finite automaton is acyclic, not only we can improve the above space-bound significantly to $(\sigma -1) (n-1)\log n+ 3n + O(\log^2 \sigma) + o(n)$ bits, we also obtain optimal query time for string acceptance checking. More specifically, using our succinct representation, we can check if a given input string $x$ can be accepted by the acyclic deterministic finite automaton using time proportional to the length of $x$, hence, the optimal query time. We also exhibit a succinct data structure for representing a non-deterministic finite automaton $\mathcal{N}$ having $n$ states over a $\sigma$-letter alphabet $\Sigma$ using $\sigma n^2+n$ bits of space, such that given an input string $x$, we can decide whether $\mathcal{N}$ accepts $x$ efficiently in $O(n^2|x|)$ time. Finally, we also provide time and space-efficient algorithms for performing several standard operations such as union, intersection, and complement on the languages accepted by deterministic finite automata.

Regularities in strings arise in various areas of science, including coding and automata theory, formal language theory, combinatorics, molecular biology and many others. A common notion to describe regularity in a string T is a cover, which is a string C for which every letter of T lies within some occurrence of C. The alignment of the cover repetitions in the given text is called a tiling. In many applications finding exact repetitions is not sufficient, due to the presence of errors. In this paper, we use a new approach for handling errors in coverable phenomena and define the approximate cover problem (ACP), in which we are given a text that is a sequence of some cover repetitions with possible mismatch errors, and we seek a string that covers the text with the minimum number of errors. We first show that the ACP is NP -hard, by studying the cover-length relaxation of the ACP, in which the requested length of the approximate cover is also given with the input string. We show that this relaxation is already NP -hard. We also study another two relaxations of the ACP, which we call the partial-tiling relaxation of the ACP and the full-tiling relaxation of the ACP, in which a tiling of the requested cover is also given with the input string. A given full tiling retains all the occurrences of the cover before the errors, while in a partial tiling there can be additional occurrences of the cover that are not marked by the tiling. We show that the partial-tiling relaxation has a polynomial time complexity and give experimental evidence that the full-tiling also has polynomial time complexity. The study of these relaxations, besides shedding another light on the complexity of the ACP, also involves a deep understanding of the properties of covers, yielding some key lemmas and observations that may be helpful for a future study of regularities in the presence of errors.

We develop a theory of vector spaces spanned by orbit-finite sets. Using this theory, we give a decision procedure for equivalence of weighted register automata, which are the common generalization of weighted automata and register automata for infinite alphabets. The algorithm runs in exponential time, and in polynomial time for a fixed number of registers. As a special case, we can decide, with the same complexity, language equivalence for unambiguous register automata, which improves previous results in three ways: (a) we allow for order comparisons on atoms, and not just equality; (b) the complexity is exponentially better; and (c) we allow automata with guessing.

We show how some problems in additive number theory can be attacked in a novel way, using techniques from the theory of finite automata. We start by recalling the relationship between first-order logic and finite automata, and use this relationship to solve several problems involving sums of numbers defined by their base-2 and Fibonacci representations. Next, we turn to harder results. Recently, Cilleruelo, Luca, & Baxter proved, for all bases b ≥ 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome (Cilleruelo et al., Math. Comput. 87, 3023–3055, 2018). However, the cases b = 2, 3, 4 were left unresolved. We prove that every natural number is the sum of at most 4 natural numbers whose base-2 representation is a palindrome. Here the constant 4 is optimal. We obtain similar results for bases 3 and 4, thus completely resolving the problem of palindromes as an additive basis. We consider some other variations on this problem, and prove similar results. We argue that heavily case-based proofs are a good signal that a decision procedure may help to automate the proof.

Graph theory plays crucial role in structuring many real-world problems including, medical sciences, control theory, expert systems and network security. Product in graphs, an operation that consider two graphs and produce a new graph by simple or complex changes, has wide range of applications in games theory, automata theory, structural mechanics and networking system. An intuitionistic fuzzy model is used to handle the vagueness and uncertainty in network problems. A Pythagorean fuzzy model is a powerful tool for describing vagueness and uncertainty more accurately as compared to intuitionistic fuzzy model. The objective of this paper is to apply the concept of Pythagorean fuzzy sets to graphs and then combine two Pythagorean fuzzy graphs (PFGs) using two new graph products namely, maximal product and the residue product. This research paper investigates the regularity for these products. Moreover, it discusses some eminent properties such as strongness, connectedness and completeness. Further, it proposes some necessary and sufficient conditions for $${\mathscr {G}}_{1}*{\mathscr {G}}_{2}$$ and $${\mathscr {G}}_{1}\cdot {\mathscr {G}}_{2}$$ to be regular. Finally, decision-making problems concerning evaluation of best company for investment and alliance partner selection of a software company are solved to better understand PFGs.

Graph learning by automata is a basic task in many applications. Among these applications are verification and testing of software and hardware systems, network exploration including Internet and GRID basing on formal models. The system or network model, in the final analysis, is a transition graph with properties to be examined. In the recent years the size of the systems and networks in everyday use and, consequently, the size of their models and graphs to be learned grows constantly. Problems arise when graph exploration by a single automaton (computer) either requires a lot of time, or a lot of computer memory, or both. Therefore, there is a task of parallel and distributed graph exploration. This task is formalized as graph learning by a set of automata (a set of computers with sufficient total memory working in parallel). This paper covers the solution of this task. First of all the behavior of the automaton on the graph is formalized. Then the algorithm of the graph learning is described in detail. The estimation of the algorithm is O ( m + nD ). Some ways of possible optimization is discussed.

In the constrained synchronization problem we ask if a given automaton admits a synchronizing word coming from a fixed regular constraint language. We show that intersecting a given constraint language with an ideal language does not increase the computational complexity. Additionally, we state a theorem giving \(\textsf {PSPACE}\)-hardness that broadly generalizes previously used constructions and a result on how to combine languages by concatenation to get polynomial time solvable constrained synchronization problems. We use these results to give a classification of the complexity landscape for small constraint automata of up to three states.

We investigate the constrained synchronization problem for weakly acyclic, or partially ordered, input automata. We show that, for input automata of this type, the problem is always in \(\textsf {NP}\). Furthermore, we give a full classification of the realizable complexities for constraint automata with at most two states and over a ternary alphabet. We find that most constrained problems that are PSPACE-complete in general become NP-complete. However, there also exist constrained problems that are PSPACE-complete in the general setting but become polynomial time solvable when considered for weakly acyclic input automata. We also investigate two problems related to subset synchronization, namely if there exists a word mapping all states into a given target subset of states, and if there exists a word mapping one subset into another. Both problems are \(\textsf {PSPACE}\)-complete in general, but in our setting the former is polynomial time solvable and the latter is \(\textsf {NP}\)-complete.

Here we study the computational complexity of the constrained synchronization problem for the class of regular commutative constraint languages. Utilizing a vector representation of regular commutative constraint languages, we give a full classification of the computational complexity of the constrained synchronization problem. Depending on the constraint language, our problem becomes \(\textsf {PSPACE}\)-complete, \(\textsf {NP}\)-complete or polynomial time solvable. In addition, we derive a polynomial time decision procedure for the complexity of the constrained synchronization problem, given a constraint automaton accepting a commutative language as input.

A k-limited automaton is a linear bounded automaton that may rewrite each tape cell only in the first k visits, where k ≥ 0 is a fixed constant. It is known that these automata accept context-free languages only. We investigate the descriptional complexity of limited automata. Since the unary languages accepted are necessarily regular, we first study the cost in the number of states when finite automata simulate a unary k-limited automaton. For the conversion of a 4n-state deterministic 1-limited automaton into one-way or two-way deterministic or nondeterministic finite automata, we show a lower bound of n ⋅ F ( n ) states, where F denotes Landau's function. So, even the ability to deterministically rewrite any cell only once gives an enormous descriptional power. For the simulation cost for removing the ability to rewrite each cell k ≥ 1 times, more precisely, the cost for the simulation of sweeping unary k-limited automata by deterministic finite automata, we obtain a lower bound of n ⋅ F ( n ) k . The upper bound of the cost for the simulation by two-way deterministic finite automata is a polynomial whose degree is quadratic in k. If the k-limited automaton is rotating, the upper bound reduces to O ( n k + 1 ) and the lower bound derived is Ω ( n k + 1 ) even for nondeterministic two-way finite automata. So, for rotating k-limited automata, the trade-off for the simulation is tight in the order of magnitude. Finally, we consider the simulation of k-limited automata over general alphabets by pushdown automata. It turns out that the cost is an exponential blow-up of the size. Furthermore, an exponential size is also necessary.

Two models of automata over infinite alphabets are presented, mainly with a focus on the alphabet [Formula: see text]. In the first model, transitions can refer to logic formulas that connect properties of successive letters. In the second, the letters are considered as columns of a labeled grid which an automaton traverses column by column. Thus, both models focus on the comparison of successive letters, i.e. “local changes”. We prove closure (and non-closure) properties, show the decidability of the respective non-emptiness problems, prove limits on decidability results for extended models, and discuss open issues in the development of a generalized theory.

Nondeterminism gives computation models the power of existential choice. As a generalization of nondeterminism, “alternation” gives computation models the power of existential choice and universal choice simultaneously. In this paper, we extend fuzzy nondeterministic automata to a model called fuzzy alternating automata over distributive lattices. Compared with the previous work, a weight labels a leaf node of the run tree rather than be involved in the edge between states when executing a transition. One advantage of our setting is that it is easy to complement a given fuzzy alternating automaton. It suffices to take the dual operation on the transition function and negate final costs on states. Moreover, we show that fuzzy alternating automata have the same expressive power as fuzzy nondeterministic automata, and the former ones are exponentially more succinct than the latter ones. In addition, we illustrate that such exponential blow-up is unavoidable.

Alternation was first proposed by Chandra et al. for obtaining a theoretical model of parallel computations. Compared with nondeterminism, alternation gives computing devices the power of universal choice in addition to existential choice. In this paper, we put forward a notion of fuzzy alternating Buchi automata over a distributive lattice L ( L -ABAs, for short). In our setting, a weight is the label of a leaf node of the run tree when executing a transition, which is helpful in complementing L -ABAs. Taking the dual operation on the transition function and negating final costs on states, we can get the complement of a given L -ABA. We point out that L -ABAs have the same expressive power as L -valued fuzzy nondeterministic Buchi automata ( L -NBAs). A construction presented here shows that languages accepted by L -valued fuzzy alternating co-Buchi automata ( L -ACAs) are also ω-regular languages. Moreover, closure properties of L -ABAs and decision problems for L -ABAs are also discussed.

In this study, the author presents a new efficient algorithm for translating linear temporal logic (LTL) formulas to Buchi automata, which are used by LTL model checkers. The general idea of this algorithm is to generate Buchi automata from LTL formulas, using the principle of alternating automata and keeping only the positive transitions without generating the intermediate generalised automata. The LTL translation is the heart of any LTL model checker, which affects its performance. The translation performance is measured in addition to its speed and the size of the produced Buchi automaton (number of states and number of transitions), by correctness of produced Buchi automaton and its level of determinism. The author will show that this method is different from the others and it is very competitive with the most efficient translators to date.

A k-limited automaton is a linear bounded automaton that may rewrite each tape square only in the first k visits, where \(k\ge 0\) is a fixed constant. It is known that these automata accept context-free languages only. We investigate deterministic k-limited automata towards their ability to perform reversible computations, that is, computations in which every configuration has at most one predecessor. A first result is that, for all \(k\ge 0\), sweeping k-limited automata accept regular languages only. In contrast to reversible finite automata, all regular languages are accepted by sweeping 0-limited automata. Then we study the computational power gained in the number k of possible rewrite operations. It is shown that the reversible 2-limited automata accept regular languages only and, thus, are strictly weaker than general 2-limited automata. Furthermore, a proper inclusion between reversible 3-limited and 4-limited automata languages is obtained. The next levels of the hierarchy are separated between every k and \(k+3\) rewrite operations. Finally, it turns out that all k-limited automata accept Church-Rosser languages only, that is, the intersection between context-free and Church-Rosser languages contains an infinite hierarchy of language families beyond the deterministic context-free languages.

One-way multi-head finite automata are considered towards their ability to perform reversible computations. It is shown that, for every number k ≥ 1 of heads, there are problems which can be solved by one-way k-head finite automata, but not by any one-way reversible k-head finite automaton. Additionally, a proper head hierarchy is obtained for one-way reversible multi-head finite automata. Closure properties and decidability problems are investigated as well. It turns out that one-way reversible finite automata with two heads are still a powerful model, since almost all commonly studied problems are not even semidecidable. Finally, descriptional complexity aspects are studied and non-recursive trade-offs are shown.

Finite languages are an important sub-regular language family, which were intensively studied during the last two decades in particular from a descriptional complexity perspective. An important contribution to the theory of finite languages are the deterministic and the recently introduced nondeterministic finite cover automata (DFCAs and NFCAs, respectively) as an alternative representation of finite languages by ordinary finite automata. We compare these two types of cover automata from a descriptional complexity point of view, showing that these devices have a lot in common with ordinary finite automata. In particular, we study how to adapt lower bound techniques for nondeterministic finite automata to NFCAs such as, e.g., the biclique edge cover technique, solving an open problem from the literature. Moreover, the trade-off of conversions between DFCAs and NFCAs as well as between finite cover automata and ordinary finite automata are investigated. Finally, we present some results on the average size of finite cover automata.

We present a disambiguation algorithm for weighted automata. The algorithm admits two main stages: a pre-disambiguation stage followed by a transition removal stage. We give a detailed description of the algorithm and the proof of its correctness. The algorithm is not applicable to all weighted automata but we prove sufficient conditions for its applicability in the case of the tropical semiring by introducing the weak twins property . In particular, the algorithm can be used with any weighted automaton over the tropical semiring for which the weighted determinization algorithm terminates and with any acyclic weighted automaton over an arbitrary weakly left divisible cancellative and commutative semiring. While disambiguation can sometimes be achieved using weighted determinization, our disambiguation algorithm in some cases can return a result that is exponentially smaller than any equivalent deterministic automaton. We also present some empirical evidence of the space benefits of disambiguation over determinization in speech recognition and machine translation applications.

We prove completeness for some language-theoretic models of the full Lambek calculus and its various fragments. First we consider syntactic concepts and syntactic concepts over regular languages, which provide a complete semantics for the full Lambek calculus $${\mathbf {FL}}_\perp $$FLź. We present a new semantics we call automata-theoretic, which combines languages and relations via closure operators which are based on automaton transitions. We establish the completeness of this semantics for the full Lambek calculus via an isomorphism theorem for the syntactic concepts lattice of a language and a construction for the universal automaton recognizing the same language. Finally, we use automata-theoretic semantics to prove completeness of relation models of binary relations and finite relation models for the Lambek calculus without and with empty antecedents (henceforth: $$\mathbf L $$L and $$\mathbf L1 $$L1), thus solving a problem left open by Pentus (Ann Pure Appl Log 75:179---213, 1995).

Automata theory based on complete residuated lattice-valued logic has been initiated by Qiu, and further systematically established by Qiu et al. In this paper, we propose the notion of nondeterministic fuzzy automata with membership values in a complete residuated lattice L, called lattice-valued nondeterministic fuzzy automata (L-NFAs). In our setting, a state of an L-NFA may have more than one transition labeled by the same input symbol, which reflects nondeterminism. To compare the behaviors of L-NFAs, we introduce two language equivalence relations which have different discriminating power. Furthermore, we extend the two relations to the complete residuated lattice-valued setting and investigate their properties such as robustness and compositionality. The theory developed here is applicable to the quantitative modeling and verification of fuzzy systems. Present a new kind of nondeterministic fuzzy automata.Introduce two language-equivalent relations and their fuzzy versions.Analyze the compositionality and robustness of the two relations.

A term, also called a tree, is said to be linear, if each variable occurs in the term only once. The linear terms and sets of linear terms, the so-called linear tree languages, play some role in automata theory and in the theory of formal languages in connection with recognizability. We define a partial superposition operation on sets of linear trees of a given type τ and study the properties of some many-sorted partial clones that have sets of linear trees as elements and partial superposition operations as fundamental operations. The endomorphisms of those algebras correspond to nondeterministic linear hypersubstitutions.

In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of finite automata with multiple independent heads that walk on Cayley graphs, called group-walking automata, and use it to define subshifts. We characterize the torsion groups (also known as periodic groups) as those on which the group-walking automata are strictly weaker than Turing machines, and those on which the head hierarchy is infinite.

The family of languages recognized by deterministic input-driven pushdown automata (IDPDA; a.k.a. visibly pushdown automata, a.k.a. nested word automata) is known to be closed under concatenation, Kleene star and reversal (under natural assumptions on the partition of the alphabet). As shown by Alur and Madhusudan (2004) 2, the Kleene star and the reversal of an n-state IDPDA can be represented by an IDPDA with 2 O ( n 2 ) states, while concatenation of an m-state and an n-state IDPDA is represented by an IDPDA with 2 O ( ( m + n ) 2 ) states. This paper presents more efficient constructions for the Kleene star and for the reversal, which yield 2 ( n log n ) states, as well as an m 2 ( n log n ) -state construction for the concatenation. These constructions are optimal up to a factor in the exponent, due to the close lower bounds previously established by Piao and Salomaa (2009) 27.

We present a new algorithm to construct a (generalized) deterministic Rabin automaton for an LTL formula $$\varphi $$ź. The automaton is the product of a co-Buchi automaton for $$\varphi $$ź and an array of Rabin automata, one for each $${\mathbf {G}}$$G-subformula of $$\varphi $$ź. The Rabin automaton for $${\mathbf {G}}\psi $$Gź is in charge of recognizing whether $${\mathbf {F}}{\mathbf {G}}\psi $$FGź holds. This information is passed to the co-Buchi automaton that decides on acceptance. As opposed to standard procedures based on Safra's determinization, the states of all our automata have a clear logical structure, which allows for various optimizations. Experimental results show improvement in the sizes of the resulting automata compared to existing methods.

We introduce a new generalization of weighted automata – automata with auxiliary weights. They allow to compute several quantities not directly computable over semirings by generalizing both semiring addition and semiring multiplication. Moreover, our automata retain key properties of ordinary weighted automata. We prove that automata over multi-hemirings of Droste and Kuich [7] can be modelled using our framework, and that automata with auxiliary weights can be used to describe several additional settings. Finally, we introduce rational expressions with auxiliary weights and prove that they are equivalent to our automata.

Automata with monitor counters, where the transitions do not depend on counter values, and nested weighted automata are two expressive automata-theoretic frameworks for quantitative properties. For a well-studied and wide class of quantitative functions, we establish that automata with monitor counters and nested weighted automata are equivalent. We study for the first time such quantitative automata under probabilistic semantics. We show that several problems that are undecidable for the classical questions of emptiness and universality become decidable under the probabilistic semantics. We present a complete picture of decidability for such automata, and even an almost-complete picture of computational complexity, for the probabilistic questions we consider., Logical Methods in Computer Science ; Volume 15, Issue 3 ; 1860-5974

We prove that one can construct various kinds of automata over finite words for which some elementary properties are actually independent from strong set theories like [Formula: see text] [Formula: see text] “There exist (at least) [Formula: see text] inaccessible cardinals”, for integers [Formula: see text]. In particular, we prove independence results for languages of finite words generated by context-free grammars, or accepted by 2-tape or 1-counter automata. Moreover we get some independence results for weighted automata and for some related finitely generated subsemigroups of the set [Formula: see text] of 3-3 matrices with integer entries. Some of these latter results are independence results from the Peano axiomatic system PA.

The main problem addressed by this thesis is that of characterising information leakage channels in interactive systems as either 'dangerous' or 'safe', on the basis of the amount of information that can be leaked. We define information information leakage in a fashion very similar to the classical definition of Goguen and Meseguer, modeling systems as finite state transducers. Interesting issues arise in the selection of the appropriate measure of information, and we propose some novel definitions which address the problems which have been identified with the traditional notion of mutual information. We show that for deterministic systems, the problem of quantifying information flow can be reduced to a natural combinatorial problem on regular languages, namely that of computing their 'width' with respect to the lexicographic partial order. We solve this problem, and show that there is a dichotomy between exponential and polynomial width, corresponding to linear and logarithmic information flow (which we characterise as 'dangerous' and 'safe' respectively). We give a polynomial time algorithm to distinguish the two cases, as well as to compute the precise rate of logarithmic information flow. We also study the analagous question for some other partially ordered structures: we show that for context-free languages there is a similar dichotomy but the problem of distinguishing the two cases is undecidable, and that for regular tree languages there is a trichotomy between doubly exponential, singly exponential and polynomial growth. Finally we consider information flow in the setting of the process algebra CSP. In order to reduce to the framework of languages and automata, we establish a general theorem showing that a wide class of finite observational models of CSP (including all known models) can be reduced to the traces model using the `priority' operator.

This paper introduces spanning tree automata (ST automata) usable for defining sets of labeled, connected graphs. The automata are simply obtained by extending ordinary top-down finite tree automata for labeled, ordered trees. It is shown that ST automata can define any finite set of labeled, connected graphs, and also some subclasses of infinite sets of graphs that can represent the structure of chemical molecules. Although the membership problem for ST automata is NP-complete, an efficient software was developed which supports a practical use of ST automata in chemoinformatics as well as in other fields.

String covers are a powerful tool for analyzing the quasi-periodicity of 1-dimensional data and find applications in automata theory, computational biology, coding and the analysis of transactional data. A cover of a string T is a string C for which every letter of T lies within some occurrence of C. String covers have been generalized in many ways, leading to k-covers, \(\lambda \)-covers, approximate covers and were studied in different contexts such as indeterminate strings.

In this chapter we introduce finite automata, discuss their properties, and present their role as recognizers of regular languages, in particular at the lexical level of compilation. After an overview of general string recognition algorithms and automata, we focus on finite-state devices. We define the notions of state accessibility, determinism, spontaneous move, ambiguity, and we analyze the relations between finite automata and grammars. We present the basic constructions for cleaning, determinizing, and minimizing automata. Then we spend more time on the methods for deriving regular expressions from automata, and, conversely, for obtaining finite deterministic recognizers from regular expressions; the latter methods are also used for eliminating nondeterminism. Finally, by exploiting their relation to finite automata, we introduce regular expressions extended with the operations of complement and intersection.

We consider the state complexity of intersection, union and the shuffle operation on commutative regular languages for arbitrary alphabets. Certain invariants will be introduced which generalize known notions from unary languages used for refined state complexity statements and existing notions for commutative languages used for the subclass of periodic languages. Our bound for shuffle is formulated in terms of these invariants and shown to be optimal, from this we derive the bound of \((2nm)^{|\varSigma |}\) for commutative languages of state complexities n and m respectively. This result is a considerable improvement over the general bound \(2^{mn-1} + 2^{(m-1)(n-1)}(2^{m-1} -1)(2^{n-1}-1)\).

International audience; In this paper, we study the lattice and the Boolean algebra, possibly closed under quotient, generated by the languages of the form $u⁎$, where $u$ is a word. We provide effective equational characterisations of these classes, i.e. one can decide using our descriptions whether a given regular language belongs or not to each of them.

In the plethora of fragments of Halpern and Shoham's modal logic of time intervals (HS), the logic AB of Allen's relations Meets and Started-by is at a central position. Statements that may be true at certain intervals, but at no sub-interval of them, such as accomplishments, as well as metric constraints about the length of intervals, that force, for instance, an interval to be at least (resp., at most, exactly) k points long, can be expressed in AB. Moreover, over the linear order of the natural numbers N, it subsumes the (point-based) logic LTL, as it can easily encode the next and until modalities. Finally, it is expressive enough to capture the {\omega}-regular languages, that is, for each {\omega}-regular expression R there exists an AB formula {\phi} such that the language defined by R coincides with the set of models of {\phi} over N. It has been shown that the satisfiability problem for AB over N is EXPSPACE-complete. Here we prove that, under the homogeneity assumption, its model checking problem is {\Delta}^p_2 = P^NP-complete (for the sake of comparison, the model checking problem for full HS is EXPSPACE-hard, and the only known decision procedure is nonelementary). Moreover, we show that the modality for the Allen relation Met-by can be added to AB at no extra cost (AA'B is P^NP-complete as well)., Comment: In Proceedings GandALF 2016, arXiv:1609.03648

Cellular automata have rich computational properties and provide many models in mathematical and physical processes. In this paper, one of the most commonly used neighborhood types of two dimensional (2D) cellular automata which is called the Moore neighborhood in two dimensional integer lattice is considered. We study the characterization of 2D linear cellular automata defined by the Moore neighborhood with periodic and null boundary conditions over ternary fields. Furthermore, we analyze some results of 2D cellular automata defined by the rule number 9840NB and finally also present applications to error correcting codes and image processing field. (C) 2016 Elsevier Inc. All rights reserved.

Since 1970, reversible finite automata have generated interest among researcher; but till now, we have not come across a model of reversible read only one-way finite automata which accept all regular languages, In this paper, we introduce a new model of one-way reversible finite automata inspired by the Watson---Crick complementarity relation and show that our model can accept all regular languages. We further show that our model accepts a language which is not accepted by any multi-head deterministic finite automaton.

In this paper, we pioneer a study of parameterized automata constructions for languages related to the design of parameterized algorithms. We focus on the k- Distinct language L k ( Σ ) ⊆ Σ k , defined as the set of words of length k over an alphabet Σ whose symbols are all distinct. This language is implicitly related to several breakthrough techniques developed during the last two decades, to design parameterized algorithms for fundamental problems such as k- Path and r- Dimensional k- Matching . Building upon the color coding, divide-and-color and narrow sieves techniques, we obtain the following automata constructions for L k ( Σ ) . We develop non-deterministic automata (NFAs) of sizes 4 k + o ( k ) ⋅ n O ( 1 ) and ( 2 e ) k + o ( k ) ⋅ n O ( 1 ) , where the latter satisfies a ‘bounded ambiguity’ property relevant to approximate counting, as well as a non-deterministic xor automaton (NXA) of size 2 k ⋅ n O ( 1 ) , where n = | Σ | . We show that our constructions can be used to develop both deterministic and randomized algorithms for k- Path , r- Dimensional k -Matching and Module Motif in a natural manner, considering also their approximate counting variants. Our framework is modular and consists of two parts: designing an automaton for k- Distinct , and designing a problem specific automaton, as well as an algorithm for deciding whether the intersection automaton's language is empty, or for counting the number of accepting paths in it.

We consider the classes of linear automata functions over finite fields with composition (superposition and feedback) operation and describe an algorithm that decides whether a finite set of functions from such class is complete. Thus we generalize the result that was known for the case of linear automata functions over prime finite fields.

We establish a relationship between reachability problems in timed automata and spacebounded counter automata. We show that reachability in timed automata with three or more clocks is logarithmic-space inter-reducible with reachability in space-bounded counter automata with two counters. We moreover show the logarithmic-space equivalence of reachability in two-clock timed automata and space-bounded one-counter automata. This last reduction has recently been employed by Fearnley and Jurdzinski to settle the computational complexity of reachability in two-clock timed automata.

In this work we study some aspects of state-complexity related to the very famous Sakoda-Sipser problem. We study the state-complexity of the regular operations, we survey the known facts and, by the way, we find some new and simpler proofs of some well known results. The analysis of the state of art allowed us to find a new and meaningful notion: Real-state processing. We investigate this notion, looking for a model of deterministic finite automata holding such an interesting property. We establish some preliminary results, which seem to indicate that there does not exists a model of deterministic finite automata having real-state processing of regular expressions, but, on the other hand, we are able of exhibiting a deterministic model of finite automata having real-state processing of star free regular expressions.

Cerny's conjecture is a longstanding open problem in automata theory. We study two different concepts, which allow to approach it from a new angle. The first one is the triple rendezvous time, i.e., the length of the shortest word mapping three states onto a single one. The second one is the synchronizing probability function of an automaton, a recently introduced tool which reinterprets the synchronizing phenomenon as a two-player game, and allows to obtain optimal strategies through a Linear Program. Our contribution is twofold. First, by coupling two different novel approaches based on the synchronizing probability function and properties of linear programming, we obtain a new upper bound on the triple rendezvous time. Second, by exhibiting a family of counterexamples, we disprove a conjecture on the growth of the synchronizing probability function. We then suggest natural follow-ups towards Cernys conjecture., Comment: A preliminary version of the results has been presented at the conference LATA 2015. The current ArXiv version includes the most recent improvement on the triple rendezvous time upper bound as well as formal proofs of all the results

In this paper we study structure and representations of cyclic automata. Corresponding to Green's equivalences in semigroup theory, we introduce three binary relations say L , R and H on cyclic automata. An automaton is said to be strict if L is an equivalence on the set of states. Some properties of these relations are established for giving characterizations of three subclasses of strict automata. Also, we provide representations of strict automata by representing the states as vectors and describing the state transitions in terms of matrix operations. These results generalize and extend Ito's representations of strongly connected automata.

The article surveys some decidability results concerning simplification problems for DPDAs on infinite words (ω-DPDAs). We summarize some recent results on the regularity problem, which asks for a given ω-DPDA, whether its language can also be accepted by a finite automaton. The results also give some insights on the equivalence problem for a subclass of ω-DPDA. Furthermore, we present some new results on the parity index problem for ω-DPDAs. For the specification of a parity condition, the states of the ω-DPDA are assigned priorities (natural numbers), and a run is accepting if the highest priority that appears infinitely often during a run is even. The basic simplification question asks whether one can determine the minimal number of priorities that are needed to accept the language of a given ω-DPDA. We provide some decidability results on variations of this question for some classes of ω-DPDAs.

The determinization of Buchi automata is a celebrated problem, with applications in synthesis, probabilistic verification, and multi-agent systems. Since the 1960s, there has been a steady progress of constructions: by McNaughton, Safra, Piterman, Schewe, and others. Despite the proliferation of solutions, they are all essentially ad-hoc constructions, with little theory behind them other than proofs of correctness. Since Safra, all optimal constructions employ trees as states of the deterministic automaton, and transitions between states are defined operationally over these trees. The operational nature of these constructions complicates understanding, implementing, and reasoning about them, and should be contrasted with complementation, where a solid theory in terms of automata run DAGs underlies modern constructions. In 2010, we described a profile-based approach to Buchi complementation, where a profile is simply the history of visits to accepting states. We developed a structural theory of profiles and used it to describe a complementation construction that is deterministic in the limit. Here we extend the theory of profiles to prove that every run DAG contains a profile tree with at most a finite number of infinite branches. We then show that this property provides a theoretical grounding for a new determinization construction where macrostates are doubly preordered sets of states. In contrast to extant determinization constructions, transitions in the new construction are described declaratively rather than operationally., Comment: In Proceedings GandALF 2013, arXiv:1307.4162