RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PERSONAL OFFICE
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Chebyshevskii Sb.: Year: Volume: Issue: Page: Find

 Chebyshevskii Sb., 2016, Volume 17, Issue 2, Pages 137–145 (Mi cheb484)

On equations and inequalities in words and word lengths

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

P.G. Demidov Yaroslavl State University

Abstract: 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. Kosovskiĭ [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$”.

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

Full text: PDF file (620 kB)
References: PDF file   HTML file

Document Type: Article
UDC: 510.53+512.53+512.54

Citation: V. G. Durnev, O. V. Zetkina, A. I. Zetkina, “On equations and inequalities in words and word lengths”, Chebyshevskii Sb., 17:2 (2016), 137–145

Citation in format AMSBIB
\Bibitem{DurZetZet16} \by V.~G.~Durnev, O.~V.~Zetkina, A.~I.~Zetkina \paper On equations and inequalities in words and word lengths \jour Chebyshevskii Sb. \yr 2016 \vol 17 \issue 2 \pages 137--145 \mathnet{http://mi.mathnet.ru/cheb484} \elib{http://elibrary.ru/item.asp?id=26254429}