Two deterministic finite automata are almost equivalent if they disagree in acceptance only for finitely many inputs. An automaton A is hyper-minimized if no automaton with fewer states is almost equivalent to A. A regular language L is canonical if the minimal automaton accepting L is hyper-minimized. The asymptotic state complexity s∗(L) of a regular language L is the number of states of a hyper-minimized automaton for a language finitely different from L. In this paper we show that: (1) the class of canonical regular languages is not closed under: intersection, union, concatenation, Kleene closure, difference, symmetric difference, reversal, homomorphism, and inverse homomorphism; (2) for any regular languages L1 and L2 the asymptotic state complexity of their sum L1 ∪ L2, intersection L1 ∩ L2, difference L1 − L2, and symmetric difference L1 ⊕ L2 can be bounded by s∗(L1)·s∗(L2). This bound is tight in binary case and in unary case can be met in infinitely many cases. (3) For any regular language L the asymptotic state complexity of its reversal LR can be bounded by 2s∗(L). This bound is tight in binary case. (4) The asymptotic state complexity of Kleene closure and concatenation cannot be bounded. Namely, for every k ≥ 3, there exist languages K, L, and M such that s∗(K) = s∗(L) = s∗(M) = 1 and s∗(K∗) = s∗(L·M) = k. These are answers to open problems formulated by Badr et al. [RAIRO-Theor. Inf. Appl.43 (2009) 69–94].

The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension $k\times k$ matrices with integer or rational entries is studied. We call these two problems $\sf IMP_k$ and $\sf MPOW_k$, respectively, for short. We prove that: (i) For $k\geq2$, $\sf IMP_k$ does not belong to ${\rm TC}^0$, unless ${\rm TC}^0={\rm NC}^1$.newline (ii) For stochastic matrices : $\sf IMP_2$ belongs to ${\rm TC}^0$ while, for $k\geq3$, $\sf IMP_k$ does not belong to ${\rm TC}^0$, unless ${\rm TC}^0={\rm NC}^1$. (iii) For any k, $\sf MPOW_k$ belongs to ${\rm TC}^0$.

We display a complexity notion based on the syntax of a tree series which yields two distinct hierarchies, one within the class of recognizable tree series and another one in the class of non-recognizable tree series.

We address the problem to know whether the relation induced by a one-rulelength-preserving rewrite system is rational. We partially answer to a conjecture of ÉricLilin who conjectured in 1991 that a one-rule length-preserving rewrite system is arational transduction if and only if the left-hand side u and theright-hand side v of the rule of the system are not quasi-conjugate orare equal, that means if u and v are distinct, there donot exist words x, y and z such thatu = xyz and v = zyx.We prove the only if part of this conjecture and identify two non trivialcases where the if part is satisfied.

We investigate the finite repetition threshold for k-letter alphabets, k ≥ 4, that is the smallest number r for which there exists an infinite r+-free word containing a finite number of r-powers. We show that there exists an infinite Dejean word on a 4-letter alphabet (i.e. a word without factors of exponent more than 7/5 ) containing only two 7/5 -powers. For a 5-letter alphabet, we show that there exists an infinite Dejean word containing only 60 5/4 -powers, and we conjecture that this number can be lowered to 45. Finally we show that the finite repetition threshold for k letters is equal to the repetition threshold for k letters, for every k ≥ 6.

A language L ⊆A* is literally idempotent in case that ua2v ∈ L if and only if uav ∈ L, for each u,v ∈ A*, a ∈ A. Varieties of literally idempotent languages result naturally by taking all literally idempotent languages in a classical (positive) variety or by considering a certain closure operator on classes of languages. We initiate the systematic study of such varieties. Various classes of literally idempotent languages can be characterized using syntactic methods. A starting example is the class of all finite unions of $B^*_1 B^*_2\dots B^*_k$ where B1,...,Bk are subsets of a given alphabet A.

There exists a bijection between one-stack sortable permutations (permutations which avoid the pattern (231)) and rooted plane trees. We define an edit distance between permutations which is consistent with the standard edit distance between trees. This one-to-one correspondence yields a polynomial algorithm for the subpermutation problem for (231) pattern-avoiding permutations.Moreover, we obtain the generating function of the edit distance between ordered unlabeled trees and some special ones.For the general case we show that the mean edit distance between a rooted plane tree and all other rooted plane trees is at least n/ln(n).Some results can be extended to labeled trees considering coloredDyck paths or, equivalently, colored one-stack sortable permutations.

We study the palindromic complexity of infinite words uβ, the fixed points of the substitution over a binary alphabet, φ(0) = 0a1, φ(1) = 0b1, with a - 1 ≥ b ≥ 1, which are canonically associated with quadratic non-simple Parry numbers β.

The recently introduced model of transducing by observing is compared with traditionalmodels for computing transductions on the one hand and the recently introduced restartingtransducers on the other hand. Most noteworthy, transducing observer systems withlength-reducing rules are almost equivalent to RRWW-transducers. With painter rules weobtain a larger class of relations that additionally includes nearly all rationalrelations.

In secret sharing, different access structures have different difficulty degrees for acceding to the secret. We give a numerical measure of how easy or how difficult is to recover the secret, depending only on the structure itself and not on the particular scheme used for realizing it. We derive some consequences.

