On Bounded Semilinear Languages, Counter Machines, and Finite-Index ET0L

DOI10.1007/978-3-319-40946-7_12zbMath1475.68156OpenAlexW2479035751MaRDI QIDQ2830214

Oscar H. Ibarra, Ian McQuillan

Publication date: 9 November 2016

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-40946-7_12

Mathematics Subject Classification ID

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

Related Items

On store languages and applications ⋮ On counting functions and slenderness of languages ⋮ On finite-index indexed grammars and their restrictions ⋮ On Families of Full Trios Containing Counter Machine Languages ⋮ On families of full trios containing counter machine languages

Cites Work

• Unnamed Item
• Unnamed Item
• The effect of end-markers on counter machines and commutativity
• Linear indexed languages
• The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index
• Reversal-bounded multipushdown machines
• Remarks on blind and partially blind one-way multicounter machines
• Some decision problems concerning semilinearity and commutation.
• 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
• CHARACTERIZATIONS OF BOUNDED SEMILINEAR LANGUAGES BY ONE-WAY AND TWO-WAY DETERMINISTIC MACHINES
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS