On equations and inequalities in words and word lengths

V. G. Durnev ; O. V. Zetkina ; A. I. Zetkina

Čebyševskij sbornik, Tome 17 (2016) no. 2, pp. 137-145.

Résumé

By $\Pi_{m}$ we denote, as usual, a free semigroup with an empty word as the neutral element of rank $m$ with free generators $a_1,\ldots,a_m$. An open question in the theory of equations on free semigroup $\Pi_{m}$, which have been well known for more than 40 years, concerns the algorithmic undecidability of the problem of compatibility for systems of equations and inequalities in words and word lengths, i.e., for systems of the type $$ \underset{i=1}{\overset{k}{\}} \, w_i (x_1, \ldots , x_n, a_1, \ldots , a_m) \, = \, u_i(x_1, \ldots , x_n, a_1, \ldots , a_m)\; \ \; \underset{\{ i, j \}\, \in \, A}{\} \; |x_i| \, = \, |x_j|, $$ where, as usual, by $|w|\, = \, |u|$, we denote the predicate "the lengths of the words $w$ and $u$ are equal". Such systems of equations and inequalities in words and word lengths were studied in the beginning of 1970s by Yu.V. Matiyasevich [15] (1968) and N. K. Kosovskiĭ [9], [10], [11]. We prove the algorithmic undecidability of a compatibility problem for systems of equations and inequalities in words and word lengths on free non-cyclic semigroup $\Pi_{m}$. For an arbitrary system of equations and inequalities of the type $$ \underset{i=1}{\overset{k}{\}} \, w_i (x_1,\ldots,x_n,a_1,\ldots,a_m)\, \leq \, u_i (x_1,\ldots,x_n,a_1,\ldots,a_m)\; \ \; \underset{\{ i, j \}\, \in \, A}{\} \; |x_i| \, = \, |x_j|, $$ where $w_i(x_1,\ldots,x_n,a_1,\ldots,a_m)$ and $u_i(x_1,\ldots,x_n,a_1,\ldots,a_m)$ are words in the alphabet $$ \lbrace\,x_1,x_2,\ldots,x_n, a_1,a_2,\ldots,a_m\,\rbrace , $$ it is shown that no algorithm can decide whether this system has a solution in free semigroup $\Pi_{m}$ at $m \geq 2$. Here $w\, \leq \, u$ denotes the predicate "the sequence $w$ of letters is a subsequence of the sequence $u$".

Détail

Keywords: free semigroup, equations in words and word lengths, inequalities in words and word lengths, compatibility problem for systems of equations and inequalities.

Bibliographie

[1] Durnev V. G., “On equations in free semigroups and groups”, Mathematical Notes, 16:5 (1974), 1024–1028 | DOI | MR

[2] Durnev V. G., “On some equations on free semigroups”, Group Theory, Homological Algebra, Yaroslavl' State University, Yaroslavl', 1977, 57–59

[3] Durnev V. G., Zetkina O. V., “On equations in free semigroups with certain constraints on their solutions”, Group Theory, Homological Algebra, Yaroslavl' State University, Yaroslavl', 2003

[4] Durnev V. G., Zetkina O. V., “On equations in free semigroups with certain constraints to their solutions”, Journal of Mathematical Sciences, 158:5 (2008), 671–676 | DOI | MR

[5] Durnev V. G., Zetkina O. V., “Equations with subsemigroup constraints to their solutions in free semigroups”, Thebyshev Sbornik, XI:3(35) (2010), 78–87 | Zbl

[6] Durnev V. G., “On equations with endomorphisms in free semigroups and groups”, Group Theory, Homological Algebra, Yaroslavl' State University, Yaroslavl', 1991, 30–35

[7] Durnev V. G., “Equations with endomorphisms in free semigroups”, Diskret. Mat., 4:2 (1992), 136–141 | MR

[8] Durnev V. G., “On equations in words and lengths with endomorphisms”, Russian Math. (Izvestiya VUZ. Matematika), 36:8 (1992), 26–30 | MR | Zbl

[9] Kosovski\u{i} N. K., “Certain properties of the solutions of equations in a free semigroup”, Investigations in constructive mathematics and mathematical logic, Proc. Steklov Math. Inst., Leningrad, 32, 1972, 21–28 | MR

[10] Kosovski\u{i} N. K., “On sets represented as solutions of equations in words and lengths”, 2nd USSR Conference on mathematical logics, Book of abstracts (Moscow, 1972), 23

[11] Kosovski\u{i} N. K., “The solution of systems that consist simultaneously of word equations and word length inequalities”, Investigations in constructive mathematics and mathematical logic, VI, Dedicated to A. A. Markov on the occasion of his 70th birthday, Proc. Steklov Math. Inst., Leningrad, 40, 1974, 24–29 | MR | Zbl

[12] Makanin G. S., “The problem of the solvability of equations in a free semigroup”, Soviet Math. Dokl., 18:2 (1977), 330–334 | MR | MR | Zbl

[13] Makanin G. S., “The problem of solvability of equations in a free semigroup”, Math. USSR Sb., 32:2 (1977), 129–198 | DOI | MR | MR | Zbl | Zbl

[14] Matiyasevich Yu. V., “Enumerable sets are Diophantine”, Soviet Math. Doklady, 11:2 (1970), 354–358 | Zbl

[15] Matiyasevich Yu. V., “The connection between systems of equations in words and lengths with Hilbert's 10th problem”, Studies on constructive mathematics and mathematical logics, Proc. Steklov Math. Inst., Leningrad, 8, 1968, 132–143

[16] Hmelevskiĭ Ju. I., “Equations in a free semigroup”, Proc. Steklov Inst. Math., 107, 1971, 1–270 | MR

[17] Buchi J. R., Senger S., “Definability in the existential theory of concatenation”, Z. math. Log. und Grundl. Math., 34:4 (1988), 337–342 | DOI | MR | Zbl

[18] Buchi J. R., Senger S., “Coding in the existential theory of concatenation”, Arch. Math. Logik, 26 (1986/87), 101–106 | DOI | MR | Zbl

[19] Karhumaki J., Mignosi F., Plandowski W., “On the expressibility of languages by word equations with a bounded number of variables”, Bull. Belg. Math. Soc. Simon Stevin, 8:2 (2001), 293–305 (accessed 25 June 2016) http://projecteuclid.org/euclid.bbms/1102714174 | MR | Zbl