Открытый доступ
Доступ предоставлен
Только для подписчиков
Том 55, № 6 (2017)
- Год: 2017
- Статей: 7
- URL: https://journal-vniispk.ru/0002-5232/issue/view/14540
Article
Structures Computable in Polynomial Time. I
Аннотация
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.
421-435
436-460
Freely Generated Projective Planes with Finite Computable Dimension
Аннотация
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.
461-484
485-500
Algebraically Equivalent Clones
Аннотация
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.
501-506
Generalized Hyperarithmetical Computability Over Structures
Аннотация
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.
507-526
Sessions of the Seminar “Algebra i Logika”
527-527