Partial Word and Equality Problems and Banach densities

Research output: Contribution to a Journal (Peer & Non Peer)Articlepeer-review

Abstract

We investigate partial Equality and Word Problems for finitely generated groups. After introducing Upper Banach (UB) density on free groups, we prove that solvability of the Equality Problem on squares of UB-generic sets implies solvability of the whole Word Problem. In particular, we prove that solvability of generic EP implies WP. We then exploit another definition of generic EP, which turns out to be equivalent to generic WP. We characterize in different ways the class of groups with unsolvable UB-generic WP, proving that it contains that of infinite algorithmically finite groups, and it is contained in that of groups with unsolvable generic WP.

Original languageEnglish
Article number107133
JournalAdvances in Mathematics
Volume368
DOIs
Publication statusPublished - 15 Jul 2020

Keywords

  • Banach densities on free groups
  • Equality problems
  • Generic computability
  • Word problems

Fingerprint

Dive into the research topics of 'Partial Word and Equality Problems and Banach densities'. Together they form a unique fingerprint.

Cite this