loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The Subgraph Bisimulation Problem
July/August 2003 (vol. 15 no. 4)
pp. 1055-1056
ASCII Text
x 
 
Agostino Dovier, Carla Piazza, "The Subgraph Bisimulation Problem," IEEE Transactions on Knowledge and Data Engineering, vol. 15, no. 4, pp. 1055-1056, July/August, 2003.
 
 
BibTex
x
 
@article{ 10.1109/TKDE.2003.1209024,
author = {Agostino Dovier and Carla Piazza},
title = {The Subgraph Bisimulation Problem},
journal ={IEEE Transactions on Knowledge and Data Engineering},
volume = {15},
number = {4},
issn = {1041-4347},
year = {2003},
pages = {1055-1056},
doi = {http://doi.ieeecomputersociety.org/10.1109/TKDE.2003.1209024},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Knowledge and Data Engineering
TI - The Subgraph Bisimulation Problem
IS - 4
SN - 1041-4347
SP1055
EP1056
EPD - 1055-1056
A1 - Agostino Dovier,
A1 - Carla Piazza,
PY - 2003
KW - Bisimulation
KW - complexity
KW - semistructured data.
VL - 15
JA - IEEE Transactions on Knowledge and Data Engineering
ER -
 

Abstract—We study the complexity of the Subgraph Bisimulation Problem, which relates to Graph Bisimulation as Subgraph Isomorphism relates to Graph Isomorphism, and we prove its NP-Completeness. Our analysis is motivated by its applications to semistructured databases.

[1] 1055 P. Aczel, Non-Well-Founded Sets Lecture Notes, CLSI, vol. 14, Stanford, 1988.[2] P. Buneman, S.B. Davidson, G.G. Hillebrand, and D. Suciu, A Query Language and Optimization Techniques for Unstructured Data Proc. ACM SIGMOD, pp. 505-516, 1996.[3] M.P. Consens and A.O. Mendelzon, Graphlog: A Visual Formalism for Real Life Recursion Proc. Ninth ACM Symp. Principles of Database Systems (PODS '90), pp. 404-416, 1990.[4] A. Cortesi, A. Dovier, E. Quintarelli, and L. Tanca, Operational and Abstract Semantics of the Query Language G-Log Theoretical Computer Science, vol. 275, nos. 1-2, pp. 521-560, 2002.[5] A. Dovier and E. Quintarelli, Model-Checking Based Data Retrieval Proc. Database Programming Languages, Eighth Int'l Workshop, pp. 62-77, 2002.[6] M.R. Garey and D.S. Johnson, Computers and Intractability A Guide to the Theory of NP-Completeness. New York: W.H. Freeman, 1979.[7] A. Lisitsa and V. Sazonov, Bounded Hyperset Theory and Web-Like Data Bases Proc. Fifth Kurt Godel Colloquium, pp. 172-185, 1997.[8] R. Milner, Operational and Algebraic Semantics of Concurrent Processes Handbook of Theoretical Computer Science, chap. 19, Elsevier Science, 1990.[9] R. Paige and R.E. Tarjan, Three Partition Refinements Algorithms SIAM J. Computing, vol. 16, no. 6, pp. 973-989, 1987.[10] J. Paredaens, P. Peelman, and L. Tanca, "G-Log: A Graph-Based Query Language," IEEE Trans. Knowledge and Data Eng., vol. 7, no. 3, pp. 436-453, 1995.

Index Terms:
Bisimulation, complexity, semistructured data.
Citation:
Agostino Dovier, Carla Piazza, "The Subgraph Bisimulation Problem," IEEE Transactions on Knowledge and Data Engineering, vol. 15, no. 4, pp. 1055-1056, July/Aug. 2003, doi:10.1109/TKDE.2003.1209024
Usage of this product signifies your acceptance of the Terms of Use.