文章基本信息

标题：Emptiness of Zero Automata Is Decidable
本地全文：下载
作者：Mikolaj Bojanczyk ; Hugo Gimbert ; Edon Kelmendi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：106:1-106:13
DOI：10.4230/LIPIcs.ICALP.2017.106
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Zero 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.
关键词：tree automata; probabilistic automata; monadic second-order logic