文章基本信息

标题：FO-Definable Transformations of Infinite Strings
本地全文：下载
作者：Vrunda Dave ; Shankara Narayanan Krishna ; Ashutosh Trivedi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：65
页码：12:1-12:14
DOI：10.4230/LIPIcs.FSTTCS.2016.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The theory of regular and aperiodic transformations of finite strings has recently received a lot of interest. These classes can be equivalently defined using logic (Monadic second-order logic and first-order logic), two-way machines (regular two-way and aperiodic two-way transducers), and one-way register machines (regular streaming string and aperiodic streaming string transducers). These classes are known to be closed under operations such as sequential composition and regular (star-free) choice; and problems such as functional equivalence and type checking, are decidable for these classes. On the other hand, for infinite strings these results are only known for regular transformations: Alur, Filiot, and Trivedi studied transformations of infinite strings and introduced an extension of streaming string transducers over infinte strings and showed that they capture monadic second-order definable transformations for infinite strings. In this paper we extend their work to recover connection for infinite strings among first-order logic definable transformations, aperiodic two-way transducers, and aperiodic streaming string transducers.
关键词：Transducers; FO-definability; Infinite Strings