2026-07-23T08:48:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12828 2024-03-06T10:50:47Z ddc:004 open_access

On the Separability Problem of String Constraints Abdulla, Parosh Aziz Atig, Mohamed Faouzi Dave, Vrunda Krishna, Shankara Narayanan string constraints separability interpolants We address the separability problem for straight-line string constraints. The separability problem for languages of a class C by a class S asks: given two languages A and B in C, does there exist a language I in S separating A and B (i.e., I is a superset of A and disjoint from B)? The separability of string constraints is the same as the fundamental problem of interpolation for string constraints. We first show that regular separability of straight line string constraints is undecidable. Our second result is the decidability of the separability problem for straight-line string constraints by piece-wise testable languages, though the precise complexity is open. In our third result, we consider the positive fragment of piece-wise testable languages as a separator, and obtain an ExpSpace algorithm for the separability of a useful class of straight-line string constraints, and a Pspace-hardness result. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Parosh Aziz Abdulla and Mohamed Faouzi Atig and Vrunda Dave and Shankara Narayanan Krishna 2020 Is Part Of LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2020.16 urn:nbn:de:0030-drops-128286 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.16 eng https://creativecommons.org/licenses/by/3.0/legalcode