Classifying word problems of finitely generated algebras via computable reducibility

DOI10.1142/S0218196723500339arXiv2305.11563MaRDI QIDQ6116397FDOQ6116397

Authors: Valentino Delle Rose, Luca San Mauro, Andrea Sorbi 

Publication date: 18 July 2023

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Abstract: We contribute to a recent research program which aims at revisiting the study of the complexity of word problems, a major area of research in combinatorial algebra, through the lens of the theory of computably enumerable equivalence relations (ceers), which has considerably grown in recent times. To pursue our analysis, we rely on the most popular way of assessing the complexity of ceers, that is via computable reducibility on equivalence relations, and its corresponding degree structure (the c-degrees). On the negative side, building on previous work of Kasymov and Khoussainov, we individuate a collection of c-degrees of ceers which cannot be realized by the word problem of any finitely generated algebra of finite type. On the positive side, we show that word problems of finitely generated semigroups realize a collection of c-degrees which embeds rich structures and is large in several reasonable ways.

Full work available at URL: https://arxiv.org/abs/2305.11563

zbMATH Keywords

finitely generated algebrasword problemscomputable reducibilitycomputably enumerable structurescomputably enumerable equivalence relations

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Word problems, etc. in computability and recursion theory (03D40)

Cites Work

• Finitely presented expansions of groups, semigroups, and algebras
• Algorithmically finite groups.
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• \(\Pi^0_1\)-presentations of algebras
• Definability of linear orders over negative equivalences
• Graphs realised by r.e. equivalence relations
• The word problem
• The degrees of hyperhyperimmune sets
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Turing computability. Theory and applications
• Computably enumerable equivalence relations
• Two notes on subshifts
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• Finitely presented expansions of computably enumerable semigroups
• Linear orders realized by c.e. equivalence relations
• Title not available (Why is that?)
• Reducibilities among equivalence relations induced by recursively enumerable structures
• Title not available (Why is that?)
• A survey on universal computably enumerable equivalence relations
• A journey to computably enumerable structures (tutorial lectures)
• The theory of ceers computes true arithmetic
• Joins and meets in the structure of ceers
• A quest for algorithmically random infinite structures
• Initial segments of the degrees of ceers
• Title not available (Why is that?)
• The category of equivalence relations
• Word problems and ceers
• Effective aspects of algorithmically random structures

Cited In (1)

• Reductions and functors from problems to word problems

This page was built for publication: Classifying word problems of finitely generated algebras via computable reducibility

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6116397)