文章基本信息

标题：On the Separability Problem of String Constraints
本地全文：下载
作者：Parosh Aziz Abdulla ; Mohamed Faouzi Atig ; Vrunda Dave 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：171
页码：16:1-16:19
DOI：10.4230/LIPIcs.CONCUR.2020.16
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：string constraints; separability; interpolants