FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME
From MaRDI portal
Publication:3586406
DOI10.1142/S0129054110007441zbMath1206.68172OpenAlexW2073495011MaRDI QIDQ3586406
Paweł Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey O. 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
Related Items
Forward analysis and model checking for trace bounded WSTS ⋮ Computational complexity of synchronization under sparse regular constraints ⋮ Unnamed Item ⋮ When is an automatic set an additive basis? ⋮ Quantitative estimates for the size of an intersection of sparse automatic sets ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ \(F\)-sets and finite automata ⋮ Unboundedness Problems for Languages of Vector Addition Systems. ⋮ Forward Analysis and Model Checking for Trace Bounded WSTS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Automatic Sequences and Generalised Polynomials ⋮ Support of an algebraic series as the range of a recursive sequence ⋮ Additive Number Theory via Approximation by Regular Languages ⋮ Structural properties of NFAs and growth rates of nondeterminism measures ⋮ A refinement of Christol's theorem for algebraic power series
Cites Work
- Unnamed Item
- Unnamed Item
- A gap result for the norms of semigroups of matrices
- Length considerations in context-free languages
- Context-free languages of sub-exponential growth
- On the complexity of computing determinants
- Computing rational forms of integer matrices
- Efficient algorithms for deciding the type of growth of products of integer matrices
- Finite state languages
- A Second Course in Formal Languages and Automata Theory
- A characterization of poly-slender context-free languages
- On the entropy of context-free languages
