Abstract
It is well-known that one-tape Turing machines working in linear time are no more powerful than finite automata, namely they recognize exactly the class of regular languages. We study the costs, in terms of description sizes, of the conversion of nondeterministic finite automata into equivalent linear-time one-tape deterministic machines. We prove a polynomial blowup from two-way nondeterministic finite automata into equivalent weight-reducing one-tape deterministic machines that work in linear time. The blowup remains polynomial if the tape in the resulting machines is restricted to the portion which initially contains the input. However, in this case the machines resulting from our construction are not weight reducing, unless the input alphabet is unary.
D. Průša was supported by the Czech Science Foundation, grant 16-05872S.
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
Similar content being viewed by others
Notes
- 1.
- 2.
For the sake of completeness, we mention that it is decidable whether or not a machine makes at most \(cm+d\) steps on input of length m, for any fixed \(c,d>0\) [1].
References
Gajser, D.: Verifying time complexity of turing machines. Theor. Comput. Sci. 600, 86–97 (2015)
Geffert, V., Guillon, B., Pighizzini, G.: Two-way automata making choices only at the endmarkers. Inf. Comp. 239, 71–86 (2014)
Geffert, V., Mereghetti, C., Pighizzini, G.: Converting two-way nondeterministic unary automata into simpler automata. Theor. Comput. Sci. 295(1–3), 189–203 (2003)
Hartmanis, J.: Computational complexity of one-tape Turing machine computations. J. ACM 15(2), 325–339 (1968)
Hennie, F.C.: One-tape, off-line Turing machine computations. Inf. Control 8(6), 553–578 (1965)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Boston (1979)
Hromkovič, J., Schnitger, G.: Nondeterminism versus determinism for two-way finite automata: generalizations of Sipser’s separation. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 439–451. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45061-0_36
Kapoutsis, C.A.: Nondeterminism is essential in small two-way finite automata with few reversals. Inf. Comput. 222, 208–227 (2013)
Kapoutsis, C.A.: Two-way automata versus logarithmic space. Theory Comput. Syst. 55(2), 421–447 (2014)
Kuroda, S.: Classes of languages and linear-bounded automata. Inf. Control 7(2), 207–223 (1964)
Michel, P.: An NP-complete language accepted in linear time by a one-tape Turing machine. Theor. Comput. Sci. 85(1), 205–212 (1991)
Pighizzini, G.: Nondeterministic one-tape off-line Turing machines. J. Autom. Lang. Comb. 14(1), 107–124 (2009)
Pighizzini, G.: Two-way finite automata: old and recent results. Fundam. Inform. 126(2–3), 225–246 (2013)
Průša, D.: Weight-reducing Hennie machines and their descriptional complexity. In: Dediu, A.-H., Martín-Vide, C., Sierra-Rodríguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 553–564. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-04921-2_45
Rabin, M.O., Scott, D.S.: Finite automata and their decision problems. IBM J. Res. Dev. 3(2), 114–125 (1959)
Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two way finite automata. In: STOC 1978, pp. 275–286 (1978)
Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177–192 (1970)
Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3(2), 198–200 (1959)
Sipser, M.: Lower bounds on the size of sweeping automata. J. Comput. Syst. Sci. 21(2), 195–202 (1980)
Tadaki, K., Yamakami, T., Lin, J.C.H.: Theory of one-tape linear-time Turing machines. Theor. Comput. Sci. 411(1), 22–43 (2010)
Trakhtenbrot, B.A.: Turing machine computations with logarithmic delay. Algebra I Log. 3, 33–48 (1964). (in Russian)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Guillon, B., Pighizzini, G., Prigioniero, L., Průša, D. (2018). Two-Way Automata and One-Tape Machines. In: Hoshi, M., Seki, S. (eds) Developments in Language Theory. DLT 2018. Lecture Notes in Computer Science(), vol 11088. Springer, Cham. https://doi.org/10.1007/978-3-319-98654-8_30
Download citation
DOI: https://doi.org/10.1007/978-3-319-98654-8_30
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-98653-1
Online ISBN: 978-3-319-98654-8
eBook Packages: Computer ScienceComputer Science (R0)