Title: Regular matching problems for infinite trees
Speaker: Mircea Marin (West University of Timișoara)
We study the matching problem “∃σ:σ(L)⊆R?” where L and R are regular tree languages over finite ranked alphabets X and Σ respectively, and σ is a substitution such that σ(x) is a set of trees in T(Σ∪H)∖H for all x∈X. Here, H denotes a set of holes which are used to define a 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
and showed that if L and R are regular, then the problem “∃σ:∀x∈X:σ(x)≠∅∧σ(L)⊆R?” is decidable. Moreover, there are only finitely many maximal solutions, which are regular and effectively computable. We extend Conway’s results when L and R are regular languages of finite and infinite trees, and language substitution is applied inside-out. We show that if L⊆T(X) and R⊆T(Σ) are regular tree languages then the problem “∃σ∀x∈X:σ(x)≠∅∧σio
(L)⊆R?” is decidable. Moreover, there are only finitely many maximal solutions, which are regular and effectively computable. The corresponding question for the outside-in extension σoi
remains open, even in the restricted setting of finite trees. Our main result is the decidability of “∃σ:σio
(L)⊆R?” if R is regular and L belongs to a class of tree languages closed under intersection with regular sets. Such a special case pops up if L is context-free.
This is joint work with Carlos Camino, Volker Diekert, Besik Dundua and Géraud Sénizergues.
 C. Camino, V. Diekert, B. Dundua, M. Marin, G. Sénizergues, Regular matching problems for infinite trees. arXiv:2004.09926 [cs.FL], 2021.