文章基本信息

标题：Aperiodicity of Rational Functions Is PSPACE-Complete
本地全文：下载
作者：Emmanuel Filiot ; Olivier Gauwin ; Nathan Lhote 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：65
页码：13:1-13:15
DOI：10.4230/LIPIcs.FSTTCS.2016.13
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Rational word transductions; decision problem; aperiodicity; bimachines