Projekt 9 - Weighted Restarting Automata

(Beginn 10/2013)

Restarting automata were introduced by Jančar et al. in 1995 to model the linguistic technique of analysis by reduction, which is used for checking the correctness of a sentence of a natural language. In order to study quantitative aspects of restarting automata, we introduce the concept of a weighted restarting automaton. A weighted restarting automaton M consists of a restarting automaton on some input alphabet Σ and a weight function ω that assigns a weight from some semiring S to each transition of M. By looking at different semirings S and different weight functions ω, various quantitative aspects of the behavior of M can be expressed through these functions. For example, by taking S to be the semiring of natural numbers with addition and multiplicaton, we can count the number of accepting computations for each input, or by using the tropical semiring, we can determine the minimal number of cycles in an accepting computation for each input. Which functions f : Σ → S can be realized in this way? We are interested in the syntactic and semantic properties of these functions, e.g., their growth rates and the closure properties under various operations. Further, we look at those transductions that are realized by weighted restarting automata, and we use these automata to define and characterize various classes of formal languages.


Qichao Wang


Wang, Q. and Otto, F.:
Weighted restarting automata as language acceptors, Han, Yo-Sub and Salomaa, K., editors, Lecture Notes in computer Science 9725, Springer, Heidelberg, (2016), 298-309.
Wang, Q. and Otto, F.:
Weighted restarting automata and pushdown relations, Theoretical Computer Science 635 (2016) 1-15.
Wang, Q., Hundeshagen, N. and Otto, F.:
Weighted restarting automata and pushdown relations, In Maletti A., editor, CAI 2015, Proc., Lecture Notes in Computer Science 9270, Springer, Heidelberg, (2015), 196-207.