Учредитель: Северный (Арктический) федеральный университет им. М.В. Ломоносова

Адрес редакции: 163002, Архангельская обл., г. Архангельск, наб. Северной Двины, д. 17, каб. 1410а

Тел: (818-2) 21-61-00(15-33)
e-mail: l.zhgileva@narfu.ru
Сайт: http://aer.narfu.ru/

16+

О журнале

Максимальные префиксные коды и подклассы класса контекстно-свободных языков. С. 121–129.

 Версия для печати

Рубрика: Физика, Математика, Информатика

УДК

519.713

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

Корабельщикова Светлана Юрьевна, кандидат физико-математических наук, доцент кафедры математического анализа, алгебры и геометрии института математики, информационных и космических технологий Северного (Арктического) федерального университета имени М.В. Ломоносова. Автор 22 научных публикаций, в т. ч. одной монографии 

Мельников Борис Феликсович, доктор физико-математических наук, профессор, заведующий кафедрой прикладной математики и информатики Тольяттинского филиала Самарского государственного университета. Автор около 200 научных публикаций, в т. ч. 6 монографий

Аннотация

В данной работе рассматривается связь максимальных префиксных кодов с теорией формальных языков и алфавитным кодированием. В терминах максимальных префиксных кодов формулируются условия коммутирования в глобальном надмоноиде свободного моноида, критерий эквивалентности пары конечных языков и ряд других результатов, связанных с бесконечными итерациями языков. Многие из этих результатов связаны с алгоритмическими проблемами для мономиальных алгебр (т. е. ассоциативных алгебр, заданных с помощью так называемых языков обструкций). 
В алфавитном кодировании преимущественно используются префиксные коды, т. к. свойство префикса гарантирует однозначную декодируемость. Максимальные префиксные коды обладают рядом дополнительных свойств: в неравенстве Макмиллана для них выполняется равенство; все вершины кодового дерева являются насыщенными. 
Мы использовали соответствие между максимальными префиксными кодами и кодовыми деревьями, благодаря чему нами произведен подсчет числа максимальных префиксных кодов заданной мощности r в q-буквенном алфавите. В работе получена общая формула, приведены примеры ее применения. 
Максимальных префиксных кодов мощности r над q-буквенным алфавитом не существует, если остаток от деления r на q-1 не равен 1. 
Частное k от деления r на q-1 можно интерпретировать как максимальное число ярусов в кодовом дереве, а также как количество пучков из q ребер, составляющих дерево. Набор (n1, n2, n3, … , ns) представляет собой распределение этих пучков по ярусам кодового дерева. 
В заключение приведен ряд нерешенных задач, сформулированы гипотезы необходимых условий коммутирования, требующие проверки.

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

контекстно-свободный язык, префиксный код, кодовое дерево, максимальный префиксный код.
Скачать статью (pdf, 4.1MB )

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

  1. Лаллеман Ж. Полугруппы и комбинаторные приложения. М., 1985. 376 с. 
  2. 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. Р. 267–274. 
  3. Melnikov B. Some Equivalence Problems for Free Monoids and for Subclasses of the CF-grammars Class // Number Theor. and Algebr. Methods in Comput. Sci. 1995. P. 125–137. 
  4. Мельников Б.Ф. Описание специальных подмоноидов глобального надмоноида свободного моноида // Изв. высш. учеб. заведений. Математика. 2004. № 3. С. 46–56. 
  5. Мельников Б. Некоторые следствия условия эквивалентности однозначных скобочных грамматик // Вестн. Моск. ун-та. Сер. 15. 1991. № 3. С. 51–53. 
  6. Дубасова О.А., Мельников Б.Ф. Об одном расширении класса контекстно-свободных языков // Программирование. 1995. № 6. С. 46–56. 
  7. Melnikov B., Kashlakova E. Some Grammatical Structures of Programming Languages as Simple Bracketed Languages // Informatica. 2000. Т. 11, № 4. С. 441–446. 
  8. Гинзбург С. Математическая теория контекстно-свободных языков. М., 1970. 232 с. 
  9. Станевичене Л. Об одном средстве исследования бесконтекстных языков // Кибернетика. 1989. № 4. С. 135–136. 
  10. Staneviciené L. D-graphs in Сontext-Free Language Theory // Informatica Lithuanian Acad. Sci. 1997. Vol. 8, №. 1. С. 43–56. 
  11. Мейтус В. Разрешимость проблемы эквивалентности детерминированных магазинных автоматов // Кибернетика и систем. анализ. 1992. № 5. С. 20–45. 
  12. Sénizergues G. L(A)=L(B)? Decidability Results From Complete Formal Systems // Theor. Comput. Sci. 2001. Vol. 251, № 1–2. С. 1–166. 
  13. Мельников Б.Ф. Подклассы класса контекстно-свободных языков. М., 1995. 160 с. 
  14. Melnikov B. 2ω-Finite Automata and Sets of Obstructions of Their Languages // Korean J. of Computational and Appl. Math. 1999. № 6. P. 23–28. 
  15. Мельников Б.Ф. Об ω-языках специальных биллиардов // Дискрет. математика. 2002. № 3. С. 95–105. 
  16. Melnikov B. On an Expansion of Nondeterministic Finite Automata // J. Applied Mathematics and Computing. 2007. Т. 24, № 1–2. С. 155–165. 
  17. Драгович В., Раднович М. Интегрируемые биллиарды, квадрики и многомерные поризмы Понселе. М., 2010. 338 с. 
  18. Уфнаровский В. Комбинаторные и асимптотические методы в алгебре // Итоги науки и техн. Современные проблемы математики. Фундамент. направления. 1990. Т. 6. С. 5–177. 
  19. Белов A., Борисенко В., Латышев В. Мономиальные алгебры // Итоги науки и техн. Соврем. математика и ее прил. Темат. обзоры. 2002. Т. 26. С. 35–214. 
  20. Корабельщикова С.Ю., Чесноков А.И. Об одном алгоритме определения количества циклических кодов // Междисциплинарные исследования в области математического моделирования и информатики: материалы 3-й науч.-практ. internet-конф. Ульяновск, 2014. С. 37–41. 
  21. Корабельщикова С.Ю., Чесноков А.И. О числе различных циклических кодов заданной длины // Вектор науки ТГУ. 2013. № 4(26). С. 25–26. 
  22. Зяблицева Л.В., Корабельщикова С.Ю., Чесноков А.И. Линейные коды, исправляющие ошибки, и алгоритмы их подсчета // Эврист. алгоритмы и распределенные вычисления. 2014. Т. 1, вып. 3. С. 47–59. 
  23. Яблонский С.В. Введение в дискретную математику: учеб. пособие для студентов вузов. 3-е изд. М., 2002. 384 с. 
  24. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М., 2004. 416 с.