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.2018.140
URN: urn:nbn:de:0030-drops-91442
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9144/
Go to the corresponding LIPIcs Volume Portal

Skrzypczak, Michal

Unambiguous Languages Exhaust the Index Hierarchy

pdf-format:
LIPIcs-ICALP-2018-140.pdf (0.5 MB)

Abstract

This work is a study of the expressive power of unambiguity in the case of automata over infinite trees. An automaton is called unambiguous if it has at most one accepting run on every input, the language of such an automaton is called an unambiguous language. It is known that not every regular language of infinite trees is unambiguous. Except that, very little is known about which regular tree languages are unambiguous.
This paper answers the question whether unambiguous languages are of bounded complexity among all regular tree languages. The notion of complexity is the canonical one, called the (parity or Rabin/Mostowski) index hierarchy. The answer is negative, as exhibited by a family of examples of unambiguous languages the cannot be recognised by any alternating parity tree automata of bounded range of priorities.
Hardness of the examples is based on the theory of signatures, previously studied by Walukiewicz. The technical core of the article is a definition of the canonical signatures together with a parity game that compares signatures of a given pair of parity games (of the same index).

BibTeX - Entry

@InProceedings{skrzypczak:LIPIcs:2018:9144,
  author =	{Michal Skrzypczak},
  title =	{{Unambiguous Languages Exhaust the Index Hierarchy}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{140:1--140:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9144},
  URN =		{urn:nbn:de:0030-drops-91442},
  doi =		{10.4230/LIPIcs.ICALP.2018.140},
  annote =	{Keywords: unambiguous automata, parity games, infinite trees, index hierarchy}
}

Keywords: unambiguous automata, parity games, infinite trees, index hierarchy
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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