For Publishers
DiscoveryMetadataPeer reviewHostingPublishing
For Researchers
JoinPublishReviewCollect
Register
Blog
About
Search
Advanced search
My ScienceOpen
Search
For Publishers
For Researchers
Blog
About
9
views
10
references
 Top references
cited by
0
    
0 reviews
 Review
0
comments
 Comment
0
recommends
+1 Recommend
0 collections
    0
    shares
      173
      similar
       All similar
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Calibrating word problems of groups via the complexity of equivalence relations

      Preprint
      Author(s): ,
      Publication date Created:

      Read this article at

      ScienceOpenArXiv
      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          (1) There is a finitely presented group with a word problem which is a uniformly effectively inseparable equivalence relation. (2) There is a finitely generated group of computable permutations with a word problem which is a universal co-computably enumerable equivalence relation. (3) Each c.e. truth-table degree contains the word problem of a finitely generated group of computable permutations.

          Related collections

          Most cited references10

          • Record: found
          • Abstract: not found
          • Article: not found

          Subgroups of Finitely Presented Groups

          G. Higman (1961)
          Article 0 comments Cited 47 times – based on 0 reviews     Review now
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Recursive Unsolvability of Group Theoretic Problems

            Michael O. Rabin (1958)
            Article 0 comments Cited 21 times – based on 0 reviews     Review now
              Bookmark
              • Record: found
              • Abstract: found
              • Article: not found

              Classifying positive equivalence relations

              Andrea Sorbi, Cláudio João Bernardi (1983)
              Given two (positive) equivalence relations ~ 1 , ~ 2 on the set ω of natural numbers, we say that ~ 1 is m-reducible to ~ 2 if there exists a total recursive function h such that for every x, y ∈ ω , we have x ~ 1 y iff hx ~ 2 hy . We prove that the equivalence relation induced in ω by a positive precomplete numeration is complete with respect to this reducibility (and, moreover, a “uniformity property” holds). This result allows us to state a classification theorem for positive equivalence relations (Theorem 2). We show that there exist nonisomorphic positive equivalence relations which are complete with respect to the above reducibility; in particular, we discuss the provable equivalence of a strong enough theory: this relation is complete with respect to reducibility but it does not correspond to a precomplete numeration. From this fact we deduce that an equivalence relation on ω can be strongly represented by a formula (see Definition 8) iff it is positive. At last, we interpret the situation from a topological point of view. Among other things, we generalize a result of Visser by showing that the topological space corresponding to a partition in e.i. sets is irreducible and we prove that the set of equivalence classes of true sentences is dense in the Lindenbaum algebra of the theory.
              Article 0 comments Cited 15 times – based on 0 reviews     Review now
                Bookmark
                All references

                Author and article information

                Journal
                Publication date Created: 2016-09-12
                Article
                ArXiV ID: 1609.03371
                SO-VID: b1f7dd2b-f06a-4e8f-bb5c-819b1439572c
                License:

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                ACM classes 03D45
                Comments 13 pages
                Categories math.LO

                ScienceOpen disciplines: Logic & Foundation
                Data availability:
                ScienceOpen disciplines: Logic & Foundation

                Comments

                Comment on this article