Følner functions and the generic word problem for finitely generated amenable groups
From MaRDI portal
(Redirected from Publication:1663531)
word problemdiscrete amenable groupseffective amenabilitygeneric computabilitygeneric equality problemFølner functions
Cut-elimination and normal-form theorems (03F05) Means on groups, semigroups, etc.; amenable groups (43A07) Decidability of theories and sets of sentences (03B25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)
Abstract: We introduce and investigate different definitions of effective amenability, in terms of computability of F{o}lner sets, Reiter functions, and F{o}lner functions. As a consequence, we prove that recursively presented amenable groups have subrecursive F{o}lner function, answering a question of Gromov, for the same class of groups we prove that solvability of the Equality Problem on a generic set (generic EP) is equivalent to solvability of the Word Problem on the whole group (WP), thus providing the first examples of finitely presented groups with unsolvable generic EP. In particular, we prove that for finitely presented groups, solvability of generic WP doesn't imply solvability of generic EP.
Recommendations
Cites work
- scientific article; zbMATH DE number 3845867 (Why is no real title available?)
- scientific article; zbMATH DE number 5152179 (Why is no real title available?)
- scientific article; zbMATH DE number 4031953 (Why is no real title available?)
- scientific article; zbMATH DE number 3762288 (Why is no real title available?)
- scientific article; zbMATH DE number 67424 (Why is no real title available?)
- scientific article; zbMATH DE number 3264411 (Why is no real title available?)
- A quasi-isometric embedding theorem for groups.
- A small simplification in hyperbolic groups
- ALMOST EVERY GROUP IS HYPERBOLIC
- ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
- Algorithmically complex residually finite groups
- Algorithmically finite groups.
- Cellular automata and groups
- Computability of Følner sets
- Entropy and isoperimetry for linear and non-linear group actions.
- Exponentially generic subsets of groups
- Fast growth in the Følner function for Thompson's group \(F\).
- Generic complexity of undecidable problems
- Generic computability, Turing degrees, and asymptotic density
- Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
- Generic-case complexity, decision problems in group theory, and random walks.
- Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
- Group-based cryptography
- On isoperimetric profiles of finitely generated groups.
- Piecewise automatic groups.
- Random walks on free solvable groups
- Speed of random walks, isoperimetry and compression of finitely generated groups
- THE WORD PROBLEM
- The class of groups all of whose subgroups with lesser number of generators are free is generic
- Topological dimension and dynamical systems. Translated from the French by the author
Cited in
(8)- On decidability of amenability in computable groups
- Exponentially generic subsets of groups
- Fluctuation bounds for ergodic averages of amenable groups
- Computability of Følner sets
- Sofic profiles of \(S(\omega)\) and computability
- Computable paradoxical decompositions
- Partial word and equality problems and Banach densities
- Graph automaton groups
This page was built for publication: Følner functions and the generic word problem for finitely generated amenable groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1663531)
