Compression techniques in group theory

DOI10.1007/978-3-030-80049-9_30MaRDI QIDQ2117795zbMATH OpenOpenAlexFDO

Authors Markus Lohrey

Publication date 22 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-80049-9_30

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The Compressed Word Problem for Groups
• Efficient Computation in Groups Via Compression
• The compressed conjugacy problem in relatively hyperbolic groups
• The compressed word problem in relatively hyperbolic groups
• Polynomial-time word problems.

Cites work

• scientific article; zbMATH DE number 3642708 (Why is no real title available?)
• scientific article; zbMATH DE number 3131923 (Why is no real title available?)
• scientific article; zbMATH DE number 4145340 (Why is no real title available?)
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1003252 (Why is no real title available?)
• scientific article; zbMATH DE number 845841 (Why is no real title available?)
• scientific article; zbMATH DE number 7559438 (Why is no real title available?)
• scientific article; zbMATH DE number 7559146 (Why is no real title available?)
• scientific article; zbMATH DE number 7561687 (Why is no real title available?)
• scientific article; zbMATH DE number 7561757 (Why is no real title available?)
• scientific article; zbMATH DE number 7650891 (Why is no real title available?)
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• Algorithmics on SLP-compressed strings: a survey
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Compressed decision problems for graph products and applications to (outer) automorphism groups.
• Compressed word problems in HNN-extensions and amalgamated products
• Compressed words and automorphisms in fully residually free groups.
• Computable Algebra, General Theory and Theory of Computable Fields
• Coxeter groups are virtually special
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Efficient Computation in Groups Via Compression
• Efficient algorithms for highly compressed data: the word problem in Higman's group is in P
• Evaluation of circuits over nilpotent and polycyclic groups
• Finite Monoids: From Word to Circuit Evaluation
• Generic-case complexity, decision problems in group theory, and random walks.
• Hierarchies of Computable groups and the word problem
• Hydra groups.
• Membership Problem for the Modular Group
• On finitely generated soluble linear groups
• On the algorithmic insolvability of the word problem in group theory
• Parallel identity testing for skew circuits with big powers and applications
• Polynomial-time word problems.
• Power circuits, exponential algebra, and time complexity
• Primality and identity testing via Chinese remaindering
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• Progress on polynomial identity testing. II
• THE GROUPS OF RICHARD THOMPSON AND COMPLEXITY
• Taming the hydra: the word problem and extreme integer compression
• The Compressed Word Problem for Groups
• The Nielsen reduction and P-complete problems in free groups
• The Smallest Grammar Problem
• The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\)
• The structure of groups with a quasiconvex hierarchy
• The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
• The word problem
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM
• Word Problems Solvable in Logspace
• Word Problems and Membership Problems on Compressed Words

Cited in

(3)

• The fully compressed subgroup membership problem
• scientific article; zbMATH DE number 2147487 (Why is no real title available?)
• Compression bases in unital groups

Describes a project that uses

Uses Software

• CRAG

This page was built for publication: Compression techniques in group theory

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