Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity
From MaRDI portal
Publication:1998865
DOI10.1016/j.tcs.2020.10.006zbMath1497.68252MaRDI 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
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
