Complexity, combinatorial group theory and the language of palutators

DOI10.1016/0304-3975(88)90134-XzbMATH Open0649.20032MaRDI QIDQ1105698FDOQ1105698

Authors: Carol Tretkoff 

Publication date: 1988

Published in: Theoretical Computer Science (Search for Journal in Brave)

Recommendations

• Space complexity and word problems of groups
• scientific article; zbMATH DE number 18644
• scientific article; zbMATH DE number 1534404
• The complexity of Dehn's algorithm for word problems in groups
• scientific article

zbMATH Keywords

complexitycommutatorlinear timeHNN extensionslanguagesword problemspalutators

Mathematics Subject Classification ID

Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Word Problems Solvable in Logspace
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some two-generator one-relator non-Hopfian groups
• Fast Pattern Matching in Strings
• The accessibility of finitely presented groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Word problems and a homological finiteness condition for monoids
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• The complexity of Dehn's algorithm for word problems in groups
• Recursive unsolvability of group theoretic problems
• Groups, the theory of ends, and context-free languages
• One-tape, off-line Turing machine computations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems
• Confluent and Other Types of Thue Systems
• Groups and NTS languages
• Thue systems as rewriting systems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Complete semi-Thue systems for abelian groups
• Finite complete rewriting systems and the complexity of word problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Commutative monoids have complete presentations by free (non-commutative) monoids
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dehn's Algorithm and the Complexity of Word Problems
• Hierarchies of Computable groups and the word problem

Cited In (4)

• Space functions and space complexity of the word problem in semigroups.
• On the parallel complexity of linear groups
• Tree-based language complexity of Thompson's group \(F\).
• Title not available (Why is that?)

This page was built for publication: Complexity, combinatorial group theory and the language of palutators

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