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

1. Bell, J.: A gap result for the norms of semigroups of matrices. Linear Algebra Appl. 402, 101–110 (2005)

   Article  MATH  MathSciNet  Google Scholar 

2. Bridson, M., Gilman, R.: Context-free languages of sub-exponential growth. J. Comput. System Sci. 64, 308–310 (2002)

   Article  MATH  MathSciNet  Google Scholar 

3. Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)

   MATH  Google Scholar 

4. Eigenwillig, A., Sharma, V., Yap, C.K.: Almost tight recursion tree bounds for the Descartes method. In: ISSAC 2006, pp. 71–78 (2006)

   Google Scholar 

5. Giesbrecht, M., Storjohann, A.: Computing rational forms of integer matrices. J. Symbolic Comput. 34, 157–172 (2002)

   Article  MATH  MathSciNet  Google Scholar 

6. Ginsburg, S.: The Mathematical Theory of Context-free Languages. McGraw-Hill, New York (1966)

   MATH  Google Scholar 

7. Ginsburg, S., Spanier, E.: Bounded ALGOL-like languages. Trans. Amer. Math. Soc. 113, 333–368 (1964)

   Article  MATH  MathSciNet  Google Scholar 

8. Ginsburg, S., Spanier, E.: Bounded regular sets. Proc. Amer. Math. Soc. 17, 1043–1049 (1966)

   Article  MATH  MathSciNet  Google Scholar 

9. Ibarra, O., Ravikumar, B.: On sparseness, ambiguity and other decision problems for acceptors and transducers. In: Monien, B., Vidal-Naquet, G. (eds.) STACS 1986. LNCS, vol. 210, pp. 171–179. Springer, Heidelberg (1985)

   Google Scholar 

10. Ilie, L., Rozenberg, G., Salomaa, A.: A characterization of poly-slender context-free languages. Theoret. Informatics Appl. 34, 77–86 (2000)

    Article  MATH  MathSciNet  Google Scholar 

11. Incitti, R.: The growth function of context-free languages. Theoret. Comput. Sci. 225, 601–605 (2001)

    Article  MathSciNet  Google Scholar 

12. Kaltofen, E., Villard, G.: On the complexity of computing determinants. Comput. Complex. 13, 91–130 (2004)

    Article  MATH  MathSciNet  Google Scholar 

13. Karpinski, M., Rytter, W., Shinohara, A.: An efficient pattern-matching algorithm for strings with short descriptions. Nordic Journal of Computing 4, 172–186 (1997)

    MATH  MathSciNet  Google Scholar 

14. Latteux, M., Thierrin, G.: On bounded context-free languages. Elektron. Informationsverarb. Kybernet. 20, 3–8 (1984)

    MATH  MathSciNet  Google Scholar 

15. Lifshits, Y.: Solving classical string problems on compressed texts. In: CPM 2007, pp. 228–240 (2007)

    Google Scholar 

16. Lyndon, R.C., Schützenberger, M.-P.: The equation a ^M = b ^N c ^P in a free group. Michigan Math. J. 9, 289–298 (1962)

    Article  MATH  MathSciNet  Google Scholar 

17. Minc, H.: Nonnegative Matrices. Wiley, Chichester (1988)

    MATH  Google Scholar 

18. Plandowski, W.: The Complexity of the Morphism Equivalence Problem for Context-Free Languages, PhD thesis

    Google Scholar 

19. Raz, D.: Length considerations in context-free languages. Theoret. Comput. Sci. 183, 21–32 (1997)

    Article  MATH  MathSciNet  Google Scholar 

20. Shur, A.M.: Combinatorial complexity of rational languages. Discr. Anal. and Oper. Research, Ser. 1 12(2), 78–99 (2005)

    MathSciNet  Google Scholar 

21. Shur, A.M.: Combinatorial complexity of regular languages. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) Computer Science – Theory and Applications. LNCS, vol. 5010, pp. 289–301. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

22. Szilard, A., Yu, S., Zhang, K., Shallit, J.: Characterizing regular languages with polynomial densities. In: Havel, I.M., Koubek, V. (eds.) MFCS 1992. LNCS, vol. 629, pp. 494–503. Springer, Heidelberg (1992)

    Google Scholar 

23. Trofimov, V.I.: Growth functions of some classes of languages. Cybernetics 6, 9–12 (1981)

    MathSciNet  Google Scholar 

Download references