Аннотация: Arguments in defense of introducing the self-referencing quantifier S?? and its approximation on dynamical systems are consistently presented. The case of classical logic is described in detail. Generated 3-valued truth tables that match the corresponding Priest tables [5]. In the process of constructing 4-valued truth tables, two more truth values were revealed that did not coincide with the original ones. Therefore, the closed tables turned out to be 6-valued. De Morgan’s law confirmed in 6-valued truth tables.

Аннотация: В статье описываются две системы, предназначенные для тестирования программ, выполняемых студентами первого курса факультета ВМК МГУ в рамках практикума на ЭВМ. Системы разрабатываются на факультете ВМК с 2017 года. Первая система тестирует программы на языке Паскаль, а вторая — на языке Ассемблера.

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

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

Аннотация: В данной работе получена асимптотическая верхняя граница для самоподобного трафика, являющегося суммой независимых фрактальных броуновских движений с разными показателями Херста H1 < H2 < . . . <H ??.

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

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

Аннотация: Ставится вопрос о возможности моделирования некоторого графа с помощью графа достижимости какой-либо сети Петри.

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

Аннотация: Под сложным структурированным объектом понимается объект, являющийся совокупностью своих элементов, каждый из которых обладает некоторыми свойствами, и эти элементы могут находиться в заданных отношениях (не обязательно бинарных). Для таких объектов адекватным языком описания является язык исчисления предикатов. Рассматривается подход к решению ряда задач распознавания и анализа сложных структурированных объектов. Введенное автором понятие изоморфизма элементарных конъюнкций предикатных формул дает возможность решать следующие задачи: создание иерархического описания множества объектов, существенно уменьшающего вычислительную сложность распознавания объектов; построение на его основе предикатных сетей для распознавания сложных структурированных объектов; построение нечетких предикатных сетей, позволяющих определить, какая часть распознаваемого объекта в какой степени похожа на часть известного объекта; «распараллеливание» процесса распознавания объекта; создание полного описания объекта при мульти-агентном сборе информации; построение онтологии множества сложных структурированных объектов.

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

Аннотация: В нашей работе мы представляем реализацию двух вариантов исчисления алиасов (синонимичных адресов) для языка с адресной арифметикой — варианта, описанного в работе [2], и нового «легкого» варианта для обнаружения утечек памяти. Разработка наших вариантов исчисления была вдохновлена исчислением алиасов для языка без адресной арифметики из работы.

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

Аннотация: В работе предлагается новый метод обобщения тематической текстовой коллекции, оснащенной таксономией предметной области. С помощью спектральных методов кластеризации из текстовой коллекции извлекаются нечеткие множества листьев таксономии, соответствующие понятиям, одновременно используемым в статьях коллекции. Эти нечеткие множества обобщаются путем их подъема в дереве таксономии с использованием критерия максимального правдоподобия. Оптимальный подъем подразумевает нахождение вершины или множества вершин в дереве таксономии, наиболее плотно покрывающих листовые понятия из обобщаемого множества. Наш метод включает два основных этапа: (1) извлечение кластеров из текстовой коллекции и (2) обобщение этих кластеров. В данной работе модернизируются оба этапа. Алгоритмы применены к структурному анализу и описанию текстовой коллекции из 17 тыс. аннотаций научных статей в области Наук о данных, опубликованных в журналах издательства Шпрингер. Таксономия Наук о данных, используемая в данной работе, является шестиуровневой иерархической таксономией, разработанной вручную международной Ассоциацией Вычислительной Техники и Вычислительных Систем (ACM-CSS [4]).

Аннотация: В статьях [3,4] предлагается метод аутентификации на основе использования универсальных хэш-функций и случайных цепочек бит. Настоящая статья является продолжением и содержит методические рекомендации по оптимизации параметров предложенной системы аутентификации.

Аннотация: Рассматриваются различные модели ветвящегося случайного блуждания с непрерывным временем по многомерной решетке. В основе процесса лежит симметричное, однородное по пространству, неприводимое случайное блуждание c конечной дисперсией скачков. Интенсивности размножения и гибели частиц в точках решетки предполагаются случайными. Для ветвящихся случайных блужданий в случайных средах характерно влияние редких флуктуаций, поэтому осредненное описание, типичное при классическом подходе, не всегда адекватно. В частности, для процессов в случайных средах характерно возникновение нерегулярных структур с выраженной неоднородностью пространственного распределения. В физической литературе для подобных явлений принят термин «перемежаемость». На основе результатов моделирования удалось показать, что эффект перемежаемости может наблюдаться и быть численно оценен в случайных средах даже на конечных временных интервалах.

Аннотация: В данной работе рассматривается понятие частичной неподвижной точки для нормальных логических программ. Мы показываем, как при помощи неподвижной точки можно сократить запись логической программы, причем экспоненциально. Также исследуем задачу о вычислении неподвижной точки в общем случае и доказываем для нее PSPACE-полноту.

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

Аннотация: Теория сложности доказательств изучает длины доказательств пропозициональных формул. За последние тридцать лет в данной области произошло ряд существенных прорывов, а также были открыты новые связи с другими разделами теории сложности вычислений. Мы рассмотрим, как основные задачи теории сложности доказательств, так и примеры применений.

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