On finite-index indexed grammars and their restrictions

DOI10.1016/j.ic.2020.104613zbMath1497.68242arXiv1610.06366MaRDI 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

zbMATH Keywords

bounded languages; ET0L languages; indexed languages; semi-linearity; finite-index; full trios

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

Related Items

Grammatical characterizations of NPDAs and VPDAs with counters, Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity, Special issue: Selected papers of the 11th international conference on language and automata theory and applications, LATA 2017, On bounded linear codes and the commutative equivalence, On counting functions and slenderness of languages

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