|
Чебышевский сборник, 2012, том 13, выпуск 1, страницы 63–80
(Mi cheb15)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Об уравнениях в свободных группах, разрешенных относительно неизвестных, с ограничениями на решения
В. Г. Дурнев, О. В. Зеткина Ярославский государственный университет им. П. Г. Демидова
Аннотация:
Устанавливается алгоритмическая неразрешимость проблемы разрешимости в свободной группе $F_2$ ранга 2 со свободными образующими $a$ и $b$ для систем уравнений с ограничениями на решения вида
$$
w(x_1, \dots , x_n) = [a, b] \& \overset{t}{\underset{i=1}{\&}} x_i \in F_2^{(1)}
$$
и вида
$$
w(x_1, \dots , x_n) = [a, b] \& x_1 \in F_2^{(2)},
$$
где $w(x_1, \dots , x_n)$ – слово в алфавите неизвестных $\{x_1, \dots , x_n\}$, $[a, b]$ – коммутатор свободных образующих $a$ и $b$, $F_2^{(1)}$ – коммутант группы $F_2$, а $F_2^{(2)}$ – ее второй коммутант.
Устанавливается существование полиномиального алгоритма, позволяющего по произвольному разрешенному относительно неизвестных уравнению вида
$$
w(x_{1},\dots ,x_{n} ) = g(a, b),
$$
где $w(x_{1},\dots ,x_{n} )$ – групповое слово в алфавите неизвестных, а $g(a, b)$ – элемент длины меньше 4 свободной группы $F_{2}$, определить, существует ли решение этого уравнения, удовлетворяющее условию
$$
x_{1} \in F_{2}^{(s)},\dots ,x_{t} \in F_{2}^{(s)},
$$
где $t$ – произвольное фиксированное число между 1 и $n$, а $F_2^{(s)}$ – $s$-ый коммутант группы $F_2$.
Устанавливается алгоритмическая разрешимость аналогичных проблем для уравнений с одним неизвестным.
Поступила в редакцию: 18.05.2012
Образец цитирования:
В. Г. Дурнев, О. В. Зеткина, “Об уравнениях в свободных группах, разрешенных относительно неизвестных, с ограничениями на решения”, Чебышевский сб., 13:1 (2012), 63–80
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/cheb15 https://www.mathnet.ru/rus/cheb/v13/i1/p63
|
Статистика просмотров: |
Страница аннотации: | 283 | PDF полного текста: | 75 | Список литературы: | 50 | Первая страница: | 1 |
|