Affiliations: College of Computer Science, Shaanxi Normal University, Xi’an, China and Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guilin, China. wangqc@snnu.edu.cn
Correspondence:
[†]
Address for correspondence: College of Computer Science, Shaanxi Normal University, Xi’an, China
Note: [*] This paper summarizes and extends results that have been announced at CIAA 2016 in Seoul, July 2016, and NCMA 2017 in Prague, August 2017. Extended abstracts appeared in the proceedings of these conferences [1, 2] and the doctoral thesis [3]. This work is supported by the National Science Foundation of China under Grant (No. 62002211), the Fundamental Research Funds for the Central Universities under Grant (No. GK202103089) and Guangxi Key Laboratory of Trusted Software (No. kx202010).
Abstract: 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.
