Minimal Ascending and Descending Tree Automata

DOI10.1137/S0097539789164078zbMath0868.68080MaRDI QIDQ4337430

Maurice Nivat, Andreas Podelski

Publication date: 19 May 1997

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

descending tree automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

Deciding top-down determinism of regular tree languages, Automata for XML -- a survey, BISIMULATION MINIMIZATION OF TREE AUTOMATA, Checking in polynomial time whether or not a regular tree language is deterministic top-down, Regular languages with variables on graphs, State Complexity of Regular Tree Languages for Tree Matching, Smoothing and compression with stochastic \(k\)-testable tree languages, Deciding equivalence of top-down XML transformations in polynomial time, A perfect hashing incremental scheme for unranked trees using pseudo-minimal automata, A Congruence-Based Perspective on Finite Tree Automata