Sökning: id:"swepub:oai:DiVA.org:uu-367961" >
Complexity of reach...
Complexity of reachability for data-aware dynamic systems
-
- Abdulla, Parosh Aziz, Professor (författare)
- Uppsala universitet,Datorteknik,Avdelningen för datorteknik
-
Aiswarya, C. (författare)
-
- Atig, Mohamed Faouzi (författare)
- Uppsala universitet,Datorteknik,Avdelningen för datorteknik
-
visa fler...
-
Montali, Marco (författare)
-
- Rezine, Othmane (författare)
- Uppsala universitet,Datorteknik,Avdelningen för datorteknik
-
visa färre...
-
(creator_code:org_t)
- IEEE Computer Society, 2018
- 2018
- Engelska.
-
Ingår i: Proc. 18th International Conference on Application of Concurrency to System Design. - : IEEE Computer Society. - 9781538670132 ; , s. 11-20
- Relaterad länk:
-
https://doi.org/10.1...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas