zbMATH — the first resource for mathematics

On reversal bounded alternating Turing machines. (English) Zbl 0643.68065
Summary: It is known that, for one-tape nondeterministic Turing machines, S(n)- space and S(n)-reversal bounded machines (S(n)\(\geq n)\) recognize the same class of languages. We present a simulation of S(n)-space bounded alternating Turing machines (ATM) of one-tape lg * S(n)-reversal bounded ATMs. We also show that ATMs making a constant number of reversals recognize only regular languages. This shows that there is a striking difference in computational power between machines making a constant number of reversals and those making an ‘almost’ constant (i.e., lg * n) number of reversals.

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
03D10 Turing machines and related notions
Full Text: DOI
[1] Baker, B.; Book, R.V., Reversal-bounded multipushdown machines, J. comput. system sci., 8, 315-322, (1974) · Zbl 0309.68043
[2] Berman, L., Precise bound for Presburger arithmetic and the reals with addition, (), 95-99
[3] Book, R.V.; Nivat, M.; Paterson, M.S., Reversal-bounded acceptors and intersections of linear languages, SIAM J. comput., 3, 283-295, (1974) · Zbl 0292.68023
[4] Chan, T.-H., Reversal complexity of counter machines, Proc. 13th ACM-STOC, 147-157, (1981)
[5] Chandra, A.K.; Kozen, D.C.; Stockmeyer, L.J., Alternation, J. ACM, 28, 114-133, (1981) · Zbl 0473.68043
[6] Duris, P.; Galil, Z., On reversal bounded counter machines and on pushdown automata with a bound on the size of the pushdown store, Inform. and control, 54, 217-227, (1982) · Zbl 0523.68037
[7] Fischer, M.J.; Ladner, R.E., Propositional modal logic of programs, (), 286-294
[8] Fischer, P.C., The reduction of tape reversals for off-line one-tape Turing machines, J. comput. system sci., 2, 136-146, (1968) · Zbl 0199.31001
[9] Fischer, P.C.; Hartmanis, J.; Blum, M., Tape reversal complexity hierarchies, (), 373-382
[10] Ginsburg, S.; Spanier, E., Finite-turn pda, SIAM J. contr. optim., 4, 429-453, (1966) · Zbl 0147.25302
[11] Hartmanis, J., Tape-reversal bounded Turing machine computations, J. comput. system sci., 2, 117-135, (1968) · Zbl 0259.68020
[12] Ibarra, O.H., Reversal-bounded multicounter machines and their decision problems, J. ACM, 25, 116-133, (1978) · Zbl 0365.68059
[13] Kameda, T.; Vollmar, R., Note on tape reversal complexity of languages, Inform. and control, 17, 203-215, (1970) · Zbl 0196.01801
[14] Kannan, R., Towards separating nondeterministic time from deterministic time, (), 235-243
[15] Liśkiewicz, M.; Loryś, K., Reversal efficient simulation of space bounded alternating Turing machines, ()
[16] Paul, W.J.; Prauss, E.J.; Reischuk, R., On alternation, Acta inform., 14, 243-255, (1980) · Zbl 0437.68025
[17] Rytter, W.; Chrobak, M., A characterization of reversal-bounded multipushdown machine languages, Theoret. comput. sci., 36, 341-344, (1985) · Zbl 0565.68079
[18] Wagner, K.; Wechsung, G., Computational complexity, () · Zbl 0584.68061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.