Paper:

# Concept Finding Proofs

## Norihiro Kamide

Waseda Institute for Advanced Study, Waseda University, 1-6-1 Nishi Waseda, Shinjuku-ku, Tokyo 169-8050, Japan

We propose a proof-theoretical way of obtaining detailed and precise information on conceptual hierarchies. The notion of concept finding proof, which represents a hierarchy of concepts, is introduced based on a substructural logic with mingle and strong negation. Mingle, which is a structural inference rule, is used to represent a process for finding a more general (or specific) concept than some given concepts. Strong negation, which is a negation connective, is used to represent a concept inverse operator. The problem for constructing a concept finding proof is shown to be decidable in PTIME.^{1} 1. This paper is an extended version of [1].

*J. Adv. Comput. Intell. Intell. Inform.*, Vol.15, No.7, pp. 777-784, 2011.

- [1] N. Kamide, “A logic for conceptual hierarchies,” Proc. of the 20th Brazilian Symposium on Artificial Intelligence (SBIA 2010), Lecture Notes in Artificial Intelligence, Vol.6404, pp. 303-312, 2010.
- [2] B. Ganter and R. Wille, “Formal concept analysis: Mathematical foundations,” Springer, 1999.
- [3] F. Baader, D. Calvanese, D. McGuinness, D. Nardi, and P. F. Patel-Schneider (Eds.), “The description logic handbook: Theory, implementation and applications,” Cambridge University Press, 2003.
- [4] A. R. Anderson and N. D. Belnap, Jr., “Entailment: The logic of relevance and necessity,” Vol.1, Princeton University Press, 1975.
- [5] N. Kamide, “Substructural logic with mingle,” J. of Logic, Language and Information, Vol.11, No.2, pp. 227-249, 2002.
- [6] N. Kamide, “Linear logics with communication-merge,” J. of Logic and Computation, Vol.15, No.1, pp. 3-20, 2005.
- [7] M. Ohnishi and K. Matsumoto, “A system for strict implication,” Annals of the Japan Association for Philosophy of Science, Vol.2, No.4, pp. 183-188, 1964.
- [8] N. Kamide, “Relevance principle for substructural logics with mingle and strong negation,” J. of Logic and Computation, Vol.12, No.6, pp. 913-928, 2002.
- [9] D. Nelson, “Constructible falsity,” J. of Symbolic Logic, Vol.14, pp. 16-26, 1949.
- [10] H. Wansing, “The logic of information structures,” Lecture Notes in Artificial Intelligence, Vol.681, p. 163, 1993.
- [11] B. A. Davey and H. A. Priestley, “Introduction to lattice and order (second edition),” Cambridge University Press, 2002.
- [12] F. Dau and J. Klinger, “From formal concept analysis to contextual logic,” In: Formal Concept Analysis: Foundations and Applications, Lecture Notes in Computer Science, Vol.3626, pp. 81-100, 2005.
- [13] F. Baader, G. Ganter, B. Sertkaya, and U. Sattler, “Completing description logic knowledge bases using formal concept analysis,” Proc. of the 20th Int. Joint Conf. on Artificial Intelligence (IJCAI 2007), pp. 230-235, 2007.
- [14] N. V. Shilov, N. O. Garania, and I. S. Anureer, “Combining propositional dynamic logic with formal concept analysis,” Proc. of Concurrency, Specification and Programming (CS & P 2006), pp. 152-161, 2006.
- [15] L. Chaudron and N. Maille, “1st order logic formal concept analysis: from logic programming to theory,” Linköping Electronic Articles in Computer and Information Science, Vol.3, No.13, p. 14, 1998.
- [16] N. Kamide and K. Kaneiwa, “Extended full computation-tree logic with sequence modal operator: Representing hierarchical tree structures,” Proc. of the 22nd Australasian Joint Conf. on Artificial Intelligence (AI’09), Lecture Notes in Artificial Intelligence, Vol.5866, pp. 485-494, Springer, 2009.