# Conway-type result for language over finite and infinite trees

- 11:00 26th September 2019 ( Michaelmas Term 2019 )Room 051

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.