2 citations · 2 across the 2 of their papers we have counts for
Showing math.LOShow all
2 papers · 1 filter
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…