A Categorical View on Algebraic Lattices in Formal Concept Analysis

• Autorzy: Hitzler P. , Krötzsch M. , Zhang G-Q.
• Języki publikacji: EN

Abstrakty

EN

Formal concept analysis has grown from a new branch of the mathematical field of lattice theory to a widely recognized tool in Computer Science and elsewhere. In order to fully benefit from this theory, we believe that it can be enriched with notions such as approximation by computation or representability. The latter are commonly studied in denotational semantics and domain theory and captured most prominently by the notion of algebraicity, e.g. of lattices. In this paper, we explore the notion of algebraicity in formal concept analysis from a category-theoretical perspective. To this end, we build on the notion of approximable concept with a suitable category and show that the latter is equivalent to the category of algebraic lattices. At the same time, the paper provides a relatively comprehensive account of the representation theory of algebraic lattices in the framework of Stone duality, relating well-known structures such as Scott information systems with further formalisms from logic, topology, domains and lattice theory.

Słowa kluczowe

EN

algebraic lattice; formal concept analysis; domain theory; stone duality; category theory

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 2,3
• Strony: 301--328
• Opis fizyczny: bibliogr. 34 poz.

Twórcy

autor

Hitzler P.

autor

Krötzsch M.

autor

Zhang G-Q.

• Institut AIFB, Universität Karlsruhe Karlsruhe, Germany,

Bibliografia

