Operator Precedence Tree Automata
Abstract
Operator-precedence tree automata (OPTA) separate the construction of a word's syntactic structure from its recognition: an operator-precedence (OP) matrix determines a canonical tree, which is evaluated by a finite bottom-up automaton with regular horizontal transition languages. OPTA define exactly the operator-precedence languages. For a fixed matrix and language, a tree-context congruence yields an effectively constructible canonical complete deterministic exact recognizer, minimal in the number of vertical states and unique up to isomorphism. For acyclic OP matrices, we characterize balanced non-counting by aperiodicity of the context transition monoid of the canonical minimal ranked tree recognizer. Combined with existing characterizations of OP languages, this gives an equivalence with first-order definability over OP words, definability in Precedence-Oriented Temporal Logic (POTL), and star-free operator-precedence expressions for acyclic matrices.