Automata, Logic and Semantics

This section of DMTCS is devoted to publishing original research from several domains covered by Volume B of the Handbook of Theoretical Computer Science (Elsevier Publisher). Our scope is suggested by the following list of keywords: automata theory, automata-theoretic complexity, automatic program verification, combinatorics of words, coding theory, concurrency, data bases, formal languages, functional programming, logic in computer science, logic programming, program specification, rewriting, semantics of programming languages, theorem proving.


Composing short 3-compressing words on a 2-letter alphabet

Cherubini, Alessandra ; Frigeri, Achille ; Liu, Zuhua.
A finite deterministic (semi)automaton A = (Q, Σ, δ) is k-compressible if there is some word w ∈ Σ + such that theimage of its state set Q under the natural action of w is reduced by at least k states. Such word w, if it exists, is calleda k-compressing word for A and A is said to be k-compressed by […]

Decidability of multiset, set and numerically decipherable directed figure codes

Moczurad, Włodzimierz.
Codes with various kinds of decipherability, weaker than the usual unique decipherability, have been studied since multiset decipherability was introduced in mid-1980s. We consider decipherability of directed figure codes, where directed figures are defined as labelled polyominoes with […]

Most Complex Regular Ideal Languages

Brzozowski, Janusz ; Davies, Sylvie ; Liu, Bo Yang Victor.
A right ideal (left ideal, two-sided ideal) is a non-empty language $L$ over an alphabet $\Sigma$ such that $L=L\Sigma^*$ ($L=\Sigma^*L$, $L=\Sigma^*L\Sigma^*$). Let $k=3$ for right ideals, 4 for left ideals and 5 for two-sided ideals. We show that there exist sequences ($L_n \mid n \ge k $) […]

Factoriality and the Pin-Reutenauer procedure

Almeida, J. ; Costa, J. C. ; Zeitoun, M..
We consider implicit signatures over finite semigroups determined by sets of pseudonatural numbers. We prove that, under relatively simple hypotheses on a pseudovariety V of semigroups, the finitely generated free algebra for the largest such signature is closed under taking factors within the free […]

Permutations of context-free, ET0L and indexed languages

Brough, Tara ; Ciobanu, Laura ; Elder, Murray ; Zetzsche, Georg.
For a language $L$, we consider its cyclic closure, and more generally the language $C^{k}(L)$, which consists of all words obtained by partitioning words from $L$ into $k$ factors and permuting them. We prove that the classes of ET0L and EDT0L languages are closed under the operators $C^k$. This […]

A note on a recent attempt to improve the Pin-Frankl bound

Gonze, François ; Jungers, Raphaël M. ; Trahtman, Avraham N..
We provide a counterexample to a lemma used in a recent tentative improvement of the Pin-Frankl bound for synchronizing automata. This example naturally leads us to formulate an open question, whose answer could fix the line of the proof, and improve the bound.

Parameterized complexity of synchronization and road coloring

Vorel, Vojtěch ; Roman, Adam.
First, we close the multi-parameter analysis of a canonical problem concerning short reset words (SYN) initiated by Fernau et al. (2013). Namely, we prove that the problem, parameterized by the number of states, does not admit a polynomial kernel unless the polynomial hierarchy collapses. Second, we […]

On the Hausdorff measure of regular ω-languages in Cantor space

Staiger, Ludwig.
This paper deals with the calculation of the Hausdorff measure of regular ω-languages, that is, subsets of the Cantor space definable by finite automata. Using methods for decomposing regular ω-languages into disjoint unions of parts of simple structure we derive two sufficient conditions under […]

Some undecidable problems about the trace-subshift associated to a Turing machine

Gajardo, Anahí ; Ollinger, Nicolas ; Torres-Avilés, Rodrigo.
We consider three problems related to dynamics of one-tape Turing machines: Existence of blocking configurations, surjectivity in the trace, and entropy positiveness. In order to address them, a reversible two-counter machine is simulated by a reversible Turing machine on the right side of its tape. […]

Classical Automata on Promise Problems

Geffert, Viliam ; Yakaryilmaz, Abuzer.
Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required […]

Canonical forms for free κ-semigroups

Costa, José Carlos.
The implicit signature κ consists of the multiplication and the (ω-1)-power. We describe a procedure to transform each κ-term over a finite alphabet A into a certain canonical form and show that different canonical forms have different interpretations over some finite semigroup. The procedure of […]

An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n+1) - p(n) ≤ 2

Leroy, Julien.
An S-adic characterization of minimal subshifts with first difference of complexity 1 ≤ p(n + 1) − p(n) ≤ 2 S. Ferenczi proved that any minimal subshift with first difference of complexity bounded by 2 is S-adic with Card(S) ≤ 3 27. In this paper, we improve this result by giving an S-adic […]

Derivatives of approximate regular expressions

Champarnaud, Jean-Marc ; Jeanne, Hadrien ; Mignot, Ludovic.
Our aim is to construct a finite automaton recognizing the set of words that are at a bounded distance from some word of a given regular language. We define new regular operators, the similarity operators, based on a generalization of the notion of distance and we introduce the family of regular […]

A stronger recognizability condition for two-dimensional languages

Anselmo, Marcella ; Madonia, Maria.
The paper presents a condition necessarily satisfied by (tiling system) recognizable two-dimensional languages. The new recognizability condition is compared with all the other ones known in the literature (namely three conditions), once they are put in a uniform setting: they are stated as bounds […]

Surjective cellular automata far from the Garden of Eden

Capobianco, Silvio ; Guillon, Pierre ; Kari, Jarkko.
One of the first and most famous results of cellular automata theory, Moore's Garden-of-Eden theorem has been proven to hold if and only if the underlying group possesses the measure-theoretic properties suggested by von Neumann to be the obstacle to the Banach-Tarski paradox. We show that several […]

