SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS
Óscar H. Ibarra, Bala Ravikumar · International Journal of Foundations of Computer Science · 2014
Almost all the decision questions concerning the resource requirements of a computational device are undecidable. Here we want to understand the exact boundary that separates the undecidable from the decidable cases of such problems by considering the time complexity of very simple devices that include NFAs (1-way and 2-way), PDAs and PDAs augmented with counters - and their unambiguous restrictions. We consider several variations - based on whether the bound holds exactly or as an upper-bound and show decidability as well as undecidability results. In the case of decidable problems, we also attempt to determine more precisely the complexity class to which the problem belongs.