Deciding top-down determinism of regular tree languages

DOI10.1007/978-3-030-86593-1_24OpenAlexW3204537254MaRDI QIDQ2140513

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)

Related Items (2)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simplifying XML schema: single-type approximations of regular tree languages
• Linear Automaton Transformations
• An Implementation of Deterministic Tree Automata Minimization
• Eliminating null rules in linear time
• Minimal Ascending and Descending Tree Automata
• Fundamentals of Computation Theory
• The minimalization of tree automata
• Depth-First Search and Linear Graph Algorithms

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