1996/01/01 by Gennady S. Makanin · 1 citation
Mathematics · Computer Science · #Advanced Differential Equations and Dynamical Systems #Mathematical Control Systems and Analysis #Polynomial and algebraic computation
paper · pdf · doi:10.1090/s0002-9947-96-01670-4
openalex publication_date 1996/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
This paper deals with the problem of describing the set <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"> <mml:semantics> <mml:mi>M</mml:mi> <mml:annotation encoding="application/x-tex">M</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of all solutions of an equation over a free semigroup <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . The standard way to do this involves the introduction of auxiliary equations containing polynomials in natural number parameters of arbitrarily high degree. Since <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has a solvable word problem, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"> <mml:semantics> <mml:mi>M</mml:mi> <mml:annotation encoding="application/x-tex">M</mml:annotation> </mml:semantics> </mml:math> </inline-formula> must be computable. However, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"> <mml:semantics> <mml:mi>M</mml:mi> <mml:annotation encoding="application/x-tex">M</mml:annotation> </mml:semantics> </mml:math> </inline-formula> cannot necessarily be computed from the standard description of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"> <mml:semantics> <mml:mi>M</mml:mi> <mml:annotation encoding="application/x-tex">M</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . The present paper shows that the only polynomials needed to describe <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"> <mml:semantics> <mml:mi>M</mml:mi> <mml:annotation encoding="application/x-tex">M</mml:annotation> </mml:semantics> </mml:math> </inline-formula> are just products of one parameter by a linear combination of some other parameters. The resulting simplification of the standard description of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"> <mml:semantics> <mml:mi>M</mml:mi> <mml:annotation encoding="application/x-tex">M</mml:annotation> </mml:semantics> </mml:math> </inline-formula> clearly can be used to compute <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"> <mml:semantics> <mml:mi>M</mml:mi> <mml:annotation encoding="application/x-tex">M</mml:annotation> </mml:semantics> </mml:math> </inline-formula> .