Pascal Tesson ; Denis Therien - Logic Meets Algebra: the Case of Regular Languages

lmcs:2226 - Logical Methods in Computer Science, February 23, 2007, Volume 3, Issue 1 -
Logic Meets Algebra: the Case of Regular Languages

Authors: Pascal Tesson ; Denis Therien

    The study of finite automata and regular languages is a privileged meeting point of algebra and logic. Since the work of Buchi, regular languages have been classified according to their descriptive complexity, i.e. the type of logical formalism required to define them. The algebraic point of view on automata is an essential complement of this classification: by providing alternative, algebraic characterizations for the classes, it often yields the only opportunity for the design of algorithms that decide expressibility in some logical fragment. We survey the existing results relating the expressibility of regular languages in logical fragments of MSO[S] with algebraic properties of their minimal automata. In particular, we show that many of the best known results in this area share the same underlying mechanics and rely on a very strong relation between logical substitutions and block-products of pseudovarieties of monoid. We also explain the impact of these connections on circuit complexity theory.

    Volume: Volume 3, Issue 1
    Published on: February 23, 2007
    Submitted on: April 15, 2006
    Keywords: Computer Science - Logic in Computer Science,D.3.1,F.1.1,F.1.3,F.4.1,F.4.3
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsReferencedBy DOI 10.1007/11874683_28
    • 10.1007/11874683_28
    • 10.1007/11874683_28
    An algebraic point of view on the crane beach property
    Lautemann, Clemens ; Tesson, Pascal ; Thérien, Denis ;

    18 Documents citing this article

    Consultation statistics

    This page has been seen 1544 times.
    This article's PDF has been downloaded 945 times.