Istituto di Scienza e Tecnologie dell'Informazione     
Meghini C., Spyratos N. Synthesizing monadic predicates. In: Journal of Logic and Computation, vol. 18 (6) pp. 831 - 847. Oxford, 2008.
We study the problem of determining a concise, quantifier-free monadic predicate for a given set of objects in a given interpretation. We ad- dress both DNF and CNF predicates, as well as important sub-languages thereof. The problem is formalized as the search of a minimal element in a set of predicates equipped with a binary relation. We show that the problem has always a solution, that finding a minimal solution is always hard, but much harder when neither the given set of objects nor its com- plement are the extent of a formal concept (in the sense of Formal Concept Analysis).
URL: http://www.ucm.es/BUCM/compludoc/W/10812/0955792X_1.htm
DOI: 10.1093/logcom/9.6.959
Subject Formal concept analysis
Monadic logic
F.4.1 Mathematical Logic

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional