Discrete Mathematics & Theoretical Computer Science |

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.

Editors: Henning Fernau ; Christoph Haase ; Juhani Eero Urho Karhumäki ; Andreas Maletti ; Anca Muscholl ; Daniel Reidenbach ; Howard Straubing ; Val Tannen

We generalize the familiar notion of periodicity in sequences to a new kindof pseudoperiodicity, and we prove some basic results about it. We revisit theresults of a 2012 paper of Shevelev and reprove his results in a simpler andmore unified manner, and provide a complete answer to one of his previouslyunresolved questions. We consider finding words with specific pseudoperiod andhaving the smallest possible critical exponent. Finally, we consider theproblem of determining whether a finite word is pseudoperiodic of a given size,and show that it is NP-complete.

We say that a language $L$ is \emph{constantly growing} if there is aconstant $c$ such that for every word $u\in L$ there is a word $v\in L$ with$\vert u\vert<\vert v\vert\leq c+\vert u\vert$. We say that a language $L$ is\emph{geometrically growing} if there is a constant $c$ such that for everyword $u\in L$ there is a word $v\in L$ with $\vert u\vert<\vert v\vert\leqc\vert u\vert$. Given two infinite languages $L_1,L_2$, we say that $L_1$\emph{dissects} $L_2$ if $\vert L_2\setminus L_1\vert=\infty$ and $\vertL_1\cap L_2\vert=\infty$. In 2013, it was shown that for every constantlygrowing language $L$ there is a regular language $R$ such that $R$ dissects$L$. In the current article we show how to dissect a geometrically growinglanguage by a homomorphic image of intersection of two context-free languages. Consider three alphabets $\Gamma$, $\Sigma$, and $\Theta$ such that $\vert\Sigma\vert=1$ and $\vert \Theta\vert=4$. We prove that there are context-freelanguages $M_1,M_2\subseteq \Theta^*$, an erasing alphabetical homomorphism$\pi:\Theta^*\rightarrow \Sigma^*$, and a nonerasing alphabetical homomorphism$\varphi : \Gamma^*\rightarrow \Sigma^*$ such that: If $L\subseteq \Gamma^*$ isa geometrically growing language then there is a regular language $R\subseteq\Theta^*$ such that $\varphi^{-1}\left(\pi\left(R\cap M_1\capM_2\right)\right)$ dissects the language $L$.

Regular synchronization languages can be used to define rational relations offinite words, and to characterize subclasses of rational relations, likeautomatic or recognizable relations. We provide a systematic study of thedecidability of uniformization and definability problems for subclasses ofrational relations defined in terms of such synchronization languages. Werephrase known results in this setting and complete the picture by addingseveral new decidability and undecidability results.

The $n$th term of an automatic sequence is the output of a deterministicfinite automaton fed with the representation of $n$ in a suitable numerationsystem. In this paper, instead of considering automatic sequences built on anumeration system with a regular numeration language, we consider those builton languages associated with trees having periodic labeled signatures and, inparticular, rational base numeration systems. We obtain two maincharacterizations of these sequences. The first one is concerned with $r$-blocksubstitutions where $r$ morphisms are applied periodically. In particular, weprovide examples of such sequences that are not morphic. The secondcharacterization involves the factors, or subtrees of finite height, of thetree associated with the numeration system and decorated by the terms of thesequence.

This paper studies three classes of cellular automata from a computational point of view: freezing cellular automata where the state of a cell can only decrease according to some order on states, cellular automata where each cell only makes a bounded number of state changes in any orbit, and finally cellular automata where each orbit converges to some fixed point. Many examples studied in the literature fit into these definitions, in particular the works on cristal growth started by S. Ulam in the 60s. The central question addressed here is how the computational power and computational hardness of basic properties is affected by the constraints of convergence, bounded number of change, or local decreasing of states in each cell. By studying various benchmark problems (short-term prediction, long term reachability, limits) and considering various complexity measures and scales (LOGSPACE vs. PTIME, communication complexity, Turing computability and arithmetical hierarchy) we give a rich and nuanced answer: the overall computational complexity of such cellular automata depends on the class considered (among the three above), the dimension, and the precise problem studied. In particular, we show that all settings can achieve universality in the sense of Blondel-Delvenne-K\r{u}rka, although short term predictability varies from NLOGSPACE to P-complete. Besides, the computability of limit configurations starting from computable initial configurations separates bounded-change from […]

