(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 permutations with a word problem which is a universal co-computably enumerable equivalence relation. (3) Each c.e.\ truth-table degree contains the word problem of a finitely generated group of computable permutations.
Nies, A., Sorbi, A. (2018). Calibrating word problems of groups via the complexity of equivalence relations. MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 28(3), 457-471 [10.1017/S0960129516000335].
Calibrating word problems of groups via the complexity of equivalence relations
SORBI, ANDREA
2018-01-01
Abstract
(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 permutations with a word problem which is a universal co-computably enumerable equivalence relation. (3) Each c.e.\ truth-table degree contains the word problem of a finitely generated group of computable permutations.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
calibrating_word_problems_of_groups_via_the_complexity_of_equivalence_relations.pdf
non disponibili
Descrizione: Articolo unico
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
177.71 kB
Formato
Adobe PDF
|
177.71 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
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/1003211