?
Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines
Automatic Control and Computer Sciences (AC&CS), Switzerland. 2021. Vol. 55. No. 7. P. 670–701.
Захаров В. А.
Переводчик: Захаров В. А.
Ключевые слова: проблема эквивалентности в моделях вычисленийfinite state transducerконечный автомат-преобразовательконтекстно-свободная грамматикаcontext-free grammarmulti-tape automatonмноголенточный автоматbiautomatonequivalence checking problemбиавтомат
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Qian X., Guan X., Zhang B. и др., Journal of Global Optimization 2026
Добавлено: 27 сентября 2026 г.
Switzerland: Springer Cham, 2026.
Добавлено: 25 сентября 2026 г.
Добавлено: 25 сентября 2026 г.
Дубич Е. В., Щагин Д. В., Славянский форум 2026 № 2 (52) С. 560–565
В статье сравниваются протоколы HTTP/2 и HTTP/3 при передаче статических файлов в условиях программно моделируемой сетевой деградации. Эксперимент показал, что HTTP/3 не является универсально более быстрым, но устойчивее проявляет себя при росте задержки и потерь пакетов. ...
Добавлено: 25 сентября 2026 г.
Joulitov A.K., Lomazova I.A., Proceedings of the Institute for System Programming of the RAS 2026 Vol. 38 No. 4(2) P. 215–224
В майнинге процессов (process mining) графы непосредственного следования (Directly-Follows Graph, DFG) популярны благодаря своей простоте и наглядности. Однако, если процесс является ациклическим, но содержит параллельные события, стандартные алгоритмы построения DFG-моделей могут генерировать «ложные» циклы, которыe не представлены в журнале событий. Такие циклы мешают анализу информационных процессов, значительно снижая интерпретируемость и точность (precision) модели. Эта проблема ...
Добавлено: 24 сентября 2026 г.
Добрина Д. Н., Нестеренко А. Ю., Прикладная дискретная математика. Приложение 2026 № 19 С. 151–159
Работа содержит результаты формального анализа криптографических механизмов, входящих в состав проекта методических рекомендаций «Защищенный универсальный протокол передачи данных и управления микросхемой интеллектуальной карты» (протокол SECUNDA). Получена формальная модель и перечень трудноразрешимых математических задач, трудоёмкостью решения которых можно оценить стойкость используемых криптографических механизмов. ...
Добавлено: 24 сентября 2026 г.
I.I. Sergeev, I.A. Lomazova, Modeling and Analysis of Information Systems 2026 Vol. 33 No. 3 P. 394–419
Объектно-ориентированный process mining сформировался как эффективная парадигма анализа событийных данных, включающих несколько взаимодействующих бизнес-объектов. Существующие методы обнаружения моделей часто опираются на объектно-ориентированные сети Петри с фиксированными кратностями дуг, что ограничивает их способность представлять параметрические закономерности потребления и производства ресурсов, а также отражать количественные зависимости между взаимодействующими типами объектов. В данной работе предлагается метод обнаружения объектно-ориентированных ...
Добавлено: 24 сентября 2026 г.
Паршаков П. А., Паклина С. Н., International Journal of Human-Computer Interaction 2026 P. 1–17
Добавлено: 23 сентября 2026 г.
Андраби У. М., Wadood E., Ojha S. K. и др., IEEE Access 2026 Vol. 14 P. 103358–103375
Добавлено: 23 сентября 2026 г.
Добавлено: 23 сентября 2026 г.
Кертес-Фаркаш А., Аквей Ф. Л., Journal of Proteome Research 2026 Vol. 25 P. 3764–3768
Добавлено: 23 сентября 2026 г.
Maddalena L., Yildiz B., Del Vecchio Blanco F. и др., Risk Analysis 2026 Vol. 46 No. 4 P. 1–26
Добавлено: 22 сентября 2026 г.
Aleksei Samarin, Alexander Savelev, Aleksei Toropov и др., Pattern Recognition and Image Analysis 2024 Vol. 34 No. 3 P. 855–862
Добавлено: 21 сентября 2026 г.
Aleksei Samarin, Назаренко А. А., Alexander Savelev и др., Pattern Recognition and Image Analysis 2024 Vol. 34 No. 3 P. 844–854
Добавлено: 21 сентября 2026 г.
Aleksei Samarin, Alexander Savelev, Aleksei Toropov и др., Optical Memory and Neural Networks (Information Optics) 2024 Vol. 33 P. 424–434
Добавлено: 21 сентября 2026 г.
Дудаков С. М., Карлов Б. Н., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 524 № 1 С. 11–18
В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и ...
Добавлено: 18 марта 2026 г.
Добавлено: 12 ноября 2023 г.
Гнатенко А. Р., Захаров В. А., Automatic Control and Computer Sciences 2021 Vol. 55 No. 7 P. 776–785
Добавлено: 17 января 2022 г.
Гнатенко А. Р., Захаров В. А., Моделирование и анализ информационных систем 2021 Т. 28 № 4 С. 356–371
К последовательным реагирующим системам относятся компьютерные программы и вычислительные устройства, которые обрабатывают потоки входных данных или сигналов управления и генерируют на выходе последовательности команд или результатов вычислений. Для проектирования таких систем полезно иметь формальные языки спецификаций, способные выражать отношения между входными и выходными потоками данных. В предшествующих работах нами было предложено семейство таких языков спецификаций, ...
Добавлено: 17 января 2022 г.
Гнатенко А. Р., Захаров В. А., Моделирование и анализ информационных систем 2020 Т. 27 № 4 С. 428–441
К последовательным реагирующим системам относятся программы и устройства, которые работают с двумя потоками данных и осуществляют преобразование входных потоков данных в выходные потоки. К числу таких систем обработки информации относятся контроллеры, драйверы устройств, компьютерные интерпретаторы. Результатом работы таких вычислительных систем являются бесконечные последовательности пар событий типа запрос-отклик, и поэтому в качестве математических моделей для них ...
Добавлено: 31 января 2021 г.
Гнатенко А. Р., Захаров В. А., Системная информатика 2020 Vol. 17 P. 21–32
Последовательные реагирующие системы, такие как контроллеры, системные драйверы, компьютерные интерпретаторы, работают с двумя потоками данных и преобразуют входные потоки данных (управляющие сигналы, инструкции) в выходные потоки управляющих сигналов (инструкции, данные). Конечные преобразователи широко используются в качестве подходящей формальной модели для подобных систем обработки информации. Поскольку вычисления преобразователей протекают во времени, темпоральная логика, очевидно, может использоваться ...
Добавлено: 9 ноября 2020 г.
Захаров В. А., Моделирование и анализ информационных систем 2020 Т. 27 № 3 С. 260–303
Конечные преобразователи, двухленточные автоматы и биавтоматы - взаимосвязанные вычислительные модели, ведущие свое происхождение от концепции конечного автомата. В вычислениях этих машин проявляется много общих черт, и удивительно, что методы анализа, разработанные для одной из указанных моделей, не находят подходящего применения в других моделях. Целью данной статьи является разработка единой методики построения быстрых алгоритмов проверки эквивалентности ...
Добавлено: 28 сентября 2020 г.