Name
Abstract | ||
|---|---|---|
We study a categorical generalisation of tree automata, as $Sigma$-algebras for a fixed endofunctor $Sigma$ endowed with initial and final states. Under mild assumptions about the base category, we present a general minimisation algorithm for these automata. We build upon and extend an existing generalisation of the Nerode equivalence to a categorical setting, and relate it to the existence of minimal automata. Lastly, we show that generalised types of side-effects, such as non-determinism, can be captured by this framework, which leads to a general determinisation procedure. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.4230/LIPIcs.CALCO.2019.6 | CALCO |
Field | DocType | Volume |
Discrete mathematics,Generalization,Categorical variable,Automaton,Functor,Equivalence (measure theory),Minimisation (psychology),Mathematics | Journal | abs/1904.08802 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gerco van Heerdt | 1 | 3 | 1.43 |
| Tobias Kappé | 2 | 0 | 0.68 |
| Jurriaan Rot | 3 | 104 | 18.53 |
| Matteo Sammartino | 4 | 15 | 6.79 |
| Alexandra Silva | 5 | 31 | 9.71 |