6
IRUS Total
Downloads
  Altmetric

Expressiveness and complexity of graph logic

File Description SizeFormat 
DTR04-3.pdfPublished version211.84 kBAdobe PDFView/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 Creative Commons