2026-07-23T20:16:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8048 2024-03-06T10:39:37Z ddc:004 open_access

Automata Minimization: a Functorial Approach Colcombet, Thomas Petrisan, Daniela functor automata minimization Choffrut's minimization algorithm subsequential transducers Brzozowski's minimization algorithm 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 applied to several phenomena in automata theory, starting with determinization and minimization (previously studied from a coalgebraic and duality theoretic perspective). We apply in particular these techniques to Choffrut's minimization algorithm for subsequential transducers and revisit Brzozowski's minimization algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Colcombet and Daniela Petrisan 2017 Is Part Of LIPIcs, Volume 72, 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CALCO.2017.8 urn:nbn:de:0030-drops-80484 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2017.8 eng https://creativecommons.org/licenses/by/3.0/legalcode