Search: onr:"swepub:oai:DiVA.org:uu-367961" >
Complexity of reach...
Complexity of reachability for data-aware dynamic systems
-
- Abdulla, Parosh Aziz, Professor (author)
- Uppsala universitet,Datorteknik,Avdelningen för datorteknik
-
Aiswarya, C. (author)
-
- Atig, Mohamed Faouzi (author)
- Uppsala universitet,Datorteknik,Avdelningen för datorteknik
-
show more...
-
Montali, Marco (author)
-
- Rezine, Othmane (author)
- Uppsala universitet,Datorteknik,Avdelningen för datorteknik
-
show less...
-
(creator_code:org_t)
- IEEE Computer Society, 2018
- 2018
- English.
-
In: Proc. 18th International Conference on Application of Concurrency to System Design. - : IEEE Computer Society. - 9781538670132 ; , s. 11-20
- Related links:
-
https://doi.org/10.1...
-
show more...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- A formal model called database manipulating systems was introduced to model data-aware dynamic systems. Its semantics is given by an infinite labelled transition systems where a label can be an unbounded relational database. Reachability problem is undecidable over schemas consisting of either a binary relation or two unary relations. We study the reachability problem under schema restrictions and restrictions on the query language. We provide tight complexity bounds for different combinations of schema and query language, by reductions to/from standard formalism of infinite state systems such as Petri nets and counter systems. Our reductions throw light into the connections between these two seemingly unrelated models.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
To the university's database