onr:"swepub:oai:DiVA.org:uu-367961"
Search: onr:"swepub:oai:DiVA.org:uu-367961" > Complexity of reach...
- 1 of 1
- Previous record
- Next record
- To hitlist
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)
- 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
- Conference paper (peer-reviewed)
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
- Proc. 18th International Conference on Application of Concurrency to System Desi... (Search for host publication in LIBRIS)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Abdulla, Parosh ...
- Aiswarya, C.
- Atig, Mohamed Fa ...
- Montali, Marco
- Rezine, Othmane
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- Proc. 18th Inter ...
- By the university
- Uppsala University
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
