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

Filiot, Emmanuel ; Gauwin, Olivier ; Lhote, Nathan ; Muscholl, Anca

On Canonical Models for Rational Functions over Infinite Words

pdf-format:
LIPIcs-FSTTCS-2018-30.pdf (0.5 MB)

Abstract

This paper investigates canonical transducers for rational functions over infinite words, i.e., functions of infinite words defined by finite transducers. We first consider sequential functions, defined by finite transducers with a deterministic underlying automaton. We provide a Myhill-Nerode-like characterization, in the vein of Choffrut's result over finite words, from which we derive an algorithm that computes a transducer realizing the function which is minimal and unique (up to the automaton for the domain).
The main contribution of the paper is the notion of a canonical transducer for rational functions over infinite words, extending the notion of canonical bimachine due to Reutenauer and Schützenberger from finite to infinite words. As an application, we show that the canonical transducer is aperiodic whenever the function is definable by some aperiodic transducer, or equivalently, by a first-order transduction. This allows to decide whether a rational function of infinite words is first-order definable.

BibTeX - Entry

@InProceedings{filiot_et_al:LIPIcs:2018:9929,
  author =	{Emmanuel Filiot and Olivier Gauwin and Nathan Lhote and Anca Muscholl},
  title =	{{On Canonical Models for Rational Functions over Infinite Words}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software  Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9929},
  URN =		{urn:nbn:de:0030-drops-99295},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.30},
  annote =	{Keywords: transducers, infinite words, minimization, aperiodicty, first-order logic}
}

Keywords: transducers, infinite words, minimization, aperiodicty, first-order logic
Collection: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 05.12.2018

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