论文标题
关于字符串约束的可分离性问题
On the Separability Problem of String Constraints
论文作者
论文摘要
我们解决直线字符串约束的可分离性问题。 S类C级的语言的可分离性问题要问：C中的两种语言A和B中，是否存在S分离A和B中的I语言i（即，我是A的超集，而不是B）？字符串约束的可分离性与字符串约束的插值基本问题相同。我们首先表明直线弦约束的常规可分离性是不可决定的。我们的第二个结果是通过可分离的字符串约束的可分离性问题通过零件可测试的语言的可分离性，尽管精确的复杂性是开放的。在我们的第三个结果中，我们将零件可测试语言的积极片段视为分离器，并获得一个expspace算法，以使有用的直线字符串约束和PSPACE硬度结果的可分离性。
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.
