Meghini C., Spyratos N. Synthesizing monadic predicates. In: Journal of Logic and Computation, vol. 18 (6) pp. 831 - 847. Oxford, 2008. |

Abstract (English) |
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 |

1) Download Document PDF |

Open access Restricted Private