Deciding top-down determinism of regular tree languages

DOI10.1007/978-3-030-86593-1_24MaRDI QIDQ2140513zbMATH OpenOpenAlexFDO

Authors Peter Leupold, Sebastian Maneth

Publication date 20 May 2022

Full work available at URL https://arxiv.org/abs/2107.03174

zbMATH Keywords

decision problemsdefinabilitydeterministic top-down tree automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• An Implementation of Deterministic Tree Automata Minimization
• Depth-First Search and Linear Graph Algorithms
• Deterministic top-down tree automata: past, present, and future
• Eliminating null rules in linear time
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 3711381 (Why is no real title available?)
• scientific article; zbMATH DE number 58315 (Why is no real title available?)
• Linear Automaton Transformations
• Minimal Ascending and Descending Tree Automata
• Simplifying XML schema: single-type approximations of regular tree languages
• The minimalization of tree automata

Cited in

(4)

• On regular tree languages and deterministic pushdown automata
• It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton
• Checking in polynomial time whether or not a regular tree language is deterministic top-down
• On the Boolean Closure of Deterministic Top-Down Tree Automata

This page was built for publication: Deciding top-down determinism of regular tree languages

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