@inproceedings{10.1007/978-3-540-85780-8_27,
    Abstract = {We give an O(n{\thinspace}+{\thinspace}t) time algorithm to determine whether an NFA with n states and t transitions accepts a language of polynomial or exponential growth. Given a NFA accepting a language of polynomial growth, we can also determine the order of polynomial growth in O(n{\thinspace}+{\thinspace}t) time. We also give polynomial time algorithms to solve these problems for context-free grammars.},
    Address = {Berlin, Heidelberg},
    Author = {Gawrychowski, Pawe{{\l}} and Krieger, Dalia and Rampersad, Narad and Shallit, Jeffrey},
    BookTitle = {Developments in Language Theory},
    Editor = {Ito, Masami and Toyama, Masafumi},
    ISBN = {978-3-540-85780-8},
    Pages = {339--358},
    Publisher = {Springer Berlin Heidelberg},
    Title = {Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time},
    Year = {2008},
    date-added = {2023-01-11 07:42:58 +0100},
    date-modified = {2023-01-11 07:42:58 +0100},
    doi = {10.1007/978-3-540-85780-8_27}
}

@inproceedings{10.1007/978-3-540-85780-8_27, Abstract = {We give an O(n{\thinspace}+{\thinspace}t) time algorithm to determine whether an NFA with n states and t transitions accepts a language of polynomial or exponential growth. Given a NFA accepting a language of polynomial growth, we can also determine the order of polynomial growth in O(n{\thinspace}+{\thinspace}t) time. We also give polynomial time algorithms to solve these problems for context-free grammars.}, Address = {Berlin, Heidelberg}, Author = {Gawrychowski, Pawe{{\l}} and Krieger, Dalia and Rampersad, Narad and Shallit, Jeffrey}, BookTitle = {Developments in Language Theory}, Editor = {Ito, Masami and Toyama, Masafumi}, ISBN = {978-3-540-85780-8}, Pages = {339--358}, Publisher = {Springer Berlin Heidelberg}, Title = {Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time}, Year = {2008}, date-added = {2023-01-11 07:42:58 +0100}, date-modified = {2023-01-11 07:42:58 +0100}, doi = {10.1007/978-3-540-85780-8_27} }