Search: onr:"swepub:oai:DiVA.org:uu-429915" >
On the Separability...
On the Separability Problem of String Constraints
-
- Abdulla, Parosh, Professor, 1961- (author)
- Uppsala universitet,Avdelningen för datorteknik,Datorteknik
-
- Atig, Mohamed Faouzi, Professor, 1981- (author)
- Uppsala universitet,Avdelningen för datorteknik,Datorteknik
-
Dave, Vrunda (author)
-
show more...
-
Krishna, Shankara Narayanan (author)
-
show less...
-
(creator_code:org_t)
- Dagstuhl, Germany, 2020
- 2020
- English.
-
In: 31st International Conference on Concurrency Theory, CONCUR 2020, September 1-4, 2020, Vienna, Austria (Virtual Conference). - Dagstuhl, Germany. - 9783959771603 ; , s. 16:1-16:19
- Related links:
-
https://doi.org/10.4...
-
show more...
-
https://urn.kb.se/re...
-
https://doi.org/10.4...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Computer Systems Sciences
- Data- och systemvetenskap
- Computer Science
- Datavetenskap
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
To the university's database