6
IRUS TotalDownloads
Altmetric
Expressiveness and complexity of graph logic
File | Description | Size | Format | |
---|---|---|---|---|
DTR04-3.pdf | Published version | 211.84 kB | Adobe PDF | View/Open |
Title: | Expressiveness and complexity of graph logic |
Authors: | Dawar, A Gardner, P Ghelli, G |
Item Type: | Report |
Abstract: | We investigate the complexity and expressive power of the spatial logic for querying graphs introduced by Cardelli, Gardner and Ghelli (ICALP 2002).We show that the model-checking complexity of versions of this logic with and without recursion is PSPACE-complete. In terms of expressive power, the version without recursion is a fragment of the monadic second-order logic of graphs and we show that it can express complete problems at every level of the polynomial hierarchy. We also show that it can define all regular languages, when interpretation is restricted to strings. The expressive power of the logic with recursion is much greater as it can express properties that are PSPACE-complete and therefore unlikely to be definable in second-order logic. |
Issue Date: | 1-Jan-2004 |
URI: | http://hdl.handle.net/10044/1/95507 |
DOI: | https://doi.org/10.25561/95507 |
Publisher: | Department of Computing, Imperial College London |
Start Page: | 1 |
End Page: | 21 |
Journal / Book Title: | Departmental Technical Report: 04/3 |
Copyright Statement: | © 2004 The Author(s). This report is available open access under a CC-BY-NC-ND (https://creativecommons.org/licenses/by-nc-nd/4.0/) |
Publication Status: | Published |
Article Number: | 04/3 |
Appears in Collections: | Computing Computing Technical Reports |
This item is licensed under a Creative Commons License