scientific article; zbMATH DE number 3642708

MaRDI QIDQ3048248zbMATH OpenFDO

Authors Hans Ulrich Simon

Publication date 1979

zbMATH Keywords

contextfree recognitionproduct-complexitytime-complexityword problem for linear groups

Mathematics Subject Classification ID

Word problems, etc. in computability and recursion theory (03D40) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cited in

(18)

• Complexity, combinatorial group theory and the language of palutators
• The complexity of Grigorchuk groups with application to cryptography
• Evaluation of circuits over nilpotent and polycyclic groups
• Compression techniques in group theory
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Evaluating matrix circuits
• On groups that have normal forms computable in logspace.
• On the parallel complexity of linear groups
• Groups with ALOGTIME-hard word problems and PSPACE-complete circuit value problems
• Complexity of word problems for HNN-extensions
• Logspace computations in graph products
• Complexity of word problems for HNN-extensions
• Parallel algorithms for power circuits and the word problem of the Baumslag group
• Improved parallel algorithms for generalized Baumslag groups
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• Residually finite non-linear hyperbolic groups
• Complexity classes of equivalence problems revisited
• Streaming word problems

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3048248)