Finding the growth rate of a regular or context-free language in polynomial time

DOI10.1142/S0129054110007441MaRDI QIDQ3586406zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit

Publication date 6 September 2010

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054110007441

zbMATH Keywords

context-free languagegrowth rateregular language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• On the growth of linear languages
• Growth rates of power-free languages
• Growth rates of complexity of power-free languages
• Growth-sensitivity of context-free languages.

Cites work

• A characterization of poly-slender context-free languages
• A gap result for the norms of semigroups of matrices
• A Second Course in Formal Languages and Automata Theory
• Computing rational forms of integer matrices
• Context-free languages of sub-exponential growth
• Efficient algorithms for deciding the type of growth of products of integer matrices
• Finite state languages
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• Introduction to algorithms
• Length considerations in context-free languages
• On the complexity of computing determinants
• On the entropy of context-free languages

Cited in

(26)

• Support of an algebraic series as the range of a recursive sequence
• Structural properties of NFAs and growth rates of nondeterminism measures
• A refinement of Christol's theorem for algebraic power series
• Computational complexity of synchronization under sparse regular constraints
• \(F\)-sets and finite automata
• Forward analysis and model checking for trace bounded WSTS
• Forward analysis and model checking for trace bounded WSTS
• Growth and ergodicity of context-free languages
• Automata theory on sliding windows
• Efficient Computation of Throughput Values of Context-Free Languages
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• When is an automatic set an additive basis?
• Unboundedness problems for languages of vector addition systems
• Automata, palindromes, and reversed subwords
• The big-O problem for labelled Markov chains and weighted automata
• The big-O problem
• Automatic sequences and generalised polynomials
• Additive Number Theory via Approximation by Regular Languages
• Widths of regular and context-free languages
• Quantitative estimates for the size of an intersection of sparse automatic sets
• Unboundedness problems for machines with reversal-bounded counters
• On the commutative equivalence of algebraic structures and related problems
• A characterization of algebraic multivariate power series with sparse support
• A graph-theoretic proof of Cobham's dichotomy for automatic sequences
• Verifying unboundedness via amalgamation
• On the growth of linear languages

This page was built for publication: Finding the growth rate of a regular or context-free language in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586406)