The Cerný conjecture for automata respecting intervals of a directed graph

Grech, Mariusz ; Kisielewicz, Andrzej.
The Cerný's conjecture states that for every synchronizing automaton with n states there exists a reset word of length not exceeding (n - 1)2. We prove this conjecture for a class of automata preserving certain properties of intervals of a directed graph. Our result unifies and generalizes some […]

Automaticity of primitive words and irreducible polynomials

Lacroix, Anne ; Rampersad, Narad.
If L is a language, the automaticity function A_L(n) (resp. N_L(n)) of L counts the number of states of a smallest deterministic (resp. non-deterministic) finite automaton that accepts a language that agrees with L on all inputs of length at most n. We provide bounds for the automaticity of the […]

The Join of the Varieties of R-trivial and L-trivial Monoids via Combinatorics on Words

Kufleitner, Manfred ; Lauser, Alexander.
The join of two varieties is the smallest variety containing both. In finite semigroup theory, the varieties of R-trivial and L-trivial monoids are two of the most prominent classes of finite monoids. Their join is known to be decidable due to a result of Almeida and Azevedo. In this paper, we give […]

Monadic Second-Order Classes of Forests with a Monadic Second-Order 0-1 Law

Bell, Jason P. ; Burris, Stanley N. ; Yeats, Karen A..
Let T be a monadic-second order class of finite trees, and let T(x) be its (ordinary) generating function, with radius of convergence rho. If rho >= 1 then T has an explicit specification (without using recursion) in terms of the operations of union, sum, stack, and the multiset operators n and (>= […]

Digraph complexity measures and applications in formal language theory

Gruber, Hermann.
We investigate structural complexity measures on digraphs, in particular the cycle rank. This concept is intimately related to a classical topic in formal language theory, namely the star height of regular languages. We explore this connection, and obtain several new algorithmic insights regarding […]

Negative bases and automata

Frougny, Christiane ; Lai, Anna Chiara.
We study expansions in non-integer negative base -beta introduced by Ito and Sadahiro. Using countable automata associated with (-beta)-expansions, we characterize the case where the (-beta)-shift is a system of finite type. We prove that, if beta is a Pisot number, then the (-beta)-shift is a sofic […]

Cubefree words with many squares

Currie, James ; Rampersad, Narad.
We construct infinite cubefree binary words containing exponentially many distinct squares of length n. We also show that for every positive integer n, there is a cubefree binary square of length 2n.

Deciding whether the ordering is necessary in a Presburger formula

Choffrut, Christian ; Frigeri, Achille.
We characterize the relations which are first-order definable in the model of the group of integers with the constant 1. This allows us to show that given a relation defined by a first-order formula in this model enriched with the usual ordering, it is recursively decidable whether or not it is […]

On the asymptotic enumeration of accessible automata

Lebensztayn, Elcio.
We simplify the known formula for the asymptotic estimate of the number of deterministic and accessible automata with n states over a k-letter alphabet. The proof relies on the theory of Lagrange inversion applied in the context of generalized binomial series.

Directed figure codes are decidable

Kolarz, Michal ; Moczurad, Wlodzimierz.
Two-dimensional structures of various kinds can be viewed as generalizations of words. Codicity verification and the defect effect, important properties related to word codes, are studied also in this context. Unfortunately, both are lost in the case of two common structures, polyominoes and […]

On the length of shortest 2-collapsing words

Cherubini, Alessandra ; Kisielewicz, Andrzej ; Piochi, Brunetto.
Given a word w over a finite alphabet Sigma and a finite deterministic automaton A = < Q,Sigma,delta >, the inequality vertical bar delta(Q,w)vertical bar <= vertical bar Q vertical bar - k means that under the natural action of the word w the image of the state set Q is reduced by at least k […]

Interaction properties of relational periods

Halava, Vesa ; Harju, Tero ; Kärki, Tomi.
We consider relational periods where the relation is a compatibility relation on words induced by a relation on letters. We introduce three types of periods, namely global, external and local relational periods, and we compare their properties by proving variants of the theorem of Fine and Wilf for […]

Shifts with decidable language and non-computable entropy

Hertling, Peter ; Spandl, Christoph.
We consider subshifts of the full shift of all binary bi-infinite sequences. On the one hand, the topological entropy of any subshift with computably co-enumerable language is a right-computable real number between 0 and 1. We show that, on the other hand, any right-computable real number between 0 […]

Multidimensional cellular automata and generalization of Fekete's lemma

Capobianco, Silvio.
Fekete's lemma is a well-known combinatorial result on number sequences: we extend it to functions defined on d-tuples of integers. As an application of the new variant, we show that nonsurjective d-dimensional cellular automata are characterized by loss of arbitrarily much information on finite […]

Leftmost derivations of propagating scattered context grammars: a new proof

Masopust, Tomáš ; Techet, Jiří.
In 1973, V. Virkkunen proved that propagating scattered context grammars which use leftmost derivations are as powerful as context-sensitive grammars. This paper brings a significantly simplified proof of this result.

On the critical exponent of generalized Thue-Morse words

Massé, Alexandre B. ; Brlek, Srečko ; Glen, Amy ; Labbé, Sébastien.
For certain generalized Thue-Morse words t, we compute the critical exponent, i.e., the supremum of the set of rational numbers that are exponents of powers in t, and determine exactly the occurrences of powers realizing it.

Latin square Thue-Morse sequences are overlap-free

Tompkins, C. Robinson.
We define a morphism based upon a Latin square that generalizes the Thue-Morse morphism. We prove that fixed points of this morphism are overlap-free sequences, generalizing results of Allouche - Shallit and Frid.