International Journal of Foundations of Computer Science

Dendric words are infinite words that are defined in terms of extension graphs. These are bipartite graphs that describe the left and right extensions of factors. Dendric words are such that all their extension graphs are trees. They are also called tree words. This class of words includes classical families of words such as Sturmian words, codings of interval exchanges, or else, Arnoux–Rauzy words. We investigate here the properties of substitutive dendric words and prove some rigidity properties, that is, algebraic properties on the set of substitutions that fix a dendric word. We also prove that aperiodic minimal dendric subshifts (generated by dendric words) cannot have rational topological eigenvalues, and thus, cannot be generated by constant length substitutions.

Elizalde (2011) characterized which permutations can be obtained by ordering consecutive elements in the trajectories of (positive) beta-transformations and beta-shifts. We prove similar results for negative bases beta.

Pairwise ordered tree alignment are combinatorial objects that appear in important applications, such as RNA secondary structure comparison. However, the usual representation of tree alignments as supertrees is ambiguous, i.e. two distinct supertrees may induce identical sets of matches between identical pairs of trees. This ambiguity is uninformative, and detrimental to any probabilistic analysis.

In this work, we consider tree alignments up to equivalence. Our first result is a precise asymptotic enumeration of tree alignments, obtained from a context-free grammar by mean of basic analytic combinatorics. Our second result focuses on alignments between two given ordered trees $S$ and $T$. By refining our grammar to align specific trees, we obtain a decomposition scheme for the space of alignments, and use it to design an efficient dynamic programming algorithm for sampling alignments under the Gibbs-Boltzmann probability distribution. This generalizes existing tree alignment algorithms, and opens the door for a probabilistic analysis of the space of suboptimal alignments.

We prove the effective closure under complementation of the class of languages of scattered and countable $N$-free posets recognized by branching automata.

Regular string-to-string functions enjoy a nice triple characterization through deterministic two-way transducers (2DFT), streaming string transducers (SST) and MSO definable functions. This result has recently been lifted to FO definable functions, with equivalent representations by means of aperiodic 2DFT and aperiodic 1-bounded SST, extending a well-known result on regular languages. In this paper, we give three direct transformations: $i)$ from 1-bounded SST to 2DFT, $ii)$ from 2DFT to copyless SST, and $iii)$ from $k$-bounded to $1$-bounded SST. We give the complexity of each construction and also prove that they preserve the aperiodicity of transducers. As corollaries, we obtain that FO definable string-to-string functions are equivalent to SST whose transition monoid is finite and aperiodic, and to aperiodic copyless SST.

We study finite-state transducers and their power for transforming infinite words. Infinite sequences of symbols are of paramount importance in a wide range of fields, from formal languages to pure mathematics and physics. While finite automata for recognising and transforming languages are well-understood, very little is known about the power of automata to transform infinite words.

The word transformation realised by finite-state transducers gives rise to a complexity comparison of words and thereby induces equivalence classes, called (transducer) degrees, and a partial order on these degrees. The ensuing hierarchy of degrees is analogous to the recursion-theoretic degrees of unsolvability, also known as Turing degrees, where the transformational devices are Turing machines. However, as a complexity measure, Turing machines are too strong: they trivialise the classification problem by identifying all computable words. Finite-state transducers give rise to a much more fine-grained, discriminating hierarchy. In contrast to Turing degrees, hardly anything is known about transducer degrees, in spite of their naturality.

We use methods from linear algebra and analysis to show that there are infinitely many atoms in the transducer degrees, that is, minimal non-trivial degrees.

We contribute to the study of square-free words. The classical notion of a square-free word has a natural generalization to partial words, studied in several papers since 2008. We prove that the maximal density of wildcards in the ternary infinite square-free partial word is surprisingly big: $3/16$. Further we show that the density of wildcards in a finitary infinite square-free partial words is at most $1/3$ and this bound is reached by a quaternary word. We demonstrate that partial square-free words can be viewed as “usual” square-free words with some letters replaced by wildcards and introduce the corresponding characteristic of infinite square-free words, called flexibility. The flexibility is estimated for some important words and classes of words; an interesting phenomenon is the existence of “rigid” square-free words, having no room for wildcards at all.

