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.

We examine inkdots placed on the input string as a way of providing advice to finite automata, and establish the relations between this model and the previously studied models of advised finite automata. The existence of an infinite hierarchy of classes of languages that can be recognized with the […]

We discuss cellular automata over arbitrary finitely generated groups. We call a cellular automaton post-surjective if for any pair of asymptotic configurations, every pre-image of one is asymptotic to a pre-image of the other. The well known dual concept is pre-injectivity: a cellular automaton […]

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 […]

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 […]

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 $) […]

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 […]

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 […]

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. […]

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 […]

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 […]

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.

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 […]

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 (>= […]

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 […]

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.

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 […]

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.

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 […]

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 […]

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 […]

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 […]

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 […]

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.

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.

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.