BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260409T002826Z
UID:Seminar-ACTO-495@lxserverA.csc.liv.ac.uk.csc.liv.ac.uk
ORGANIZER:CN=Nikhil Mande:MAILTO:Nikhil.Mande@liverpool
DTSTART:20190621T140000
DTEND:20190621T150000
SUMMARY:Algorithms, Complexity Theory and Optimisation Series
DESCRIPTION:Prof. Volker Diekert: About a Conway-type result for tree language\n\nConway 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$.\n\nIn 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.\n\nThe talk is about a joint work with Carlos Camino (Stuttgart),  Besik Dundua (Tbilisi), and Mircea Marin (Timisoara).\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=495
LOCATION:
END:VEVENT
END:VCALENDAR