Prefix pushdown automata and their simplification

DOI10.1080/00207169908804789MaRDI QIDQ4254588zbMATH OpenOpenAlexFDO

Authors Alexander Meduna

Publication date 29 June 1999

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207169908804789

zbMATH Keywords

prefix pushdown automaton

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 6606350
• Simultaneously One-Turn Two-Pushdown Automata
• Automata with two-sided pushdowns defined over free groups generated by reduced alphabets
• Descriptional complexity of pushdown store languages
• Descriptional complexity of pushdown store languages

Cites work

• Context free derivations on word monoids
• Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages
• Generalized forbidding grammars
• On the generative power of regular pattern grammars

Cited in

(7)

• Computing the prefix of an automaton
• Automata transformations of prefix decidable and decidable by Buchi superwords
• Prefix and Right-Partial Derivative Automata
• scientific article; zbMATH DE number 1886071 (Why is no real title available?)
• Eliminating stack symbols in push-down automata and linear indexed grammars
• Markers and deterministic acceptors for non-deterministic languages
• Automata with two-sided pushdowns defined over free groups generated by reduced alphabets

This page was built for publication: Prefix pushdown automata and their simplification

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