ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS

DOI10.1142/S012905419900006XzbMath1319.68126OpenAlexW2089201742MaRDI QIDQ5248992

Henning Fernau, Gheorghe Păun, Juergen Dassow

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s012905419900006x

zbMATH Keywords

Chomsky hierarchyrecursively enumerable languagematrix grammarleftmost derivation

Mathematics Subject Classification ID

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

Related Items (5)

One-Sided Random Context Grammars with Leftmost Derivations ⋮ Solutions to four open problems concerning controlled pure grammar systems ⋮ Nonterminal complexity of programmed grammars. ⋮ On some derivation mechanisms and the complexity of their Szilard languages ⋮ On the computational completeness of generalized forbidding matrix grammars

Cites Work

• Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages
• A note on: `Deque automata and a subfamily of context-sensitive languages which contains all semilinear bounded languages' (by K. Ayers)
• Multiple equality sets and Post machines
• A note on morphic characterization of languages
• Reversal-bounded multipushdown machines
• On representing recursively enumerable languages by internal contextual languages
• Petri net algorithms in the theory of matrix grammars
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• The Power of the Queue
• Programmed Grammars and Classes of Formal Languages
• Matrix grammars with a leftmost restriction
• Simple matrix languages with a leftmost restriction
• Computability of Recursive Functions

This page was built for publication: ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS