2026-07-21T14:19:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9127 2024-03-06T10:43:25Z ddc:004 open_access

Resynchronizing Classes of Word Relations Descotte, María Emilia Figueira, Diego Puppis, Gabriele synchronized word relations containment resynchronization A natural approach to define binary word relations over a finite alphabet A is through two-tape 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 i-labelled letters. While this formalism defines the well-studied class of Rational relations (a.k.a. non-deterministic finite state transducers), enforcing restrictions on the reading regime from the tapes, which we call synchronization, yields various sub-classes 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 length-preserving 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 re-synchronize languages from {1, 2} x A preserving the denoted relation whenever the inclusion holds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik María Emilia Descotte and Diego Figueira and Gabriele Puppis 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.123 urn:nbn:de:0030-drops-91270 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.123 eng https://creativecommons.org/licenses/by/3.0/legalcode