|
Сложность проблемы равенства слов в модальных и псевдобулевых алгебрах с малым числом порождающих
М. Н. Рыбаков Тверской государственный университет, ул. Желябова, д. 33, г. Тверь, 170100, Россия
Аннотация:
В работе рассматривается проблема равенства термов в гейтинговых и модальных алгебрах с конечным числом порождающих. Показано, что проблема равенства константных термов в модальных алгебрах и проблема равенства произвольных термов в $0$-порожденных модальных алгебрах являются $\mathrm{PSPACE}$-полными. В случае гейтинговых алгебр показано, что аналогичные результаты получаются для термов от двух переменных и, соответственно, для $2$-порожденных гейтинговых алгебр. Кроме того, показано, что если равенство двух позитивных термов не является верным в классе гейтинговых алгебр, то оно опровергается в некоторой $2$-порожденной алгебре. Также обсуждаются вопросы, касающиеся проблемы равенства термов в подклассах класса модальных и класса гейтинговых алгебр. Результаты, близкие упомянутым, получены для бесконечных семейств таких подклассов. Все представленные в работе результаты являются оптимальными в том смысле, что уменьшение числа порождающих либо уже невозможно, либо приводит к ситуации, когда задача равенства термов решается полиномиально по времени.
Ключевые слова:
проблема равенства термов, модальная алгебра, гейтингова алгебра, псевдобулева алгебра, конечно-порожденная алгебра.
Поступила: 25.07.2021 Исправленный вариант: 21.08.2021 Принята к публикации: 29.09.2021
Образец цитирования:
М. Н. Рыбаков, “Сложность проблемы равенства слов в модальных и псевдобулевых алгебрах с малым числом порождающих”, Изв. вузов. Матем., 2022, № 5, 42–60; Russian Math. (Iz. VUZ), 66:5 (2022), 33–48
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ivm9774 https://www.mathnet.ru/rus/ivm/y2022/i5/p42
|
Статистика просмотров: |
Страница аннотации: | 115 | PDF полного текста: | 24 | Список литературы: | 26 | Первая страница: | 6 |
|