Classifying word problems of finitely generated algebras via computable reducibility

DOI10.1142/S0218196723500339MaRDI QIDQ6116397zbMATH OpenFDO

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)

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)

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.

Cites work

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

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)