Abstract
A CD-system of restarting automata is called strictly deterministic if all its component systems are deterministic, and if there is a unique successor system for each component. Here we show that the strictly deterministic CD-systems of restarting automata are strictly more powerful than the corresponding deterministic types of restarting automata, but that they are strictly less powerful than the corresponding deterministic types of nonforgetting restarting automata. In fact, we present an infinite hierarchy of language classes based on the number of components of strictly deterministic CD-systems of restarting automata.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Buntrock, G.: Wachsende kontext-sensitive Sprachen. Habilitationsschrift, Fakultät für Mathematik und Informatik, Universität Würzburg (1996)
Csuhaj-Varju, E., Dassow, J., Kelemen, J., Păun, G.: Grammar Systems. A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, London (1994)
Dassow, J., Păun, G., Rozenberg, G.: Grammar systems. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 2, pp. 155–213. Springer, Berlin (1997)
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)
Lautemann, C.: One pushdown and a small tape. In: K. Wagner (ed.) Dirk Siefkes zum 50. Geburtstag, Technische Universität Berlin and Universität Augsburg, pp. 42–47 (1988)
Messerschmidt, H., Otto, F.: On nonforgetting restarting automata that are deterministic and/or monotone. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol. 3967, pp. 247–258. Springer, Heidelberg (2006)
Messerschmidt, H., Otto, F.: Cooperating distributed systems of restarting automata. Intern. J. Found. Comput. Sci. (to appear)
Messerschmidt, H., Stamer, H.: Restart-Automaten mit mehreren Restart-Zuständen. In: H. Bordihn (ed.) Workshop Formale Methoden in der Linguistik und 14. Theorietag Automaten und Formale Sprachen, Proc. Institut für Informatik, Universität Potsdam, pp. 111–116 (2004)
Oliva, K., Kvĕton, P., Ondruska, R.: The computational complexity of rule-based part-of-speech tagging. In: Matoušek, V., Mautner, P. (eds.) TSD 2003. LNCS (LNAI), vol. 2807, Springer, Heidelberg (2003)
Otto, F.: Restarting automata and their relations to the Chomsky hierarchy. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 55–74. Springer, Heidelberg (2003)
Otto, F.: Restarting automata. In: Ésik, Z., Martin-Vide, C., Mitrana, V. (eds.) Recent Advances in Formal Languages and Applications, Studies in Computational Intelligence, vol. 25, pp. 269–303. Springer, Berlin (2006)
Plátek, M., Lopatková, M., Oliva, K.: Restarting automata: Motivations and applications. In: Holzer, M. (ed.) Workshop “Petrinets” und 13. Theorietag “Automaten und Formale Sprachen”, Institut für Informatik, Technische Universität München, Garching, pp. 90–96 (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Messerschmidt, H., Otto, F. (2007). Strictly Deterministic CD-Systems of Restarting Automata. In: Csuhaj-Varjú, E., Ésik, Z. (eds) Fundamentals of Computation Theory. FCT 2007. Lecture Notes in Computer Science, vol 4639. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74240-1_37
Download citation
DOI: https://doi.org/10.1007/978-3-540-74240-1_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74239-5
Online ISBN: 978-3-540-74240-1
eBook Packages: Computer ScienceComputer Science (R0)