English
2019 год, том 23, выпуск 3 (PDF)
Данная работа относится к области семантического анализа юридических документов. В статье приводится один из возможных подходов по моделированию правил движения. Описаны основные этапы семантического разбора некоторого класса предложений.
Ключевые слова: семантический анализ нормативно-правовых актов, прагматический анализ, построение семантической модели текста.
В работе описывается новое расширение метода резолюции, использующее графовое представление опровержений булевых формул в конъюнктивной нормальной форме. Доказывается, что невыполнимость булевой формулы равносильна существованию для неё графового опровержения.
Ключевые слова: Метод резолюции, графовые опровержения, невыполнимость, булевы формулы.
Рассматривается множество функций, заданных бесповторными формулами с бинарными операциями конъюнкции (логического И) и дизъюнкции (логического ИЛИ). Для функций, заданных формулами с фиксированным числом операций, исследуются значения весов — числа наборов, на которых функция принимает значение 1. Найдены асимптотические оценки для числа бесповторных формул, задающих функции с весом из определенных диапазонов, в частности, — числа формул, задающих функции, у которых доля единиц среди значений не превышает четверти.
Ключевые слова: булева функция, бесповторная формула, вес функции, асимптотическая оценка.
В работе представлены коды, задающие изображения с точностью до аффинных преобразований, в том числе некоторый новый код.
Ключевые слова: распознавание образов, изображения, коды изображения.
В данной статье рассматривается модель прямоугольных многомерных схем. Элементы схем расположены в ячейках d-мерной прямоугольной решетки. Каждая пара соседних ячеек решетки соединена шиной, в которой может быть до k проводов. Доказана верхняя оценка функции Шеннона для сложности данного вида схем \( \frac{2^n}{\min(n,d \log{k})} \).
Ключевые слова: многомерные схемы, многослойные схемы, асимптотика функции Шеннона, сложность схем.
Уточнены перечни предполных классов в классах линейных автоматов над конечными полями. Найден критерий конечности числа предполных надклассов для заданного множества линейных автоматов.
Ключевые слова: конечный автомат, линейный автомат, операции композиции, обратная связь, полнота, замкнутый класс, предполный класс, конечное поле.
Рассматривается проблема полноты системы автоматных функций с линейными переходами относительно операции суперпозиции. Эта система не является полной, более того, любая дополняющая ее до базиса система автоматов бесконечна.
Ключевые слова: конечный автомат, полнота, суперпозиция, замкнутый класс.
Рассматривается задача реализации булевых функций неизбыточными двухполюсными контактными схемами, допускающими короткие единичные проверяющие тесты относительно обрывов и замыканий контактов. Описаны все функции, для которых минимальная длина указанного теста равна 0, 1, 2 и 3. Доказано, что для почти всех булевых функций от n переменных эта длина равна 4.
Ключевые слова: контактная схема, булева функция, обрыв контакта, замыкание контакта, единичный проверяющий тест.
Исследуется вопрос о корректности аксиом интуиционистской теории множеств относительной семантики реализуемости, основанной на гиперарифметических видах.
Ключевые слова: конструктивная семантика, реализуемость, аксиоматическая теория множеств, гиперарифметические виды.
Для классов передаточных функций линейных автоматов над конечным полем с операциями, индуцированными операциями композиции над этими автоматами, найдены все максимальные подалгебры.
Ключевые слова: конечный автомат, линейный автомат, передаточная функция, операции композиции, обратная связь, полнота, замкнутый класс, предполный класс, конечное поле.