Minimal Ascending and Descending Tree Automata

DOI10.1137/S0097539789164078MaRDI QIDQ4337430zbMATH OpenFDO

Authors M. 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)

Recommendations

• scientific article; zbMATH DE number 139615
• Incremental construction of minimal tree automata
• Minimization of symbolic tree automata
• Minimization of deterministic top-down tree automata
• scientific article; zbMATH DE number 4201643
• scientific article; zbMATH DE number 1867116
• Database Programming Languages
• Minimizing Deterministic Weighted Tree Automata

Cited in

(12)

• State complexity of regular tree languages for tree matching
• A perfect hashing incremental scheme for unranked trees using pseudo-minimal automata
• A congruence-based perspective on finite tree automata
• Regular languages with variables on graphs
• scientific article; zbMATH DE number 3856422 (Why is no real title available?)
• Automata for XML -- a survey
• Deciding equivalence of top-down XML transformations in polynomial time
• BISIMULATION MINIMIZATION OF TREE AUTOMATA
• Deciding top-down determinism of regular tree languages
• Smoothing and compression with stochastic \(k\)-testable tree languages
• scientific article; zbMATH DE number 139615 (Why is no real title available?)
• Checking in polynomial time whether or not a regular tree language is deterministic top-down

This page was built for publication: Minimal Ascending and Descending Tree Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4337430)