We show that, with the exception of the words $a^2ba^2$ and $b^2ab^2$, all(finite or infinite) binary patterns in the Prouhet-Thue-Morse sequence canactually be found in that sequence as segments (up to exchange of letters inthe infinite case). This result was previously attributed to unpublished workby D. Guaiana and may also be derived from publications of A. Shur onlyavailable in Russian. We also identify the (finitely many) finite binarypatterns that appear non trivially, in the sense that they are obtained byapplying an endomorphism that does not map the set of all segments of thesequence into itself.

We consider weighted tree automata (wta) over strong bimonoids and theirinitial algebra semantics and their run semantics. There are wta for whichthese semantics are different; however, for bottom-up deterministic wta and forwta over semirings, the difference vanishes. A wta is crisp-deterministic if itis bottom-up deterministic and each transition is weighted by one of the unitelements of the strong bimonoid. We prove that the class of weighted treelanguages recognized by crisp-deterministic wta is the same as the class ofrecognizable step mappings. Moreover, we investigate the following twocrisp-determinization problems: for a given wta ${\cal A}$, (a) does thereexist a crisp-deterministic wta which computes the initial algebra semantics of${\cal A}$ and (b) does there exist a crisp-deterministic wta which computesthe run semantics of ${\cal A}$? We show that the finiteness of the Nerodealgebra ${\cal N}({\cal A})$ of ${\cal A}$ implies a positive answer for (a),and that the finite order property of ${\cal A}$ implies a positive answer for(b). We show a sufficient condition which guarantees the finiteness of ${\calN}({\cal A})$ and a sufficient condition which guarantees the finite orderproperty of ${\cal A}$. Also, we provide an algorithm for the construction ofthe crisp-deterministic wta according to (a) if ${\cal N}({\cal A})$ is finite,and similarly for (b) if ${\cal A}$ has finite order property. We prove that itis undecidable whether an arbitrary wta ${\cal A}$ is […]

This paper introduces a notion of equivalence for higher-dimensionalautomata, called weak equivalence. Weak equivalence focuses mainly on atraditional trace language and a new homology language, which captures theoverall independence structure of an HDA. It is shown that weak equivalence iscompatible with both the tensor product and the coproduct of HDAs and that,under certain conditions, HDAs may be reduced to weakly equivalent smaller onesby merging and collapsing cubes.

We introduce MSO graph storage types, and call a storage type MSO-expressibleif it is isomorphic to some MSO graph storage type. An MSO graph storage typehas MSO-definable sets of graphs as storage configurations and as storagetransformations. We consider sequential automata with MSO graph storage andassociate with each such automaton a string language (in the usual way) and agraph language; a graph is accepted by the automaton if it represents a correctsequence of storage configurations for a given input string. For each MSO graphstorage type, we define an MSO logic which is a subset of the usual MSO logicon graphs. We prove a Büchi-Elgot-Trakhtenbrot theorem, both for the stringcase and the graph case. Moreover, we prove that (i) each MSO graphtransduction can be used as storage transformation in an MSO graph storagetype, (ii) every automatic storage type is MSO-expressible, and (iii) thepushdown operator on storage types preserves the property ofMSO-expressibility. Thus, the iterated pushdown storage types areMSO-expressible.

