RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Чебышевский сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Чебышевский сб., 2016, том 17, выпуск 2, страницы 137–145 (Mi cheb484)  

Об уравнениях и неравенствах в словах и длинах

В. Г. Дурнев, О. В. Зеткина, А. И. Зеткина

Ярославский государственный университет им. П. Г. Демидова

Аннотация: Через $\Pi_{m}$, как обычно, мы обозначаем свободную полугруппу с пустым словом в качестве нейтрального элемента ранга $m$ со свободными образующими $a_1,\ldots,a_m$. В теории уравнений на свободной полугруппе $\Pi_{m}$ хорошо известен открытый уже более 40 лет вопрос об алгоритмической разрешимости проблемы совместности для систем уравнений в словах и длинах, т.е. систем вида
$$ \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|, $$
где через $|w|  =   |u|$, как обычно, обозначается предикат “ длины слов $w$ и $u$ равны”. Изучение таких систем уравнений в словах и длинах было начато в начале 70-ых годов прошлого века в работах Ю.В. Матиясевича [15] и Н.К. Косовского [9], [10], [11].
В настоящей заметке доказывается алгоритмическая неразрешимость проблемы совместности для систем уравнений и неравенств в словах и длинах на свободной нециклической полугруппе $\Pi_{m}$: показано, что при $m \geq 2$ не возможно создать алгоритм, позволяющий для произвольной системы неравенств и равенств вида
$$ \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|, $$
где $w_i(x_1,\ldots,x_n,a_1,\ldots,a_m)$ и $u_i(x_1,\ldots,x_n,a_1,\ldots,a_m)$ – слова в алфавите
$$ \lbrace x_1,x_2,\ldots,x_n, a_1,a_2,\ldots,a_m \rbrace , $$
определить, имеет ли она решение в свободной полугруппе $\Pi_{m}$, где через $w  \leq   u$ обозначается предикат “ последовательность букв $w$ является подпоследовательностью последовательности букв $u$”.
Библиография: 19 названий.

Ключевые слова: свободная полугруппа, уравнения в словах и длинах, неравенства в словах и длинах, проблема совместности для систем уравнений и неравенств.

Полный текст: PDF файл (620 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 510.53+512.53+512.54
Поступила в редакцию: 31.03.2016

Образец цитирования: В. Г. Дурнев, О. В. Зеткина, А. И. Зеткина, “Об уравнениях и неравенствах в словах и длинах”, Чебышевский сб., 17:2 (2016), 137–145

Цитирование в формате AMSBIB
\RBibitem{DurZetZet16}
\by В.~Г.~Дурнев, О.~В.~Зеткина, А.~И.~Зеткина
\paper Об уравнениях и неравенствах в словах и длинах
\jour Чебышевский сб.
\yr 2016
\vol 17
\issue 2
\pages 137--145
\mathnet{http://mi.mathnet.ru/cheb484}
\elib{http://elibrary.ru/item.asp?id=26254429}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/cheb484
  • http://mi.mathnet.ru/rus/cheb/v17/i2/p137

    ОТПРАВИТЬ: 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
  • Просмотров:
    Эта страница:98
    Полный текст:20
    Литература:15

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019