Bottom-Up Quotients for Tree Languages
Jean-Marc Champarnaud, Ludovic Mignot, Nadia Ouali Sebti, Djelloul Ziadi · HAL (Le Centre pour la Communication Scientifique Directe) · 2017
We extend the notion of tree language quotients to bottom-up quotients. Instead of computing the residual of a tree language from top to bottom and producing a list of tree languages, we compute a set of $k$-ary trees, where $k$ is an arbitrary integer. We define the quotient formula for different combinations of tree languages: union, symbol products, compositions, iterated symbol products and iterated composition. These computations lead to the definition of the bottom-up quotient tree automaton, that turns out to be the minimal deterministic tree automaton associated with a regular tree language in the case of the $0$-ary trees. Furthermore, we also define a syntactic test to determine whether a tree belongs to a given tree language, that allows us to define a new membership decision algorithm, without constructing the whole automaton.