Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity

DOI10.1016/j.tcs.2020.10.006zbMath1497.68252OpenAlexW3093340218MaRDI QIDQ1998865

Oscar H. Ibarra, Arturo Carpi, Ian McQuillan, Flavio D'Alessandro

Publication date: 9 March 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.10.006

zbMATH Keywords

matrix grammarscounter machinesrational seriescommutative equivalenceET0L-systems

Mathematics Subject Classification ID

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

Related Items (2)

Unboundedness problems for machines with reversal-bounded counters ⋮ On the Commutative Equivalence of Algebraic Formal Series and Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The effect of end-markers on counter machines and commutativity
• On the commutative equivalence of bounded context-free and regular languages: the code case
• On the commutative equivalence of semi-linear sets of \(\mathbb{N}^k\)
• On inherently ambiguous E0L languages
• Linear indexed languages
• Analytic models and ambiguity of context-free languages
• The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index
• On ambiguity in EOL systems
• Reversal-bounded multipushdown machines
• Context-free grammar forms
• Remarks on blind and partially blind one-way multicounter machines
• On the family of finite index matrix languages
• Some decision problems concerning semilinearity and commutation.
• On finite-index indexed grammars and their restrictions
• On the commutative equivalence of bounded context-free and regular languages: the semi-linear case
• On families of full trios containing counter machine languages
• On counting functions and slenderness of languages
• On the structure of the counting function of sparse context-free languages.
• Checking automata and one-way stack languages
• Rational sets in commutative monoids
• On the generating sequences of regular languages on k symbols
• Deux Familles de Langages Incomparables
• The characterization of nonexpansive grammars by rational power series
• 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
• Inherent ambiguity of minimal linear grammars
• Finite-Turn Pushdown Automata
• On Context-Free Languages
• MULTI-PUSH-DOWN LANGUAGES AND GRAMMARS

This page was built for publication: Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity