No label defined (Q4428702)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1984268
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1984268

      Statements

      0 references
      22 September 2003
      0 references
      computable structures
      0 references
      presentation
      0 references
      degree spectra
      0 references
      computable dimension
      0 references
      categoricity
      0 references
      survey
      0 references
      In this survey paper the author considers the question of whether computability properties of structures depend on the choice of a presentation and if so, then how? Let \(R\) be a relation not included in the language of a computable structure \({\mathcal A}\). The author describes some classic results giving conditions on \({\mathcal A}\) or \(R\) that restrict the possible variations in the computable dimension of \({\mathcal A}\) and the computational complexity of \(R\). Further, in the absence of such conditions, the author discusses the possible computable dimensions of \({\mathcal A}\) and, in terms of Turing degrees, variations of \(R\) in different presentations. The author also discusses recent results of the author, Khoussainov, Hirschfeldt and others about the possible degree spectra of computable relations on computable structures and the connections with computable dimension and categoricity both in a general model-theoretic setting and in some restricted classes of structures (graphs, linear and partial orderings, lattices, Abelian and nilpotent groups, rings etc.). For the entire collection see [Zbl 1017.00016].
      0 references

      Identifiers