Expressiveness and Complexity of Graph Logic Export

@misc{citeulike:2443202, 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 ...}, author = {Philippa, Anuj D.}, citeulike-article-id = {2443202}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.753}, keywords = {graphs, logic}, posted-at = {2008-02-28 12:10:06}, priority = {0}, title = {Expressiveness and Complexity of Graph Logic}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.753} }

TY - GEN ID - citeulike:2443202 L3 - citeulike-article-id:2443202 N2 - 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 ... TI - Expressiveness and Complexity of Graph Logic KW - graphs KW - logic AU - Philippa, Anuj UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.753 ER -