Word problem (mathematics)
In computational mathematics, a word problem is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities.
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computational mathematics, a word problem is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities. A prototypical example is the word problem for groups, but there are many other instances as well. Some deep results of computational theory concern the undecidability of this question in many important cases.
In computer algebra one often wishes to encode mathematical expressions using an expression tree. But there are often multiple equivalent expression trees. The question naturally arises of whether there is an algorithm which, given as input two expressions, decides whether they represent the same element.
Such an algorithm is called a solution to the word problem. For example, imagine that x,y,z are symbols representing real numbers - then a relevant solution to the word problem would, given the input (x \cdot y)/z \mathrel{\overset{?}{=}} (x/z)\cdot y , produce the output EQUAL , and similarly produce NOT_EQUAL from (x \cdot y)/z \mathrel{\overset{?}{=}} (x/x)\cdot y . The most direct solution to a word problem takes the form of a normal form theorem and algorithm that maps every element in an equivalence class of expressions to a single encoding known as the normal form - the word problem is then solved by comparing these normal forms via syntactic equality.
For example one might decide that x \cdot y \cdot z^{-1} is the normal form of (x \cdot y)/z , (x/z)\cdot y , and (y/z)\cdot x , and devise a transformation system to rewrite those expressions to that form, in the process proving that all equivalent expressions will be rewritten to the same normal form. But not all solutions to the word problem use a normal form theorem - there are algebraic properties that indirectly imply the existence of an algorithm.
While the word problem asks whether two terms containing constants are equal, a proper extension of the word problem known as the unification problem asks whether two terms t_1,t_2 containing variables have instances that are equal, or in other words whether the equation t_1 = t_2 has any solutions. As a common example, 2 + 3 \mathrel{\overset{?}{=}} 8 + (-3) is a word problem in the integer group \mathbb{Z} , while 2 + x \mathrel{\overset{?}{=}} 8 + (-x) is a unification problem in the same group; since the former terms happen to be equal in \mathbb{Z} , the latter problem has the substitution \{x \mapsto 3\} as a solution.
The accessibility problem for string rewriting systems (semi-Thue systems or semigroups) can be stated as follows: Given a semi-Thue system T:=(\Sigma, R) and two words (strings) u, v \in \Sigma^* , can u be transformed into v by applying rules from R ? Note that the rewriting here is one-way. The word problem is the accessibility problem for symmetric rewrite relations, i.e. Thue systems.
The accessibility and word problems are undecidable, i.e. there is no general algorithm for solving this problem. This even holds if we limit the systems to have finite presentations, i.e. a finite set of symbols and a finite set of relations on those symbols. Even the word problem restricted to ground terms is not decidable for certain finitely presented semigroups.
The word problem for groups
Given a presentation \langle S\mid \mathcal{R} \rangle for a group G, the word problem is the algorithmic problem of deciding, given as input two words in S, whether they represent the same element of G. The word problem is one of three algorithmic problems for groups proposed by Max Dehn in 1911. It was shown by Pyotr Novikov in 1955 that there exists a finitely presented group G such that the word problem for G is undecidable.
Example: A term rewriting system to decide the word problem in the free group
Bläsius and Bürckert demonstrate the Knuth–Bendix algorithm on an axiom set for groups. The algorithm yields a confluent and noetherian term rewrite system that transforms every term into a unique normal form. The rewrite rules are numbered incontiguous since some rules became redundant and were deleted during the algorithm run.
The equality of two terms follows from the axioms if and only if both terms are transformed into literally the same normal form term. For example, the terms ((a^{-1} \cdot a) \cdot (b \cdot b^{-1}))^{-1} \mathrel{\overset{R2}{\rightsquigarrow}} (1 \cdot (b \cdot b^{-1}))^{-1} \mathrel{\overset{R13}{\rightsquigarrow}} (1 \cdot 1)^{-1} \mathrel{\overset{R1}{\rightsquigarrow}} 1 ^{-1} \mathrel{\overset{R8}{\rightsquigarrow}} 1 , and b \cdot ((a \cdot b)^{-1} \cdot a) \mathrel{\overset{R17}{\rightsquigarrow}} b \cdot ((b^{-1} \cdot a^{-1}) \cdot a) \mathrel{\overset{R3}{\rightsquigarrow}} b \cdot (b^{-1} \cdot (a^{-1} \cdot a)) \mathrel{\overset{R2}{\rightsquigarrow}} b \cdot (b^{-1} \cdot 1) \mathrel{\overset{R11}{\rightsquigarrow}} b \cdot b^{-1} \mathrel{\overset{R13}{\rightsquigarrow}} 1 share the same normal form, viz.
1 ; therefore both terms are equal in every group. As another example, the term 1 \cdot (a \cdot b) and b \cdot (1 \cdot a) has the normal form a \cdot b and b \cdot a , respectively. Since the normal forms are literally different, the original terms cannot be equal in every group.
In fact, they are usually different in non-abelian groups.
See also
Conjugacy problem Group isomorphism problem
Text derived from https://en.wikipedia.org/w/index.php?oldid=1334682150 under CC BY-SA 4.0; modifications have been made.