|
Published Articles >> Table of Contents >> Abstract
July/August 2003 (Vol. 15, No. 4)
pp. 1055-1056
The Subgraph Bisimulation Problem
Agostino Dovier
Carla Piazza
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TKDE.2003.1209024
Send link to a friend
| 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.
|
 References
|
[1] 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.
|
 Additional Information
|
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,
Jul/Aug,
2003
|
|
RSS Feed