2 citations · 2 across the 3 of their papers we have counts for
3 papers
math.LO2023
Classifying word problems of finitely generated algebras via computable reducibility
Valentino Delle Rose, Luca San Mauro, Andrea Sorbi
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 len…
math.LO2016
Calibrating word problems of groups via the complexity of equivalence relations
André Nies, Andrea Sorbi
(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…
math.LO2010★ 2 cited
Intuitionistic Logic and Muchnik Degrees
Andrea Sorbi, Sebastiaan A. Terwijn
We prove that there is a factor of the Muchnik lattice that captures intuitionistic propositional logic. This complements a now classic result of Skvortsova for the Medvedev lattic…