Complexity, combinatorial group theory and the language of palutators

DOI10.1016/0304-3975(88)90134-XzbMath0649.20032MaRDI QIDQ1105698

Carol Tretkoff

Publication date: 1988

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

zbMATH Keywords

complexity; HNN extensions; linear time; commutator; languages; word problems; palutators

Mathematics Subject Classification ID

20E06: Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

Related Items

On the parallel complexity of linear groups

Cites Work

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