Abstract
A natural approach to define binary word relations over a finite alphabet A is through twotape finite state automata that recognize regular languages over {1, 2} x A, where (i,a) is interpreted as reading letter a from tape i. Accordingly, a word w in L denotes the pair (u_1,u_2) in A^* x A^* in which u_i is the projection of w onto ilabelled letters. While this formalism defines the wellstudied class of Rational relations (a.k.a. nondeterministic finite state transducers), enforcing restrictions on the reading regime from the tapes, which we call synchronization, yields various subclasses of relations. Such synchronization restrictions are imposed through regular properties on the projection of the language onto {1,2}. In this way, for each regular language C subseteq {1,2}^*, one obtains a class Rel({C}) of relations. Regular, Recognizable, and lengthpreserving rational relations are all examples of classes that can be defined in this way.
We study the problem of containment for synchronized classes of relations: given C,D subseteq {1,2}^*, is Rel({C}) subseteq Rel({D})? We show a characterization in terms of C and D which gives a decidability procedure to test for class inclusion. This also yields a procedure to resynchronize languages from {1, 2} x A preserving the denoted relation whenever the inclusion holds.
BibTeX  Entry
@InProceedings{descotte_et_al:LIPIcs:2018:9127,
author = {Mar{\'i}a Emilia Descotte and Diego Figueira and Gabriele Puppis},
title = {{Resynchronizing Classes of Word Relations}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {123:1123:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9127},
URN = {urn:nbn:de:0030drops91270},
doi = {10.4230/LIPIcs.ICALP.2018.123},
annote = {Keywords: synchronized word relations, containment, resynchronization}
}
Keywords: 

synchronized word relations, containment, resynchronization 
Collection: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) 
Issue Date: 

2018 
Date of publication: 

04.07.2018 