Том 12, серия 1, номер 2, 2005 г., Стр. 78-99

УДК 519.718
А. М. Шур
Комбинаторная сложность рациональных языков

Аннотация:
Комбинаторной сложностью языка $L$ называется функция, сопоставляющая числу $n$ число различных слов длины $n$ в языке $L$. Точному вычислению и оценкам комбинаторной сложности различных языков посвящены десятки работ. В статье приводится классификация по сложности произвольных рациональных языков и доказывается, что все эти классы остаются нетривиальными при переходе к подклассу рациональных языков – языкам с конечными антисловарями. Для таких языков известен алгоритм оценки сложности. Этот алгоритм экспоненциален по памяти, но находит практическое применение. Обсуждаются приближения произвольных факторных языков языками с конечными антисловарями, доказывается теорема о приближениях языка Туэ–Морса и формулируется общая гипотеза о сложности таких приближений.

Шур А. М. ¹
1. Уральский гос. университет,
пр. Ленина, 51, 620083 Екатеринбург, Россия
е-mail: Arseny.Shur@usu.ru

Статья поступила 18 августа 2004 г.
Исправленный вариант — 27 декабря 2004 г.