DOI: 10.33048/alglog.2021.60.501 |
УДК 510.5:512.58 |
В. Делле Розе, Л. Сан Мауро, А. Сорби |
О категории отношений эквивалентности, 451—470. |
Устанавливается несколько первоначальных фактов о категории ${\mathbb{E}\mathrm{q}}$ отношений эквивалентности на множестве натуральных чисел, где морфизмом между двумя отношениями эквивалентности $R,S$ является отображение из множества классов эквивалентности $R$ во множество классов эквивалентности $S$, индуцированное вычислимой функцией. Рассматриваются некоторые полные подкатегории ${\mathbb{E}\mathrm{q}}$, напр., категория ${\mathbb{E}\mathrm{q}}(\Sigma^0_1)$ позитивных отношений эквивалентности, категория ${\mathbb{E}\mathrm{q}}(\Pi^0_1)$ негативных отношений эквивалентности, и категория ${\mathbb{E}\mathrm{q}}({\mathrm{Dark}}^*)$, чьими объектами являются тёмные позитивные отношения и позитивные отношения, имеющие только конечное число классов эквивалентности. Хотя во всех этих категориях мономорфизмы совпадают с инъективными морфизмами, показывается, что в ${\mathbb{E}\mathrm{q}}(\Sigma^0_1)$ эпиморфизмы совпадают с сюръективными морфизмами, но в ${\mathbb{E}\mathrm{q}}(\Pi^0_1)$ существуют эпиморфизмы, не являющиеся сюръективными. Более того, ${\mathbb{E}\mathrm{q}}$, ${\mathbb{E}\mathrm{q}}(\Sigma^0_1)$ и ${\mathbb{E}\mathrm{q}}({\mathrm{Dark}}^*)$ замкнуты относительно конечных произведений, бинарных копроизведений и коуравнителей, но в ${\mathbb{E}\mathrm{q}}(\Pi^0_1)$ найдётся пара морфизмов, чей коуравнитель в ${\mathbb{E}\mathrm{q}}$ не является объектом в ${\mathbb{E}\mathrm{q}}(\Pi^0_1)$. |
Ключевые слова: категория отношений эквивалентности на множестве натуральных чисел, категория позитивных отношений эквивалентности, категория негативных отношений эквивалентности, категория тёмных позитивных и позитивных отношений. |
Адреса авторов:
Delle Rose, Valentino,
Dipartimento di Ingegneria Informatica e Scienze Matematiche
Universit\`a Degli Studi di Siena,
Siena, Italy.
e-mail: valentin.dellerose@student.unisi.it |
DOI: 10.33048/alglog.2021.60.502 |
УДК 510.649 |
С. М. Дудаков, Б. Н. Карлов, С. Л. Кузнецов, Е. М. Фофанова |
Сложность исчислений Ламбека с модальностями и тотальной выводимости в грамматиках, 471—496. |
Исчисление Ламбека с единицей можно определить как атомарную теорию (алгебраическую логику) класса моноидов с делениями. Это исчисление, как теория более широкого класса алгебр, чем гейтинговы алгебры, оказывается слабее интуиционистской логики, и в нём отсутствуют структурные правила перестановки, сокращения и ослабления. Рассматриваются расширения исчисления Ламбека модальностями — экспоненциалом, под знаком которого разрешены все структурные правила, и релевантной модальностью, под знаком которой разрешены только правила перестановки и сокращения. Исчисление Ламбека с релевантной модальностью применяется в математической лингвистике. Оба эти расширения алгоритмически неразрешимы. Рассматриваются их фрагменты, в которых модальность может применяться только к формулам хорновой глубины не более 1. Для этих фрагментов доказывается разрешимость и принадлежность классу {\textup{NP}}. Для доказательства, в случае релевантной модальности, вводится новое понятие ${\mathcal{R}}$-тотальной выводимости в контекстно-свободных грамматиках — существование вывода, использующего каждое правило не менее определённого числа раз. Устанавливается {\textup{NP}}-полнота задачи ${\mathcal{R}}$-тотальной выводимости для контекстно-свободных грамматик, а также выясняется сложность этой задачи для более общих классов порождающих грамматик. |
Ключевые слова: исчисление Ламбека, субструктурная логика, экспоненциал, релевантная модальность, алгоритмическая сложность, контекстно-свободные грамматики, тотальная выводимость. |
Адрес автора:
Дудаков Сергей Михайлович, Тверской гос. ун-т, г. Тверь, Россия. e-mail: sergeydudakov@yandex.ru |
DOI: 10.33048/alglog.2021.60.503 |
УДК 512.54 |
Я. Н. Нужин, А. В. Степанов |
Разложение Брюа для ковровых подгрупп групп Шевалле над полями, 497—509. |
Устанавливаются необходимые и достаточные условия существования разложения Брюа для ковровой подгруппы группы Шевалле над полем, определяемой неприводимым замкнутым ковром аддитивных подгрупп. Оказывается, что ковровые подгруппы, допускающие разложение Брюа и отличные от групп Шевалле, исчерпываются группами, лежащими между группами Шевалле типа $B_l$, $C_l$, $F_4$ или $G_2$ над различными несовершенными полями исключительных характеристик 2 или соответственно 3, большее из которых является алгебраическим расширением меньшего поля. |
Ключевые слова: разложение Брюа, группа Шевалле, ковровая подгруппа. |
Адрес автора:
Нужин Яков Нифантьевич, Сиб. федерал. ун-т, Ин-т матем. фундам.
информ., г. Красноярск, Россия. e-mail: nuzhin2008@rambler.ru |
DOI: 10.33048/alglog.2021.60.504 |
УДК 512.54.01 |
С. А. Шахова |
Классы Леви квазимногообразий групп с коммутантом экспоненты $p$, 510—524. |
Классом Леви, порождённым классом групп $\mathcal{M}$, называется класс всех групп, в которых нормальное замыкание каждого элемента принадлежит $\mathcal{M}$. Даётся описание классов Леви, порождённых квазимногообразием $\mathcal{K}^{p^{s}}$ и некоторыми его подквазимногообразиями, где $\mathcal{K}^{p^{s}}$ — квазимногообразие групп с коммутантом экспоненты $p$, в которых элементы порядка степени $p$, меньшего $p^{s}$, содержатся в центре группы, $p$ — простое число, $p\neq 2$, $s\geq 2$ и $s>2$ при $p=3$. |
Ключевые слова: квазимногообразие, класс Леви, нильпотентная группа. |
Адрес автора: Шахова Светлана Александровна, Алтайский гос. ун-т, г. Барнаул, Россия. e-mail: ssa@math.asu.ru |