Height-Deterministic Pushdown Automata

DOI10.1007/978-3-540-74456-6_13MaRDI QIDQ3525562zbMATH OpenOpenAlexFDO

Authors Dirk Nowotka, Jiří Srba

Publication date 17 September 2008

Published in Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74456-6_13

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Pushdown automata and constant height: decidability and bounds
• Pushdown automata and constant height: decidability and bounds
• Efficient determinization of visibly and height-deterministic pushdown automata
• On the complexity of membership and counting in height-deterministic pushdown automata
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• scientific article; zbMATH DE number 2150277
• On the height of a finite automaton
• Removing nondeterminism in constant height pushdown automata
• Removing nondeterminism in constant height pushdown automata

Cited in

(23)

• Generalizing input-driven languages: theoretical and practical benefits
• Efficient determinization of visibly and height-deterministic pushdown automata
• Operator precedence and the visibly pushdown property
• Colored nested words
• Pushdown automata and constant height: decidability and bounds
• Tree template matching in ranked ordered trees by pushdown automata
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• Semi-deterministic pushdown automata (SDPDA) of order ``\(n\) and \(\beta\)-languages
• Deterministic set automata
• Operator precedence languages: their automata-theoretic and logic characterization
• Precedence automata and languages
• Arbology: trees and pushdown automata
• Descriptional complexity of input-driven pushdown automata
• Synchronization of Regular Automata
• On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata
• On the complexity of membership and counting in height-deterministic pushdown automata
• scientific article; zbMATH DE number 3905868 (Why is no real title available?)
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• scientific article; zbMATH DE number 7439739 (Why is no real title available?)
• Tree template matching in ranked ordered trees by pushdown automata
• Pushdown automata and constant height: decidability and bounds
• Aperiodicity, Star-freeness, and First-order Logic Definability of Operator Precedence Languages
• Weighted one-deterministic-counter automata

This page was built for publication: Height-Deterministic Pushdown Automata

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