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

Emptiness of Zero Automata Is Decidable

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:44:15Z
dc.abstract.enZero automata are a probabilistic extension of parity automata on infinite trees. The satisfiability of a certain probabilistic variant of MSO, called TMSO+zero, reduces to the emptiness problem for zero automata. We introduce a variant of zero automata called nonzero automata. We prove that for every zero automaton there is an equivalent nonzero automaton of quadratic size and the emptiness problem of nonzero automata is decidable, with complexity co-NP. These results imply that TMSO+zero has decidable satisfiability.
dc.affiliationUniwersytet Warszawski
dc.conference.countryPolska
dc.conference.datefinish2017-07-14
dc.conference.datestart2017-07-10
dc.conference.placeWarszawa
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesshortcutICALP
dc.conference.shortcutICALP 2017
dc.conference.weblinkhttp://icalp17.mimuw.edu.pl/
dc.contributor.authorBojańczyk, Mikołaj
dc.contributor.authorGimbert, Hugo
dc.contributor.authorKelmendi, Edon
dc.date.accessioned2024-01-24T22:47:25Z
dc.date.available2024-01-24T22:47:25Z
dc.date.issued2017
dc.description.financeNie dotyczy
dc.identifier.doi10.4230/LIPICS.ICALP.2017.106
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/106150
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2017/7474/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages106:1--106:13
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.entree automata
dc.subject.enprobabilistic automata
dc.subject.enmonadic second-order logic
dc.titleEmptiness of Zero Automata Is Decidable
dc.typeJournalArticle
dspace.entity.typePublication