On the commutative equivalence of bounded context-free and regular languages: the code case

DOI10.1016/J.TCS.2014.10.005zbMath1304.68098OpenAlexW2051092114MaRDI QIDQ476875

Flavio D'Alessandro, Benedetto Intrigila

Publication date: 2 December 2014

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

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

zbMATH Keywords

semilinear setbounded context-free languagecommutative equivalence

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

On counting functions and slenderness of languages ⋮ Coding by minimal linear grammars ⋮ On the Commutative Equivalence of Algebraic Formal Series and Languages ⋮ On bounded linear codes and the commutative equivalence ⋮ On the commutative equivalence of semi-linear sets of \(\mathbb{N}^k\) ⋮ Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity ⋮ On the commutative equivalence of bounded context-free and regular languages: the semi-linear case

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the commutative equivalence of semi-linear sets of \(\mathbb{N}^k\)
• A decision method for Parikh slenderness of context-free languages
• Quasi-polynomials, linear Diophantine equations and semi-linear sets
• The Parikh counting functions of sparse context-free languages are quasi-polynomials
• Analytic models and ambiguity of context-free languages
• Decision problems concerning thinness and slenderness of formal languages
• On the structure of the counting function of sparse context-free languages.
• Semigroups, Presburger formulas, and languages
• Rational sets in commutative monoids
• On the generating sequences of regular languages on k symbols
• A characterization of poly-slender context-free languages
• There Does Not Exist a Minimal Full Trio with Respect to Bounded Context-Free Languages
• On Context-Free Languages
• On Parikh slender context-free languages

This page was built for publication: On the commutative equivalence of bounded context-free and regular languages: the code case