When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.81
URN: urn:nbn:de:0030-drops-145214
URL: https://drops.dagstuhl.de/opus/volltexte/2021/14521/
 Go to the corresponding LIPIcs Volume Portal

### On Guidable Index of Tree Automata

 pdf-format:

### Abstract

We study guidable parity automata over infinite trees introduced by Colcombet and Löding, which form an expressively complete subclass of all non-deterministic tree automata. We show that, for any non-deterministic automaton, an equivalent guidable automaton with the smallest possible index can be effectively found. Moreover, if an input automaton is of a special kind, i.e. it is deterministic or game automaton then a guidable automaton with an optimal index can be deterministic (respectively game) automaton as well. Recall that the problem whether an equivalent non-deterministic automaton with the smallest possible index can be effectively found is open, and a positive answer is known only in the case when an input automaton is a deterministic, or more generally, a game automaton.

### BibTeX - Entry

@InProceedings{niwinski_et_al:LIPIcs.MFCS.2021.81,
author =	{Niwi\'{n}ski, Damian and Skrzypczak, Micha{\l}},
title =	{{On Guidable Index of Tree Automata}},
booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages =	{81:1--81:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-201-3},
ISSN =	{1868-8969},
year =	{2021},
volume =	{202},
editor =	{Bonchi, Filippo and Puglisi, Simon J.},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
}