文章基本信息

标题：Continuity of Functional Transducers: A Profinite Study of Rational Functions
本地全文：下载
作者：Paperman, Charles ; Carton, Olivier ; Cadilhac, Michaël 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2020
卷号：16
期号：1
页码：1-29
语种：English
出版社：Technical University of Braunschweig
摘要：A word-to-word function is continuous for a class of languages~V if its inverse maps V_languages to~V. This notion provides a basis for an algebraic study of transducers, and was integral to the characterization of the sequential transducers computable in some circuit complexity classes. Here, we report on the decidability of continuity for functional transducers and some standard classes of regular languages. To this end, we develop a robust theory rooted in the standard profinite analysis of regular languages. Since previous algebraic studies of transducers have focused on the sole structure of the underlying input automaton, we also compare the two algebraic approaches. We focus on two questions: When are the automaton structure and the continuity properties related, and when does continuity propagate to superclasses?
关键词：Computer Science - Formal Languages and Automata Theory;Computer Science - Logic in Computer Science