Open Access Open Access  Restricted Access Access granted  Restricted Access Subscription Access

Vol 55, No 6 (2017)

Article

Structures Computable in Polynomial Time. I

Alaev P.E.

Abstract

It is proved that every computable locally finite structure with finitely many functions has a presentation computable in polynomial time. Furthermore, a structure computable in polynomial time is polynomially categorical iff it is finite. If a structure is computable in polynomial time and locally finite then it is weakly polynomially categorical (i.e., categorical with respect to primitive recursive isomorphisms) iff it is finite.

Algebra and Logic. 2017;55(6):421-435
pages 421-435 views

Subgroups, Automorphisms, and Lie Algebras Related to the Basis-Conjugating Automorphism Group

Bardakov V.G., Neshchadim M.V.

Abstract

We study some subgroups of the automorphism group of a free group, their factorizations into a semidirect product, automorphism groups, and adjoint Lie algebras.

Algebra and Logic. 2017;55(6):436-460
pages 436-460 views

Freely Generated Projective Planes with Finite Computable Dimension

Kogabaev N.T.

Abstract

It is proved that for every natural n ≥ 1, there exists a computable freely generated projective plane with computable dimension n. It is stated that the class of freely generated projective planes is complete with respect to degree spectra of automorphically nontrivial structures, effective dimensions, expansions by constants, and degree spectra of relations.

Algebra and Logic. 2017;55(6):461-484
pages 461-484 views

Spectrum of the Field of Computable Real Numbers

Korovina M.V., Kudinov O.V.

Abstract

Necessary and sufficient conditions for a Turing degree to be an element of the spectrum of the classical field of computable real numbers are established.

Algebra and Logic. 2017;55(6):485-500
pages 485-500 views

Algebraically Equivalent Clones

Pinus A.G.

Abstract

Two functional clones F and G on a set A are said to be algebraically equivalent if sets of solutions for F- and G-equations coincide on A. It is proved that pairwise algebraically nonequivalent existentially additive clones on finite sets A are finite in number. We come up with results on the structure of algebraic equivalence classes, including an equationally additive clone, in the lattices of all clones on finite sets.

Algebra and Logic. 2017;55(6):501-506
pages 501-506 views

Generalized Hyperarithmetical Computability Over Structures

Stukachev A.I.

Abstract

We consider the class of approximation spaces generated by admissible sets, in particular by hereditarily finite superstructures over structures. Generalized computability on approximation spaces is conceived of as effective definability in dynamic logic. By analogy with the notion of a structure Σ-definable in an admissible set, we introduce the notion of a structure effectively definable on an approximation space. In much the same way as the Σ-reducibility relation, we can naturally define a reducibility relation on structures generating appropriate semilattices of degrees of structures (of arbitrary cardinality), as well as a jump operation. It is stated that there is a natural embedding of the semilattice of hyperdegrees of sets of natural numbers in the semilattices mentioned, which preserves the hyperjump operation. A syntactic description of structures having hyperdegree is given.

Algebra and Logic. 2017;55(6):507-526
pages 507-526 views

Sessions of the Seminar “Algebra i Logika”

Algebra and Logic. 2017;55(6):527-527
pages 527-527 views