Efficient determinization of visibly and height-deterministic pushdown automata

DOI10.1016/j.cl.2016.07.005zbMath1387.68160OpenAlexW2482236631MaRDI QIDQ1749148

Jan Trávníček, Jan Janoušek, Radomír Polách, Bořivoj Melichar

Publication date: 15 May 2018

Published in: Computer Languages, Systems \& Structures (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cl.2016.07.005

zbMATH Keywords

deterministic pushdown automatapushdown automatadeterminizationvisibly pushdown automataheight-deterministic pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Detecting useless transitions in pushdown automata

Uses Software

• XPath
• VPAlib
• ALT

Cites Work

• Unnamed Item
• Unnamed Item
• Early nested word automata for XPath query answering on XML streams
• Height-Deterministic Pushdown Automata
• Visibly pushdown languages
• Properties of Visibly Pushdown Transducers
• Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation
• Regularity Problems for Visibly Pushdown Languages
• Marrying Words and Trees