Abstract
Graphs and partial orders are fundamental to conceptual structures theory. Conceptual graphs are used in the knowledge base and canonical basis as well as for type and conceptual relation definitions. Partial orders are used to specify the associations among types and relations, as well as graphs in the generalization hierarchy. The speed with which basic operations on these structures can be achieved will have a pronounced effect on efficiency. In this paper we explore the use of spanning trees as underlying representations of graphs and partial orders, and their effect on storage and operational efficiency. The simple structure of trees can be exploited to improve matching and joins of graphs (through normalization), to refine search algorithms on orders, and for taxonomic encoding. Although this inquisition is preliminary in nature, we provide some useful techniques for gaining efficiency through the use of spanning trees, including an implementation with a special form of feature term.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
H. Aït-Kaci, R. Boyer, P. Lincoln and R. Nasr, Efficient Implementation of Lattice Operations. ACM Transactions on Programming Languages. 11(1): 115–146. 1989.
H. Aït-Kaci and A. Podelski. Towards a Meaning of Life. Journal of Logic Programming. 16(3/4): 195. 1993.
B. Carpenter. The Logic of Typed Feature Structures. Cambridge University Press, London, England. 1992.
M. Chein and M. Mugnier. Specialization: Where do the Difficulties Occur? Proc. of 7th Annual Workshop. Las Cruces, NM. H. Pfeiffer and T. Nagle (Eds.), 1992.
G. Ellis. Compiled Hierarchical Retrieval. Conceptual Structures: Current Research and Practice. T. Nagle et al (Eds.). Ellis Horwood, New York, 1992.
G. Ellis. Efficient Retrieval from Hierarchies of Objects using Lattice Operations. Proc. of First Int'l Conf. on Conceptual Structures. Quebec City, Canada, 1993.
A. Fall. Sparse Logical Terms. To appear in Applied Mathematics Letters, 1995.
A. Fall. The Foundations of Taxonomic Encoding. Submitted to ACM Transactions on Programming Languages and Systems. Also available as Simon Fraser University Technical Report SFU CSS TR 94-20.
D. Gardiner, B. Tjan and J. Slagle. Extending Conceptual Structures: Representation Issues and Reasoning Operations. Conceptual Structures: Current Research and Practice. T. Nagle et al (Eds.). Ellis Horwood, New York, 1992.
G. Mineau. Normalizing Conceptual Graphs. Conceptual Structures: Current Research and Practice. T. Nagle et al (Eds.). Ellis Horwood, New York, 1992.
M. Mugnier and M. Chein. Polynomial Algorithms for Projections and Matching. Proc. of 7th Workshop. Las Cruces, NM. H. Pfeiffer and T. Nagle (Eds.), 1992.
L. Roberts, R. Levinson and R. Hughey. Issues in Parallel Hardware for Graph Retrieval. Proc. of First Int'l Conf. on Conceptual Structures, Theory and Applications. Quebec City, Canada, 1993.
J. Sowa. Conceptual Structures: Information Processing in Mind and Machine. Addison-Wesley, 1984.
G. Yang, Y. Choi, J. Oh. CGMA: A Novel Conceptual Graph Matching Algorithm. Proc. of 7th Workshop. Las Cruces, NM. H. Pfeiffer and T. Nagle (Eds), 1992.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fall, A. (1995). Spanning tree representations of graphs and orders in conceptual structures. In: Ellis, G., Levinson, R., Rich, W., Sowa, J.F. (eds) Conceptual Structures: Applications, Implementation and Theory. ICCS 1995. Lecture Notes in Computer Science, vol 954. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60161-9_41
Download citation
DOI: https://doi.org/10.1007/3-540-60161-9_41
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60161-6
Online ISBN: 978-3-540-49539-0
eBook Packages: Springer Book Archive