On reducing the number of stack symbols in a PDA

DOI10.1007/BF01189852MaRDI QIDQ3141998zbMATH OpenOpenAlexFDO

Authors Jonathan Goldstine, John K. Price, Detlef Wotschke

Publication date 21 August 1994

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01189852

zbMATH Keywords

determinism-preserving transformationsnondeterminismpushdown automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 4178795
• Parikh image of pushdown automata
• scientific article; zbMATH DE number 4074488
• Descriptional complexity of pushdown store languages
• A direct construction of finite state automata for pushdown store languages

Cites work

• A note on the succinctness of descriptions of deterministic languages
• A pushdown automaton or a context-free grammar - which is more economical?
• A regularity test for pushdown machines
• Amounts of nondeterminism in finite automata
• An Infinite Hierarchy of Context-Free Languages
• scientific article; zbMATH DE number 3640909 (Why is no real title available?)
• On Goedel speed-up and succinctness of language representations
• On measuring nondeterminism in regular languages
• Regularity and Related Problems for Deterministic Pushdown Automata
• Succinctness of Descriptions of Unambiguous Context-Free Languages

Cited in

(10)

• Detecting useless transitions in pushdown automata
• Simplifying DPDA using supplementary information
• scientific article; zbMATH DE number 4178795 (Why is no real title available?)
• Regulated Nondeterminism in Pushdown Automata
• scientific article; zbMATH DE number 4074488 (Why is no real title available?)
• Digging input-driven pushdown automata
• Detecting useless transitions in pushdown automata
• Generalizing Cook's transformation to imperative stack programs
• Sweeping input-driven pushdown automata
• Regulated nondeterminism in pushdown automata

This page was built for publication: On reducing the number of stack symbols in a PDA

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