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.2016.13
URN: urn:nbn:de:0030-drops-68482
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6848/
Go to the corresponding LIPIcs Volume Portal

Filiot, Emmanuel ; Gauwin, Olivier ; Lhote, Nathan

Aperiodicity of Rational Functions Is PSPACE-Complete

pdf-format:
LIPIcs-FSTTCS-2016-13.pdf (0.5 MB)

Abstract

It is known that a language of finite words is definable in monadic second-order logic - MSO - (resp. first-order logic - FO -) iff it is recognized by some finite automaton (resp. some aperiodic finite automaton). Deciding whether an automaton A is equivalent to an aperiodic one is known to be PSPACE-complete. This problem has an important application in logic: it allows one to decide whether a given MSO formula is equivalent to some FO formula. In this paper, we address the aperiodicity problem for functions from finite words to finite words (transductions), defined by finite transducers, or equivalently by bimachines, a transducer model studied by Schützenberger and Reutenauer. Precisely, we show that the problem of deciding whether a given bimachine is equivalent to some aperiodic one is PSPACE-complete.

BibTeX - Entry

@InProceedings{filiot_et_al:LIPIcs:2016:6848,
  author =	{Emmanuel Filiot and Olivier Gauwin and Nathan Lhote},
  title =	{{Aperiodicity of Rational Functions Is PSPACE-Complete}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6848},
  URN =		{urn:nbn:de:0030-drops-68482},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.13},
  annote =	{Keywords: Rational word transductions, decision problem, aperiodicity, bimachines}
}

Keywords: Rational word transductions, decision problem, aperiodicity, bimachines
Collection: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Issue Date: 2016
Date of publication: 10.12.2016

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