On computable formal concepts in computable formal contexts

Autor:	A. S. Morozov, M. A. L’vova
Rok vydání:	2007
Předmět:	Discrete mathematics Computable function Computable model theory utm theorem General Mathematics Diagonal lemma Gap theorem Formal system Mathematical economics Computable analysis Church's thesis Mathematics
Zdroj:	Siberian Mathematical Journal. 48:871-878
ISSN:	1573-9260 0037-4466
DOI:	10.1007/s11202-007-0089-y
Popis:	We introduce and study the notions of computable formal context and computable formal concept. We give some examples of computable formal contexts in which the computable formal concepts fail to form a lattice and study the complexity aspects of formal concepts in computable contexts. In particular, we give some sufficient conditions under which the computability or noncomputability of a formal concept could be recognized from its lattice-theoretic properties. We prove the density theorem showing that in a Cantor-like topology every formal concept can be approximated by computable ones. We also show that not all formal concepts have lattice-theoretic approximations as suprema or infima of families of computable formal concepts.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::131a739b6b02b6e8e70eadd1be21cf37 https://doi.org/10.1007/s11202-007-0089-y Zobrazit plný text záznamu Plný text ve formátu PDF