2019 год, том 23, выпуск 3 (PDF)

Менькин М.И. Автоматический перевод правил дорожного движения в теоретико-графовую формальную модель

Данная работа относится к области семантического анализа юридических документов. В статье приводится один из возможных подходов по моделированию правил движения. Описаны основные этапы семантического разбора некоторого класса предложений.

Ключевые слова: семантический анализ нормативно-правовых актов, прагматический анализ, построение семантической модели текста.

Боков Г.В. О графовом расширении метода резолюции для булевых формул

В работе описывается новое расширение метода резолюции, использующее графовое представление опровержений булевых формул в конъюнктивной нормальной форме. Доказывается, что невыполнимость булевой формулы равносильна существованию для неё графового опровержения.

Ключевые слова: Метод резолюции, графовые опровержения, невыполнимость, булевы формулы.

Еременко А.Р., Яшунский А.Д. О весе функций, заданных бесповторными И/ИЛИ формулами

Рассматривается множество функций, заданных бесповторными формулами с бинарными операциями конъюнкции (логического И) и дизъюнкции (логического ИЛИ). Для функций, заданных формулами с фиксированным числом операций, исследуются значения весов — числа наборов, на которых функция принимает значение 1. Найдены асимптотические оценки для числа бесповторных формул, задающих функции с весом из определенных диапазонов, в частности, — числа формул, задающих функции, у которых доля единиц среди значений не превышает четверти.

Ключевые слова: булева функция, бесповторная формула, вес функции, асимптотическая оценка.

В.Н. Козлов Коды, определяющие изображения с точностью до аффинных преобразований

В работе представлены коды, задающие изображения с точностью до аффинных преобразований, в том числе некоторый новый код.

Ключевые слова: распознавание образов, изображения, коды изображения.

Сытдыков Т. Р. Сложность синтеза многомерных прямоугольных схем

В данной статье рассматривается модель прямоугольных многомерных схем. Элементы схем расположены в ячейках d-мерной прямоугольной решетки. Каждая пара соседних ячеек решетки соединена шиной, в которой может быть до k проводов. Доказана верхняя оценка функции Шеннона для сложности данного вида схем 2^n / min(n,d log k).

Ключевые слова: многомерные схемы, многослойные схемы, асимптотика функции Шеннона, сложность схем.

Часовских А.А. О числе максимальных надклассов в классе линейных автоматов

Уточнены перечни предполных классов в классах линейных автоматов над конечными полями. Найден критерий конечности числа предполных надклассов для заданного множества линейных автоматов.

Ключевые слова: конечный автомат, линейный автомат, операции композиции, обратная связь, полнота, замкнутый класс, предполный класс, конечное поле.

Бабин Д.Н. Автоматы с линейными переходами

Рассматривается проблема полноты системы автоматных функций с линейными переходами относительно операции суперпозиции. Эта система не является полной, более того, любая дополняющая ее до базиса система автоматов бесконечна.

Ключевые слова: конечный автомат, полнота, суперпозиция, замкнутый класс.

Попков К.А. Короткие единичные проверяющие тесты для контактных схем при обрывах и замыканиях контактов

Рассматривается задача реализации булевых функций неизбыточными двухполюсными контактными схемами, допускающими короткие единичные проверяющие тесты относительно обрывов и замыканий контактов. Описаны все функции, для которых минимальная длина указанного теста равна 0, 1, 2 и 3. Доказано, что для почти всех булевых функций от n переменных эта длина равна 4.

Ключевые слова: контактная схема, булева функция, обрыв контакта, замыкание контакта, единичный проверяющий тест.

Коновалов А.Ю. Некорректность интуиционистской теории множеств относительно конструктивной семантики, основанной на гиперарифметических видах.

Исследуется вопрос о корректности аксиом интуиционистской теории множеств относительной семантики реализуемости, основанной на гиперарифметических видах.

Ключевые слова:конструктивная семантика, реализуемость, аксиоматическая теория множеств, гиперарифметические виды.

Часовских А.А. О классах передаточных функций линейных автоматов

Для классов передаточных функций линейных автоматов над конечным полем с операциями, индуцированными операциями композиции над этими автоматами, найдены все максимальные подалгебры.

