TY - GEN
T1 - On Two Types of Concept Lattices in the Theory of Numberings
AU - Bazhenov, Nikolay
AU - Mustafa, Manat
AU - Nurakunov, Anvar
N1 - Funding Information:
Keywords: Numbering · Index set · Computable structure · Concept lattice · Formal Concept Analysis The work was supported by Nazarbayev University Faculty Development Competitive Research Grants N021220FD3851. The work of Bazhenov is supported by the Mathematical Center in Akademgorodok under the agreement No. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation.
Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023/1
Y1 - 2023/1
N2 - The theory of numberings studies uniform computations for families of mathematical objects. A large body of literature is devoted to investigations of Rogers semilattices for computable families S, i.e. uniformly enumerable families of computably enumerable subsets of the set of natural numbers ω. Working within the framework of Formal Concept Analysis, we introduce two approaches to classification of at most countable families S⊂ P(ω). Similarly to the classical theory of numberings, each of the approaches assigns to a family S its own concept lattice. Our first approach captures the cardinality of a family S. We prove the following: if S contains at least two elements, then the corresponding concept lattice is a modular lattice of height 3 such that the number of its atoms equals the cardinality of S. Our second approach provides a much richer environment: we show that any countable complete lattice can be obtained as the concept lattice induced by an appropriate family S. In addition, we employ the index sets technique, and consider the following isomorphism problem: given two computable families S and T, how hard is it to determine whether the corresponding concept lattices are isomorphic? The isomorphism problem for the first approach is a Π30 -complete set, and the isomorphism problem for the second approach is Σ11 -hard.
AB - The theory of numberings studies uniform computations for families of mathematical objects. A large body of literature is devoted to investigations of Rogers semilattices for computable families S, i.e. uniformly enumerable families of computably enumerable subsets of the set of natural numbers ω. Working within the framework of Formal Concept Analysis, we introduce two approaches to classification of at most countable families S⊂ P(ω). Similarly to the classical theory of numberings, each of the approaches assigns to a family S its own concept lattice. Our first approach captures the cardinality of a family S. We prove the following: if S contains at least two elements, then the corresponding concept lattice is a modular lattice of height 3 such that the number of its atoms equals the cardinality of S. Our second approach provides a much richer environment: we show that any countable complete lattice can be obtained as the concept lattice induced by an appropriate family S. In addition, we employ the index sets technique, and consider the following isomorphism problem: given two computable families S and T, how hard is it to determine whether the corresponding concept lattices are isomorphic? The isomorphism problem for the first approach is a Π30 -complete set, and the isomorphism problem for the second approach is Σ11 -hard.
KW - Computable structure
KW - Concept lattice
KW - Formal Concept Analysis
KW - Index set
KW - Numbering
UR - http://www.scopus.com/inward/record.url?scp=85147844181&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85147844181&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-20350-3_8
DO - 10.1007/978-3-031-20350-3_8
M3 - Conference contribution
AN - SCOPUS:85147844181
SN - 9783031203497
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 79
EP - 92
BT - Theory and Applications of Models of Computation - 17th Annual Conference, TAMC 2022, Proceedings
A2 - Du, Ding-Zhu
A2 - Du, Donglei
A2 - Wu, Chenchen
A2 - Xu, Dachuan
PB - Springer Science and Business Media Deutschland GmbH
T2 - 17th Annual Conference on Theory and Applications of Models of Computation, TAMC 2022
Y2 - 16 September 2022 through 18 September 2022
ER -