Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

On Guidable Index of Tree Automata

Uproszczony widok
dc.abstract.enWe 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryEstonia
dc.conference.datefinish2021-08-27
dc.conference.datestart2021-08-23
dc.conference.placeTallinn
dc.conference.seriesInternational Symposium on Mathematical Foundations of Computer Science
dc.conference.seriesInternational Symposium on Mathematical Foundations of Computer Science
dc.conference.seriesshortcutMFCS
dc.conference.shortcutMFCS 2021
dc.conference.weblinkhttps://compose.ioc.ee/mfcs/
dc.contributor.authorNiwiński, Damian
dc.contributor.authorSkrzypczak, Michał
dc.date.accessioned2024-01-25T15:45:13Z
dc.date.available2024-01-25T15:45:13Z
dc.date.issued2021
dc.description.financePublikacja bezkosztowa
dc.description.volume202
dc.identifier.doi10.4230/LIPICS.MFCS.2021.81
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/114702
dc.identifier.weblinkhttps://doi.org/10.4230/LIPIcs.MFCS.2021.81
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages81:1--81:14
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.titleOn Guidable Index of Tree Automata
dc.typeJournalArticle
dspace.entity.typePublication