2014 | OriginalPaper | Buchkapitel
Tree Automata with Height Constraints between Brothers
verfasst von : Carles Creus, Guillem Godoy
Erschienen in: Rewriting and Typed Lambda Calculi
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We define the tree automata with height constraints between brothers (
TACBB
H
). Constraints of equalities and inequalities between heights of siblings that restrict the applicability of the rules are allowed in
TACBB
H
. These constraints allow to express natural tree languages like complete or balanced (like AVL) trees. We prove decidability of emptiness and finiteness for
TACBB
H
, and also for a more general class that additionally allows to combine equality and disequality constraints between brothers.