Regulated pushdown automata

MaRDI QIDQ2714410zbMATH OpenFDO

Authors Alexander Meduna, Dušan Kolář

Publication date 13 June 2001

Published in Acta Cybernetica (Search for Journal in Brave)

zbMATH Keywords

pushdown automataregulated automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

As the use of grammar rules can be regulated by control languages, this paper suggests to regulate the use of rules of pushdown automata by control langauges. For regular control langauges, it is proven that this regulation has no effect on the power of pushdown automata. However the pushdown automata regulated by linear control langauges characterize the family of recursively enumerable languages. The results are established in terms of acceptance by final state, of acceptance by empty pushdown and of the combination of both.

Recommendations

• Regulated nondeterminism in pushdown automata: the non-regular case
• Regulated nondeterminism in pushdown automata
• Regulated Nondeterminism in Pushdown Automata
• scientific article; zbMATH DE number 1886071
• Controlled pure grammar systems

Cited in

(8)

• Storage products and linear control of derivations
• Regulated nondeterminism in pushdown automata: the non-regular case
• Regulated Nondeterminism in Pushdown Automata
• Controlled finite automata
• scientific article; zbMATH DE number 1886071 (Why is no real title available?)
• Scattered context grammars with one non-context-free production are computationally complete
• Self-regulating finite automata
• Regulated nondeterminism in pushdown automata

This page was built for publication: Regulated pushdown automata

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