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 -