Ключевые слова: конечный автомат, линейный автомат, передаточная функция, операции композиции, обратная связь, полнота, замкнутый класс, предполный класс, конечное поле.

Доклады семинара «Теория автоматов»

2019 год, том 23, выпуск 2 (PDF)

Ботхолов А.Ж. Восстановление нот из двузвучия

В данной работе рассматривается восстановление нот из одновременного звучания двух нот в терминах амплитуд и частот. Приведены методы восстановления амплитуд двух нот, которые были одновременно сыграны двумя различными музыкальными инструментами. Описаны случаи существования и не существования одновременно двух решений для задачи восстановления нот.

Ключевые слова: основной тон, обертон, амплитуда, частота, огибающая ноты, суммарная спектрограмма.

Кушнарева Л.П., Кузьминых Д.В. Персистентные гомологии для марковских цепей и их применение к анализу текста на естественном языке

В работе предложен новый метод введения персистентных топологических инвариантов для марковских цепей. Продемонстрирован пример использования этих инвариантов для прикладной задачи классификации текстов.

Ключевые слова: Топологический анализ данных, персиcтентные гомологии, марковские цепи, текст на естественном языке

Казаков И.Б. Критерий надежности канала с запрещениями

В работе исследуется возможность надежной передачи информации в ситуации, когда противник в каждой момент времени может блокировать некоторое подмножество символов алфавита. Показано, что гарантированно надежный канал существует тогда и только тогда, когда мощность алфавита n и число разрешенных символов k удовлетворяют неравенству n ≤ 2k − 2.

Ключевые слова: скрытые каналы, блуждания по плоскости, запрещения алфавитных символов, передаваемый язык

В.Н. Козлов Сегментация изображений и преобразования, сохраняющие форму фигур

Изображением в работе называем конечное ( непустое) множество точек в евклидовых пространствах разной размерности. Кратко работа состоит в том, чтобы имея изображение, принадлежащую некоторому образу, извлечь из этого изображения то, что можно было бы назвать описанием этого образа.

Ключевые слова: математическое определение изображения, описание зрительного образа, распознавание изображений.

Пивень Н.А. Некоторые свойства перестановочной конструкции для параметрического задания квазигрупп

В работе исследуются свойства так называемой перестановочной конструкции, введенной ранее. Выясняется, что конструкция несколько избыточна, но в результате ее улучшения, она оказывается инъективной для случая линейных правильных семейств булевых функций, и, возможно, инъективной в общем.

Ключевые слова: квазигруппы, правильные семейства булевых функций, латинские квадраты, параметрическое задание

Собянин П.И. Об алгоритме проверки наличия подквазигруппы в квазигруппе

Рассматривается алгоритм проверки наличия подквазигруппы в квазигруппе. Сравнивается скорость выполнения его последовательной и параллельной версий на вычислительной архитектуре CUDA.

Ключевые слова: квазигруппа, подквазигруппа, GPU, CUDA.

Ведерников И.К. Критерий почти полного прогнозирования сверхслова в многозначном алфавите

Автомат прогнозирует следующий символ входного сверхслова, если он выдает этот символ на выходе в предыдущий момент времени. В работе для произвольного сверхслова в многозначном алфавите исследуется вопрос его почти полного прогнозирования, т.е. когда прогноз правильный почти всегда. Получен результат, позволяющий сузить класс автоматов, которыми прогнозируется сверхслово, а также доказан критерий почти полной прогнозируемости сверхслова.

Ключевые слова: почти полное прогнозирование, прогнозирующий автомат, автоматное прогнозирование сверхслов, критерий прогнозируемости.

Ефимов А.А. Верхняя оценка энергопотребления объемных схем, реализующих булевы операторы.

В данной работе рассматриваются объёмные схемы, являющиеся обобщением плоских схем в пространстве. Был рассмотрен класс схем, реализующих булевы операторы. Для этого класса получена верхняя оценка потенциала — меры мощности, равной количеству элементов схемы, выдающих единицу на данном входном наборе. Показано, что любой оператор от n переменных можно реализовать объемной схемой, потенциал которой не превосходит O(m · 2n/3 ), если m ≤ n, и √ O( m n · 3 n · 2n/3 ), если m > n.

