Commonmark migration
Source Link

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:

  • Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
  • Or there exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.

This has been shown for instance in:

Roberto Incitti:
"The growth function of context-free languages"
Theoretical Computer Science 255 (2001), Pages 601-605

 

Martin R. Bridson, Robert H. Gilman:
"Context-Free Languages of Sub-exponential Growth"
Journal of Computer and System Sciences 64 (2002), Pages 308-310

And for a given context-free grammar, one can decide in polynomial time whether the generated language has polynomial or exponential growth:

Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
"Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time.
International Journal of Foundations of Computer Science 21 (2010), Pages 597-618

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:

  • Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
  • Or there exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.

This has been shown for instance in:

Roberto Incitti:
"The growth function of context-free languages"
Theoretical Computer Science 255 (2001), Pages 601-605

 

Martin R. Bridson, Robert H. Gilman:
"Context-Free Languages of Sub-exponential Growth"
Journal of Computer and System Sciences 64 (2002), Pages 308-310

And for a given context-free grammar, one can decide in polynomial time whether the generated language has polynomial or exponential growth:

Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
"Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time.
International Journal of Foundations of Computer Science 21 (2010), Pages 597-618

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:

  • Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
  • Or there exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.

This has been shown for instance in:

Roberto Incitti:
"The growth function of context-free languages"
Theoretical Computer Science 255 (2001), Pages 601-605

Martin R. Bridson, Robert H. Gilman:
"Context-Free Languages of Sub-exponential Growth"
Journal of Computer and System Sciences 64 (2002), Pages 308-310

And for a given context-free grammar, one can decide in polynomial time whether the generated language has polynomial or exponential growth:

Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
"Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time.
International Journal of Foundations of Computer Science 21 (2010), Pages 597-618

added 388 characters in body
Source Link
Gamow
  • 5.7k
  • 6
  • 21
  • 38

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:

  • Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
  • Or there exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.

This has been shown for instance in:

Roberto Incitti:
"The growth function of context-free languages"
Theoretical Computer Science 255, (2001), Pages 601-605

Martin R. Bridson, Robert H. Gilman:
"Context-Free Languages of Sub-exponential Growth"
Journal of Computer and System Sciences 64, (2002), Pages 308-310

And for a given context-free grammar, one can decide in polynomial time whether the generated language has polynomial or exponential growth:

Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
"Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time.
International Journal of Foundations of Computer Science 21 (2010), Pages 597-618

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:

  • Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
  • Or there exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.

This has been shown for instance in:

Roberto Incitti:
"The growth function of context-free languages"
Theoretical Computer Science 255, (2001), Pages 601-605

Martin R. Bridson, Robert H. Gilman:
"Context-Free Languages of Sub-exponential Growth"
Journal of Computer and System Sciences 64, (2002), Pages 308-310

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:

  • Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
  • Or there exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.

This has been shown for instance in:

Roberto Incitti:
"The growth function of context-free languages"
Theoretical Computer Science 255 (2001), Pages 601-605

Martin R. Bridson, Robert H. Gilman:
"Context-Free Languages of Sub-exponential Growth"
Journal of Computer and System Sciences 64 (2002), Pages 308-310

And for a given context-free grammar, one can decide in polynomial time whether the generated language has polynomial or exponential growth:

Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, Jeffrey Shallit:
"Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time.
International Journal of Foundations of Computer Science 21 (2010), Pages 597-618

added 141 characters in body
Source Link
Gamow
  • 5.7k
  • 6
  • 21
  • 38

Every context-free language has either polynomial growth or polynomialexponential growth: In. In the notation of the question poser:

  • Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
  • Or there exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.

This has been shown for instance in:

Roberto Incitti:
"The growth function of context-free languages"
Theoretical Computer Science 255, (2001), Pages 601-605

Martin R. Bridson, Robert H. Gilman:
"Context-Free Languages of Sub-exponential Growth"
Journal of Computer and System Sciences 64, (2002), Pages 308-310

Every context-free language has either polynomial growth or polynomial growth: In the notation of the question poser:

  • Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
  • Or there exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.

This has been shown for instance in:

Martin R. Bridson, Robert H. Gilman:
"Context-Free Languages of Sub-exponential Growth"
Journal of Computer and System Sciences 64, (2002), Pages 308-310

Every context-free language has either polynomial growth or exponential growth. In the notation of the question poser:

  • Either there is a polynomial $p$ so that $w_n\le p(n)$ for all $n$
  • Or there exists a $c>1$, so that $w_n\ge c^n$ for infinitely many $n$.

This has been shown for instance in:

Roberto Incitti:
"The growth function of context-free languages"
Theoretical Computer Science 255, (2001), Pages 601-605

Martin R. Bridson, Robert H. Gilman:
"Context-Free Languages of Sub-exponential Growth"
Journal of Computer and System Sciences 64, (2002), Pages 308-310

Source Link
Gamow
  • 5.7k
  • 6
  • 21
  • 38
Loading