Weakly precomplete computably enumerable equivalence relations

Using computable reducibility ? on equivalence relations, we investigate weakly precomplete ceers (a “ceer” is a computably enumerable equivalence relation on the natural numbers), and we compare their class with the more restricted class of precomplete ceers. We show that there are infinitely many isomorphism types of universal (in fact uniformly finitely precomplete) weakly precomplete ceers , that are not precomplete; and there are infinitely many isomorphism types of non‐universal weakly precomplete ceers. Whereas the Visser space of a precomplete ceer always contains an infinite effectively discrete subset, there exist weakly precomplete ceers whose Visser spaces do not contain infinite effectively discrete subsets. As a consequence, contrary to precomplete ceers which always yield partitions into effectively inseparable sets, we show that although weakly precomplete ceers always yield partitions into computably inseparable sets, nevertheless there are weakly precomplete ceers for which no equivalence class is creative. Finally, we show that the index set of the precomplete ceers is Σ₃‐complete, whereas the index set of the weakly precomplete ceers is Π₃‐complete. As a consequence of these results, we also show that the index sets of the uniformly precomplete ceers and of the e‐complete ceers are Σ₃‐complete.     

The computable Lipschitz degrees of computably enumerable sets are not dense

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility (Downey et al. (2004) [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense (George Barmpalias, Andrew E.M. Lewis (2006) [2]), however the problem for the computable Lipschitz degrees is more complex.     

The computable embedding problem

Calvert calculated the complexity of the computable isomorphism problem for a number of familiar classes of structures. Rosendal suggested that it might be interesting to do the same for the computable embedding problem. By the computable isomorphism problem and (computable embedding problem) we mean the difficulty of determining whether there exists an isomorphism (embedding) between two members of a class of computable structures. For some classes, such as the class of \mathbbQ \mathbb{Q} -vector spaces and the class of linear orderings, it turns out that the two problems have the same complexity. Moreover, calculations are essentially the same. For other classes, there are differences. We present examples in which the embedding problem is trivial (within the class) and the computable isomorphism problem is more complicated. We also give an example in which the embedding problem is more complicated than the isomorphism problem.     

Lattice embeddings and array noncomputable degrees

We focus on a particular class of computably enumerable (c. e.) degrees, the array noncomputable degrees defined by Downey, Jockusch, and Stob, to answer questions related to lattice embeddings and definability in the partial ordering (??, ≤) of c. e. degrees under Turing reducibility. We demonstrate that the latticeM₅ cannot be embedded into the c. e. degrees below every array noncomputable degree, or even below every nonlow array noncomputable degree. As Downey and Shore have proved that M₅ can be embedded below every nonlow₂ degree, our result is the best possible in terms of array noncomputable degrees and jump classes. Further, this result shows that the array noncomputable degrees are definably different from the nonlow₂ degrees. We note also that there are embeddings of M₅ in which all five degrees are array noncomputable, and in which the bottom degree is the computable degree 0 but the other four are array noncomputable. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Obstructions to homotopy equivalences

An obstruction theory is developed to decide when an isomorphism of rational cohomology can be realized by a rational homotopy equivalence (either between rationally nilpotent spaces, or between commutative graded differential algebras). This is used to show that a cohomology isomorphism can be so realized whenever it can be realized over some field extension (a result obtained independently by Sullivan).In particular an algorithmic method is given to decide when a c.g.d.a. has the same homotopy type as its cohomology (the c.g.d.a. is called formal in this case).The chief technique is the construction of a canonically filtered model for a commutative graded differential algebra (over a field of characteristic zero) by perturbing the minimal model for the cohomology algebra. This filtered model is also used to give a simple construction of the Eilenberg-Moore spectral sequence arising from the bar construction. An example is given of a c.g.d.a. whose Eilenberg-Moore sequence collapses, yet which is not formal.     

Degree spectra of the successor relation of computable linear orderings

We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turing degrees determined by b is the degree spectrum of the successor relation of some computable linear ordering. This follows from our main result, that for a large class of linear orderings the degree spectrum of the successor relation is closed upward in the c.e. Turing degrees. The authors acknowledge partial support by the NSF binational grant DMS-0554841, and Harizanov by the NSF grant DMS-0704256, and Chubb by the Sigma Xi Grant in Aid of Research.     

Extensions of homomorphisms to dense extensions of semigroups

Gluskin [2] has shown that if α is an isomorphism of a weakly reductive semigroup S onto a semigroup T, if V is a dense extension of S and T is densely embedded in W then α extends uniquely to an isomorphism of V into W. Here we consider the problem of extending epimorphisms and as a consequence of a few simple observations obtain as the main theorem a homomorphism of Ω(S), for any semisimple semigroup S, into the product of the translational hulls of the principal factors of S. A few consequences are considered.     

The isomorphism problem for classes of computable fields

Theories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out several examples. One motivation is to see whether some classes whose set of countable members is very complex become classifiable when we consider only computable members. We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. For real closed fields we show that the isomorphism problem is ¹₁ complete (the maximum possible), and for others we show that it is of relatively low complexity. We show that the isomorphism problem for algebraically closed fields, Archimedean real closed fields, or vector spaces is ⁰₃ complete.     

Complexity of some natural problems on the class of computable I-algebras

We study computable Boolean algebras with distinguished ideals (I-algebras for short). We prove that the isomorphism problem for computable I-algebras is Σ ₁ ¹ -complete and show that the computable isomorphism problem and the computable categoricity problem for computable I-algebras are Σ ₃ ⁰ -complete.     

Complexity of a knot invariant

The algebraic structures called quandles constitute a complete invariant for tame knots. However, determining when two quandles are isomorphic is an empirically hard problem, so there is some dissatisfaction with quandles as knot invariants. We have confirmed this apparent difficulty, showing within the framework of Borel reducibility that the general isomorphism problem for quandles is as complex as possible. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Joining to high degrees via noncuppables

Cholak, Groszek and Slaman proved in J Symb Log 66:881–901, 2001 that there is a nonzero computably enumerable (c.e.) degree cupping every low c.e. degree to a low c.e. degree. In the same paper, they pointed out that every nonzero c.e. degree can cup a low₂ c.e. degree to a nonlow₂ degree. In Jockusch et al. (Trans Am Math Soc 356:2557–2568, 2004) improved the latter result by showing that every nonzero c.e. degree c is cuppable to a high c.e. degree by a low₂ c.e. degree b. It is natural to ask in which subclass of low₂ c.e. degrees can b in Jockusch et al. (Trans Am Math Soc 356:2557–2568, 2004) be located. Wu proved in Math Log Quart 50:189–201, 2004 that b can be cappable. We prove in this paper that b in Jockusch, Li and Yang’s result can be noncuppable, improving both Jockusch, Li and Yang, and Wu’s results.     

On the translational hull of a type B semigroup

In this paper, the translational hull of a type B semigroup is considered. We prove that the translational hull of a type B semigroup is itself a type B semigroup, and give some properties and characterizations of the translational hulls of such semigroups. Moreover, we consider the translational hulls of some special type B semigroups. These results strengthen the results of Fountain and Lawson (Semigroup Forum 32:79–86, 1985) on adequate semigroups. Finally, we give a new proof of a problem posted by Petrich on translational hulls of inverse semigroups in Petrich (Inverse Semigroups, Wiley, New York, 1984).     

Finite degree: algebras in general and semigroups in particular

An algebra A has finite degree if its term functions are determined by some finite set of finitary relations on A. We study this concept for finite algebras in general and for finite semigroups in particular. For example, we show that every finite nilpotent semigroup has finite degree (more generally, every finite algebra with bounded p _n -sequence), and every finite commutative semigroup has finite degree. We give an example of a five-element unary semigroup that has infinite degree. We also give examples to show that finite degree is not preserved in general under taking subalgebras, homomorphic images, direct products or subdirect factors.     

On Nondeterminism,Enumeration Reducibility and Polynomial Bounds

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e-reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non-deterministic polynomial time reducibility. We define the polynomial time e-degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe-degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.     

交换矩阵半群的可约性

首先分别给出单生矩阵半群或者摹群不可约、不可分解以及完全可约的充分必要条件,其次讨论一般域上矩阵半群的可约性的一些条件,最后特别地讨论实数域上矩阵半群的可约性,完全确定了实数域上对称和反对称矩阵组成的不可约交换矩阵半群.     

On Dehn Functions of Infinite Presentations of Groups

We introduce two new types of Dehn functions of group presentations which seem more suitable (than the standard Dehn function) for infinite group presentations and prove the fundamental equivalence between the solvability of the word problem for a group presentation defined by a decidable set of defining words and the property of being computable for one of the newly introduced functions (this equivalence fails for the standard Dehn function). Elaborating on this equivalence and making use of this function, we obtain a characterization of finitely generated groups for which the word problem can be solved in nondeterministic polynomial time. We also give upper bounds for these functions, as well as for the standard Dehn function, for two well-known periodic groups. In particular, we prove that the (standard) Dehn function of a 2-group Γ of intermediate growth, defined by a system of defining relators due to Lysenok, is bounded from above by C₁x² log₂ x, where C₁ > 1 is a constant. We also show that the (standard) Dehn function of a free m-generator Burnside group B(m, n) of exponent n ≥ 2⁴⁸, where n is either odd or divisible by 2⁹, defined by a minimal system of defining relators, is bounded from above by the subquadratic function x^19/12. Received: September 2007, Revision: March 2008, Accepted: March 2008     

On the word problem for the free Burnside semigroups satisfying <Emphasis Type="Italic">x</Emphasis><Superscript>2</Superscript> = <Emphasis Type="Italic">x</Emphasis><Superscript>3</Superscript>

We study the word problem for the free Burnside semigroups satisfying x ² = x ³. For any k > 2, we reduce this problem for the k-generated free Burnside semigroup B(2, 1, k) to the word problem for the two-generated semigroup B(2, 1, 2). Furthermore, if every element of B(2, 1, 2) is a regular language, then every element of B(2, 1, k) appears to be a regular language as well. Thus, Brzozowski’s conjecture holds for the semigroup B(2, 1, k) if and only if it holds for B(2, 1, 2).     

Bisimulations for fuzzy automata

Bisimulations have been widely used in many areas of computer science to model equivalence between various systems, and to reduce the number of states of these systems, whereas uniform fuzzy relations have recently been introduced as a means to model the fuzzy equivalence between elements of two possible different sets. Here we use the conjunction of these two concepts as a powerful tool in the study of equivalence between fuzzy automata. We prove that a uniform fuzzy relation between fuzzy automata A and B is a forward bisimulation if and only if its kernel and co-kernel are forward bisimulation fuzzy equivalence relations on A and B and there is a special isomorphism between factor fuzzy automata with respect to these fuzzy equivalence relations. As a consequence we get that fuzzy automata A and B are UFB-equivalent, i.e., there is a uniform forward bisimulation between them, if and only if there is a special isomorphism between the factor fuzzy automata of A and B with respect to their greatest forward bisimulation fuzzy equivalence relations. This result reduces the problem of testing UFB-equivalence to the problem of testing isomorphism of fuzzy automata, which is closely related to the well-known graph isomorphism problem. We prove some similar results for backward-forward bisimulations, and we point to fundamental differences. Because of the duality with the studied concepts, backward and forward-backward bisimulations are not considered separately. Finally, we give a comprehensive overview of various concepts on deterministic, nondeterministic, fuzzy, and weighted automata, which are related to bisimulations.     

Computable dimension for ordered fields

The computable dimension of a structure counts the number of computable copies up to computable isomorphism. In this paper, we consider the possible computable dimensions for various classes of computable ordered fields. We show that computable ordered fields with finite transcendence degree are computably stable, and thus have computable dimension 1. We then build computable ordered fields of infinite transcendence degree which have infinite computable dimension, but also such fields which are computably categorical. Finally, we show that 1 is the only possible finite computable dimension for any computable archimedean field.     

Pseudo-jump inversion,upper cone avoidance,and strong jump-traceability

There are noncomputable c.e. sets, computable from every c.e. set relative to which ∅^′${\varnothing }^{\prime }$ is strongly jump-traceable. This yields a natural pseudo-jump operator, increasing on all sets, which cannot be inverted back to a minimal pair or even avoiding an upper cone.