Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1109/ACSD.2018.000-3 | 2018 18th International Conference on Application of Concurrency to System Design (ACSD) |
Keywords | Field | DocType |
reachability problem,database driven systems,complexity,decidability | Query language,Petri net,Relational database,Unary operation,Binary relation,Computer science,Theoretical computer science,Reachability,Reachability problem,Undecidable problem | Conference |
ISSN | ISBN | Citations |
1550-4808 | 978-1-5386-7014-9 | 0 |
PageRank | References | Authors |
0.34 | 17 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Parosh Aziz Abdulla | 1 | 2010 | 122.22 |
| C. Aiswarya | 2 | 3 | 1.43 |
| Mohamed Faouzi Atig | 3 | 505 | 40.94 |
| Marco Montali | 4 | 1280 | 99.36 |
| Othmane Rezine | 5 | 26 | 3.80 |