УДК

512.5

Сведения об авторах

С.Ю. Корабельщикова*, Б.Ф. Мельников**
*Северный (Арктический) федеральный университет имени М.В. Ломоносова
**Тольяттинский филиал Самарского национального исследовательского университета имени академика С.П. Королёва

Аннотация

Приведен и доказан ряд свойств глобальных надмоноидов свободных моноидов, которые, в свою очередь, также являются моноидами. В частности, доказаны условия наличия левого и правого делителей в рассматриваемых глобальных надмоноидах, из которых следует несвободность последних. На основании этих свойств доказано необходимое условие выполнения равенства A^m = Bⁿ для глобальных надмоноидов свободных моноидов, которое состоит в наличии у глобальных надмоноидов А и В общего корня (в общем случае различной степени). Результаты получены при условии, что по крайней мере один из языков обладает свойством префикса. Также рассмотрена задача нахождения корня n-й степени из заданного языка. Она решается для языка специального вида, состоящего из всех слов длиной от t₁ до t₂ (t₁ ≤ t₂) над алфавитом Σ . Очевидно, что критерий существования корня n-й степени – делимость t₁ и t₂ на n. В работе приведено необходимое и достаточное условие того, что язык специального вида является корнем n-й степени из заданного языка такого же вида, введены понятия тривиального и первообразного корня, представлен пример, поясняющий данные определения. Все приведенные в статье примеры актуальны для прикладных вопросов рассматриваемой теории, в частности для построения специальных вариантов автоматизированного преобразования регулярных грамматических структур и контекстно-свободных грамматик в системах автоматизации построения компиляторов. В терминах введенных нами понятий формулируется необходимое условие того, что язык произвольного вида в алфавите Σ является корнем n-й степени из заданного языка специального вида. Вопрос о том, достаточно ли полученное авторами условие, пока остается открытым.

Ключевые слова

свободный моноид, глобальный надмоноид, префиксный язык, корень из элементов надмоноида

Список литературы

1. Melnikov B. Some Equivalence Problems for Free Monoids and for Subclasses of the CF-grammars Class. 1995. P. 67–68.
2. Мельников Б.Ф. Описание специальных подмоноидов глобального надмоноида свободного моноида // Изв. вузов. Математика. 2004. № 3(502). С. 46–56.
3. Melnikov B. The Equality Condition for Infinite Catenations of Two Sets of Finite Words // Int. J. of Found. of Comp. Sci. 1993. Vol. 4, № 3. P. 267–274.
4. Корабельщикова С.Ю., Мельников Б.Ф. Итерации языков и максимальные префиксные коды // Вестн. Воронеж. гос. ун-та. Сер.: Физика. Математика. 2015. № 2. С. 106–120.
5. Саломаа А. Жемчужины теории формальных языков. М., 1986. 159 с.
6. Лаллеман Ж. Полугруппы и комбинаторные приложения. М., 1985. 440 с.
7. Лидл Р., Пильц Г. Прикладная абстрактная алгебра. Екатеринбург, 1997. 764 с.
8. Корабельщикова С.Ю., Чесноков А.И., Тутыгин А.Г. О первообразных корнях из языков специального вида // Дискретные модели в теории управляющих систем: тр. IX Междунар. конф. (Москва и Подмосковье, 20–22 мая 2015 г.). М., 2015. С. 116–118.
9. Корабельщикова С.Ю., Чесноков А.И. Лунная арифметика в приложении к задаче извлечения корней из языков специального вида // Информатизация процессов формирования открытых систем на основе САПР, АСНИ и систем искусственного интеллекта «Инфос-2015»: 8-я междунар. науч.-техн. конф. (26–27 июня 2015 г.). Вологда, 2015. С. 73–77.
10. Melnikov B.F., Melnikova A.A. Some Properties of the Basis Finite Automaton // Korean Journal of Computational and Applied Mathematics. 2002. Vol. 9, № 1. P. 135–150.
11. Мельников Б.Ф., Пивнева С.В., Рогова О.А. Репрезентативность случайно сгенерированных недетерминированных конечных автоматов с точки зрения соответствующих базисных автоматов // Стохаст. оптимизация в информатике. 2010. Т. 6, № 1-1. С. 74–82.
12. Корабельщикова С.Ю., Мельников Б.Ф. Максимальные префиксные коды и проблема равенства в разных классах языков // Проблемы теоретической кибернетики: материалы XVII Междунар. конф. (Казань, 16–20 июня 2014 г.). Казань, 2014. C. 143–146.