License
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://drops.dagstuhl.de/opus/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
Seminar: 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)
Issue Date: 2017
Date of publication: 02.11.2017


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