Complexity, combinatorial group theory and the language of palutators

DOI10.1016/0304-3975(88)90134-XMaRDI QIDQ1105698zbMATH OpenFDO

Authors Carol Tretkoff

Publication date 1988

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

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)

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 DE number 4145340

Cites work

• scientific article; zbMATH DE number 4014693 (Why is no real title available?)
• scientific article; zbMATH DE number 3642708 (Why is no real title available?)
• scientific article; zbMATH DE number 3841223 (Why is no real title available?)
• scientific article; zbMATH DE number 3871338 (Why is no real title available?)
• scientific article; zbMATH DE number 3876579 (Why is no real title available?)
• scientific article; zbMATH DE number 3911754 (Why is no real title available?)
• scientific article; zbMATH DE number 3920761 (Why is no real title available?)
• scientific article; zbMATH DE number 3983496 (Why is no real title available?)
• scientific article; zbMATH DE number 4036065 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3784868 (Why is no real title available?)
• scientific article; zbMATH DE number 3786761 (Why is no real title available?)
• scientific article; zbMATH DE number 3471577 (Why is no real title available?)
• scientific article; zbMATH DE number 3504960 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 3992933 (Why is no real title available?)
• scientific article; zbMATH DE number 3224578 (Why is no real title available?)
• Commutative monoids have complete presentations by free (non-commutative) monoids
• Complete semi-Thue systems for abelian groups
• Confluent and Other Types of Thue Systems
• Dehn's Algorithm and the Complexity of Word Problems
• Fast Pattern Matching in Strings
• Finite complete rewriting systems and the complexity of word problem
• Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems
• Groups and NTS languages
• Groups, the theory of ends, and context-free languages
• Hierarchies of Computable groups and the word problem
• One-tape, off-line Turing machine computations
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Recursive unsolvability of group theoretic problems
• Some two-generator one-relator non-Hopfian groups
• The accessibility of finitely presented groups
• The complexity of Dehn's algorithm for word problems in groups
• Thue systems as rewriting systems
• Word Problems Solvable in Logspace
• Word problems and a homological finiteness condition for monoids

Cited in

(4)

• scientific article; zbMATH DE number 1224049 (Why is no real title available?)
• On the parallel complexity of linear groups
• Space functions and space complexity of the word problem in semigroups.
• Tree-based language complexity of Thompson's group \(F\).

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)