文章基本信息

标题：Aperiodic Two-way Transducers and FO-Transductions
本地全文：下载
作者：Olivier Carton ; Luc Dartois
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：41
页码：160-174
DOI：10.4230/LIPIcs.CSL.2015.160
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Deterministic two-way transducers on finite words have been shown by Engelfriet and Hoogeboom to have the same expressive power as MSO-transductions. We introduce a notion of aperiodicity for these transducers and we show that aperiodic transducers correspond exactly to FO-transductions. This lifts to transducers the classical equivalence for languages between FO-definability, recognition by aperiodic monoids and acceptance by counter-free automata.
关键词：Transducer; first-order; two-way; transition monoid; aperiodic