Верхние оценки конечно-автоматной сложности обобщенных регулярных выражений в однобуквенном алфавите

В работе сравнивается сложность задания регулярного события конечным автоматом и обобщенным регулярным выражением. Мерой сложности автомата является число его состояний $G$ , мерой сложности обобщенного регулярного выражения его уточненная длина $\alpha$. Показано, что для обобщенных (есть операции теоретико-множественного дополнения и пересечения) регулярных выражений в днобуквенном алфавите $G\leqslant3^\alpha$.