Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time

DOI10.1007/978-3-540-85780-8_27zbMath1161.68528OpenAlexW1774334694MaRDI QIDQ3533023

Dalia Krieger, Narad Rampersad, Paweł Gawrychowski, Jeffrey O. Shallit

Publication date: 30 October 2008

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85780-8_27

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

Methods for the estimation of the size of lookahead tree state-space, A representation theorem for (\(q\)-)holonomic sequences, Ideals of equations for elements in a free group and context-free languages, Prefixes of the Fibonacci word that end with a cube, Deciding regularity of hairpin completions of regular languages in polynomial time, An efficient generalized shift-rule for the prefer-max de Bruijn sequence, Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract), The binomial equivalence classes of finite words, A New Hierarchy for Automaton Semigroups

Cites Work

• A gap result for the norms of semigroups of matrices
• The equation \(a_ M=b^ Nc^ P\) in a free group
• 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
• Almost tight recursion tree bounds for the Descartes method
• Combinatorial Complexity of Regular Languages
• Processing Compressed Texts: A Tractability Border
• A characterization of poly-slender context-free languages
• Characterizing regular languages with polynomial densities
• Bounded Algol-Like Languages
• Bounded Regular Sets
• The growth function of context-free languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item