Quantitative formalisms of regularity, a partial survey

Abstract. The question of extending the concept of regularity to a more quantitative setting has been considered since the origins of formal language theory and a large number of solutions to this question have been proposed. In in this lecture, I will review only a part of them. First, I will explain the equivalence between weighted automata, rational formal power series and matrix representations in a general setting. In the second part of the lecture, I will focus on quantitative formalisms using a (min, +) or (max, +) setting, like distance automata and the more recent notion of cost function.  

hosted by