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.CSL.2021.36
URN: urn:nbn:de:0030-drops-134709
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13470/
Go to the corresponding LIPIcs Volume Portal

Rabinovich, Alexander ; Tiferet, Doron

Degrees of Ambiguity for Parity Tree Automata

pdf-format:
LIPIcs-CSL-2021-36.pdf (0.6 MB)

Abstract

An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is finitely (respectively, countably) ambiguous if for every input it has at most finitely (respectively, countably) many accepting computations. An automaton is boundedly ambiguous if there is k ∈ ℕ, such that for every input it has at most k accepting computations. We consider Parity Tree Automata (PTA) and prove that the problem whether a PTA is not unambiguous (respectively, is not boundedly ambiguous, not finitely ambiguous) is co-NP complete, and the problem whether a PTA is not countably ambiguous is co-NP hard.

BibTeX - Entry

@InProceedings{rabinovich_et_al:LIPIcs:2021:13470,
  author =	{Alexander Rabinovich and Doron Tiferet},
  title =	{{Degrees of Ambiguity for Parity Tree Automata}},
  booktitle =	{29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-175-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{183},
  editor =	{Christel Baier and Jean Goubault-Larrecq},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13470},
  URN =		{urn:nbn:de:0030-drops-134709},
  doi =		{10.4230/LIPIcs.CSL.2021.36},
  annote =	{Keywords: automata on infinite trees, degree of ambiguity, omega word automata, parity automata}
}

Keywords: automata on infinite trees, degree of ambiguity, omega word automata, parity automata
Collection: 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)
Issue Date: 2021
Date of publication: 13.01.2021

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