{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T11:20:23Z","timestamp":1758280823401,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540857792"},{"type":"electronic","value":"9783540857808"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-85780-8_27","type":"book-chapter","created":{"date-parts":[[2008,9,9]],"date-time":"2008-09-09T05:23:54Z","timestamp":1220937834000},"page":"339-358","source":"Crossref","is-referenced-by-count":6,"title":["Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"first","affiliation":[]},{"given":"Dalia","family":"Krieger","sequence":"additional","affiliation":[]},{"given":"Narad","family":"Rampersad","sequence":"additional","affiliation":[]},{"given":"Jeffrey","family":"Shallit","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.laa.2004.12.007","volume":"402","author":"J. Bell","year":"2005","unstructured":"Bell, J.: A gap result for the norms of semigroups of matrices. Linear Algebra Appl.\u00a0402, 101\u2013110 (2005)","journal-title":"Linear Algebra Appl."},{"key":"27_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1006\/jcss.2001.1804","volume":"64","author":"M. Bridson","year":"2002","unstructured":"Bridson, M., Gilman, R.: Context-free languages of sub-exponential growth. J. Comput. System Sci.\u00a064, 308\u2013310 (2002)","journal-title":"J. Comput. System Sci."},{"key":"27_CR3","volume-title":"Introduction to Algorithms","author":"T. Cormen","year":"2001","unstructured":"Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Eigenwillig, A., Sharma, V., Yap, C.K.: Almost tight recursion tree bounds for the Descartes method. In: ISSAC 2006, pp. 71\u201378 (2006)","DOI":"10.1145\/1145768.1145786"},{"key":"27_CR5","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1006\/jsco.2002.0554","volume":"34","author":"M. Giesbrecht","year":"2002","unstructured":"Giesbrecht, M., Storjohann, A.: Computing rational forms of integer matrices. J. Symbolic Comput.\u00a034, 157\u2013172 (2002)","journal-title":"J. Symbolic Comput."},{"key":"27_CR6","volume-title":"The Mathematical Theory of Context-free Languages","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg, S.: The Mathematical Theory of Context-free Languages. McGraw-Hill, New York (1966)"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"333","DOI":"10.2307\/1994067","volume":"113","author":"S. Ginsburg","year":"1964","unstructured":"Ginsburg, S., Spanier, E.: Bounded ALGOL-like languages. Trans. Amer. Math. Soc.\u00a0113, 333\u2013368 (1964)","journal-title":"Trans. Amer. Math. Soc."},{"key":"27_CR8","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.2307\/2036087","volume":"17","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg, S., Spanier, E.: Bounded regular sets. Proc. Amer. Math. Soc.\u00a017, 1043\u20131049 (1966)","journal-title":"Proc. Amer. Math. Soc."},{"key":"27_CR9","series-title":"Lecture Notes in Computer Science","first-page":"171","volume-title":"STACS 86","author":"O. Ibarra","year":"1985","unstructured":"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.\u00a0210, pp. 171\u2013179. Springer, Heidelberg (1985)"},{"key":"27_CR10","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1051\/ita:2000100","volume":"34","author":"L. Ilie","year":"2000","unstructured":"Ilie, L., Rozenberg, G., Salomaa, A.: A characterization of poly-slender context-free languages. Theoret. Informatics Appl.\u00a034, 77\u201386 (2000)","journal-title":"Theoret. Informatics Appl."},{"key":"27_CR11","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1016\/S0304-3975(00)00152-3","volume":"225","author":"R. Incitti","year":"2001","unstructured":"Incitti, R.: The growth function of context-free languages. Theoret. Comput. Sci.\u00a0225, 601\u2013605 (2001)","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR12","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s00037-004-0185-3","volume":"13","author":"E. Kaltofen","year":"2004","unstructured":"Kaltofen, E., Villard, G.: On the complexity of computing determinants. Comput. Complex.\u00a013, 91\u2013130 (2004)","journal-title":"Comput. Complex."},{"key":"27_CR13","first-page":"172","volume":"4","author":"M. Karpinski","year":"1997","unstructured":"Karpinski, M., Rytter, W., Shinohara, A.: An efficient pattern-matching algorithm for strings with short descriptions. Nordic Journal of Computing\u00a04, 172\u2013186 (1997)","journal-title":"Nordic Journal of Computing"},{"key":"27_CR14","first-page":"3","volume":"20","author":"M. Latteux","year":"1984","unstructured":"Latteux, M., Thierrin, G.: On bounded context-free languages. Elektron. Informationsverarb. Kybernet.\u00a020, 3\u20138 (1984)","journal-title":"Elektron. Informationsverarb. Kybernet."},{"key":"27_CR15","unstructured":"Lifshits, Y.: Solving classical string problems on compressed texts. In: CPM 2007, pp. 228\u2013240 (2007)"},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1307\/mmj\/1028998766","volume":"9","author":"R.C. Lyndon","year":"1962","unstructured":"Lyndon, R.C., Sch\u00fctzenberger, M.-P.: The equation a\n                           \n                    M\n                  \u2009=\u2009b\n                           \n                    N\n                  \n                           c\n                           \n                    P\n                   in a free group. Michigan Math. J.\u00a09, 289\u2013298 (1962)","journal-title":"Michigan Math. J."},{"key":"27_CR17","volume-title":"Nonnegative Matrices","author":"H. Minc","year":"1988","unstructured":"Minc, H.: Nonnegative Matrices. Wiley, Chichester (1988)"},{"key":"27_CR18","unstructured":"Plandowski, W.: The Complexity of the Morphism Equivalence Problem for Context-Free Languages, PhD thesis"},{"key":"27_CR19","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(96)00308-8","volume":"183","author":"D. Raz","year":"1997","unstructured":"Raz, D.: Length considerations in context-free languages. Theoret. Comput. Sci.\u00a0183, 21\u201332 (1997)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"27_CR20","first-page":"78","volume":"1 12","author":"A.M. Shur","year":"2005","unstructured":"Shur, A.M.: Combinatorial complexity of rational languages. Discr. Anal. and Oper. Research, Ser.\u00a01 12(2), 78\u201399 (2005)","journal-title":"Discr. Anal. and Oper. Research, Ser."},{"key":"27_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/978-3-540-79709-8_30","volume-title":"Computer Science \u2013 Theory and Applications","author":"A.M. Shur","year":"2008","unstructured":"Shur, A.M.: Combinatorial complexity of regular languages. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) Computer Science \u2013 Theory and Applications. LNCS, vol.\u00a05010, pp. 289\u2013301. Springer, Heidelberg (2008)"},{"key":"27_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1007\/3-540-55808-X_48","volume-title":"Mathematical Foundations of Computer Science 1992","author":"A. Szilard","year":"1992","unstructured":"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.\u00a0629, pp. 494\u2013503. Springer, Heidelberg (1992)"},{"key":"27_CR23","first-page":"9","volume":"6","author":"V.I. Trofimov","year":"1981","unstructured":"Trofimov, V.I.: Growth functions of some classes of languages. Cybernetics\u00a06, 9\u201312 (1981)","journal-title":"Cybernetics"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85780-8_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,6]],"date-time":"2023-02-06T21:30:56Z","timestamp":1675719056000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-85780-8_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540857792","9783540857808"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85780-8_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}