Efficient determinization of visibly and height-deterministic pushdown automata

DOI10.1016/J.CL.2016.07.005MaRDI QIDQ1749148zbMATH OpenOpenAlexFDO

Authors Radomír Polách, Jan Trávníček, Jan Janoušek, 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)

Recommendations

• On Model Checking for Visibly Pushdown Automata
• On the complexity of membership and counting in height-deterministic pushdown automata
• Height-Deterministic Pushdown Automata
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• Five Determinisation Algorithms

Cites work

• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• Arbology: trees and pushdown automata
• Early nested word automata for XPath query answering on XML streams
• Height-Deterministic Pushdown Automata
• Marrying Words and Trees
• Properties of visibly pushdown transducers
• Regularity Problems for Visibly Pushdown Languages
• Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation
• Visibly pushdown languages

Cited in

(11)

• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• Trimming visibly pushdown automata
• Height-Deterministic Pushdown Automata
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• On the Expressive Power of 2-Stack Visibly Pushdown Automata
• On Model Checking for Visibly Pushdown Automata
• Detecting useless transitions in pushdown automata
• Detecting useless transitions in pushdown automata
• On the complexity of membership and counting in height-deterministic pushdown automata
• Schema-based automata determinization
• Pushdown automata and constant height: decidability and bounds

Describes a project that uses

Uses Software

• ALT
• VPAlib
• XPath

This page was built for publication: Efficient determinization of visibly and height-deterministic pushdown automata

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