License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.17
URN: urn:nbn:de:0030-drops-185514
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18551/
Go to the corresponding LIPIcs Volume Portal

Barceló, Pablo ; Figueira, Diego ; Morvan, Rémi

Separating Automatic Relations

pdf-format:
LIPIcs-MFCS-2023-17.pdf (0.9 MB)

Abstract

We study the separability problem for automatic relations (i.e., relations on finite words definable by synchronous automata) in terms of recognizable relations (i.e., finite unions of products of regular languages). This problem takes as input two automatic relations R and R', and asks if there exists a recognizable relation S that contains R and does not intersect R'. We show this problem to be undecidable when the number of products allowed in the recognizable relation is fixed. In particular, checking if there exists a recognizable relation S with at most k products of regular languages that separates R from R' is undecidable, for each fixed k ⩾ 2. Our proofs reveal tight connections, of independent interest, between the separability problem and the finite coloring problem for automatic graphs, where colors are regular languages.

BibTeX - Entry

@InProceedings{barcelo_et_al:LIPIcs.MFCS.2023.17,
  author =	{Barcel\'{o}, Pablo and Figueira, Diego and Morvan, R\'{e}mi},
  title =	{{Separating Automatic Relations}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18551},
  URN =		{urn:nbn:de:0030-drops-185514},
  doi =		{10.4230/LIPIcs.MFCS.2023.17},
  annote =	{Keywords: Automatic relations, recognizable relations, separability, finite colorability}
}

Keywords: Automatic relations, recognizable relations, separability, finite colorability
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI