Эта публикация цитируется в
1 статье
Сложность исчислений Ламбека с модальностями и тотальной выводимости в грамматиках
С. М. Дудаковa,
Б. Н. Карловa,
С. Л. Кузнецовb,
Е. М. Фофановаc a Тверской гос. ун-т, г. Тверь, РОССИЯ
b Матем. ин-т им. В. А. Стеклова РАН, г. Москва, РОССИЯ
c Московский гос. ун-т им. М. В. Ломоносова, г. Москва, РОССИЯ
Аннотация:
Исчисление Ламбека с единицей можно определить как атомарную теорию (алгебраическую логику) класса моноидов с делениями. Это исчисление, как теория более широкого класса алгебр, чем гейтинговы алгебры, оказывается слабее интуиционистской логики, и в нём отсутствуют структурные правила перестановки, сокращения и ослабления. Рассматриваются расширения исчисления Ламбека модальностями — экспоненциалом, под знаком которого разрешены все структурные правила, и релевантной модальностью, под знаком которой разрешены только правила перестановки и сокращения. Исчисление Ламбека с релевантной модальностью применяется в математической лингвистике. Оба эти расширения алгоритмически неразрешимы. Рассматриваются их фрагменты, в которых модальность может применяться только к формулам хорновой глубины не более
$1$. Для этих фрагментов доказывается разрешимость и принадлежность классу NP. Для доказательства, в случае релевантной модальности, вводится новое понятие
${\mathcal{R}}$-тотальной выводимости в контекстно-свободных грамматиках — существование вывода, использующего каждое правило не менее определённого числа раз. Устанавливается NP-полнота задачи
${\mathcal{R}}$-тотальной выводимости для контекстно-свободных грамматик, а также выясняется сложность этой задачи для более общих классов порождающих грамматик.
Ключевые слова:
исчисление Ламбека, субструктурная логика, экспоненциал, релевантная модальность, алгоритмическая сложность, контекстно-свободные грамматики, тотальная выводимость.
УДК:
510.649 Поступило: 02.04.2021
Окончательный вариант: 29.11.2021
DOI:
10.33048/alglog.2021.60.502