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

Gawrychowski, P., Krieger, D., Rampersad, N., & Shallit, J. (2008). Finding the Growth Rate of a Regular or Context-Free Language in Polynomial Time. DLT 2008.

Type

Book chapter

Intellectual base

Review or monograph

Year

2008

DOI

10.1007/978-3-540-85780-8_27

ISBN

9783540857792

Link

https://doi.org/10.1007/978-3-540-85780-8_27

Cited by

1 citation across 1 artifact.

Domain-specific

• Factor Complexity Function
  • Regular languages exhibit a polynomial-versus-exponential growth dichotomy; polynomial-density regular languages admit constrained repeated-block forms.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:bb8a0e0e7d91 · see in the full table