The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index

DOI10.1016/0890-5401(87)90012-5zbMath0638.68067MaRDI QIDQ1099632

Brigitte Rozoy

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90012-5

zbMATH Keywords

Dyck language over one parenthesis; EDT0L system; grammar index; matrix grammar

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Hybrid modes in cooperating distributed grammar systems: Combining the \(t\)-mode with the modes \(\leqslant k\) and \(=k\), Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity, On finite-index indexed grammars and their restrictions, On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• One way finite visit automata
• Some decision problems concerning sequential transducers and checking automata
• Scattered context grammars
• A characterization of two-way deterministic classes of languages
• Finite-turn checking automata
• Semi-discrete context-free languages^†
• Deux Familles de Langages Incomparables
• Pumping Lemmas for Regular Sets
• The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable
• Parallel context-free languages
• Bounded-crossing transducers
• On the effect of the finite index restriction on several families of grammars
• Outils et résultats pour les transducteurs boustrophédons
• Parallel context-free languages
• One-way stack automata
• On the index of a context-free grammar and language
• An analog of a theorem about context-free languages
• Simple matrix languages
• Two-way sequential transductions and stack automata
• On a Special Class of Recurrent Events