License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.51
URN: urn:nbn:de:0030-drops-116138
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11613/
Thinniyam, Ramanathan S. ;
Zetzsche, Georg
Regular Separability and Intersection Emptiness Are Independent Problems
Abstract
The problem of regular separability asks, given two languages K and L, whether there exists a regular language S that includes K and is disjoint from L. This problem becomes interesting when the input languages K and L are drawn from language classes beyond the regular languages. For such classes, a mild and useful assumption is that they are full trios, i.e. closed under rational transductions.
All the results on regular separability for full trios obtained so far exhibited a noteworthy correspondence with the intersection emptiness problem: In each case, regular separability is decidable if and only if intersection emptiness is decidable. This raises the question whether for full trios, regular separability can be reduced to intersection emptiness or vice-versa.
We present counterexamples showing that neither of the two problems can be reduced to the other. More specifically, we describe full trios C_1, D_1, C_2, D_2 such that (i) intersection emptiness is decidable for C_1 and D_1, but regular separability is undecidable for C_1 and D_1 and (ii) regular separability is decidable for C_2 and D_2, but intersection emptiness is undecidable for C_2 and D_2.
BibTeX - Entry
@InProceedings{thinniyam_et_al:LIPIcs:2019:11613,
author = {Ramanathan S. Thinniyam and Georg Zetzsche},
title = {{Regular Separability and Intersection Emptiness Are Independent Problems}},
booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
pages = {51:1--51:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-131-3},
ISSN = {1868-8969},
year = {2019},
volume = {150},
editor = {Arkadev Chattopadhyay and Paul Gastin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11613},
URN = {urn:nbn:de:0030-drops-116138},
doi = {10.4230/LIPIcs.FSTTCS.2019.51},
annote = {Keywords: Regular separability, intersection emptiness, decidability}
}
|
Keywords: |
|
Regular separability, intersection emptiness, decidability |
|
Collection: |
|
39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.12.2019 |