A deterministic automaton recognizing a givenω-regular languageis constructed from an ω-regular expressionwith the help of derivatives.The construction is related to Safra's algorithm, in about the same way as the classicalderivative method is related to the subset construction.

We prove two cases of a strong version of Dejean's conjecture involving extremal letter frequencies. The results are that there exist an infinite $\left({\frac{5}{4}^+}\right)$-free word over a 5 letter alphabet with letter frequency $\frac{1}{6}$ and an infinite $\left({\frac{6}{5}^+}\right)$-free word over a 6 letter alphabet with letter frequency $\frac{1}{5}$.

In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [IEEE Commun. Lett. 3 (1999) 245–247]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decoding by this method is defined. It is proved also that this transducer is minimal. Here we consider the number of states of such a transducer, related to some features of the considered prefix code X. We find some bounds of such a number of states in relation with different notions of “size” of X. In particular, we give an exact formula for the number of states of transducers associated to maximal prefix codes. We moreover consider two special cases of codes: maximal uniform codes and a class of codes, that we name string-codes. We show that they represent, for maximal codes, the extreme cases with regard to the number of states in terms of different sizes. Moreover we prove that prefix codes corresponding to isomorphic trees have transducers that are isomorphic as unlabeled graphs.

Communication complexity of two-party (multiparty)protocols has established itself as a successful method for proving lower bounds on the complexity of concrete problems for numerous computing models. While the relations between communication complexity and oblivious, semilective computations are usually transparent and the main difficulty is reduced to proving nontrivial lower bounds on the communication complexity of given computing problems, the situation essentially changes, if one considers non-oblivious or multilective computations. The known lower bound proofs for such computations are far from being transparent and the crucial ideas of these proofs are often hidden behind some nontrivial combinatorial analysis. The aim of this paper is to create a general framework for the use of two-party communication protocols for lower bound proofs on multilective computations. The result of this creation is not only a transparent presentation of some known lower bounds on the complexity of multilective computations on distinct computing models, but also the derivation of new nontrivial lower bounds on multilective VLSI circuits and multilective planar Boolean circuits.In the case of VLSI circuits we obtain a generalization ofThompson's lower bounds on AT 2 complexity for multilective circuits.The Ω(n 2) lower bound on the number of gates of any k-multilectiveplanar Boolean circuit computing a specific Boolean function of n variablesis established for $k<\frac{1}{2} \log_2 n$ . Another advantage of this framework is that it provides lower bounds for a lot of concrete functions. This contrasts to the typical papersdevoted to lower bound proofs, where one establishes a lower bound for one or a few specific functions.

We study hybrid systems with strong resets from the perspective of formal language theory. We define a notion of hybrid regular expression and prove a Kleene-like theorem for hybrid systems. We also prove the closure of these systems under determinisation and complementation. Finally, we prove that the reachability problem is undecidable for synchronized products of hybrid systems.

We study infinite words u over an alphabet $\mathcal{A}$ satisfying the property $\mathcal{P} :~\mathcal{P}(n)+\mathcal{P}(n+1) = 1+ \#\mathcal{A}\ {\rm for\ any}\ n \in\mathbb{N}$ , where $\mathcal{P}(n)$ denotes the number ofpalindromic factors of length n occurring in the language of u.We study also infinite words satisfying a strongerproperty $\mathcal{PE}$ : every palindrome of u has exactly one palindromic extension in u. For binary words, the properties $\mathcal{P}$ and $\mathcal{PE}$ coincide and these properties characterize Sturmian words, i.e.,words with the complexity C(n) = n + 1 for any $n \in \mathbb{N}$ . In this paper, we focus on ternary infinite wordswith the language closed under reversal. For such words u,we prove that if C(n) = 2n + 1 for any $n \in \mathbb{N}$ ,then u satisfies the property $\mathcal{P}$ andmoreover u is rich in palindromes. Also a sufficient condition for the property $\mathcal{PE}$ is given.We construct a word demonstrating that $\mathcal{P}$ on a ternaryalphabet does not imply $\mathcal{PE}$ .

We consider a recently defined notion of k-abelian equivalence of words by concentrating on avoidance problems. The equivalence class of a word depends on the numbers of occurrences of different factors of length k for a fixed natural number k and the prefix of the word. We have shown earlier that over a ternary alphabet k-abelian squares cannot be avoided in pure morphic words for any natural number k. Nevertheless, computational experiments support the conjecture that even 3-abelian squares can be avoided over ternary alphabets. In this paper we establish the first avoidance result showing that by choosing k to be large enough we have an infinite k-abelian square-free word over three letter alphabet. In addition, this word can be obtained as a morphic image of a pure morphic word.

Laminations are classic sets of disjoint and non-self-crossing curves on surfaces. Lamination languages are languages of two-way infinite words which code laminations by using associated labeled embedded graphs, and which are subshifts. Here, we characterize the possible exact affine factor complexities of these languages through bouquets of circles, i.e. graphs made of one vertex, as representative coding graphs. We also show how to build families of laminations together with corresponding lamination languages covering all the possible exact affine complexities.