Abstract
Stateless deterministic ordered restarting automata characterize the class of regular languages. Here we introduce a notion of reversibility for these automata and show that each regular language is accepted by such a reversible stateless deterministic ordered restarting automaton. We study the descriptional complexity of these automata, showing that they are exponentially more succinct than nondeterministic finite-state acceptors. We also look at the case of unary input alphabets.
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
Bennett, C.H.: Logical reversibiliy of computation. IBM J. Res. Dev. 17, 525–532 (1973)
Chrobak, M.: Finite automata and unary languages. Theoretical Computer Science 47, 149–158 (1986)
Ellul, K.: Descriptional complexity measures of regular languages. Master’s thesis, University of Waterloo (2004)
Jančar, P., Mráz, F., Plátek, M., Vogel, J.: Restarting automata. In: Reichel, H. (ed.) FCT 1995. LNCS, vol. 965, pp. 283–292. Springer, Heidelberg (1995)
Kutrib, M., Malcher, A.: Reversible pushdown automata. J. Comput. System Sci. 78, 1814–1827 (2012)
Kutrib, M., Malcher, A., Wendlandt, M.: Reversible queue automata. In: Bensch, S., Freund, R., Otto, F., (eds.) Proc. Sixth Workshop on Non-Classical Models of Automata and Applications \((\)NCMA 2014\()\), books@ocg.at, Band 304, pp. 163–178. Oesterreichische Computer Gesellschaft, Wien (2014)
Kwee, K., Otto, F.: On some decision problems for stateless deterministic ordered restarting automata. In: Shallit, J., Okhotin, A. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 165–176. Springer, Heidelberg (2015)
Landau, E.: Über die Maximalordnung der Permutationen gegebenen Grades. Archiv. der Math. und Phys. 3, 92–103 (1903)
Landau, E.: Handbuch von der Lehre der Verteilung der Primzahlen, vol. I. Teubner, Leipzig (1909)
Mráz, F., Otto, F.: Ordered restarting automata for picture languages. In: Geffert, V., Preneel, B., Rovan, B., Štuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol. 8327, pp. 431–442. Springer, Heidelberg (2014)
Otto, F.: Restarting automata. In: Ésik, Z., Martín-Vide, C., Mitrana, V. (eds.) Recent Advances in Formal Languages and Applications. Studies in Computational Intelligence, vol. 25, pp. 269–303. Springer, Heidelberg (2006)
Otto, F.: On the descriptional complexity of deterministic ordered restarting automata. In: Jürgensen, H., Karhumäki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 318–329. Springer, Heidelberg (2014)
Pin, J.-E.: On reversible automata. In: Simon, I. (ed.) LATIN 1992. LNCS, vol. 583, pp. 401–416. Springer, Heidelberg (1992)
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, Heidelberg (2014)
Szalay, M.: On the maximal order in \({S}_n\) and \({S}_n^*\). Acta Arithmetica 37, 321–331 (1980)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Otto, F., Wendlandt, M., Kwee, K. (2015). Reversible Ordered Restarting Automata. In: Krivine, J., Stefani, JB. (eds) Reversible Computation. RC 2015. Lecture Notes in Computer Science(), vol 9138. Springer, Cham. https://doi.org/10.1007/978-3-319-20860-2_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-20860-2_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-20859-6
Online ISBN: 978-3-319-20860-2
eBook Packages: Computer ScienceComputer Science (R0)