Sökning: onr:"swepub:oai:DiVA.org:uu-429915" >
On the Separability...
On the Separability Problem of String Constraints
-
- Abdulla, Parosh, Professor, 1961- (författare)
- Uppsala universitet,Avdelningen för datorteknik,Datorteknik
-
- Atig, Mohamed Faouzi, Professor, 1981- (författare)
- Uppsala universitet,Avdelningen för datorteknik,Datorteknik
-
Dave, Vrunda (författare)
-
visa fler...
-
Krishna, Shankara Narayanan (författare)
-
visa färre...
-
(creator_code:org_t)
- Dagstuhl, Germany, 2020
- 2020
- Engelska.
-
Ingår i: 31st International Conference on Concurrency Theory, CONCUR 2020, September 1-4, 2020, Vienna, Austria (Virtual Conference). - Dagstuhl, Germany. - 9783959771603 ; , s. 16:1-16:19
- Relaterad länk:
-
https://doi.org/10.4...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.4...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Computer Systems Sciences
- Data- och systemvetenskap
- Computer Science
- Datavetenskap
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas