- This event has passed.

# Regular matching problems for infinite trees

## March 25, 2021 @ 10:00 am - 12:00 pm

**Title: **Regular matching problems for infinite trees

**Speaker: **Mircea Marin (West University of Timișoara)

**Abstract: **

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

This is joint work with Carlos Camino, Volker Diekert, Besik Dundua and Géraud Sénizergues.

*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.

**References**:

[1] C. Camino, V. Diekert, B. Dundua, M. Marin, G. Sénizergues, Regular matching problems for infinite trees. arXiv:2004.09926 [cs.FL], 2021.