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 (Print) 18 (2008): 831–847. doi:10.1093/logcom/exn006
Publisher: Oxford University Press,, Oxford , Regno Unito
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:44200,
title = {Synthesizing monadic predicates},
author = {Meghini C. and Spyratos N.},
publisher = {Oxford University Press,, Oxford , Regno Unito},
doi = {10.1093/logcom/exn006},
journal = {Journal of logic and computation (Print)},
volume = {18},
pages = {831–847},
year = {2008}
}
0000-0003-0069-7429