Abstract
We present a constructive variant of the Hennie machine. It is demonstrated how it can facilitate the design of finite-state machines. We focus on the deterministic version of the model and study its descriptional complexity. The model’s succinctness is compared with common devices that include the nondeterministic finite automaton, two-way finite automaton and pebble automaton.
The author was supported by the Grant Agency of the Czech Republic under the project P103/10/0783.
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
Birget, J.C.: State-complexity of finite-state devices, state compressibility and incompressibility. Mathematical Systems Theory 26(3), 237–269 (1993)
Durak, B.: Two-way finite automata with a write-once track. J. Autom. Lang. Comb. 12(1), 97–115 (2007)
Globerman, N., Harel, D.: Complexity results for two-way and multi-pebble automata and their logics. Theoretical Computer Science 169, 161–184 (1996)
Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. UCS 8(2), 193–234 (2002)
Hartmanis, J.: Computational complexity of one-tape Turing machine computations. J. ACM 15(2), 325–339 (1968)
Hennie, F.: One-tape, off-line Turing machine computations. Information and Control 8(6), 553–578 (1965)
Kari, J., Moore, C.: New results on alternating and non-deterministic two-dimensional finite-state automata. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 396–406. Springer, Heidelberg (2001)
Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: SWAT (FOCS), pp. 188–191. IEEE Computer Society (1971)
Papadimitriou, C.M.: Computational complexity. Addison-Wesley, Reading (1994)
Průša, D., Mráz, F.: Two-dimensional sgraffito automata. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol. 7410, pp. 251–262. Springer, Heidelberg (2012)
Radó, T.: On non-computable functions. Bell System Technical Journal 41(3), 877–884 (1962)
Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 1–17 (2008)
Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two way finite automata. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 1978, New York, NY, USA, pp. 275–286 (1978)
Shannon, C.E.: A universal Turing machine with two internal states. Annals of Mathematics Studies 34, 157–165 (1956)
Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3(2), 198–200 (1959)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Průša, D. (2014). Weight-Reducing Hennie Machines and Their Descriptional Complexity. In: Dediu, AH., Martín-Vide, C., Sierra-Rodríguez, JL., Truthe, B. (eds) Language and Automata Theory and Applications. LATA 2014. Lecture Notes in Computer Science, vol 8370. Springer, Cham. https://doi.org/10.1007/978-3-319-04921-2_45
Download citation
DOI: https://doi.org/10.1007/978-3-319-04921-2_45
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04920-5
Online ISBN: 978-3-319-04921-2
eBook Packages: Computer ScienceComputer Science (R0)