|
Теоретические основы прикладной дискретной математики
Об уравнениях в свободных моноидах и полугруппах с ограничениями на решения
В. Г. Дурнев, А. И. Зеткина Ярославский государственный университет им. П. Г. Демидова, г. Ярославль, Россия
Аннотация:
Изучаются алгоритмические проблемы для уравнений в свободных моноидах и полугруппах (уравнения в словах и длинах) с дополнительными ограничениями на решения. Доказывается, что невозможно построить алгоритм, позволяющий по произвольной системе уравнений в словах и длинах в свободном моноиде (свободной полугруппе) ранга 2 с одним дополнительным ограничением на решение в форме принадлежности одной его компоненты языку сбалансированных слов или равенства проекций двух компонент решения на одну выделенную свободную образующую определить, имеет ли она решение. Аналогичный результат установлен для систем неравенств в словах.
Ключевые слова:
системы уравнений в свободных моноидах и свободных полугруппах, уравнения в словах и длинах, уравнения с ограничениями на решения.
Образец цитирования:
В. Г. Дурнев, А. И. Зеткина, “Об уравнениях в свободных моноидах и полугруппах с ограничениями на решения”, ПДМ, 2023, № 59, 5–19
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm791 https://www.mathnet.ru/rus/pdm/y2023/i1/p5
|
Статистика просмотров: |
Страница аннотации: | 132 | PDF полного текста: | 53 | Список литературы: | 38 |
|