Статья: NP-ПОЛНОТА ЗАДАЧИ ОБ ЭЙЛЕРОВОМ МАРШРУТЕ В КРАТНОМ ГРАФЕ (2024)

В работе исследуются автоматические методы классификации русскоязычных предложений на два класса: содержащие и не содержащие ироничный посыл. Рассматриваемые методы могут быть разделены на три категории: классификаторы на основе эмбеддингов языковых моделей, классификаторы с использованием информации о тональности и классификаторы с обучением эмбеддингов обнаружению иронии. Составными элементами классификаторов являются нейронные сети, такие как BERT, RoBERTa, BiLSTM, CNN, а также механизм внимания и полносвязные слои. Эксперименты по обнаружению иронии проводились с использованием двух корпусов русскоязычных предложений: первый корпус составлен из публицистических текстов из открытого корпуса OpenCorpora, второй корпус является расширением первого и дополнен ироничными предложениями с ресурса Wiktionary. Лучшие результаты продемонстрировала группа классификаторов на основе чистых эмбеддингов языковых моделей с максимальным значением F-меры 0.84, достигнутым связкой из RoBERTa, BiLSTM, механизма внимания и пары полносвязных слоев в ходе экспериментов на расширенном корпусе. В целом использование расширенного корпуса давало результаты на 2-5% выше результатов на базовом корпусе. Достигнутые результаты являются лучшими для рассматриваемой задачи в случае русского языка и сравнимы с лучшими для английского.

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

Статья посвящена разработке подхода к решению основных задач теории супервизорного управления логическими дискретно-событийными системами (ДСС), основанного на представлении их в виде позитивно-образованных формул (ПОФ). Рассматриваются логические ДСС в автоматной форме, понимаемые как генераторы некоторых регулярных языков. Язык ПОФ представляет собой полный язык первого порядка, формулы которого имеют регулярную структуру из чередующихся типовых кванторов и не содержат в синтаксисе оператора отрицания. Ранее было доказано, что любая формула классического исчисления предикатов первого порядка может быть представлена в виде ПОФ. ПОФ имеют наглядное древовидное представление и естественную вопросно-ответную процедуру поиска вывода с помощью единственного правила вывода. Показано, как разработанное в 1990-х годах для решения некоторых задач управления динамическими системами исчисление ПОФ позволяет решать базовые задачи теории супервизорного управления, такие как проверка критериев существования супервизорного управления, автоматическая модификация ограничений на поведение управляемой системы и реализация супервизора. Благодаря некоторым особенностям исчисления ПОФ существует возможность применения немонотонного вывода. Продемонстрировано, как представленный метод на основе ПОФ позволяет выполнять дополнительную обработку событий во время логического вывода. Также представлена программная система Bootfrost, или так называемый прувер, разработанный для опровержения полученных ПОФ, кратко описываются особенности его реализации. В качестве иллюстративного примера рассматривается задача управления автономным мобильным роботом.

Процесс-ориентированное программирование - один из подходов к разработке управляющего программного обеспечения. Процесс-ориентированная программа определяется как последовательность процессов. Каждый процесс представляется набором именованных состояний, содержащих программный код, которые задают логику поведения процесса. Выполнение программы заключается в последовательном исполнении этих процессов в их текущих состояниях на каждой итерации цикла управления. Процессы могут взаимодействовать через изменение состояний друг друга и через разделяемые переменные. Статья является развитием метода классификации темпоральных требований к процесс-ориентированным программам с целью упростить и автоматизировать дедуктивную верификацию таких программ. Метод состоит из следующих шагов. На первом шаге требования формализуются на специализированном языке DV-TRL, варианте типизированной логики предикатов первого порядка с набором интерпретированных типов и предикатных и функциональных символов, позволяющем отражать специфические понятия систем управления в процесс-ориентированной парадигме. На втором шаге формализованные требования разбиваются на классы, каждый из которых определяется шаблоном - параметрической формулой языка DV-TRL, причем условия корректности, порождаемые для процесс-ориентированных программ относительно требований, удовлетворяющих одному шаблону, имеют одну и ту же схему доказательства. На третьем шаге разрабатываются соответствующие схемы доказательства. В статье мы сначала даём краткое введение в язык poST, процесс-ориентированное расширение языка ST стандарта МЭК 61131-3. Далее определяется язык DV-TRL. Мы также приводим коллекцию требований на естественном языке для нескольких систем управления. Затем мы определяем шаблоны, позволяющие полностью покрыть все требования этой коллекции и для каждого из шаблонов приводим пример формализованного требования из коллекции и описываем схему доказательства условий корректности для этого шаблона. Статистика распределения требований из коллекции по шаблонам выявляет наиболее востребованные шаблоны. Мы также провели анализ связанных работ.