One-way Resynchronizability of Word Transducers

被引：0
作者：
Bose, Sougata [1 ]
Krishna, S. N. [2 ]
Muscholl, Anca [1 ]
Puppis, Gabriele [3 ]
机构：
[1] Univ Bordeaux, LaBRI, Bordeaux, France
[2] Indian Inst Technol, Dept Comp Sci & Engn, Bombay, Maharashtra, India
[3] Univ Udine, Dept Math Comp Sci & Phys, Udine, Italy
来源：
FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES, FOSSACS 2021 | 2021年 / 12650卷
关键词：
String transducers; Resynchronizers; One-way transducers; EQUIVALENCE PROBLEM; 2-WAY; UNSOLVABILITY;
D O I：
10.1007/978-3-030-71995-1_7
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
The origin semantics for transducers was proposed in 2014, and it led to various characterizations and decidability results that are in contrast with the classical semantics. In this paper we add a further decidability result for characterizing transducers that are close to one-way transducers in the origin semantics. We show that it is decidable whether a non-deterministic two-way word transducer can be resynchronized by a bounded, regular resynchronizer into an origin-equivalent one-way transducer. The result is in contrast with the usual semantics, where it is undecidable to know if a non-deterministic two-way transducer is equivalent to some one-way transducer.
引用
收藏
页码：124 / 143
页数：20
相关论文
共 23 条
  • [1] Expressiveness of streaming string transducers
    Alur, Rajeev
    Cerny, Pavol
    [J]. IARCS ANNUAL CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE (FSTTCS 2010), 2010, 8 : 1 - 12
  • [2] [Anonymous], 2014, 34 INT C FDN SOFTWAR
  • [3] [Anonymous], 2018, LIPICS
  • [4] [Anonymous], 2016, LIPICS
  • [5] ONE-WAY DEFINABILITY OF TWO-WAY WORD TRANSDUCERS
    Baschenis, Felix
    Gauwin, Olivier
    Muscholl, Anca
    Puppis, Gabriele
    [J]. LOGICAL METHODS IN COMPUTER SCIENCE, 2018, 14 (04) : 1 - 54
  • [6] Bojanczyk M., 2017, ICALP, V80
  • [7] Bojanczyk M, 2014, LECT NOTES COMPUT SC, V8573, P26
  • [8] Bose S., 2019, LIPIcs, V138
  • [9] Colcombet T, 2007, LECT NOTES COMPUT SC, V4639, P226
  • [10] Courcelle B, 2012, ENCYCLOP MATH APPL, V138, P1, DOI 10.1017/CBO9780511977619
123