Сложность константного фрагмента пропозициональной динамической логики

Основной результат работы состоит в том, что константные фрагменты логик ${\ bf K} ^\ ast $ (с $ {\ bf K}$-модальностью и её "рефлексивно-транзитивным замыканием"), PDL, а также некоторых других являются EXPTIME-полными. Доказательство содержит описание довольно общей идеи построения полиномиального погружения логик в их фрагменты от $n$ переменных (и даже в константные фрагменты, как в случае ${\ bf K}^\ ast$ и PDL). В качестве следствия описанной конструкции получена EXPTIME-полнота фрагментов от одной переменной логик знания с оператором всеобщего знания.