In this paper we will deal with the balance properties of the infinite binary words associated to β-integers when β is a quadratic simple Pisot number. Those words are the fixed points of the morphisms of the type $\varphi(A)=A^pB$, $\varphi(B)=A^q$ for $p\in\mathbb N$, $q\in\mathbb N$, $p\geq q$, where $\beta=\frac{p+\sqrt{p^2+4q}}{2}$. We will prove that such word is t-balanced with $t=1+\left[(p-1)/(p+1-q)\right]$. Finally, in the case that p < q it is known [B. Adamczewski, Theoret. Comput. Sci.273 (2002) 197–224] that the fixed point of the substitution $\varphi(A)=A^pB$, $\varphi(B)=A^q$ is not m-balanced for any m. We exhibit an infinite sequence of pairs of words with the unbalance property.

The depth hierarchy results for monotone circuits of Raz and McKenzie [5] are extended to the case of monotone circuits of semi-unbounded fan-in. It follows that the inclusions NCi ⊆ SACi ⊆ ACi are proper in the monotone setting, for every i ≥ 1.

We explore the borderline between decidability and undecidability of the following question: “Let C be a class of codes. Given a machine ${\mathfrak{M}}$ of type X, is it decidable whether the language $L({{\mathfrak{M}}})$ lies in C or not?” for codes in general, ω-codes, codes of finite and bounded deciphering delay, prefix, suffix and bi(pre)fix codes, and for finite automata equipped with different versions of push-down stores and counters.

In this paper we investigate the average Horton-Strahler number of all possible tree-structures of binary tries. For that purpose we consider a generalization of extended binary trees where leaves are distinguished in order to represent the location of keys within a corresponding trie. Assuming a uniform distribution for those trees we prove that the expected Horton-Strahler number of a tree with α internal nodes and β leaves that correspond to a key is asymptotically given by $$\frac{4^{2\beta-\alpha}\log(\alpha)(2\beta-1)(\alpha+1)(\alpha+2){2\alpha+1\choose \alpha-1}}{8\sqrt{\pi}\alpha^{3/2}\log(2)(\beta-1)\beta{2\beta\choose \beta}^2}$$ provided that α and β grow in some fixed proportion ρ when α → ∞ . A similar result is shown for trees with α internal nodes but with an arbitrary number of keys.

An ever present, common sense idea in language modelling research is that, for aword to be a valid phrase, it should comply with multiple constraints atonce. A new language definition model is studied, based on agreement or consensusbetween similar strings. Considering a regular set of strings over a bipartitealphabet made by pairs of unmarked/marked symbols, a match relation isintroduced, in order to specify when such strings agree. Then a regular setover the bipartite alphabet can be interpreted as specifying another languageover the unmarked alphabet, called the consensual language. A word is in theconsensual language if a set of corresponding matching strings is in theoriginal language. The family thus defined includes the regular languages andalso interesting non-semilinear ones. The word problem can be solved inNLOGSPACE, hence in P time. The emptiness problem is undecidable. Closure properties areproved for intersection with regular sets and inverse alphabetical homomorphism.Several conditions for a consensual definition to yield a regular language arepresented, and it is shown that the size of a consensual specification ofregular languages can be in a logarithmic ratio with respect to a DFA. Thefamily is incomparable with context-free and tree-adjoining grammar families.

The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root rule” of the two-dimensional bandwidth, which is useful in evaluating B2(G) for some typical graphs.

The purpose of this paper is to show connections between iterated length-preserving rational transductions and linear space computations. Hence, we study the smallest family of transductions containing length-preserving rational transductions and closed under union, composition and iteration. We give several characterizations of this class using restricted classes of length-preserving rational transductions, by showing the connections with "context-sensitive transductions" and transductions associated with recognizable picture languages.

We investigate the number of iterations needed by an addition algorithm due to Burks et al. if the input is random. Several authors have obtained results on the average case behaviour, mainly using analytic techniques based on generating functions. Here we take a more probabilistic view which leads to a limit theorem for the distribution of the random number of steps required by the algorithm and also helps to explain the limiting logarithmic periodicity as a simple discretization phenomenon.

We prove that a word of length n from a finitely ambiguous context-free language can be generated at random under uniform distribution in O(n2 log n) time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time 1-NAuxPDA with polynomially bounded ambiguity.

We study D0L power series over commutative semirings. We show that a sequence(cn )n≥0 of nonzero elements of a field A is the coefficientsequence of a D0L power series if and only if there exist a positive integerk and integers βi for 1 ≤ i ≤ k such that $c_{n+k}=c_{n+k-1}^{\beta_1}c_{n+k-2}^{\beta_2}\ldots c_n^{\beta_k}$ for alln ≥ 0. As a consequence we solve the equivalence problem of D0L powerseries over computable fields.

