License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CALCO.2017.8
URN: urn:nbn:de:0030-drops-80484
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8048/
Go to the corresponding LIPIcs Volume Portal

Colcombet, Thomas ; Petrisan, Daniela

Automata Minimization: a Functorial Approach

pdf-format:
LIPIcs-CALCO-2017-8.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{colcombet_et_al:LIPIcs:2017:8048,
  author =	{Thomas Colcombet and Daniela Petrisan},
  title =	{{Automata Minimization: a Functorial Approach}},
  booktitle =	{7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-033-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{72},
  editor =	{Filippo Bonchi and Barbara K{\"o}nig},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8048},
  URN =		{urn:nbn:de:0030-drops-80484},
  doi =		{10.4230/LIPIcs.CALCO.2017.8},
  annote =	{Keywords: functor automata, minimization, Choffrut's minimization algorithm, subsequential transducers, Brzozowski's minimization algorithm}
}

Keywords: functor automata, minimization, Choffrut's minimization algorithm, subsequential transducers, Brzozowski's minimization algorithm
Collection: 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)
Issue Date: 2017
Date of publication: 17.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI