License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.106
URN: urn:nbn:de:0030-drops-74745
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7474/
Go to the corresponding LIPIcs Volume Portal

Bojanczyk, Mikolaj ; Gimbert, Hugo ; Kelmendi, Edon

Emptiness of Zero Automata Is Decidable

pdf-format:
LIPIcs-ICALP-2017-106.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{bojanczyk_et_al:LIPIcs:2017:7474,
  author =	{Mikolaj Bojanczyk and Hugo Gimbert and Edon Kelmendi},
  title =	{{Emptiness of Zero Automata Is Decidable}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{106:1--106:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7474},
  URN =		{urn:nbn:de:0030-drops-74745},
  doi =		{10.4230/LIPIcs.ICALP.2017.106},
  annote =	{Keywords: tree automata, probabilistic automata, monadic second-order logic}
}

Keywords: tree automata, probabilistic automata, monadic second-order logic
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI