A Complete Taxonomy of Restarting Automata without Auxiliary Symbols

• Autorzy: Otto Friedrich

Identyfikatory

DOI

10.3233/FI-2021-2035

• Języki publikacji: EN

Abstrakty

EN

A complete taxonomy is presented for restarting automata without auxiliary symbols. In this taxonomy, the language classes that are accepted by deterministic and nondeterministic, monotone, weakly monotone, and non-monotone, shrinking and length-reducing restarting automata are compared to each other with respect to inclusion. As it turns out, the 45 types of restarting automata considered yield 29 different classes of languages. By presenting a collection of rather simple example languages, it is shown that, for any two of these language classes ℒ₁ and ℒ₂, the class ℒ₁ is a subclass of ℒ₂ if and only if ℒ₁ is defined by a type of restarting automaton that is a restriction of a type of restarting automaton that defines the class ℒ₂.

Słowa kluczowe

EN

taxonomy; foreign language education; robots; language schools

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 180, nr 1-2
• Strony: 77--101
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Otto Friedrich

• Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany

Bibliografia

• [1] Otto F. On shrinking restarting automata. In: Freund R, Mráz F, Průša D (eds.), Ninth Workshop on Non-Classical Models of Automata and Applications (NCMA 2017), Proc., volume 329 of [e-mail], Österreichische Computer Gesellschaft, Wien 2017 pp. 181-195.
• [2] Jančar P, Mráz F, Plátek M, Vogel J. Restarting automata. In: Reichel H (ed.), FCT’95, Proc., Lecture Notes in Computer Science 965, pp. 283-292. Springer, Berlin, 1995. doi:10.1007/3-540-60249-6_60.
• [3] Plátek M. Two-way restarting automata and j-monotonicity. In: Pacholski L, Ružička P (eds.), SOFSEM 2001, Proc., Lecture Notes in Computer Science 2234, Springer, Berlin 2001 pp. 316-325. doi:10.1007/3-540-45627-9_28.
• [4] Otto F. Restarting automata. In: Ésik Z, Martín-Vide C, Mitrana V (eds.), Recent Advances in Formal Languages and Applications, volume 25 of Studies in Computational Intelligence, Springer, Berlin 2006 pp. 269-303.
• [5] McNaughton R, Narendran P, Otto F. Church-Rosser Thue systems and formal languages. Journal of the Association for Computing Machinery, 1988. 35:324-344. doi:10.1145/42282.42284.
• [6] Niemann G, Otto F. Restarting automata, Church-Rosser languages, and representations of r.e. languages. In: Rozenberg G, Thomas W (eds.), Developments in Language Theory-Foundations, Applications, and Perspectives, DLT 1999, Proc., pp. 103-114. World Scientific, Singapore, 2000.
• [7] Niemann G, Otto F. Further results on restarting automata. In: Ito M, Imaoka T (eds.), Words, Languages and Combinatorics III, Proc., World Scientific, Singapore 2003 pp. 352-369. doi:10.1142/9789812704979_0027.
• [8] Jančar P, Mráz F, Plátek M, Vogel J. On monotonic automata with a restart operation. Journal of Automata, Languages and Combinatorics, 1999. 4:287-311. doi:10.25596/jalc-1999-287.
• [9] Dahlhaus E, Warmuth M. Membership for growing context-sensitive grammars is polynomial. Journal of Computer and System Sciences, 1986. 33:456-472. doi:10.1016/0022-0000(86)90062-0.
• [10] Jurdziński T, Loryś K, Niemann G, Otto F. Some results on RWW- and RRWW-automata and their relation to the class of growing context-sensitive languages. Journal of Automata, Languages and Combinatorics, 2004. 9:407-437. doi:10.25596/jalc-2004-407.
• [11] Otto F. Restarting automata and their relations to the Chomsky hierarchy. In: Ésik Z, Fülöp Z (eds.), DLT 2003, Proc., Lecture Notes in Computer Science 2710, pp. 55-74. Springer, Berlin, 2003. doi:10.1007/3-540-45007-6_5.
• [12] Otto F, Jurdziński T. On left-monotone restarting automata. Mathematische Schriften Kassel 17/03, Universität Kassel, 2003.
• [13] Jurdziński T, Otto F. Shrinking restarting automata. International Journal of Foundations of Computer Science, 2007. 18:361-385. doi:10.1142/S0129054107004723.
• [14] Buntrock G, Otto F. Growing context-sensitive languages and Church-Rosser languages. Information and Computation, 1998. 141:1-36.
• [15] Buntrock G, Loryś K. On growing context-sensitive languages. In: Kuich W (ed.), ICALP’92, Proc., Lecture Notes in Computer Science 623, pp. 77-88. Springer, Berlin, 1992. doi:10.1007/3-540-55719-9_65.
• [16] Book R, Otto F. String-Rewriting Systems. Springer, New York, 1993. doi:10.1007/978-1-4613-9771-7_3.
• [17] Čulik, II K, Cohen R. LR-regular grammars - an extension of LR(k) grammars. Journal of Computer and System Sciences, 1973. 7:66-96. doi:10.1016/S0022-0000(73)80050-9.
• [18] Buntrock G. Wachsende kontext-sensitive Sprachen. Habilitationsschrift, Fakultät für Mathematik und Informatik, Universität Würzburg, 1996. (In German).
• [19] Lautemann C. One pushdown and a small tape. In: Wagner K (ed.), Dirk Siefkes zum 50. Geburtstag, pp. 42-47. Technische Universität Berlin and Universität Augsburg, 1988.
• [20] Niemann G, Otto F. The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages. Information and Computation, 2005. 197:1-21.
• [21] Jurdziński T, Mráz F, Otto F, Plátek M. Degrees of non-monotonicity for restarting automata. Theoretical Computer Science, 2006. 369:1-34. doi:10.1016/j.tcs.2006.08.029.
• [22] Jurdziński T, Mráz F, Otto F, Plátek M. Monotone deterministic RL-automata don’t need auxiliary symbols. In: De Felice C, Restivo A (eds.), DLT 2005, Proc., Lecture Notes in Computer Science 3572, Springer, Berlin, 2005 pp. 284-295. doi:10.1007/11505877_25.
• [23] Otto F. Left-to-right regular languages and two-way restarting automata. RAIRO-Theoretical Informatics and Applications, 2009. 43:653-665. doi:10.1051/ita/2009013.
• [24] Mráz F, Otto F. Hierarchies of weakly monotone restarting automata. RAIRO-Theoretical Informatics and Applications, 2005. 39:325-342. doi:10.1051/ita:2005021.
• [25] Jurdziński T, Otto F, Mráz F, Plátek M. On the complexity of 2-monotone restarting automata. Theory of Computing Systems, 2008. 42:488-518. doi:10.1007/s00224-007-9004-y.
• [26] Jurdziński T, Loryś K. Lower bound technique for length-reducing automata. Information and Computation, 2007. 205:1387-1412. doi:10.1016/j.ic.2007.02.003.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).