On Definite and Nilpotent DR Tree Languages
Ferenc Gécseg, Balázs Imreh · Journal of automata, languages and combinatorics · 2004
The sets recognized by deterministic root-to-frontier tree recognizers, the DR tree languages, are determined by their path languages. A path language of a tree language $T$ consists of the words describing the paths leading from the root of a tree in $T$ to its leaves labelled with a given leaf symbol. The greatest congruence saturating the path languages yields the syntactic path monoid of $T$ which is finite for a path closed $T$ exactly in case $T$ is a DR tree language. We introduce the concepts of definite and nilpotent DR tree languages and, by means of syntactic path semigroups, characterize them.