Abstract
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), NPDAs and NPDAs 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. We also introduce a stronger version of machine equivalence (known as run-time equivalence) and identify classes of machines for which run-time equivalence is decidable (undecidable). In the case of decidable problems, we also attempt to determine more precisely the complexity class to which the problem belongs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baker, B., Book, R.: Reversal-bounded multipushdown machines. J. Comput. Syst. Sci. 8, 315–332 (1974)
Chan, T., Ibarra, O.H.: On the finite-valuedness problem for sequential machines. Theor. Comput. Sci. 23, 95–101 (1983)
Cui, C., Dang, Z., Fischer, T.R., Ibarra, O.H.: Similarity in languages and programs (submitted)
Chatterjee, K., Doyen, L., Henzinger, T.A.: Quantitative Languages. ACM Transactions on Computational Logic (2010)
Ginsburg, S., Greibach, S.A., Harrison, M.A.: One-way stack automata. J. ACM 14, 389–418 (1967)
Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. Journal of Universal Computer Science 8(2), 193–234 (2002)
Greibach, S.A.: A new normal-Form theorem for context-free phrase structure grammars. J. ACM 12, 42–52 (1965)
Gurari, E., Ibarra, O.H.: The complexity of decision problems for finite-turn multicounter machines. J. Comput. Syst. Sci. 22, 220–229 (1981)
Gurari, E., Ibarra, O.H.: A note on finite-valued and finitely ambiguous transducers. Math. Systems Theory 16, 61–66 (1983)
Harju, T., Karhumaki, J.: The equivalence problem of multitape finite automata. Theor. Comput. Sci. 78, 347–355 (1991)
Hashiguchi, K.: Limitedness theorem on finite automata with distance functions. J. Comput. Syst. Sci. 24, 233–244 (1982)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley Publishing Company (1979)
Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. ACM 25, 116–133 (1978)
Ibarra, O.H.: The unsolvability of the equivalence problem for ε-free NGSM’s with unary input (output) alphabet and applications. SIAM J. Computing 7, 524–532 (1978)
Ibarra, O.H., Jiang, T., Tran, N.Q., Wang, H.: New decidability results concerning two-way counter machines and applications. SIAM J. Comput. 24, 123–137 (1995)
Kozen, D.: Lower bounds for natural proof systems. In: IEEE Conf. on Foundations of Computer Science, pp. 254–266 (1977)
Leung, H., Podolskiy, V.: The limitedness problem on distance automata: Hashiguchi’s method revisited. Theor. Comput. Sci. 310, 147–158 (2004)
Minsky, M.: Recursive unsolvability of Post’s problem of Tag and other topics in the theory of Turing machines. Ann. of Math. 74, 437–455 (1961)
Stearns, R., Hunt, H.: On the equivalence and containment problems for unambiguous regular expressions, grammars and automata. SIAM Journal on Computing 14, 598–611 (1985)
Turing, A.M.: On Computable numbers, with an application to the Entscheidungsproblem. Proc. London Math. Soc., s2 42, 230–265 (1937)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ibarra, O.H., Ravikumar, B. (2013). Some Decision Questions Concerning the Time Complexity of Language Acceptors. In: Béal, MP., Carton, O. (eds) Developments in Language Theory. DLT 2013. Lecture Notes in Computer Science, vol 7907. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38771-5_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-38771-5_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38770-8
Online ISBN: 978-3-642-38771-5
eBook Packages: Computer ScienceComputer Science (R0)