About a Conway-type result for tree language

21^st June 2019, 14:00
Prof. Volker Diekert
Stuttgart University

Abstract

Conway developed in his classical text book from 1971 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 substitutions $\sigma : V\to 2^{\Sigma^*}$ such that $\sigma(L)\subseteq R$? In his setting, if $\sigma$ satisfies $\sigma(L)\subseteq R$, then $\sigma$ is called a solution to the instance $L\subseteq R$. There is a natural partial order on substitutions $\sigma : V\to 2^{\sigma^*}$ by defining $\sigma\leq \sigma'$ by $\forall X\in V : \sigma(X)\subseteq \sigma'(X)$. Conway showed that the set of maximal solutions is finite; and moreover, he showed that for every maximal solution the set $\sigma(X)$ is regular for each $X\in V$.

In my talk I report on some ongoing research to produce similar results for regular tree languages. The talk presents some new results and some pointers to open problems.

The talk is about a joint work with Carlos Camino (Stuttgart), Besik Dundua (Tbilisi), and Mircea Marin (Timisoara).