Complexity of word problems for HNN-extensions

DOI10.1016/J.JCSS.2023.02.005MaRDI QIDQ5925702zbMATH OpenOpenAlexFDO

Authors Markus Lohrey

Publication date 21 April 2023

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2023.02.005

zbMATH Keywords

HNN-extensionshyperbolic groupssomethingword problems

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• A non-cyclic one-relator group all of whose finite quotients are cyclic
• Algorithmics on SLP-compressed strings: a survey
• Almost finitely presented soluble groups
• An introduction to right-angled Artin groups.
• Artin groups of large type are shortlex automatic with regular geodesics.
• Combinatorics of Coxeter Groups
• Compressed word problems in HNN-extensions and amalgamated products
• Computable Algebra, General Theory and Theory of Computable Fields
• Context-Free Groups and Bass–Serre Theory
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• scientific article; zbMATH DE number 3642708 (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 1941341 (Why is no real title available?)
• scientific article; zbMATH DE number 1842475 (Why is no real title available?)
• Knapsack problems in groups
• Logspace computations in graph products
• On finitely generated soluble linear groups
• ON PRODUCTS OF QUASICONVEX SUBGROUPS IN HYPERBOLIC GROUPS
• On the algorithmic insolvability of the word problem in group theory
• Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group.
• Polynomial-time word problems.
• Power circuits, exponential algebra, and time complexity
• Some two-generator one-relator non-Hopfian groups
• Subgroups of small Cancellation Groups
• Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
• The Compressed Word Problem for Groups
• The decision problem for some classes of sentences without quantifiers
• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
• The Nielsen reduction and P-complete problems in free groups
• The word problem
• The word problem
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• Verbal subgroups of hyperbolic groups have infinite width.
• Word Problems Solvable in Logspace
• WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM

Cited in

(1)

• Undecidability of the word problem for Yamamura's HNN-extension under nice conditions.

This page was built for publication: Complexity of word problems for HNN-extensions

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