Abstract We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (non)expressiveness results translate to class separations. A typical example of a polynomial recursive sequence is bn = n!. Our main result is that the sequence un = nn is not polynomial recursive.

We study the matching problem of regular tree languages, that is, "$\exists \sigma:\sigma(L)\subseteq R$?" where $L,R$ are regular tree languages over the union of finite ranked alphabets $\Sigma$ and $\mathcal{X}$ where $\mathcal{X}$ is an alphabet of variables and $\sigma$ is a substitution such that $\sigma(x)$ is a set of trees in $T(\Sigma\cup H)\setminus H$ for all $x\in \mathcal{X}$. Here, $H$ denotes a set of "holes" which are used to define a "sorted" concatenation of trees. Conway studied this problem in the special case for languages of finite words in his classical textbook "Regular algebra and finite machines" published in 1971. He showed that if $L$ and $R$ are regular, then the problem "$\exists \sigma \forall x\in \mathcal{X}: \sigma(x)\neq \emptyset\wedge \sigma(L)\subseteq R$?" is decidable. Moreover, there are only finitely many maximal solutions, the maximal solutions are regular substitutions, and they are effectively computable. We extend Conway's results when $L,R$ are regular languages of finite and infinite trees, and language substitution is applied inside-out, in the sense of Engelfriet and Schmidt (1977/78). More precisely, we show that if $L\subseteq T(\Sigma\cup\mathcal{X})$ and $R\subseteq T(\Sigma)$ are regular tree languages over finite or infinite trees, then the problem "$\exists \sigma \forall x\in \mathcal{X}: \sigma(x)\neq \emptyset\wedge \sigma_{\mathrm{io}}(L)\subseteq R$?" is decidable. Here, the subscript "$\mathrm{io}$" in $\sigma_{\mathrm{io}}(L)$ refers to "inside-out". Moreover, there are only finitely many maximal solutions $\sigma$, the maximal solutions are regular substitutions and effectively computable. The corresponding question for the outside-in extension $\sigma_{\mathrm{oi}}$ remains open, even in the restricted setting of finite trees.

We present an algorithm for the following problem: given a context-free grammar for the word problem of a virtually free group $G$, compute a finite graph of groups $\mathcal{G}$ with finite vertex groups and fundamental group $G$. Our algorithm is non-deterministic and runs in doubly exponential time. It follows that the isomorphism problem of context-free groups can be solved in doubly exponential space. Moreover, if, instead of a grammar, a finite extension of a free group is given as input, the construction of the graph of groups is in NP and, consequently, the isomorphism problem in PSPACE.

For the whole class of linear term rewriting systems and for each integer k, we define k-bounded rewriting as a restriction of the usual notion of rewriting. We show that the k-bounded uniform termination, the k-bounded termination, the inverse k-bounded uniform, and the inverse k-bounded problems are decidable. The k-bounded class (BO(k)) is, by definition, the set of linear systems for which every derivation can be replaced by a k-bounded derivation. In general, for BO(k) systems, the uniform (respectively inverse uniform) k-bounded termination problem is not equivalent to the uniform (resp. inverse uniform) termination problem, and the k-bounded (respectively inverse k-bounded) termination problem is not equivalent to the termination (respectively inverse termination) problem. This leads us to define more restricted classes for which these problems are equivalent: the classes BOLP(k) of k-bounded systems that have the length preservation property. By definition, a system is BOLP(k) if every derivation of length n can be replaced by a k-bounded derivation of length n. We define the class BOLP of bounded systems that have the length preservation property as the union of all the BOLP(k) classes. The class BOLP contains (strictly) several already known classes of systems: the inverse left-basic semi-Thue systems, the linear growing term rewriting systems, the inverse Linear-Finite-Path-Ordering systems, the strongly bottom-up systems.

The bisimulation problem for equational graphs of finite out-degree is shown to be decidable. We reduce this problem to the $\eta$-bisimulation problem for deterministic rational (vectors of) boolean series on the alphabet of a deterministic pushdown automaton ${\cal M}$. We then exhibit a complete formal system for deducing equivalent pairs of such vectors.

The bisimulation problem for equational graphs of finite out-degree is shown to be decidable. We reduce this problem to the /spl eta/-bisimulation problem for deterministic rational (vectors of) Boolean series on the alphabet of a dpda M. We then exhibit a complete formal system for deducing equivalent pairs of such vectors.

For several decision problems about semi-Thue systems, we try to locate the frontier between the decidable and the undecidable from the point of view of the number of rules. We show that the the Termination Problem, the U-Termination Problem, the Accessibility Problem and the Common-Descendant Problem are undecidable for 3 rules semi-Thue systems. As a corollary we obtain the undecidability of the Post-Correspondence Problem for 7 pairs of words.