We consider nondeterministic higher-order recursion schemes as recognizers of languages of finite words or finite trees. We propose a type system that allows to solve the simultaneous-unboundedness problem (SUP) for schemes, which asks, given a set of letters A and a scheme G, whether it is the case that for every number n the scheme accepts a word (a tree) in which every letter from A appears at least n times. Using this type system we prove that SUP is (m-1)-EXPTIME-complete for word-recognizing schemes of order m, and m-EXPTIME-complete for tree-recognizing schemes of order m. Moreover, we establish the reflection property for SUP: out of an input scheme G one can create its enhanced version that recognizes the same language but is aware of the answer to SUP.

A formal inverse of a given automatic sequence (the sequence of coefficientsof the composition inverse of its associated formal power series) is alsoautomatic. The comparison of properties of the original sequence and its formalinverse is an interesting problem. Such an analysis has been done before forthe Thue{Morse sequence. In this paper, we describe arithmetic properties offormal inverses of the generalized Thue-Morse sequences and formal inverses oftwo modifications of the Rudin{Shapiro sequence. In each case, we give therecurrence relations and the automaton, then we analyze the lengths of stringsof consecutive identical letters as well as the frequencies of letters. We alsocompare the obtained results with the original sequences.

Let $S_{a,b}$ denote the sequence of leading digits of $a^n$ in base $b$. Itis well known that if $a$ is not a rational power of $b$, then the sequence$S_{a,b}$ satisfies Benford's Law; that is, digit $d$ occurs in $S_{a,b}$ withfrequency $\log_{b}(1+1/d)$, for $d=1,2,\dots,b-1$. In this paper, we investigate the \emph{complexity} of such sequences. Wefocus mainly on the \emph{block complexity}, $p_{a,b}(n)$, defined as thenumber of distinct blocks of length $n$ appearing in $S_{a,b}$. In our mainresult we determine $p_{a,b}(n)$ for all squarefree bases $b\ge 5$ and allrational numbers $a>0$ that are not integral powers of $b$. In particular, weshow that, for all such pairs $(a,b)$, the complexity function $p_{a,b}(n)$ is\emph{affine}, i.e., satisfies $p_{a,b}(n)=c_{a,b} n + d_{a,b}$ for all$n\ge1$, with coefficients $c_{a,b}\ge1$ and $d_{a,b}\ge0$, given explicitly interms of $a$ and $b$. We also show that the requirement that $b$ be squarefreecannot be dropped: If $b$ is not squarefree, then there exist integers $a$ with$1

## The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints

It is known that 2-state binary and 3-state unary probabilistic finiteautomata and 2-state unary quantum finite automata recognize uncountably manylanguages with cutpoints. These results have been obtained by associating eachrecognized language with a cutpoint and then by using the fact that there areuncountably many cutpoints. In this note, we prove the same results for fixedcutpoints: each recognized language is associated with an automaton (i.e.,algorithm), and the proofs use the fact that there are uncountably manyautomata. For each case, we present a new construction.

## New tools for state complexity

A monster is an automaton in which every function from states to states isrepresented by at least one letter. A modifier is a set of functions allowingone to transform a set of automata into one automaton. We revisit some languagetransformation algorithms in terms of modifier and monster. These newtheoretical concepts allow one to find easily some state complexities. Weillustrate this by retrieving the state complexity of the Star of Intersectionand the one of the Square root operation.

## A Characterization of Morphic Words with Polynomial Growth

A morphic word is obtained by iterating a morphism to generate an infiniteword, and then applying a coding. We characterize morphic words with polynomialgrowth in terms of a new type of infinite word called a $\textit{zigzag word}$.A zigzag word is represented by an initial string, followed by a finite list ofterms, each of which repeats for each $n \geq 1$ in one of three ways: it growsforward [$t(1)\ t(2)\ \dotsm\ t(n)]$, backward [$t(n)\ \dotsm\ t(2)\ t(1)$], orjust occurs once [$t$]. Each term can recursively contain subterms with theirown forward and backward repetitions. We show that an infinite word is morphicwith growth $\Theta(n^k)$ iff it is a zigzag word of depth $k$. As corollaries,we obtain that the morphic words with growth $O(n)$ are exactly the ultimatelyperiodic words, and the morphic words with growth $O(n^2)$ are exactly themultilinear words.

## New results on classical and quantum counter automata

We show that one-way quantum one-counter automaton with zero-error is morepowerful than its probabilistic counterpart on promise problems. Then, weobtain a similar separation result between Las Vegas one-way probabilisticone-counter automaton and one-way deterministic one-counter automaton. We also obtain new results on classical counter automata regarding languagerecognition. It was conjectured that one-way probabilistic one blind-counterautomata cannot recognize Kleene closure of equality language [A. Yakaryilmaz:Superiority of one-way and realtime quantum machines. RAIRO - Theor. Inf. andApplic. 46(4): 615-641 (2012)]. We show that this conjecture is false, and alsoshow several separation results for blind/non-blind counter automata.

## On the insertion of n-powers

In algebraic terms, the insertion of $n$-powers in words may be modelled atthe language level by considering the pseudovariety of ordered monoids definedby the inequality $1\le x^n$. We compare this pseudovariety with several othernatural pseudovarieties of ordered monoids and of monoids associated with theBurnside pseudovariety of groups defined by the identity $x^n=1$. Inparticular, we are interested in determining the pseudovariety of monoids thatit generates, which can be viewed as the problem of determining the Booleanclosure of the class of regular languages closed under $n$-power insertions. Weexhibit a simple upper bound and show that it satisfies all pseudoidentitieswhich are provable from $1\le x^n$ in which both sides are regular elementswith respect to the upper bound.

## Decision Problems for Subclasses of Rational Relations over Finite and Infinite Words

We consider decision problems for relations over finite and infinite wordsdefined by finite automata. We prove that the equivalence problem for binarydeterministic rational relations over infinite words is undecidable in contrastto the case of finite words, where the problem is decidable. Furthermore, weshow that it is decidable in doubly exponential time for an automatic relationover infinite words whether it is a recognizable relation. We also revisit thisproblem in the context of finite words and improve the complexity of thedecision procedure to single exponential time. The procedure is based on apolynomial time regularity test for deterministic visibly pushdown automata,which is a result of independent interest.

## IMP with exceptions over decorated logic

In this paper, we facilitate the reasoning about impure programming languages, by annotating terms with “decorations”that describe what computational (side) effect evaluation of a term may involve. In a point-free categorical language,called the “decorated logic”, we formalize the mutable state and the exception effects first separately, exploiting anice duality between them, and then combined. The combined decorated logic is used as the target language forthe denotational semantics of the IMP+Exc imperative programming language, and allows us to prove equivalencesbetween programs written in IMP+Exc. The combined logic is encoded in Coq, and this encoding is used to certifysome program equivalence proofs.

## Weighted Regular Tree Grammars with Storage

We introduce weighted regular tree grammars with storage as combination of(a) regular tree grammars with storage and (b) weighted tree automata overmultioperator monoids. Each weighted regular tree grammar with storagegenerates a weighted tree language, which is a mapping from the set of trees tothe multioperator monoid. We prove that, for multioperator monoids canonicallyassociated to particular strong bi-monoids, the support of the generatedweighted tree languages can be generated by (unweighted) regular tree grammarswith storage. We characterize the class of all generated weighted treelanguages by the composition of three basic concepts. Moreover, we proveresults on the elimination of chain rules and of finite storage types, and wecharacterize weighted regular tree grammars with storage by a new weightedMSO-logic.

## Inkdots as advice for finite automata

We examine inkdots placed on the input string as a way of providing advice tofinite automata, and establish the relations between this model and thepreviously studied models of advised finite automata. The existence of aninfinite hierarchy of classes of languages that can be recognized with the helpof increasing numbers of inkdots as advice is shown. The effects of differentforms of advice on the succinctness of the advised machines are examined. Wealso study randomly placed inkdots as advice to probabilistic finite automata,and demonstrate the superiority of this model over its deterministic version.Even very slowly growing amounts of space can become a resource of meaningfuluse if the underlying advised model is extended with access to secondarymemory, while it is famously known that such small amounts of space are notuseful for unadvised one-way Turing machines.

## Post-surjectivity and balancedness of cellular automata over groups

We discuss cellular automata over arbitrary finitely generated groups. Wecall a cellular automaton post-surjective if for any pair of asymptoticconfigurations, every pre-image of one is asymptotic to a pre-image of theother. The well known dual concept is pre-injectivity: a cellular automaton ispre-injective if distinct asymptotic configurations have distinct images. Weprove that pre-injective, post-surjective cellular automata are reversible.Moreover, on sofic groups, post-surjectivity alone implies reversibility. Wealso prove that reversible cellular automata over arbitrary groups arebalanced, that is, they preserve the uniform measure on the configurationspace.

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

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 w. A word is k-collapsing if it is k-compressing foreach k-compressible automaton, and it is k-synchronizing if it is k-compressing for all k-compressible automata withk+1 states. We compute a set W of short words such that each 3-compressible automaton on a two-letter alphabetis 3-compressed at least by a word in W. Then we construct a shortest common superstring of the words in W and,with a further refinement, we obtain a 3-collapsing word of length 53. Moreover, as previously announced, we showthat the shortest 3-synchronizing word is not 3-collapsing, illustrating the new bounds 34 ≤ c(2, 3) ≤ 53 for the length c(2, 3) of the shortest 3-collapsing word on a two-letter alphabet.

## Decidability of multiset, set and numerically decipherable directed figure codes

Codes with various kinds of decipherability, weaker than the usual uniquedecipherability, have been studied since multiset decipherability wasintroduced in mid-1980s. We consider decipherability of directed figure codes,where directed figures are defined as labelled polyominoes with designatedstart and end points, equipped with catenation operation that may use a mergingfunction to resolve possible conflicts. This is one of possible extensionsgeneralizing words and variable-length codes to planar structures. Here,verification whether a given set is a code is no longer decidable in general.We study the decidability status of figure codes depending on catenation type(with or without a merging function), decipherability kind (unique, multiset,set or numeric) and code geometry (several classes determined by relativepositions of start and end points of figures). We give decidability orundecidability proofs in all but two cases that remain open.

## Most Complex Regular Ideal Languages

A right ideal (left ideal, two-sided ideal) is a non-empty language $L$ overan 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 fortwo-sided ideals. We show that there exist sequences ($L_n \mid n \ge k $) ofright, left, and two-sided regular ideals, where $L_n$ has quotient complexity(state complexity) $n$, such that $L_n$ is most complex in its class under thefollowing measures of complexity: the size of the syntactic semigroup, thequotient complexities of the left quotients of $L_n$, the number of atoms(intersections of complemented and uncomplemented left quotients), the quotientcomplexities of the atoms, and the quotient complexities of reversal, star,product (concatenation), and all binary boolean operations. In that sense,these ideals are "most complex" languages in their classes, or "universalwitnesses" to the complexity of the various operations.

## Permutations of context-free, ET0L and indexed languages

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 both sharpens and generalises Brandstädt's result that if $L$ is context-free then $C^{k}(L)$ is context-sensitive and not context-free in general for $k \geq 3$. We also show that the cyclic closure of an indexed language is indexed.

## Factoriality and the Pin-Reutenauer procedure

We consider implicit signatures over finite semigroups determined by sets ofpseudonatural numbers. We prove that, under relatively simple hypotheses on apseudovariety V of semigroups, the finitely generated free algebra for thelargest such signature is closed under taking factors within the free pro-Vsemigroup on the same set of generators. Furthermore, we show that the naturalanalogue of the Pin-Reutenauer descriptive procedure for the closure of arational language in the free group with respect to the profinite topologyholds for the pseudovariety of all finite semigroups. As an application, weestablish that a pseudovariety enjoys this property if and only if it is full.

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

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. By completing the machine in different ways, we prove that none of the former problems is decidable. In particular, the problems about blocking configurations and entropy are shown to be undecidable for the class of reversible Turing machines.

## Classical Automata on Promise Problems

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 by corresponding one-way deterministic automata cannot be bounded by a constant. For this family, we show that even two-way nondeterminism does not help to save a single state. By comparing this with the corresponding state complexity of alternating machines, we then get a tight exponential gap between two-way nondeterministic and one-way alternating automata solving unary promise problems. Second, despite of the existing quadratic gap between Las Vegas realtime probabilistic automata and one-way deterministic automata for language recognition, we show that, by turning to promise problems, the tight gap becomes exponential. Last, we show that the situation is different for one-way probabilistic automata with two-sided bounded-error. We present a family of unary promise problems that is very easy for these machines; solvable with only two states, but the number of states in two-way alternating or any simpler automata is not limited by a constant. Moreover, we show that one-way bounded-error probabilistic automata can solve promise problems not solvable at all by any other classical model.

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

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 which ω-languages with a closure definable by a finite automaton have the same Hausdorff measure as this closure. The first of these condition is related to the homogeneity of the local behaviour of the Hausdorff dimension of the underlying set, and the other with a certain topological density of the set in its closure.

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

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

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 consider a related canonical problem concerning synchronizing road colorings (SRCP). Here we give a similar complete multi-parameter analysis. Namely, we show that the problem, parameterized by the number of states, admits a polynomial kernel and we close the previous research of restrictions to particular values of both the alphabet size and the maximum length of a reset word.

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

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 characterization of these subshifts with a set S of 5 morphisms, solving by this way the S-adic conjecture for this particular case.

## Canonical forms for free κ-semigroups

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 construction of the canonical forms, which is inspired in McCammond\textquoterights normal form algorithm for ω-terms interpreted over the pseudovariety A of all finite aperiodic semigroups, consists in applying elementary changes determined by an elementary set Σ of pseudoidentities. As an application, we deduce that the variety of κ-semigroups generated by the pseudovariety S of all finite semigroups is defined by the set Σ and that the free κ-semigroup generated by the alphabet A in that variety has decidable word problem. Furthermore, we show that each ω-term has a unique ω-term in canonical form with the same value over A. In particular, the canonical forms provide new, simpler, representatives for ω-terms interpreted over that pseudovariety.

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

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 earlier results obtained by other authors.

## Surjective cellular automata far from the Garden of Eden

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 other results from the literature, already known to characterize surjective cellular automata in dimension d, hold precisely when the Garden-of-Eden theorem does. We focus in particular on the balancedness theorem, which has been proven by Bartholdi to fail on amenable groups, and we measure the amount of such failure.

## Derivatives of approximate regular expressions

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 expressions extended to similarity operators, that we call AREs (Approximate Regular Expressions). We set formulae to compute the Brzozowski derivatives and the Antimirov derivatives of an ARE, which allows us to give a solution to the ARE membership problem and to provide the construction of two recognizers for the language denoted by an ARE. As far as we know, the family of approximative regular expressions is introduced for the first time in this paper. Classical approximate regular expression matching algorithms are approximate matching algorithms on regular expressions. Our approach is rather to process an exact matching on approximate regular expressions.

## A stronger recognizability condition for two-dimensional languages

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 on the growth of some complexity functions defined for two-dimensional languages. The gaps between such functions are analyzed and examples are shown that asymptotically separate them. Finally the new recognizability condition results to be the strongest one, while the remaining ones are its particular cases. The problem of deciding whether a two-dimensional language is recognizable is here related to the one of estimating the minimal size of finite automata recognizing a sequence of (one-dimensional) string languages.

## Automaticity of primitive words and irreducible polynomials

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 language of primitive words and the language of unbordered words over a k-letter alphabet. We also give a bound for the automaticity of the language of base-b representations of the irreducible polynomials over a finite field. This latter result is analogous to a result of Shallit concerning the base-k representations of the set of prime numbers.

## Digraph complexity measures and applications in formal language theory

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 both cycle rank and star height. Among other results, we show that computing the cycle rank is NP-complete, even for sparse digraphs of maximum outdegree 2. Notwithstanding, we provide both a polynomial-time approximation algorithm and an exponential-time exact algorithm for this problem. The former algorithm yields an O((log n)^(3/2))- approximation in polynomial time, whereas the latter yields the optimum solution, and runs in time and space O*(1.9129^n) on digraphs of maximum outdegree at most two. Regarding the star height problem, we identify a subclass of the regular languages for which we can precisely determine the computational complexity of the star height problem. Namely, the star height problem for bideterministic languages is NP-complete, and this holds already for binary alphabets. Then we translate the algorithmic results concerning cycle rank to the bideterministic star height problem, thus giving a polynomial-time approximation as well as a reasonably fast exact exponential algorithm for bideterministic star height.

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

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 a new proof for Almeida and Azevedo's effective characterization of the join of R-trivial and L-trivial monoids. This characterization is a single identity of omega-terms using three variables.

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

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 (>= n). Using this, one has an explicit expression for T(x) in terms of the initial functions x and x . (1 - x(n))(-1), the operations of addition and multiplication, and the Polya exponentiation operators E-n, E-(>= n). Let F be a monadic-second order class of finite forests, and let F (x) = Sigma(n) integral(n)x(n) be its (ordinary) generating function. Suppose F is closed under extraction of component trees and sums of forests. Using the above-mentioned structure theory for the class T of trees in F, Compton's theory of 0-1 laws, and a significantly strengthened version of 2003 results of Bell and Burris on generating functions, we show that F has a monadic second-order 0-1 law iff the radius of convergence of F (x) is 1 iff the radius of convergence of T (x) is >= 1.

## Negative bases and automata

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 system. In that case, addition (and more generally normalization on any alphabet) is realizable by a finite transducer. We then give an on-line algorithm for the conversion from positive base beta to negative base -beta. When beta is a Pisot number, the conversion can be realized by a finite on-line transducer.

## Deciding whether the ordering is necessary in a Presburger formula

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 first-order definable without the ordering.

## On the asymptotic enumeration of accessible automata

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.

## Cubefree words with many squares

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.

## Directed figure codes are decidable

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 figures. We consider directed figures defined as labelled polyominoes with designated start and end points, equipped with catenation operation that uses a merging function to resolve possible conflicts. We prove that in this setting verification whether a given finite set of directed figures is a code is decidable and we give a constructive algorithm. We also clarify the status of the defect effect for directed figures.

## On the length of shortest 2-collapsing words

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 states. The word w is k-collapsing (k-synchronizing) if this inequality holds for any deterministic finite automaton ( with k + 1 states) that satisfies such an inequality for at least one word. We prove that for each alphabet Sigma there is a 2-collapsing word whose length is vertical bar Sigma vertical bar(3)+6 vertical bar Sigma vertical bar(2)+5 vertical bar Sigma vertical bar/2. Then we produce shorter 2-collapsing and 2-synchronizing words over alphabets of 4 and 5 letters.

## Interaction properties of relational periods

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 these periods.

## Shifts with decidable language and non-computable entropy

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 and 1, whether computable or not, is the entropy of some subshift with even polynomial time decidable language. In addition, we show that computability of the entropy of a subshift does not imply any kind of computability of the language of the subshift

## Multidimensional cellular automata and generalization of Fekete's lemma

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 supports, at a growth rate greater than that of the support's boundary determined by the automaton's neighbourhood index.

## Leftmost derivations of propagating scattered context grammars: a new proof

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

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

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.