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.2019.6
URN: urn:nbn:de:0030-drops-114341
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11434/
Go to the corresponding LIPIcs Volume Portal

van Heerdt, Gerco ; Kappé, Tobias ; Rot, Jurriaan ; Sammartino, Matteo ; Silva, Alexandra

Tree Automata as Algebras: Minimisation and Determinisation

pdf-format:
LIPIcs-CALCO-2019-6.pdf (0.6 MB)

Abstract

We study a categorical generalisation of tree automata, as algebras for a fixed endofunctor endowed with initial and final states. Under mild assumptions about the base category, we present a general minimisation algorithm for these automata. We then build upon and extend an existing generalisation of the Nerode equivalence to a categorical setting and relate it to the existence of minimal automata. Finally, we show that generalised types of side-effects, such as non-determinism, can be captured by this categorical framework, leading to a general determinisation procedure.

BibTeX - Entry

@InProceedings{vanheerdt_et_al:LIPIcs:2019:11434,
  author =	{Gerco van Heerdt and Tobias Kapp{\'e} and Jurriaan Rot and Matteo Sammartino and Alexandra Silva},
  title =	{{Tree Automata as Algebras: Minimisation and Determinisation}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-120-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{139},
  editor =	{Markus Roggenbach and Ana Sokolova},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11434},
  URN =		{urn:nbn:de:0030-drops-114341},
  doi =		{10.4230/LIPIcs.CALCO.2019.6},
  annote =	{Keywords: tree automata, algebras, minimisation, determinisation, Nerode equivalence}
}

Keywords: tree automata, algebras, minimisation, determinisation, Nerode equivalence
Collection: 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)
Issue Date: 2019
Date of publication: 25.11.2019

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