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.FSTTCS.2019.50
URN: urn:nbn:de:0030-drops-116122
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11612/
Go to the corresponding LIPIcs Volume Portal

Rabinovich, Alexander ; Tiferet, Doron

Degrees of Ambiguity of Büchi Tree Automata

pdf-format:
LIPIcs-FSTTCS-2019-50.pdf (0.5 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 in N, such that for every input it has at most k accepting computations. We consider nondeterministic Büchi automata (NBA) over infinite trees and prove that it is decidable in polynomial time, whether an automaton is unambiguous, boundedly ambiguous, finitely ambiguous, or countably ambiguous.

BibTeX - Entry

@InProceedings{rabinovich_et_al:LIPIcs:2019:11612,
  author =	{Alexander Rabinovich and Doron Tiferet},
  title =	{{Degrees of Ambiguity of B{\"u}chi Tree Automata}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{50:1--50:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11612},
  URN =		{urn:nbn:de:0030-drops-116122},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.50},
  annote =	{Keywords: automata on infinite trees, ambiguous automata}
}

Keywords: automata on infinite trees, ambiguous automata
Collection: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 04.12.2019

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