𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of the word problem for abelian l-groups

✍ Scribed by Volker Weispfenning

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
365 KB
Volume
48
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On complexity of the word problem in bra
On complexity of the word problem in braid groups and mapping class groups
✍ Hessam Hamidi-Tehrani πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 350 KB

We prove that the word problem in the mapping class group of the once-punctured surface of genus g has complexity O(|w| 2 g) for |w| log(g) where |w| is the length of the word in a (standard) set of generators. The corresponding bound in the case of the closed surface is O(|w| 2 g 2 ). We also carry

The P-DNP Problem for Infinite Abelian G
The P-DNP Problem for Infinite Abelian Groups
✍ Christine Gaßner πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 123 KB

We consider a uniform model of computation for groups. This is a generalization of the Blum Shub Smale model over the additive group of real numbers. We show that the inequalities P{DNP and PQ{DNPQ hold for computations with or without parameters over arbitrary infinite abelian groups.