• [1] Abramsky, S.: Domain theory in logical form, Annals of Pure and Applied Logic, 51, 1991, 1-77.
• [2] Abramsky, S., Jung, A.: Domain theory, Handbook of Logic in Computer Science (S. Abramsky, D. M. Gabbay, T. S. E. Maibaum, Eds.), vol. III, Oxford University Press, 1994.
• [3] Borceux, F.: Handbook of Categorical Algebra 1: Basic Category Theory, vol. 53 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, 1994.
• [4] Cederquist, J., Coquand, T.: Entailment relations and distributive lattices, Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, Prague, Czech Republic, 1998 (S. Buss, P. Hájek, P. Pudlák, Eds.), Lecture Notes in Logic, vol. 13 of Lecture Notes in Logic, Association for Symbolic Logic, 2000.
• [5] Coquand, T., Zhang, G.-Q.: Sequents, frames and completeness, Proceedings of the Annual Conference of the European Association for Computer Science Logic (CLS2000), Fischbachau/Munich,Germany (P. Clote, H. Schwichtenberg, Eds.), Lecture Notes in Computer Science, vol. 1862 of Lecture Notes in Computer Science, Springer, 2000.
• [6] Davey, B. A., Priestley, H. A.: Introduction to Lattices and Order, second edition, Cambridge University Press, 2002.
• [7] Droste, M., Göbel, R.: Non-deterministic information systems and their domains, Theoretical Computer Science, 75, 1990, 289-309.
• [8] Dunn, J. M., Hardegree, G. M.: Algebraic methods in philosophical logic, Clarendon Press, 2001.
• [9] Ganter, B., Wille, R.: Formal Concept Analysis - Mathematical Foundations, Springer, 1999.
• [10] Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M., Scott, D. S.: Continuous Lattices and Domains, vol. 93 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2003.
• [11] Hitzler, P.: Default Reasoning over Domains and Concept Hierarchies, Proceedings of the 27th German conference on Artificial Intelligence, KI'2004, Ulm, Germany, September 2004 (S. Biundo, T. Frühwirth, G. Palm, Eds.), Lecture Notes in Artificial Intelligence, vol. 3238 of Lecture Notes in Artificial Intelligence, Springer, Berlin, 2004, 351-365.
• [12] Hitzler, P., Wendt, M.: Formal Concept Analysis and Resolution in Algebraic Domains, Using Conceptual Structures - Contributions to ICCS 2003 (A. de Moor, B. Ganter, Eds.), Shaker Verlag, Aachen, 2003, 157-170.
• [13] Hitzler, P., Zhang, G.-Q.: A cartesian closed category of approximable concept structures, Proceedings of the International Conference On Conceptual Structures, Huntsville, Alabama, USA (K.-E. Wolff, H. D. Pfeiffer, H. S. Delugach, Eds.), Lecture Notes in Computer Science, Lecture Notes in Computer Science, Springer, July 2004, 170-185.
• [14] Johnstone, P. T.: Stone spaces, Cambridge University Press, 1982.
• [15] Jung, A., Kegelmann,M., Moshier, M. A.: Multi lingual sequent calculus and coherent spaces, Fundamenta Informaticae, XX, 1999, 1-42.
• [16] Lawvere, F. W., Rosebrugh, R.: Sets for mathematics, Cambridge University Press, 2003.
• [17] Lloyd, J. W.: Foundations of Logic Programming, 2nd extended edition, Springer Verlag, 1987.
• [18] Mac Lane, S.: Categories for the Working Mathematician, Springer, 1971.
• [19] McLarty, C.: Elementary categories, elementary toposes, Clarendon Press, 1992.
• [20] Rounds, W. C., Zhang, G.-Q.: Clausal Logic and Logic Programming in Algebraic Domains, Information and Computation, 171(2), 2001, 156-182.
• [21] Scott, D. S.: Domains for denotational semantics, Proceedings of the 9th Colloquium on Automata, Languages and Programming, Aarhus, Denmark (ICALP'82) (M. Nielsen, E. M. Schmidt, Eds.), Lecture Notes in Computer Science, vol. 140 of Lecture Notes in Computer Science, Springer, 1982.
• [22] Scott, D. S.: Lectures on a mathematical theory of computation, Theoretical Foundations of Programming Methodology (M. Broy, G. Schmidt, Eds.), Carnegie-Mellon University, Department of Computer Science, Pittsburgh, D. Reidel Publishing Company, 1982, 145-292.
• [23] Seda, A. K.: Topology and the Semantics of Logic Programs, Fundamenta Informaticae, 24(4), 1995, 359- 386.
• [24] Simmons, H.: The coverage technique for enriched posets, Available from the author's homepage www.cs.man.ac.uk/~hsimmons. 2004.
• [25] Smyth, M. B.: Topology, Handbook of Logic in Computer Science (S. Abramsky, D. M. Gabbay, T. S. E. Maibaum, Eds.), vol. I, Oxford University Press, 1992.
• [26] Stone, H. M.: Topological representations of distributive lattices and Brouwerian logics, Časopis pro Pěstování Matematiky a Fysiky, 67, 1937, 1-25.
• [27] Stumme, G.: Formal Concept Analysis on its Way from Mathematics to Computer Science, Conceptual Structures: Integration and Interfaces, Proc. ICCS 2002 (U. Priss, D. Corbett, G. A. (eds.), Eds.), LNAI, LNAI, Springer, 2002, 2-19.
• [28] Wille, R.: Restructuring lattice theory: An approach based on hierarchies of concepts, in: Ordered Sets (I. Rival, Ed.), Reidel, Dordrecht-Boston, 1982, 445-470.
• [29] Zhang, G.-Q.: Logic of Domains, Birkhäuser, Boston, 1991.
• [30] Zhang, G.-Q.: Disjunctive systems and L-domains, Proceedings of the 19th International Colloquium on Automata, Languages, and Programming (ICALP'92), Vienna, Austria (W. Kuich, Ed.), Lecture Notes in Computer Science, vol. 623 of Lecture Notes in Computer Science, Springer, 1992.
• [31] Zhang, G.-Q.: Chu spaces, concepts lattices, and domains, Proceedings of the 19th Conference of the Mathematical Foundations of Programming Semantics, Montreal, Canada, 2003, Electronic Notes in Theoretical Computer Science, vol. 83 of Electronic Notes in Theoretical Computer Science, 2003.
• [32] Zhang, G.-Q.: Topology, Lattices, and Logic Programming, Presentation at the DIMACS Lattice Workshop, Juli 8-10, 2003.
• [33] Zhang, G.-Q., Rounds, W.: Reasoning with power defaults, Theoretical Computer Science, 323(1-3), 2004, 321-350.
• [34] Zhang, G.-Q., Shen, G.: Approximable concepts, Chu spaces, and information systems, Theory and Applications of Categories, 200x, To appear.