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.

Delle Rose, V., San Mauro, L., Sorbi, A. (2023). Classifying word problems of finitely generated algebras via computable reducibility. INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 33(4), 751-768 [10.1142/S0218196723500339].

Classifying word problems of finitely generated algebras via computable reducibility

Andrea Sorbi
2023-01-01

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.
2023
Delle Rose, V., San Mauro, L., Sorbi, A. (2023). Classifying word problems of finitely generated algebras via computable reducibility. INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 33(4), 751-768 [10.1142/S0218196723500339].
File in questo prodotto:
File Dimensione Formato  
word-problems-classifying.pdf

non disponibili

Descrizione: file pdf
Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 372.65 kB
Formato Adobe PDF
372.65 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2305.11563.pdf

accesso aperto

Tipologia: Pre-print
Licenza: PUBBLICO - Pubblico con Copyright
Dimensione 227.83 kB
Formato Adobe PDF
227.83 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1243254