Synthesizing monadic predicates

Meghini C, Spyratos N

Formal concept analysis  Arts and Humanities (miscellaneous)  Theoretical Computer Science  Hardware and Architecture  Software  Logic  Monadic logic 

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).

Source: JOURNAL OF LOGIC AND COMPUTATION, vol. 18 (issue 6), pp. 831-847

Metrics