License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.28
URN: urn:nbn:de:0030-drops-168268
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16826/
Go to the corresponding LIPIcs Volume Portal

Carton, Olivier ; Douéneau-Tabot, Gaëtan

Continuous Rational Functions Are Deterministic Regular

pdf-format:
LIPIcs-MFCS-2022-28.pdf (0.8 MB)

Abstract

A word-to-word function is rational if it can be realized by a non-deterministic one-way transducer. Over finite words, it is a classical result that any rational function is regular, i.e. it can be computed by a deterministic two-way transducer, or equivalently, by a deterministic streaming string transducer (a one-way automaton which manipulates string registers).
This result no longer holds for infinite words, since a non-deterministic one-way transducer can guess, and check along its run, properties such as infinitely many occurrences of some pattern, which is impossible for a deterministic machine. In this paper, we identify the class of rational functions over infinite words which are also computable by a deterministic two-way transducer. It coincides with the class of rational functions which are continuous, and this property can thus be decided. This solves an open question raised in a previous paper of Dave et al.

BibTeX - Entry

@InProceedings{carton_et_al:LIPIcs.MFCS.2022.28,
  author =	{Carton, Olivier and Dou\'{e}neau-Tabot, Ga\"{e}tan},
  title =	{{Continuous Rational Functions Are Deterministic Regular}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16826},
  URN =		{urn:nbn:de:0030-drops-168268},
  doi =		{10.4230/LIPIcs.MFCS.2022.28},
  annote =	{Keywords: infinite words, rational functions, determinization, continuity, streaming string transducers, two-way transducers}
}

Keywords: infinite words, rational functions, determinization, continuity, streaming string transducers, two-way transducers
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

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