UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Tree automata as algebras: Minimisation and determinisation

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 Green open access

[img]
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 > Provost and Vice Provost Offices
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 Chemical Engineering
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
Downloads since deposit
3Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item