Thomas Colcombet ; Daniela Petrişan - Automata Minimization: a Functorial Approach

lmcs:4159 - Logical Methods in Computer Science, March 23, 2020, Volume 16, Issue 1 - https://doi.org/10.23638/LMCS-16(1:32)2020
Automata Minimization: a Functorial ApproachArticle

Authors: Thomas Colcombet ; Daniela Petrişan

    In this paper we regard languages and their acceptors - such as deterministic or weighted automata, transducers, or monoids - as functors from input categories that specify the type of the languages and of the machines to categories that specify the type of outputs. Our results are as follows: A) We provide sufficient conditions on the output category so that minimization of the corresponding automata is guaranteed. B) We show how to lift adjunctions between the categories for output values to adjunctions between categories of automata. C) We show how this framework can be instantiated to unify several phenomena in automata theory, starting with determinization, minimization and syntactic algebras. We provide explanations of Choffrut's minimization algorithm for subsequential transducers and of Brzozowski's minimization algorithm in this setting.


    Volume: Volume 16, Issue 1
    Published on: March 23, 2020
    Accepted on: March 2, 2020
    Submitted on: December 21, 2017
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Formal Languages and Automata Theory
    Funding:
      Source : OpenAIRE Graph
    • Duality in Formal Languages and Logic - a unifying approach to complexity and semantics; Funder: European Commission; Code: 670624
    • Challenges for Logic, Transducers and Automata; Funder: French National Research Agency (ANR); Code: ANR-16-CE40-0007

    1 Document citing this article

    Consultation statistics

    This page has been seen 1556 times.
    This article's PDF has been downloaded 1247 times.