van Heerdt, G;
Kappé, T;
Rot, J;
Sammartino, M;
Silva, A;
(2019)
Tree automata as algebras: Minimisation and determinisation.
In:
Proceedings of the 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019).
(pp. 6:1-6:22).
LIPICS
Preview |
Text
LIPIcs-CALCO-2019-6.pdf - Published Version Download (594kB) | Preview |
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.
| Type: | Proceedings paper |
|---|---|
| Title: | Tree automata as algebras: Minimisation and determinisation |
| Event: | 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019) |
| ISBN-13: | 978-3-95977-120-7 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.4230/LIPIcs.CALCO.2019.6 |
| Publisher version: | https://doi.org/10.4230/LIPIcs.CALCO.2019.6 |
| Language: | English |
| Additional information: | © Gerco van Heerdt, Tobias Kappé, Jurriaan Rot, Matteo Sammartino, and Alexandra Silva; licensed under Creative Commons License CC-BY 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). |
| Keywords: | tree automata, algebras, minimisation, determinisation, Nerode equivalence |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10088222 |
Archive Staff Only
 |
View Item |
