Portal de Periódicos da CAPES

FINDING THE GROWTH RATE OF A REGULAR OR CONTEXT-FREE LANGUAGE IN POLYNOMIAL TIME

2010; World Scientific; Volume: 21; Issue: 04 Linguagem: Inglês

10.1142/s0129054110007441

1793-6373

Paweł Gawrychowski, Dalia Krieger, Narad Rampersad, JEFFREY SHALLIT,

DNA and Biological Computing

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.