Back to Search
Start Over
The Word Problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable
- Publication Year :
- 2011
-
Abstract
- We prove that the Word Problem in the Baumslag group G ( 1 , 2 ) = 〈 a , b ; a a b = a 2 〉 which has a non-elementary Dehn function is decidable in polynomial time.
- Subjects :
- Computational complexity theory
Group Theory (math.GR)
0102 computer and information sciences
01 natural sciences
Dehn function
Power circuit
Combinatorics
Mathematics::Group Theory
Magnus breakdown algorithm
FOS: Mathematics
0101 mathematics
Baumslag group
Time complexity
Mathematics
Discrete mathematics
Algebra and Number Theory
One-relator group
010102 general mathematics
Word Problem
Mathematics::Geometric Topology
Decidability
Computational complexity
010201 computation theory & mathematics
Word problem (mathematics)
Word problem for groups
Mathematics - Group Theory
Computer Science::Formal Languages and Automata Theory
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....90159904b82df3c11feb6a2bfc66b939