Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-15T22:12:48.447Z Has data issue: false hasContentIssue false
  • English
  • Français

Calibrating word problems of groups via the complexity of equivalence relations

Published online by Cambridge University Press:  19 October 2016

ANDRÉ NIES and
ANDREA SORBI
ANDRÉ NIES
Affiliation:
Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand Email: andre@cs.auckland.ac.nz
ANDREA SORBI
Affiliation:
Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche, Università di Siena, 53100 Siena, Italy Email: andrea.sorbi@unisi.it
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

(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.

References

Andrews, U., Lempp, S., Miller, J. S., Ng, K. M., San Mauro, L. and Sorbi, A. (Mar. 2014) Universal computably enumerable equivalence relations. Journal of Symbolic Logic 79 (1) 60–88.Google Scholar
Andrews, U. and Sorbi, A. (2015) Jumps of computably enumerable equivalence relations, in preparation.Google Scholar
Bernardi, C. (1981) On the relation provable equivalence and on partitions in effectively inseparable sets. Studia Logica 40 (1) 29–37.Google Scholar
Bernardi, C. and Montagna, F. (1984) Equivalence relations induced by extensional formulae: Classifications by means of a new fixed point property. Fundamenta Mathematicae 124 (3) 221–232.Google Scholar
Bernardi, C. and Sorbi, A. (1983) Classifying positive equivalence relations. Journal of Symbolic Logic 48 (3) 529–538.CrossRefGoogle Scholar
Boone, W. W. (1966) Word problems and recursively enumerable degrees of unsolvability. A first paper on Thue systems. Annals of Mathematics 83 (3) 520–571.Google Scholar
Boone, W. W. (1966b) Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups. Annals of Mathematics 84 (1) 49–84.CrossRefGoogle Scholar
Boone, W. W. (1971) Word problems and recursively enumerable degrees of unsolvability. An emendation. Annals of Mathematics 94 (3) 389–391.Google Scholar
Clapham, C. R. J. (1964) Finitely presented groups with word problems of arbitrary degrees of insolubility. Proceedings of the London Mathematical Society 3 (4) 633–676.Google Scholar
Collins, D. J. (1971) Truth-table degrees and the Boone groups. Annals of Mathematics 94 (3) 392–396.Google Scholar
Coskey, S., Hamkins, J. D. and Miller, R. (2012) The hierarchy of equivalence relations on the natural numbers. Computability 1 (1) 15–38.Google Scholar
Ershov, Yu. L. (1973a) Positive equivalences. Algebra and Logic 10 (6) 378–394.Google Scholar
Ershov, Yu. L. (1973b) Theorie der Numerierungen I. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19 289–388.Google Scholar
Ershov, Yu. L. (1975) Theorie der Numerierungen II. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 21 473–584.Google Scholar
Fokina, E. B., Friedman, S. D., Harizanov, V., Knight, J. F., Mc Coy, C. and Montalbán, A. (2012a) Isomorphism relations on computable structures. Journal of Symbolic Logic 77 (1) 122–132.Google Scholar
Fokina, E. B., Friedman, S. D. and Nies, A. (2012b) Equivalence relations that are Σ0 3 complete for computable reducibility. In: Ong, L. and de Queiroz, R. (eds.) Logic, Language, Information and Computation: 19th International Workshop, WoLLIC 2012, Buenos Aires, Argentina, September 3-6, 2012, Proceedings. Theoretical Computer Science and General Issues, Lecture Notes in Computer Science, volume 7456, Springer-Verlag, Berlin, Heidelberg, 26–33.Google Scholar
Fridman, A. A. (1962) Degrees of unsolvability of the problem of identity in finitely presented groups. Soviet Mathematics 3 (Part 2) 1733–1737.Google Scholar
Gao, S. and Gerdes, P. (2001) Computably enumerable equivalence relations. Studia Logica 67 (1) 27–59.Google Scholar
Higman, G. (1961) Subgroups of finitely presented groups. Proceedings of the Royal Society of London. Series A 262 (1311) 455–475.Google Scholar
Ianovski, E., Miller, R., Ng, K. M. and Nies, A. (2014) Complexity of equivalence relations and preorders from computability theory. Journal of Symbolic Logic 79 (3) 859–881.Google Scholar
Kargapolov, M. I. and Merzljakov, Ju. I. (1979) Fundamentals of the Theory of Groups, Graduate Texts in Mathematics, 2nd edition, Springer-Verlag, New York, Heidelberg, Berlin.Google Scholar
Lyndon, R. C. and Schupp, P. E. (1977) Combinatorial Group Theory, Springer-Verlag, Berlin Heidelberg.Google Scholar
Miller, C. F. III (1971) Group-Theoretic Decision Problems and their Classification. Annals of Mathematical Studies, volume 68, Princeton University Press, Princeton, New Jersey.Google Scholar
Miller, C. F. III (2002) The word problem in quotients of a group. Available at: http://www.ms.unimelb.edu.au/cfm/papers/paperpdfs/wpqg.pdf.Google Scholar
Montagna, F. (1982) Relative precomplete numerations and arithmetic. Journal of Philosphical Logic 11 (4) 419–430.Google Scholar
Morozov, A. S. (2000) Higman's question revisited. Algebra and Logic 39 (2) 78–83.Google Scholar
Rabin, M. O. (1958) Recursive unsolvability of group theoretic problems. Annals of Mathematics Series 2 67 (1) 172–174.Google Scholar
Soare, R. I. (1987) Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic, Omega Series, Springer-Verlag, Heidelberg.Google Scholar
Visser, A. (1980) Numerations, λ-calculus & arithmetic. In: Seldin, J. P. and Hindley, J. R. (eds.) To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism, Academic Press, London, 259–284.Google Scholar
Ziegler, M. (1976) Ein rekursiv aufzählbarer btt-Grad, der nicht zum Wortproblem einer Gruppe gehört. Zeitschrift für mathematische Logik und Grundlagen der Mathematik 22 165–168.Google Scholar