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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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. 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$”.

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 137--145
\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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019