Ключевые слова: схемы из функциональных элементов, объёмные схемы, мощность схемы, потенциал.

Кан А. Н. Вопросы выразимости в классе согласованных функций

В настоящей работе рассматривается 2-полнота в классе P согласованных функций. Данный класс был рассмотрен ранее в работах [3, 4]. Он является предполным в классе P L кусочно-линейных функций. В нем было найдено два 2-предполных класса: класс CP L непрерывных функций, класс P F согласованных финитных функций.

Ключевые слова: Класс кусочно-линейных функций, класс кусочно-линейных непрерывных функций, класс согласованных функций, класс финитных функций, класс согласованных финитных функций, 2-предполнота, функция Хэвисайда.

Капустин Ю.С. Об элементарной выразимости в логике предикатов

В математике часто новые понятия вводятся с помощью некоторых кванторных определений. При наличии достаточно большого запаса таких понятий они могут позволить переформулировать новые кванторные определения бескванторным образом. Это делает заслуживающей рассмотрения задачу отыскания базисных понятий в заданной предметной области, которые делают избыточным дальнейшее кванторное определение. Интересной также является задача создания компьютерных программ, автоматически вводящих такие базисы. В данной работе рассматриваются 3 простых случая сведения кванторной выразимости к бескванторной. Исследуются предикаты и функции, определенные через ∈ и заданные на множестве Z ∪ 2Z , где Z — множество целых чисел. Кроме того, рассматриваются предикаты, выразимые через тот же предикат на множестве точек плоскости и прямых, лежащих в ней. Также рассмотрены предикаты, выразимые на множестве натуральных чисел с отношением делимости на нем. Во всех случаях удалось найти базисы бескванторной выразимости.

Ключевые слова: кванторная выразимость, логика предикатов.

Коновалов А. Ю. Некорректность теории множеств Цермело-Френкеля относительно конструктивной семантики, основанной на гиперарифметических видах

Определяется семантика реализуемости для формул языка теории множеств, основанная на гиперарифметических видах. Исследуется вопрос о корректности аксиом теории множеств Цермело-Френкеля относительной этой семантики.

Ключевые слова: конструктивная семантика, реализуемость, аксиоматическая теория множеств, гиперарифметические виды.

2019 год, том 23, выпуск 1 (PDF)

Голиков К.А. Алгоритм обучения систем с дискретным управлением

Разработан алгоритм обучения для задачи позиционирования систем с дискретным управлением, основанный на методе обобщения проб и ошибок, сохраняющихся в базе данных, с помощью глобальной интерполяции и градиентного спуска. Оптимизация алгоритма производится по критерию сокращения времени обучения (числа попыток). Алгоритм был протестирован на симуляторе для моделей систем, действующих на плоскости, двух разных типов: для мобильного робота с двумя ведущими гусеницами и для открытой кинематической цепи с вращательными и призматическими сочленениями.

Ключевые слова: позиционирование, алгоритм обучения, робот, интерполяция, аппроксимация.

Менькин М. И. Объектная модель правил дорожного движения

Данная работа относится к области семантического анализа юридических документов. Под семантикой нормативно-правовых актов будем понимать отображение, на вход которого поступает текст нормативно-правового акта, а на выходе получается его формальная модель. В статье описывается один из возможных подходов построения формальной модели правил дорожного движения.

Ключевые слова: семантический анализ нормативно-правовых актов, прагматический анализ, построение формальных моделей.

Боков Г. В. О конечных заданиях логических систем

В работе рассматривается задача конечного представления логических систем пропозициональными исчислениями. Исследуются три типа логических систем: линейные, монотонные и импликативные. Для каждого из этих типов логических систем доказаны достаточные условия их конечного задания. Кроме того, доказан критерий конечного задания произвольной логической системы множества классических тавтологий.

Ключевые слова: логические системы, пропозициональные исчисления, конечное задание, правила вывода.

Галатенко А.В., Панкратьев А.Е., Родин С.Б. Полиномиальная полнота конечных квазигрупп

