The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index
From MaRDI portal
Publication:1099632
DOI10.1016/0890-5401(87)90012-5zbMath0638.68067OpenAlexW2026265861MaRDI QIDQ1099632
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
Related Items (4)
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
This page was built for publication: The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index
