Conway-type result for language over finite and infinite trees

Volker Diekert

In his classical text book from 1971 Conway developed a factorization calculus for regular languages. In particular, he considered the following question. Given two disjoint alphabets $\Sigma$ of constants and $V$ of variables as well as two regular languages $L\subseteq(\Sigma\cup V)^*$ and $R\subseteq \Sigma^{*$: what can be said about the set of \subst{s} $\sig \colon V\to 2}{\Sigma^{*}$ such that $\sig(L)\subseteq R$? In his setting, if $\sig$ satisfies $\sig(L)\subseteq R$, then $\sig$ is called a \emph{\solu} to the instance $L\subseteq R$. There is a natural partial order on \subst{s} $\sig \colon V\to 2}{\Sigma^*}$ by defining $\sig\leq \sig'$ by $\forall X\in V \colon \sig(X)\subseteq \sig'(X)$. Conway showed that the set of maximal \solu{s} is finite; and moreover, he showed that for every maximal \solu the set $\sig(X)$ is regular for each $X\in V$.

The talk reports on a joint work with Carlos Camino (Stuttgart), Besik Dundua (Tbilisi), and Mircea Marin (Timișoara) on a generalization to language over finite and infinite trees. We present some new results and some pointers to open problems.