Search Results

Documents authored by Bilkowski, Marcin


Document
Unambiguity and uniformization problems on infinite trees

Authors: Marcin Bilkowski and Michał Skrzypczak

Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)


Abstract
A nondeterministic automaton is called unambiguous if it has at most one accepting run on every input. A regular language is called unambiguous if there exists an unambiguous automaton recognizing this language. Currently, the class of unambiguous languages of infinite trees is not well-understood. In particular, there is no known decision procedure verifying if a given regular tree language is unambiguous. In this work we study the self-dual class of bi-unambiguous languages - languages that are unambiguous and their complement is also unambiguous. It turns out that thin trees (trees with only countably many branches) emerge naturally in this context. We propose a procedure P designed to decide if a given tree automaton recognizes a bi-unambiguous language. The procedure is sound for every input. It is also complete for languages recognisable by deterministic automata. We conjecture that P is complete for all inputs but this depends on a new conjecture stating that there is no MSO-definable choice function on thin trees. This would extend a result by Gurevich and Shelah on the undefinability of choice on the binary tree. We provide a couple of equivalent statements to our conjecture, we also give several related results about uniformizability on thin trees. In particular, we provide a new example of a language that is not unambiguous, namely the language of all thin trees. The main tool in our studies are algebras that can be seen as an adaptation of Wilke algebras to the case of infinite trees.

Cite as

Marcin Bilkowski and Michał Skrzypczak. Unambiguity and uniformization problems on infinite trees. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 81-100, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{bilkowski_et_al:LIPIcs.CSL.2013.81,
  author =	{Bilkowski, Marcin and Skrzypczak, Micha{\l}},
  title =	{{Unambiguity and uniformization problems on infinite trees}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{81--100},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Ronchi Della Rocca, Simona},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.81},
  URN =		{urn:nbn:de:0030-drops-41916},
  doi =		{10.4230/LIPIcs.CSL.2013.81},
  annote =	{Keywords: nondeterministic automata, infinite trees, MSO logic}
}
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