DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2019.22

Closure Properties of Synchronized Relations

Authors: María Emilia Descotte, Diego Figueira, and Santiago Figueira

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract

A standard approach to define k-ary word relations over a finite alphabet A is through k-tape finite state automata that recognize regular languages L over {1, ..., k} x A, where (i,a) is interpreted as reading letter a from tape i. Accordingly, a word w in L denotes the tuple (u_1, ..., u_k) in (A^*)^k in which u_i is the projection of w onto i-labelled letters. While this formalism defines the well-studied class of rational relations, 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 L onto {1, ..., k}. In this way, for each regular language C subseteq {1, ..., k}^*, one obtains a class Rel({C}) of relations. Synchronous, Recognizable, and Length-preserving rational relations are all examples of classes that can be defined in this way. We study basic properties of these classes of relations, in terms of closure under intersection, complement, concatenation, Kleene star and projection. We characterize the classes with each closure property. For the binary case (k=2) this yields effective procedures.

Cite as

María Emilia Descotte, Diego Figueira, and Santiago Figueira. Closure Properties of Synchronized Relations. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{descotte_et_al:LIPIcs.STACS.2019.22,
  author =	{Descotte, Mar{\'\i}a Emilia and Figueira, Diego and Figueira, Santiago},
  title =	{{Closure Properties of Synchronized Relations}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.22},
  URN =		{urn:nbn:de:0030-drops-102614},
  doi =		{10.4230/LIPIcs.STACS.2019.22},
  annote =	{Keywords: synchronized word relations, rational, closure, characterization, intersection, complement, Kleene star, concatenation}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2018.123

Resynchronizing Classes of Word Relations

Authors: María Emilia Descotte, Diego Figueira, and Gabriele Puppis

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

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.

Cite as

María Emilia Descotte, Diego Figueira, and Gabriele Puppis. Resynchronizing Classes of Word Relations. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 123:1-123:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{descotte_et_al:LIPIcs.ICALP.2018.123,
  author =	{Descotte, Mar{\'\i}a Emilia and Figueira, Diego and Puppis, Gabriele},
  title =	{{Resynchronizing Classes of Word Relations}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{123:1--123:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.123},
  URN =		{urn:nbn:de:0030-drops-91270},
  doi =		{10.4230/LIPIcs.ICALP.2018.123},
  annote =	{Keywords: synchronized word relations, containment, resynchronization}
}

Search Results

Documents authored by Descotte, María Emilia

Closure Properties of Synchronized Relations

Abstract

Cite as

Resynchronizing Classes of Word Relations

Abstract

Cite as

Thanks for your feedback!

Could not send message