On Two Types of Concept Lattices in the Theory of Numberings

Nikolay Bazhenov, Manat Mustafa, Anvar Nurakunov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation - 17th Annual Conference, TAMC 2022, Proceedings
EditorsDing-Zhu Du, Donglei Du, Chenchen Wu, Dachuan Xu
PublisherSpringer Science and Business Media Deutschland GmbH
Pages79-92
Number of pages14
ISBN (Print)9783031203497
DOIs
Publication statusPublished - Jan 2023
Event17th Annual Conference on Theory and Applications of Models of Computation, TAMC 2022 - Virtual, Online
Duration: Sept 16 2022Sept 18 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13571 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th Annual Conference on Theory and Applications of Models of Computation, TAMC 2022
CityVirtual, Online
Period9/16/229/18/22

Keywords

  • Computable structure
  • Concept lattice
  • Formal Concept Analysis
  • Index set
  • Numbering

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'On Two Types of Concept Lattices in the Theory of Numberings'. Together they form a unique fingerprint.

Cite this