Languages Accepted by Weighted Restarting Automata

• Autorzy: Wang Qichao

Identyfikatory

DOI

10.3233/FI-2021-2038

• Języki publikacji: EN

Abstrakty

EN

Weighted restarting automata have been introduced to study quantitative aspects of computations of restarting automata. In earlier works we studied the classes of functions and relations that are computed by weighted restarting automata. Here we use them to define classes of formal languages by restricting the weight associated to a given input word through an additional requirement. In this way, weighted restarting automata can be used as language acceptors. First, we show that by using the notion of acceptance relative to the tropical semiring, we can avoid the use of auxiliary symbols. Furthermore, a certain type of word-weighted restarting automata turns out to be equivalent to non-forgetting restarting automata, and another class of languages accepted by word-weighted restarting automata is shown to be closed under the operation of intersection. This is the first result that shows that a class of languages defined in terms of a quite general class of restarting automata is closed under intersection. Finally, we prove that the restarting automata that are allowed to use auxiliary symbols in a rewrite step, and to keep on reading after performing a rewrite step can be simulated by regular-weighted restarting automata that cannot do this.

Słowa kluczowe

EN

weighted restarting automata; non-forgetting restarting automata; semiring; relative acceptance condition; closure properties

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

Twórcy

autor

Wang Qichao

• College of Computer Science, Shaanxi Normal University, Xi’an, China
• Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin, China

Bibliografia

• [1] Wang Q, Otto F. Weighted Restarting Automata as Language Acceptors. In: Han Y, Salomaa K (eds.), Proceedings of the 21st International Conference on Implementation and Application of Automata, volume 9705 of Lecture Notes in Computer Science. Springer, Switzerland, 2016 pp. 298-309. doi:10.1007/978-3-319-40946-7_25.
• [2] Wang Q. On the expressive power of weighted restarting automata. In: Freund R, Mráz F, Prusa D (eds.), Proceedings of the Ninth Workshop on Non-Classical Models of Automata and Applications, volume 329 of [e-mail]. Österreichische Computer Gesellschaft, 2017 pp. 227-241.
• [3] Wang Q. Weighted Restarting Automata. Ph.D. thesis, Fachbereich Elektrotechnik/Informatik, University of Kassel, Germany, 2018.
• [4] Jancar P, Mráz F, Plátek M, Vogel J. Restarting Automata. In: Reichel H (ed.), Proceedings of the 11th International Symposium on Fundamentals of Computation Theory, volume 965 of Lecture Notes in Computer Science. Springer, Heidelberg, 1995 pp. 283-292. doi:10.1007/3-540-60249-6_60.
• [5] Otto F, Wang Q. Weighted restarting automata. Soft Computing, 2018. 22(4):1067-1083. doi:10.1007/s00500-016-2164-4.
• [6] Wang Q, Hundeshagen N, Otto F. Weighted restarting automata and pushdown relations. In: Maletti A (ed.), Proceedings of the 6th International Conference on Algebraic Informatics, volume 9270 of Lecture Notes in Computer Science, pp. 196-207. Springer, Heidelberg, 2015. doi:10.1007/978-3-319-23021-4_18.
• [7] Wang Q, Otto F. Weighted restarting automata and pushdown relations. Theor. Comput. Sci., 2016. 635:1-15. doi:10.1016/j.tcs.2016.04.038.
• [8] Kambites M. Formal Languages and Groups as Memory. Communications in Algebra, 2009. 37(1):193-208. doi:10.1080/00927870802243580.
• [9] Cavaliere M, Leupold P. Evolution and Observation: A Non-standard Way to Accept Formal Languages. In: Margenstern M (ed.), Proceedings of the 4th International Conference on Machines, Computations, and Universality, volume 3354 of Lecture Notes in Computer Science. Springer, Heidelberg, 2004 pp. 153-163. doi:10.1007/978-3-540-31834-7_12.
• [10] Cavaliere M, Leupold P. Observation of String-Rewriting Systems. Fundam. Inform., 2006. 74(4):447-462.
• [11] 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, pp. 269-303. Springer, Heidelberg, 2006.
• [12] Jancar P, Mráz F, Plátek M, Vogel J. On Monotonic Automata with a Restart Operation. J. Auto. Lang. Comb., 1999. 4(4):287-312. doi:10.25596/jalc-1999-287.
• [13] Jurdziński T, Lorys K, Niemann G, Otto F. Some Results on RWW- and RRWW-automata and Their Relation to the Class of Growing Context-sensitive Languages. J. Autom. Lang. Comb., 2004. 9(4):407-437. doi:10.25596/jalc-2004-407.
• [14] Valiant LG. The Complexity of Enumeration and Reliability Problems. SIAM J. Comput., 1979. 8(3):410-421. URL http://dblp.uni-trier.de/db/journals/siamcomp/siamcomp8.html#Valiant79.
• [15] Messerschmidt H, Otto F. On Non-forgetting Restarting Automata That Are Deterministic and/or Monotone. In: Grigoriev D, Harrison J, Hirsch EA (eds.), Computer Science - Theory and Applications, The First International Computer Science Symposium in Russia, Proceedings, Lecture Notes in Computer Science. Springer, Heidelberg, 2006 pp. 247-258. doi:10.1007/11753728_26.
• [16] Niemann G, Otto F. On the Power of RRWW-Automata. In: Ito M, Paun G, Yu S (eds.), Words, Semigroups, and Transductions - Festschrift in Honor of Gabriel Thierrin. World Scientific, 2001 pp. 341-355. doi:10.1142/9789812810908_0026.

Uwagi

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