Functions for parametrization of solutions

of an equation in a free monoid

Authors:
Gennady S. Makanin and Tatiana A. Makanina

Journal:
Trans. Amer. Math. Soc. **352** (2000), 1-54

MSC (1991):
Primary 20M05; Secondary 03D40, 20F10

Published electronically:
March 29, 1999

MathSciNet review:
1491869

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we introduce recursive functions

of the word variables , natural number variables and variables whose values are finite sequences of natural number variables. By means of these functions we give finite expressions for the family of solutions of the equation

where is an arbitrary word in the alphabet , in a free monoid.

**1.**Roger C. Lyndon,*Equations in free groups*, Trans. Amer. Math. Soc.**96**(1960), 445–457. MR**0151503**, 10.1090/S0002-9947-1960-0151503-8**2.**Roger C. Lyndon,*Groups with parametric exponents*, Trans. Amer. Math. Soc.**96**(1960), 518–533. MR**0151502**, 10.1090/S0002-9947-1960-0151502-6**3.**Ju. I. Hmelevskiĭ,*The solution of word equations with three unknowns*, Dokl. Akad. Nauk SSSR**177**(1967), 1023–1025 (Russian). MR**0220847****4.**Ju. I. Hmelevskiĭ,*Equations in a free semigroup*, Trudy Mat. Inst. Steklov.**107**(1971), 286 (Russian). MR**0369575**

Ju. I. Hmelevskiĭ,*Equations in free semigroups*, American Mathematical Society, Providence, R.I., 1976. Translated by G. A. Kandall from the Russian original: Trudy Mat. Inst. Steklov. 107 (1971). MR**0393284****5.**G. S. Makanin and P. Goralcik,*Structure of the solutions of one parametric equation*, Report of research, LIR, INSA of Rouen, April 1996.**6.**G. S. Makanin and H. Abdulrab,*Functions for the general solution of parametric word equations*, Report of research, LIR, INSA of Rouen, June 1996.**7.**G. S. Makanin,*Systems of standard equations in words of an 𝑛-layer alphabet with unknowns*, Sibirsk. Mat. Zh.**19**(1978), no. 3, 637–645, 718 (Russian). MR**501771****8.**G. S. Makanin,*Identification of the rank of equations in a free semigroup*, Izv. Akad. Nauk SSSR Ser. Mat.**43**(1979), no. 3, 547–602, 734 (Russian). MR**541660****9.**M. Lothaire,*Combinatorics on words*, Encyclopedia of Mathematics and its Applications, vol. 17, Addison-Wesley Publishing Co., Reading, Mass., 1983. A collective work by Dominique Perrin, Jean Berstel, Christian Choffrut, Robert Cori, Dominique Foata, Jean Eric Pin, Guiseppe Pirillo, Christophe Reutenauer, Marcel-P. Schützenberger, Jacques Sakarovitch and Imre Simon; With a foreword by Roger Lyndon; Edited and with a preface by Perrin. MR**675953**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (1991):
20M05,
03D40,
20F10

Retrieve articles in all journals with MSC (1991): 20M05, 03D40, 20F10

Additional Information

**Gennady S. Makanin**

Affiliation:
Steklov Mathematical Institute, Vavilova 42, 117 966, Moscow GSP-1, Russia

**Tatiana A. Makanina**

Affiliation:
Steklov Mathematical Institute, Vavilova 42, 117 966, Moscow GSP-1, Russia

DOI:
http://dx.doi.org/10.1090/S0002-9947-99-02287-4

Received by editor(s):
April 14, 1997

Published electronically:
March 29, 1999

Article copyright:
© Copyright 1999
American Mathematical Society