
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. 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 noncyclic 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 Received: 31.03.2016
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 137145
\mathnet{http://mi.mathnet.ru/cheb484}
\elib{http://elibrary.ru/item.asp?id=26254429}
Linking options:
http://mi.mathnet.ru/eng/cheb484 http://mi.mathnet.ru/eng/cheb/v17/i2/p137
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles

Number of views: 
This page:  101  Full text:  21  References:  15 
