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 Words

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
    Accepted on: June 25, 2015
    Submitted on: December 3, 2009
    Keywords: Computer Science - Formal Languages and Automata Theory
    Fundings :
      Source : OpenAIRE Research Graph
    • Games and Automata for Logic Extensions; Funder: European Commission; Code: 259454

    Linked data

    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.mfcs.2022.64
    Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.2208.00536
    • 10.4230/lipics.mfcs.2022.64
    • 10.48550/arxiv.2208.00536
    Countdown μ-Calculus
    Kołodziejski, Jędrzej ; Klin, Bartek ;

    20 Documents citing this article

    Share

    Consultation statistics

    This page has been seen 454 times.
    This article's PDF has been downloaded 243 times.