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

Douéneau-Tabot, Gaëtan

On the Complexity of Infinite Advice Strings

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

Abstract

We investigate in this paper a notion of comparison between infinite strings. In a general way, if M is a computation model (e.g. Turing machines) and C a class of objects (e.g. languages), the complexity of an infinite word alpha can be measured with respect to the amount of objects from C that are presentable with machines from M using alpha as an oracle.
In our case, the model M is finite automata and the objects C are either recognized languages or presentable structures, known respectively as advice regular languages and advice automatic structures. This leads to several different classifications of infinite words that are studied in detail; we also derive logical and computational equivalent measures. Our main results explore the connections between classes of advice automatic structures, MSO-transductions and two-way transducers. They suggest a closer study of the resulting hierarchy over infinite words.

BibTeX - Entry

@InProceedings{douneautabot:LIPIcs:2018:9126,
  author =	{Ga{\"e}tan Dou{\'e}neau-Tabot},
  title =	{{On the Complexity of Infinite Advice Strings}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{122:1--122:13},
  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/9126},
  URN =		{urn:nbn:de:0030-drops-91260},
  doi =		{10.4230/LIPIcs.ICALP.2018.122},
  annote =	{Keywords: infinite words, advice automata, automatic structures, transducers}
}

Keywords: infinite words, advice automata, automatic structures, transducers
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