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: https://drops.dagstuhl.de/opus/volltexte/2019/11434/
van Heerdt, Gerco ; Kappé, Tobias ; Rot, Jurriaan ; Sammartino, Matteo ; Silva, Alexandra
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: | 25.11.2019 |
