@article{Gawrychowski:Krieger:Rampersad:Shallit:IJFCS:2010,
    Abstract = {We give an O(n + t) time algorithm to determine whether an NFA with n states and t transitions accepts a language of polynomial or exponential growth. Given an NFA accepting a language of polynomial growth, we can also determine the order of polynomial growth in O(n+t) time. We also give polynomial time algorithms to solve these problems for context-free grammars.},
    Author = {Gawrychowski, Pawe\l and Krieger, Dalia and Rampersad, Narad and Shallit, Jeffrey},
    EPrint = {https://doi.org/10.1142/S0129054110007441},
    File = {FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME - a.pdf},
    Journal = {International Journal of Foundations of Computer Science},
    Number = {04},
    Pages = {597--618},
    Title = {FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME},
    URL = {https://doi.org/10.1142/S0129054110007441},
    Volume = {21},
    Year = {2010},
    bdsk-url-1 = {https://doi.org/10.1142/S0129054110007441},
    date-added = {2023-01-11 07:43:35 +0100},
    date-modified = {2023-01-16 11:27:58 +0100},
    doi = {10.1142/S0129054110007441}
}

@article{Gawrychowski:Krieger:Rampersad:Shallit:IJFCS:2010, Abstract = {We give an O(n + t) time algorithm to determine whether an NFA with n states and t transitions accepts a language of polynomial or exponential growth. Given an NFA accepting a language of polynomial growth, we can also determine the order of polynomial growth in O(n+t) time. We also give polynomial time algorithms to solve these problems for context-free grammars.}, Author = {Gawrychowski, Pawe\l and Krieger, Dalia and Rampersad, Narad and Shallit, Jeffrey}, EPrint = {https://doi.org/10.1142/S0129054110007441}, File = {FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME - a.pdf}, Journal = {International Journal of Foundations of Computer Science}, Number = {04}, Pages = {597--618}, Title = {FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME}, URL = {https://doi.org/10.1142/S0129054110007441}, Volume = {21}, Year = {2010}, bdsk-url-1 = {https://doi.org/10.1142/S0129054110007441}, date-added = {2023-01-11 07:43:35 +0100}, date-modified = {2023-01-16 11:27:58 +0100}, doi = {10.1142/S0129054110007441} }