On finite-index indexed grammars and their restrictions
From MaRDI portal
Publication:2042723
DOI10.1016/j.ic.2020.104613zbMath1497.68242arXiv1610.06366OpenAlexW3047836129MaRDI QIDQ2042723
Oscar H. Ibarra, Ian McQuillan, Flavio D'Alessandro
Publication date: 21 July 2021
Published in: Information and Computation, Language and Automata Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1610.06366
Related Items (6)
On counting functions and slenderness of languages ⋮ On the Commutative Equivalence of Algebraic Formal Series and Languages ⋮ On bounded linear codes and the commutative equivalence ⋮ Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity ⋮ Grammatical characterizations of NPDAs and VPDAs with counters ⋮ Special issue: Selected papers of the 11th international conference on language and automata theory and applications, LATA 2017
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear indexed languages
- The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index
- Reversal-bounded multipushdown machines
- On the complexity and decidability of some problems involving shuffle
- On Families of Full Trios Containing Counter Machine Languages
- On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L
- A Generalization of Linear Indexed Grammars Equivalent to Simple Context-Free Tree Grammars
- An Approach to Computing Downward Closures
- Reversal-Bounded Multicounter Machines and Their Decision Problems
- On ETOL systems of finite index
- On the effect of the finite index restriction on several families of grammars
- The equivalence of four extensions of context-free grammars
- Indexed Grammars—An Extension of Context-Free Grammars
- Nested Stack Automata
This page was built for publication: On finite-index indexed grammars and their restrictions
