Архив статей журнала
Генерические алгоритмы решают проблемы на множествах почти всех входов, выдавая неопределённый ответ для остальных редких входов. В статье доказывается, что проблема равенства генерически разрешима в конечно порождённых полугруппах S, для которых существует такая конгруэнция θ, что полугруппа S/θ является бесконечным финитно аппроксимируемым моноидом с сокращениями и с разрешимой проблемой равенства. Это обобщает ранее полученный результат автора о генерической разрешимости проблемы равенства в конечно определённых полугруппах, которые остаются бесконечными при добавлении свойств коммутативности и сокращения. Отметим, что примерами таких полугрупп служат полугруппы с одним определяющим соотношением, а также так называемые сбалансированные полугруппы, для которых Вон доказал генерическую разрешимость проблемы равенства. В частности, сбалансированными являются классические полугруппы Цейтина и Маканина с неразрешимой проблемой равенства.
Ранее К. Дошен и М. Божич ввели четыре независимые интуиционистские модальные логики - по одной для каждого из четырёх типов модальных операторов: необходимости N, возможности P, невозможности Im и не-необходимости Un. Эти логики обозначаются HKM, где M∈{N,P,Un,Im}. Интерес к тому, чтобы рассматривать четыре типа модальных операторов по отдельности, связан именно с тем, что над интуиционистской логикой они не могут быть сведены друг к другу. Здесь изучаются расширения логик HKM, у которых есть нормальные напарники. Оказывается, что нормальные напарники есть у всех расширений логик HKN и HKUn. Для расширений HKP и HKIm получен критерий существования нормальных напарников, который заключается в присутствии некоторого модального закона двойного отрицания. Также показывается, как добавление этого закона влияет на выразительные возможности логики. Особый интерес представляет результат о том, что расширения HKP и HKIm имеют нормальных напарников, только если они дефинициально эквивалентны расширениям HKN и HKUn соответственно. Этот результат является ещё одним примером различия в поведении четырёх типов модальных операторов над интуиционистской логикой.