Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en van Heerdt, Gerco; Kappé, Tobias; Rot, Jurriaan; Sammartino, Matteo; Silva, Alexandra http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-114341
URL:

; ; ; ;

Tree Automata as Algebras: Minimisation and Determinisation

pdf-format:


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
Seminar: 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)
Issue date: 2019
Date of publication: 2019


DROPS-Home | Imprint | Privacy Published by LZI