GROUPS THAT DO AND DO NOT HAVE GROWING CONTEXT-SENSITIVE WORD PROBLEM.

Area of Science:

• Group Theory
• Theoretical Computer Science
• Formal Languages

Background:

• The word problem for groups is a fundamental concept in group theory and computational complexity.
• Cannon's algorithm provides a method for solving the word problem in certain groups.
• Context-sensitive languages and growing context-sensitive languages represent different levels of computational complexity.

Purpose of the Study:

• To establish a precise characterization of groups whose word problem is a growing context-sensitive language.
• To generalize existing results on Cannon's algorithms and word problem complexity.
• To provide new examples of groups that separate different classes of formal languages.

Main Methods:

• Utilizing non-deterministic Cannon's algorithms to analyze group word problem solvability.
• Generalizing the framework established by Goodman and Shapiro for deterministic algorithms.
• Constructing and analyzing specific group examples to demonstrate language-theoretic separations.

Main Results:

• A group's word problem is a growing context-sensitive language if and only if it is solvable by a non-deterministic Cannon's algorithm.
• Identification of numerous groups that do not admit non-deterministic Cannon's algorithms.
• New examples of groups that distinguish between context-sensitive and growing context-sensitive word problems.

Conclusions:

• The study provides a definitive link between non-deterministic Cannon's algorithms and growing context-sensitive word problems in group theory.
• The findings expand the landscape of known groups with varying word problem complexities.
• This work offers a novel language-theoretic separation result within the study of group word problems.