The theory of regular cost functions is a quantitative extension to theclassical notion of regularity. A cost function associates to each input anon-negative integer value (or infinity), as opposed to languages which onlyassociate to each input the two values "inside" and "outside". This theory is acontinuation of the works on distance automata and similar models. These modelsof automata have been successfully used for solving the star-height problem,the finite power property, the finite substitution problem, the relativeinclusion star-height problem and the boundedness problem for monadic-secondorder logic over words. Our notion of regularity can be -- as in the classicaltheory of regular languages -- equivalently defined in terms of automata,expressions, algebraic recognisability, and by a variant of the monadicsecond-order logic. These equivalences are strict extensions of thecorresponding classical results. The present paper introduces the cost monadiclogic, the quantitative extension to the notion of monadic second-order logicwe use, and show that some problems of existence of bounds are decidable forthis logic. This is achieved by introducing the corresponding algebraicformalism: stabilisation monoids.
展开▼