We study hardness of approximating several minimaximal and maximinimal NP-optimizationproblems related to the minimum linear ordering problem (MINLOP). MINLOP is to find a minimum weight acyclic tournament in a given arc-weighted completedigraph. MINLOP is APX-hard but its unweighted version is polynomial timesolvable. We prove that MIN-MAX-SUBDAG problem, which is a generalization ofMINLOP and requires to find a minimum cardinality maximal acyclic subdigraphof a given digraph, is, however, APX-hard. Using results of Håstad concerning hardness of approximating independence number of a graph we then prove similar results concerning MAX-MIN-VC (respectively, MAX-MIN-FVS) which requires to find a maximum cardinality minimal vertex cover in a given graph (respectively,a maximum cardinality minimal feedback vertex set in a given digraph). We alsoprove APX-hardness of these and several related problems on various degree bounded graphs and digraphs.

We design algorithms of “optimal" data complexity for several natural problems about first-order queries on structures of bounded degree. For that purpose, we first introduce a framework to deal with logical or combinatorial problems R ⊂ I x O whose instances x ∈ I may admit of several solutions R(x) = {y ∈ O : (x,y) ∈ R}. One associates to such a problem several specific tasks: compute a random (for the uniform probability distribution) solution y ∈ R(x); enumerate without repetition each solution yj in some specific linear order y0 < y1 < ... < yn-1 where R(x) = {y0,...,yn-1}; compute the solution yj of rankj in the linear order <. Algorithms of “minimal" data complexity are presented for the following problems: given any first-order formula $\varphi(\bar{v})$ and any structure S of bounded degree: (1) compute a random element of $\varphi(S)=\{\bar{a}: (S,\bar{a})\models\varphi(\bar{v})\}$; (2) compute the jth element of $\varphi(S)$ for some linear order of $\varphi(S)$; (3) enumerate the elements of $\varphi(S)$ in lexicographical order. More precisely, we prove that, for any fixed formula φ, the above problem (1) (resp. (2), (3)) can be computed within average constant time (resp. within constant time, with constant delay) after a linear (O(|S|)) precomputation. Our essential tool for deriving those complexity results is a normalization procedure of first-order formulas on bijective structures.

In Hoare's (1961) original version of the algorithm  the partitioning element in the central divide-and-conquer step is chosen uniformly at random from the set S in question.Here we consider a variant where this element is the median of a sample of size 2k+1 from S. We investigate convergencein distribution of the number of comparisons required and obtain a simple explicit result for the limitingaverage performance of the median-of-three version.

We study cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are equipped with an external pushdown store. In this way we obtain an automata-theoretical characterization for the class of word languages that are linearizations of context-free trace languages.

Nous établissons quelques propriétés des mots sturmiens et classifions, ensuite, les mots infinis qui possèdent, pour tout entier naturel non nul n, exactement n+2 facteurs de longueur n. Nous définissons également la notion d'insertion k à k sur les mots infinis puis nous calculons la complexité des mots obtenus en appliquant cette notion aux mots sturmiens. Enfin nous étudions l'équilibre et la palindromie d'une classe particulière de mots de complexité n+2 que nous appelons mots quasi-sturmiens par insertion et que nous caractérisons à l'aide des vecteurs de Parikh.

Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is still unknown. In 1992, Schöniger and Waterman proposed the simplification hypothesis that the inversions do not overlap. They also presented an O(n6) exact solution for the alignment with non-overlapping inversions problem and introduced a heuristic for it that brings the average case complexity down. (In this work, n is the maximal length of both sequences that are aligned.) The present paper gives two exact algorithms for the simplified problem. We give a quite simple dynamic program with O(n4)-time and O(n2)-space complexity for alignments with non-overlapping inversions and exhibit a sparse and exact implementation version of this procedure that uses much less resources for some applications with real data.

Natural algorithms to compute rational expressions for recognizablelanguages, even those which work well in practice, may produce very longexpressions. So, aiming towards the computation of the commutative image of arecognizable language, one should avoid passing through an expressionproduced this way.We modify here one of those algorithms in order to compute directly a semilinear expression for the commutative imageof a recognizable language. We also give a secondmodification of the algorithm which allows the direct computation of theclosure in the profinite topology of the commutative image. As anapplication, we give a modification of an algorithm for computing the Abelian kernel of a finite monoid obtainedby the author in 1998 which is much more efficient in practice.

An infinite permutation α is a linear ordering of N. We study properties of infinite permutations analogous to those of infinite words, and show some resemblances and some differences between permutations and words. In this paper, we try to extend to permutations the notion of automaticity. As we shall show, the standard definitions which are equivalent in the case of words are not equivalent in the context of permutations. We investigate the relationships between these definitions and prove that they constitute a chain of inclusions. We also construct and study an automaton generating the Thue-Morse permutation.

Let w be an infinite fixed point of a binary k-uniform morphism f, and let Ew be the critical exponent of w. We give necessary and sufficient conditions for Ew to be bounded, and an explicit formula to compute it when it is. In particular, we show that Ew is always rational. We also sketch an extension of our method to non-uniform morphisms over general alphabets.

Drawing on an analogy with temporal fixpoint logic, we relate the arithmetic fixpoint definable sets to the winning positions of certain games, namely games whose winning conditions lie in the difference hierarchy over $\Sigma^0_2$. This both provides a simple characterization of the fixpoint hierarchy, and refines existing results on the power of the game quantifier in descriptive set theory. We raise the problem of transfinite fixpoint hierarchies.