Приводится обзор результатов, связанных с проверкой полиномиальной полноты конечных квазигрупп. Работа подготовлена по материалам доклада на семинаре “Теория автоматов”.

Ключевые слова: квазигруппа, латинский квадрат, полиномиальная полнота, простота, аффинность

Дергач П.С., Данилевская Е.Д. О прогрессивном представлении периодических семейств с ограничениями на начало и шаг

В статье изучается множество K(n) := N \ (n, n), исследуется его представление в виде объединения как можно меньшего количества арифметических прогрессий с ограничением на начало или шаг. В каждом из двух случаев найдены соответствующие точные оценки.

Ключевые слова: арифметическая прогрессия, натуральный ряд, проблема минимизации, типы ограничений.

Коновалов А. Ю. Равномерная V -реализуемость принципа Маркова в V -перечислимой области

Определяются различные варианты понятия V -реализуемости для формул языка логики предикатов, основанные на использовании функций из множества V для интерпретации импликации и квантора всеобщности. Устанавливается, что принцип Маркова является слабо V -реализуемым, не является равномерно V - реализуемым и является V -реализуемым равномерно в области M , если множество M ⊆ N является V -перечислимым.

Ключевые слова: конструктивная семантика, реализуемость, абсолютная реализуемость, обобщенная реализуемость, принцип Маркова.

Агафонова М.В. О минимальной Шефферовой функции в классе кусочно-параллельных функций, определенных над двоично-рациональными числами

В настоящей статье рассматривается класс нейронных кусочно- параллельных функций с двоично-рациональными коэффициентами(BPP). Приводится доказательство существования в нем минимальной Шефферовой функции. Под минимальной Шефферовой функцией в рассматриваемом классе, понимается функция этого класса, порождающая этот класс по операциям суперпозиции и содержащая минимально возможное количество переменных и пороговых функций. Было установлено, что в данном классе минимальная Шефферова функция содержит две переменных и одну пороговую функцию. Также в статье приводится одно из необходимых условий Шефферовости функции, принадлежащей BPP.

Ключевые слова: класс, кусочно-параллельные функции, нейронные функции, двоично-рациональные коэффициенты, операции суперпозици, Шефферова функция.

Ефимов А.А. Верхняя оценка энергопотребления в классе объемных схем

В данной работе рассматриваются объёмные схемы, являющиеся обобщением плоских схем в пространстве. Был рассмотрен класс схем, реализующих булевы функции. Для этого класса получена верхняя оценка потенциала — меры мощности, равной количеству элементов схемы, выдающих единицу на данном входном наборе. Показано, что любую функцию от n переменных можно реализовать объемной схемой, потенциал которой не превосходит O(2n/3 ).

Ключевые слова: схемы из функциональных элементов, объёмные схемы, мощность схемы, потенциал.

Коновалов А. Ю. Условие корректности и полноты классической логики для семантики относительной V -реализуемости

Пусть L — некоторое расширение языка арифметики, V — некоторый класс числовых функций. Определяется понятие V - реализуемости для предикатных формул, основанное на оценке предикатных переменных формулами языка L. Устанавливается корректность и полнота классической логики относительно семантики V -реализуемости в случае, когда класс V содержит все функции, определимые в языке L.

Ключевые слова: конструктивная семантика, реализуемость, обобщенная реализуемость, формальная арифметика.

Кудрявцев В.Б., Бабин Д.Н. О классификациях базисов в Pk по разрешимости полноты для автоматов

Рассматривается проблема полноты систем автоматных функций с операциями суперпозиции и обратной связи вида Φ ∪ ν, где Φ ⊆ Pk , ν - конечно. При k = 2 решение этой задачи приводит к разделению решётки замкнутых классов Поста на сильные (наличие которых в исследуемой системе гарантирует разрешимость задачи полноты конечных базисов) и слабые (наличие которых в исследуемой системе этого не гарантирует). При k = 2 эта задача для систем автоматных функций произвольного вида была решена (Бабин Д.Н. 1998). В статье рассмотрены следствия и возможные обощения этой задачи, а также некоторые результаты для Pk , k > 2.

Ключевые слова: булева функция, конечный автомат, алгоритмическая разрешимосить.