scientific article

zbMath0413.68044MaRDI QIDQ3048248

Hans Ulrich Simon

Publication date: 1979

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

time-complexitycontextfree recognitionproduct-complexityword problem for linear groups

Mathematics Subject Classification ID

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

Related Items (15)

On the parallel complexity of linear groups ⋮ Complexity, combinatorial group theory and the language of palutators ⋮ Evaluating Matrix Circuits ⋮ On groups that have normal forms computable in logspace. ⋮ Parallel algorithms for power circuits and the word problem of the Baumslag group ⋮ Improved parallel algorithms for generalized Baumslag groups ⋮ A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups ⋮ The complexity of Grigorchuk groups with application to cryptography ⋮ Evaluation of circuits over nilpotent and polycyclic groups ⋮ Complexity classes of equivalence problems revisited ⋮ Unnamed Item ⋮ Complexity of word problems for HNN-extensions ⋮ Complexity of word problems for HNN-extensions ⋮ Logspace computations in graph products ⋮ Compression techniques in group theory

This page was built for publication: