文章基本信息

标题：On Equivalence and Uniformisation Problems for Finite Transducers
本地全文：下载
作者：Emmanuel Filiot ; Isma{\"e}l Jecker ; Christof L{\"o}ding 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：55
页码：125:1-125:14
DOI：10.4230/LIPIcs.ICALP.2016.125
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Transductions are binary relations of finite words. For rational transductions, i.e., transductions defined by finite transducers, the inclusion, equivalence and sequential uniformisation problems are known to be undecidable. In this paper, we investigate stronger variants of inclusion, equivalence and sequential uniformisation, based on a general notion of transducer resynchronisation, and show their decidability. We also investigate the classes of finite-valued rational transductions and deterministic rational transductions, which are known to have a decidable equivalence problem. We show that sequential uniformisation is also decidable for them.
关键词：Transducers; Equivalence; Uniformisation