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

lmcs:1221 - Logical Methods in Computer Science, August 13, 2013, Volume 9, Issue 3 - https://doi.org/10.2168/LMCS-9(3:3)2013
Regular Cost Functions, Part I: Logic and Algebra over WordsArticle

Authors: Thomas Colcombet

    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.


    Volume: Volume 9, Issue 3
    Published on: August 13, 2013
    Imported on: December 3, 2009
    Keywords: Computer Science - Formal Languages and Automata Theory
    Funding:
      Source : OpenAIRE Graph
    • Games and Automata for Logic Extensions; Funder: European Commission; Code: 259454

    21 Documents citing this article

    Consultation statistics

    This page has been seen 1120 times.
    This article's PDF has been downloaded 320 times.