2021/05/20 by Beaudry, Martin
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2105.09970
A leaf path language is a Boolean combination of sets of the form \mathsfmEk L, with k ≥ 1 and L a regular word language, which consist of those forests where the node labels in at least k leaf-to-root paths make up a word that belongs to L. We look at the class *D of the languages recognized by iterated wreath products of syntactic algebras of leaf path languages. We prove the existence of an algorithm that, given a regular forest language, returns in finite time a sequence of such algebras; their wreath product is divided by the language's syntactic algebra if, and only if this language belongs to *D, which makes membership in this class a decidable question. The result also applies to the subclasses PDL and CTL^*.