A nondeterministic finite automaton is unambiguous if it has at most one accepting computation on every input string. We investigate the state complexity of basic regular operations on languages represented by unambiguous finite automata. We get tight upper bounds for reversal ($n$), intersection ($mn$), left and right quotients ($2^n-1$), positive closure ($\frac{3}{4}{2}^n-1$), star ($\frac{3}{4}{2}^n$), shuffle ($2^{mn}-1$), and concatenation ($\frac{3}{4}{2}^{m+n}-1$). To prove tightness, we use a binary alphabet for intersection and left and right quotients, a ternary alphabet for star and positive closure, a five-letter alphabet for shuffle, and a seven-letter alphabet for concatenation. For complementation, we reduce the trivial upper bound $2^n$ to $2^{0.7856n+logn}$. We also get some partial results for union and square.

The well-known synchronous context-free grammars (SCFGs) and synchronous tree-substitution grammars (STSGs), both of which are used as tree-to-tree translation models in statistical machine translation are investigated. Their composition hierarchies are established in both the unweighted as well as the weighted case. More precisely, it is shown that SCFGs are closed under composition in both cases and that there is a close connection between compositions of STSGs and compositions of certain tree transducers. With the help of the close ties, the composition closure of STSGs is identified in both cases as well. The results for the weighted case utilize a new lifting technique that might prove useful also in similar setups.

We investigate the complexity of the solvability problem for restricted classes of word equations with and without regular constraints. The solvability problem for unrestricted word equations remains $NP$-hard, even if, on both sides, between any two occurrences of the same variable no other different variable occurs; for word equations with regular constraints, the solvability problems remains $NP$-hard for equations whose two sides share no variables or with two variables, only one of which is repeated. On the other hand, word equations with only one repeated variable (but an arbitrary number of variables) and at least one non-repeated variable on each side, can be solved in polynomial-time.

This work is a study of the class of non-deterministic automata on infinite trees that are unambiguous i.e. have at most one accepting run on every tree. The motivating question asks if the fact that an automaton is unambiguous implies some drop in the descriptive complexity of the language recognised by the automaton. As it turns out, such a drop occurs for the parity index and does not occur for the weak parity index.

More precisely, given an unambiguous parity automaton ${𝒜}$ of index $(i,2j)$, we show how to construct an alternating automaton ${T}{r}{a}{n}{s}{f}{o}{r}{m}{a}{t}{i}{o}{n}({𝒜})$ which accepts the same language, but is simpler in terms of the acceptance condition. In particular, if ${𝒜}$ is a Büchi automaton ($i=0,j=1$) then ${T}{r}{a}{n}{s}{f}{o}{r}{m}{a}{t}{i}{o}{n}({𝒜})$ is a weak alternating automaton. In general, ${T}{r}{a}{n}{s}{f}{o}{r}{m}{a}{t}{i}{o}{n}({𝒜})$ belongs to the class $\mathrm{\text{comp}}(i+1,2j)$, what implies that it is simultaneously of alternating index $(i,2j)$ and of the dual index $(i+1,2j+1)$. The transformation algorithm is based on a separation procedure of Arnold and Santocanale (2005).

In the case of non-deterministic automata with the weak parity condition, we provide a separation procedure analogous to the one used above. However, as illustrated by examples, this separation procedure cannot be used to prove a complexity drop in the weak case, as there is no such drop.

We prove connections between one-variable word equations and three-variable constant-free word equations, and use them to prove that the number of equations in an independent system of three-variable constant-free equations is at most logarithmic with respect to the length of the shortest equation in the system. We also study two well-known conjectures. The first conjecture claims that there is a constant $c$ such that every one-variable equation has either infinitely many solutions or at most $c$. The second conjecture claims that there is a constant $c$ such that every independent system of three-variable constant-free equations with a nonperiodic solution is of size at most $c$. We prove that the first conjecture implies the second one, possibly for a different constant.