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

DOI10.1007/978-3-540-85780-8_27MaRDI QIDQ3533023zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey 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) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Finding the growth rate of a regular or 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
• Almost tight recursion tree bounds for the Descartes method
• Bounded Algol-Like Languages
• Bounded Regular Sets
• Characterizing regular languages with polynomial densities
• Combinatorial Complexity of Regular Languages
• Computing rational forms of integer matrices
• Context-free languages of sub-exponential growth
• scientific article; zbMATH DE number 6004833 (Why is no real title available?)
• scientific article; zbMATH DE number 3880130 (Why is no real title available?)
• scientific article; zbMATH DE number 3808970 (Why is no real title available?)
• scientific article; zbMATH DE number 3978429 (Why is no real title available?)
• scientific article; zbMATH DE number 193132 (Why is no real title available?)
• scientific article; zbMATH DE number 1045405 (Why is no real title available?)
• 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
• Processing Compressed Texts: A Tractability Border
• The equation \(a_ M=b^ Nc^ P\) in a free group
• The growth function of context-free languages

Cited in

(13)

• An efficient generalized shift-rule for the prefer-max de Bruijn sequence
• Methods for the estimation of the size of lookahead tree state-space
• Prefixes of the Fibonacci word that end with a cube
• Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract)
• Finding the growth rate of a regular or context-free language in polynomial time
• A representation theorem for (q-)holonomic sequences
• The binomial equivalence classes of finite words
• A new hierarchy for automaton semigroups
• Ideals of equations for elements in a free group and context-free languages
• Computing the bandwidth of meager timed automata
• Bandwidth of timed automata: 3 classes
• Deciding regularity of hairpin completions of regular languages in polynomial time
• On the growth of linear languages

This page was built for publication: Finding the Growth Rate of a Regular of 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 Q3533023)