Search Results

Documents authored by Tiferet, Doron

Document
DOI: 10.4230/LIPIcs.CSL.2021.36
Degrees of Ambiguity for Parity Tree Automata

Authors: Alexander Rabinovich and Doron Tiferet

Published in: LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021)

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.
Cite as

Alexander Rabinovich and Doron Tiferet. Degrees of Ambiguity for Parity Tree Automata. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 183, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{rabinovich_et_al:LIPIcs.CSL.2021.36,
  author =	{Rabinovich, Alexander and Tiferet, Doron},
  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 =	{Baier, Christel and Goubault-Larrecq, Jean},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.36},
  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}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.80
Ambiguity Hierarchy of Regular Infinite Tree Languages

Authors: Alexander Rabinovich and Doron Tiferet

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is k-ambiguous (for k > 0) if for every input it has at most k accepting computations. An automaton is boundedly ambiguous if there is k ∈ ℕ, such that for every input it has at most k accepting computations. An automaton is finitely (respectively, countably) ambiguous if for every input it has at most finitely (respectively, countably) many accepting computations. The degree of ambiguity of a regular language is defined in a natural way. A language is k-ambiguous (respectively, boundedly, finitely, countably ambiguous) if it is accepted by a k-ambiguous (respectively, boundedly, finitely, countably ambiguous) automaton. Over finite words every regular language is accepted by a deterministic automaton. Over finite trees every regular language is accepted by an unambiguous automaton. Over ω-words every regular language is accepted by an unambiguous Büchi automaton [Arnold, 1983] and by a deterministic parity automaton. Over infinite trees there are ambiguous languages [Carayol et al., 2010]. We show that over infinite trees there is a hierarchy of degrees of ambiguity: For every k > 1 there are k-ambiguous languages which are not k-1 ambiguous; there are finitely (respectively countably, uncountably) ambiguous languages which are not boundedly (respectively finitely, countably) ambiguous.
Cite as

Alexander Rabinovich and Doron Tiferet. Ambiguity Hierarchy of Regular Infinite Tree Languages. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{rabinovich_et_al:LIPIcs.MFCS.2020.80,
  author =	{Rabinovich, Alexander and Tiferet, Doron},
  title =	{{Ambiguity Hierarchy of Regular Infinite Tree Languages}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.80},
  URN =		{urn:nbn:de:0030-drops-127495},
  doi =		{10.4230/LIPIcs.MFCS.2020.80},
  annote =	{Keywords: automata on infinite trees, ambiguous automata, monadic second-order logic}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.50
Degrees of Ambiguity of Büchi Tree Automata

Authors: Alexander Rabinovich and Doron Tiferet

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

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.
Cite as

Alexander Rabinovich and Doron Tiferet. Degrees of Ambiguity of Büchi Tree Automata. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{rabinovich_et_al:LIPIcs.FSTTCS.2019.50,
  author =	{Rabinovich, Alexander and Tiferet, Doron},
  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 =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.50},
  URN =		{urn:nbn:de:0030-drops-116122},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.50},
  annote =	{Keywords: automata on infinite trees, ambiguous automata}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact