Верхняя оценка конечноавтоматной сложности для одного класса порождающих схем с операциями дополнения и пересечения

Порождающие схемы (ПС) – это способ порождения регулярных множеств, обобщающий обычные регулярные выражения в двух направлениях: (I) допускаются операции теоретико-множественного дополнения и пересечения, (2) вместо операций объединения, конкатенации и итерации используются ориентированные графы, дугам которых приписаны множества слов. Минимальное число состояний конечного автомата, допускающего множество, представимое данной ПС, оценивается в терминах сложности этой ПС. Эта функция, как показано в [I], растет очень быстро для класса всех ПС, но ограничена функцией вида $2^{2^n}$ для класса ПС с ограничениями на расположение вхождений операций пересечения и дополнения. В настоящей статье эта оценка улучшена: гиперэкспонента от $n$ заменена на число монотонных булевских функций от $n$ переменных. Доказательство основано на специальном соотношении между множествами слов и множествами вершин и дуг ПС.