On the structure of the counting function of sparse context-free languages.
From MaRDI portal
Publication:2490812
Recommendations
- The Parikh counting functions of sparse context-free languages are quasi-polynomials
- scientific article; zbMATH DE number 4033108
- On the density of regular and context-free languages
- On the commutative equivalence of bounded context-free and regular languages
- On the Density of Regular and Context-Free Languages
Cites work
- A characterization of poly-slender context-free languages
- Analytic models and ambiguity of context-free languages
- Decision problems concerning thinness and slenderness of formal languages
- scientific article; zbMATH DE number 3880130 (Why is no real title available?)
- scientific article; zbMATH DE number 5643878 (Why is no real title available?)
- scientific article; zbMATH DE number 3978429 (Why is no real title available?)
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 194009 (Why is no real title available?)
- scientific article; zbMATH DE number 1259068 (Why is no real title available?)
- scientific article; zbMATH DE number 3293666 (Why is no real title available?)
- Length considerations in context-free languages
- On a conjecture about slender context-free languages
- ON GENERALIZED SLENDERNESS OF CONTEXT-FREE LANGUAGES
- On lengths of words in context-free languages
- On Parikh slender context-free languages
- The growth function of context-free languages
Cited in
(25)- The Parikh counting functions of sparse context-free languages are quasi-polynomials
- The complexity of computing the number of strings of given length in context-free languages
- On sparse languages \(L\) such that \(LL= \Sigma^*\)
- On counting functions of languages
- 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
- Stefano Varricchio (1960-2008)
- On counting functions and slenderness of languages
- Sparse and slender subsets of monoids.
- On the commutative equivalence of bounded context-free and regular languages
- On the density of regular and context-free languages
- Comparing Complexity Functions of a Language and Its Extendable Part
- scientific article; zbMATH DE number 3978429 (Why is no real title available?)
- scientific article; zbMATH DE number 4033108 (Why is no real title available?)
- A representation theorem for (q-)holonomic sequences
- 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 differentiation functions, structure functions, and related languages of context-free grammars
- ON SPARSE 0L LANGUAGES OVER THE BINARY ALPHABET
- Semilinearity of families of languages
- Volume formula and growth rates of the balls of strings under the edit distances
- Quasi-polynomials, linear Diophantine equations and semi-linear sets
- On the context-freeness of the set of words containing overlaps
- On bounded rational trace languages
- On the separability of sparse context-free languages and of bounded rational relations
This page was built for publication: On the structure of the counting function of sparse context-free languages.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2490812)
