WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM

DOI10.1142/S0218196700000078zbMath1083.20507OpenAlexW2065701704MaRDI QIDQ4786246

Derek F. Holt

Publication date: 15 December 2002

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218196700000078

zbMATH Keywords

Turing machinesfinitely generated groupsword problemformal languagesword-hyperbolic groupsreal-time languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Hyperbolic groups and nonpositively curved groups (20F67)

Related Items (16)

Notions of hyperbolicity in monoids. ⋮ Generic-case complexity, decision problems in group theory, and random walks. ⋮ CONJUGACY OF FINITE SUBSETS IN HYPERBOLIC GROUPS ⋮ Average-case complexity and decision problems in group theory. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ ON A GENERALIZATION OF DEHN'S ALGORITHM ⋮ Knapsack in hyperbolic groups ⋮ The generalised word problem in hyperbolic and relatively hyperbolic groups ⋮ Complexity of word problems for HNN-extensions ⋮ DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS ⋮ Complexity of word problems for HNN-extensions ⋮ THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS ⋮ Asymptotic invariants, complexity of groups and related problems ⋮ Compression techniques in group theory

Cites Work

• Groups, the theory of ends, and context-free languages
• The theory of ends, pushdown automata, and second-order logic
• Real time computation
• The complexity of Dehn's algorithm for word problems in groups
• A NOTE ON CONTEXT-SENSITIVE LANGUAGES AND WORD PROBLEMS
• Real-Time Definable Languages

This page was built for publication: WORD-HYPERBOLIC GROUPS HAVE REAL-TIME WORD PROBLEM