Logspace computations in graph products

DOI10.1016/j.jsc.2015.11.009zbMath1335.68103OpenAlexW1936658532MaRDI QIDQ5925209

Volker Diekert, Jonathan Kausch

Publication date: 11 February 2016

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jsc.2015.11.009

zbMATH Keywords

geodesicsword problemgraph productsconjugacy problemlogspace complexityalgorithmic group theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Graph operations (line graphs, products, etc.) (05C76)

Related Items

A Heuristic for Direct Product Graph Decomposition, Knapsack in graph groups, Complexity of word problems for HNN-extensions, Complexity of word problems for HNN-extensions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On groups that have normal forms computable in logspace.
• Graph groups, coherence, and three-manifolds
• A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups.
• On some equations in free partially commutative monoids
• Morse theory and finiteness properties of groups
• On linear and residual properties of graph products
• Embeddings of graph braid and surface groups in right-angled Artin groups and braid groups.
• Logspace Computations in Coxeter Groups and Graph Groups
• Algorithmics on SLP-compressed strings: A survey
• Some geodesic problems in groups
• The Length of Elements in Free Solvable Groups
• Asymptotic invariants, complexity of groups and related problems
• The set of minimal braids is co-NP-complete
• SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE
• WORD EQUATIONS OVER GRAPH PRODUCTS
• The conjugacy problem in subgroups of right-angled Artin groups
• Word Problems Solvable in Logspace
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• COMPRESSED DECISION PROBLEMS FOR GRAPH PRODUCTS AND APPLICATIONS TO (OUTER) AUTOMORPHISM GROUPS
• The word and geodesic problems in free solvable groups
• Parallel Program Schemata and Maximal Parallelism I. Fundamental Results
• DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
• Generalized Free Products of Linear Groups
• Logspace computations in graph products