Finite turns and the regular closure of linear context-free languages

DOI10.1016/j.dam.2007.05.021zbMath1123.68062OpenAlexW2037800309MaRDI QIDQ2384399

Andreas Malcher, Martin Kutrib

Publication date: 21 September 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.05.021

zbMATH Keywords

context-free languagescomputational capacityclosures of languagestime-efficient recognizersfinite turn pushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (11)

IN MEMORIAM CHANDRA KINTALA ⋮ On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems ⋮ Context-dependent nondeterminism for pushdown automata ⋮ Investigations on the power of matrix insertion-deletion systems with small sizes ⋮ On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2 ⋮ On bounded languages and reversal-bounded automata ⋮ Formal grammars for turn-bounded deterministic context-free languages ⋮ Kernels of Sub-classes of Context-Free Languages ⋮ On Extended Regular Expressions ⋮ Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems ⋮ Boolean kernels of context-free languages

Cites Work

• Parallel parsing on a one-way linear array of finite-state machines
• Derivation-bounded languages
• Real-time language recognition by one-dimensional cellular automata
• Turn-bounded grammars and their relation to ultralinear languages
• Regular Closure of Deterministic Languages
• On The Space Complexity Of Turn Bounded Pushdown Automata
• Finite-Turn Pushdown Automata
• An Infinite Hierarchy of Context-Free Languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Finite turns and the regular closure of linear context-free languages