Colcombet, Thomas - Regular Cost Functions, Part I: Logic and Algebra over Words

lmcs:1221 - Logical Methods in Computer Science, August 13, 2013, Volume 9, Issue 3
Regular Cost Functions, Part I: Logic and Algebra over Words

Authors: Colcombet, Thomas

The theory of regular cost functions is a quantitative extension to the classical notion of regularity. A cost function associates to each input a non-negative integer value (or infinity), as opposed to languages which only associate to each input the two values "inside" and "outside". This theory is a continuation of the works on distance automata and similar models. These models of automata have been successfully used for solving the star-height problem, the finite power property, the finite substitution problem, the relative inclusion star-height problem and the boundedness problem for monadic-second order logic over words. Our notion of regularity can be -- as in the classical theory of regular languages -- equivalently defined in terms of automata, expressions, algebraic recognisability, and by a variant of the monadic second-order logic. These equivalences are strict extensions of the corresponding classical results. The present paper introduces the cost monadic logic, the quantitative extension to the notion of monadic second-order logic we use, and show that some problems of existence of bounds are decidable for this logic. This is achieved by introducing the corresponding algebraic formalism: stabilisation monoids.


Source : oai:arXiv.org:1212.6937
DOI : 10.2168/LMCS-9(3:3)2013
Volume: Volume 9, Issue 3
Published on: August 13, 2013
Submitted on: December 3, 2009
Keywords: Computer Science - Formal Languages and Automata Theory


Share

Consultation statistics

This page has been seen 83 times.
This article's PDF has been downloaded 20 times.