Iterated linear control and iterated one-turn pushdowns

DOI10.1007/BF01704910zbMath0636.68106MaRDI QIDQ3776663

Heiko Vogler

Publication date: 1986

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

zbMATH Keywords

control languageiterated linear controllinear context-free grammarnondeterministic one way automataone-turn pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

The OI-hierarchy is closed under control ⋮ Weighted iterated linear control ⋮ Iterated stack automata and complexity classes ⋮ A geometric hierarchy beyond context-free languages ⋮ Storage products and linear control of derivations ⋮ Gaining Power by Input Operations: Finite Automata and Beyond ⋮ Complete formal systems for equivalence problems ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear indexed languages
• Macro tree transducers
• Pushdown machines for the macro tree transducer
• Tree transducers, L systems, and two-way machines
• The IO- and OI-hierarchies
• Attribute grammars and recursive program schemes. I. II
• A geometric hierarchy of languages
• Control sets on context-free grammar forms
• IO and OI. I
• One way finite visit automata
• Some definitional suggestions for automata theory
• A hierarchy between context-free and context-sensitive languages
• Proof of correctness of data representations
• On the equivalence problem for attribute systems
• Bounded nesting in macro grammars
• Control sets on linear grammars
• Finite-Turn Pushdown Automata
• Control sets on grammars
• Indexed Grammars—An Extension of Context-Free Grammars
• Programmed Grammars and Classes of Formal Languages
• Full AFLs and nested iterated substitution