Document Open Access Logo

On the Complexity of Infinite Advice Strings

Author Gaëtan Douéneau-Tabot

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.122.pdf
  • Filesize: 0.53 MB
  • 13 pages

Document Identifiers

Author Details

Gaëtan Douéneau-Tabot
  • École Normale Supérieure Paris-Saclay, Université Paris-Saclay, Cachan, France

Funding

  • Douéneau-Tabot, Gaëtan: This work was partially done during a stay of the author in RWTH Aachen University.

Cite As Get BibTex

Gaëtan Douéneau-Tabot. On the Complexity of Infinite Advice Strings. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 122:1-122:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.122

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Automata over infinite objects
Keywords
  • infinite words
  • advice automata
  • automatic structures
  • transducers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Faried Abu Zaid. Algorithmic solutions via model theoretic interpretations. PhD thesis, RWTH Aachen University, 2016. URL: http://dx.doi.org/10.18154/RWTH-2017-07663.
  2. Faried Abu Zaid, Erich Grädel, and Frederic Reinhardt. Advice Automatic Structures and Uniformly Automatic Classes. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), 2017. Google Scholar
  3. Jean-Paul Allouche and Jeffrey Shallit. Automatic sequences: theory, applications, generalizations. Cambridge university press, 2003. Google Scholar
  4. Rajeev Alur, Emmanuel Filiot, and Ashutosh Trivedi. Regular transformations of infinite strings. In Proceedings of the 2012 27th Annual IEEE/ACM Symposium on Logic in Computer Science, pages 65-74. IEEE Computer Society, 2012. Google Scholar
  5. Robert M. Baer and Edwin H. Spanier. Referenced automata and metaregular families. Journal of Computer and System Sciences, 3(4):423-446, 1969. Google Scholar
  6. Vince Bárány. A hierarchy of automatic ω-words having a decidable MSO theory. RAIRO-Theoretical Informatics and Applications, 42(3):417-450, 2008. Google Scholar
  7. Aleksandrs Belovs. Some algebraic properties of machine poset of infinite words. RAIRO-Theoretical Informatics and Applications, 42(3):451-466, 2008. Google Scholar
  8. Achim Blumensath and Erich Grädel. Automatic structures. In Logic in Computer Science, 2000. Proceedings. 15th Annual IEEE Symposium on, pages 51-62. IEEE, 2000. Google Scholar
  9. Gaëtan Douéneau-Tabot. Comparing the power of advice strings: a notion of complexity for infinite words. arXiv preprint arXiv:1801.04908, 2018. Google Scholar
  10. Jörg Endrullis, Jan Willem Klop, Aleksi Saarela, and Markus Whiteland. Degrees of transducibility. In International Conference on Combinatorics on Words, pages 1-13. Springer, 2015. Google Scholar
  11. Joost Engelfriet and Hendrik Jan Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Transactions on Computational Logic (TOCL), 2(2):216-254, 2001. Google Scholar
  12. Bakhadyr Khoussainov, André Nies, Sasha Rubin, and Frank Stephan. Automatic structures: richness and limitations. In Logic in Computer Science, 2004. Proceedings of the 19th Annual IEEE Symposium on, pages 44-53. IEEE, 2004. Google Scholar
  13. Alex Kruckman, Sasha Rubin, John Sheridan, and Ben Zax. A Myhill-Nerode theorem for automata with advice. In GandALF, pages 238-246, 2012. Google Scholar
  14. Christof Löding and Thomas Colcombet. Transforming structures by set interpretations. Logical Methods in Computer Science, 3, 2007. Google Scholar
  15. Alexander Rabinovich. A proof of Kamp’s theorem. Logical Methods in Computer Science, 10(1), 2014. Google Scholar
  16. Frédéric Reinhardt. Automatic structures with parameters. Master’s thesis, Rheinisch-Westfälischen Technischen Hochschule Aachen, 2013. Google Scholar
  17. Arto Salomaa. On finite automata with a time-variant structure. Information and Control, 13(2):85-98, 1968. Google Scholar
  18. Dana Scott. Some definitional suggestions for automata theory. Journal of Computer and System Sciences, 1(2):187-212, 1967. Google Scholar
  19. Aleksei Lvovich Semenov. Logical theories of one-place functions on the set of natural numbers. Mathematics of the USSR-Izvestiya, 22(3):587, 1984. Google Scholar
  20. Todor Tsankov. The additive group of the rationals does not have an automatic presentation. The Journal of Symbolic Logic, 76(04):1341-1351, 2011. Google Scholar
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 About DROPS Imprint Privacy Contact