?
Equivalence Checking Problem for Finite State Transducers
Lecture Notes in Computer Science. 2015. Vol. 9270. P. 208-221.
Zakharov V.A.
Научное направление:
Компьютерные науки
Приоритетные направления:
компьютерно-математическое
Язык:
английский
Ключевые слова: полугруппаcomplexitysemigroup алгоритмическая сложностьfinite state transducerequivalence checkingконечный автомат-преобразовательпроверка эквивалентности
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Захаров В. А., Труды Института системного программирования РАН 2015 Т. 27 № 2 С. 221-250
Автоматы-преобразователи с конечным числом состояний над полугруппами могут служить простой моделью последовательных реагирующих программ. Эти программы работают во взаимодействии с окружающей средой, получая на входе поток управляющих сигналов и выполняя последовательности действий. Как только программа достигает определенного состояния управления, она выдает на выходе текущий результат вычисления. Элементарные действия реагирующей программы можно рассматривать как порождающие элементы ...
Добавлено: 30 сентября 2015 г.
Захаров В. А., Temerbekova G., Системная информатика 2016 No. 7 P. 33-44
Добавлено: 13 октября 2016 г.
Захаров В. А., Темербекова Г. Г., Моделирование и анализ информационных систем 2016 Т. 23 № 6 С. 741-753
Автоматы-преобразователи над полугруппами можно использовать в качестве модели последовательных реагирующих программ, работающих в постоянном взаимодействии со своим окружением. Получив очередную порцию данных, реагирующая программа выполняет некоторую последовательность действий и предъявляет результат. Такие программы возникают при проектировании компьютерных драйверов, алгоритмов, работающих в оперативном режиме, сетевых коммутаторов. Во многих случаях проблема верификации программ такого рода может быть ...
Добавлено: 13 октября 2016 г.
Захаров В. А., Джусупекова З., В кн. : Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.). : М. : Изд-во механико-математического факультета МГУ, 2016. С. 190-192.
Автоматы-преобразователи в качестве модели последовательных реагирующих программы используются в системном программировании, в компьютерной лингвистике, в криптографии, при проектировании микроэлектронных схем и др. Преобразователь принимает на входе последовательность сигналов и выполняет некоторую последовательность действий, преобразуя тем самым конечные слова входного алфавита в полугрупповое выражение, значения которых и являются результатами вычислений.
Мы рассматриваем автоматы-преобразователи над произвольной полугруппой $S$, ...
Добавлено: 13 октября 2016 г.
Захаров В. А., Temerbekova G., Automatic Control and Computer Sciences 2017 Vol. 51 No. 7 P. 523-530
Добавлено: 13 октября 2016 г.
Захаров В. А., Новикова Т. А., Труды Института системного программирования РАН 2014 Т. 26 № 2 С. 245-268
Задача унификации пары подстановок θ_1 и θ_2 состоит в вычислении такой пары подстановок η' и η'', чтобы композиции θ_1 η' и θ_2 η'' были равны. По существу, задача унификации подстановок равносильна задаче решения линейных уравнений вида θ_1 X=θ_2 Y в полугруппе подстановок. Но некоторые линейные уравнения над подстановками также можно рассматривать как новые варианты задачи ...
Добавлено: 30 сентября 2015 г.
Захаров В. А., Темербекова Г. Г., В кн. : Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.). : М. : Изд-во механико-математического факультета МГУ, 2016. С. 232-234.
Потоковые алгоритмы возникают при решении многих прикладных задач. В статье предложена модель потоковых программ- автоматов-преобразователей над полугруппами- и для нее была исследована проблема эквивалентности. В настоящей работе описан метод оптимизации потоковых программ. Этот метод является обобщением ранее известного подхода, предложенного в статье для минимизации автоматов-преобразователей. Решение задачи минимизации потоковых программ над группами представлено в статье ...
Добавлено: 13 октября 2016 г.
Гнатенко А. Р., Захаров В. А., Proceedings of the Institute for System Programming of the RAS 2018 Vol. 30 No. 3 P. 303-324
Добавлено: 14 июня 2018 г.
Захаров В. А., В кн. : Дискретные модели в теории управляющих систем: Х Международная конференция, Москва и Подмосковье, 23-25 мая 2018 г. : Труды. : МГУ, МАКС Пресс, 2018. С. 128-130.
Показано, каким образом задача проверки эквивалентности двухленточных детерминированных автоматов может быть сведена к задаче проверки эквивалентности слабо недетерминированных конечных автоматов-преобразователей, работающих над полугруппой префиксных регулярных языков с операцией конкатенации. ...
Добавлено: 14 июня 2018 г.
Авдошин С. М., Набебин А. А., М. : ДМК Пресс, 2017
Книга содержит необходимые сведения из универсальных и классических алгебр, системы аксиом для основных алгебраических структур (группоид, моноид, полугруппы, группы, частичные порядки, кольца, поля). Описываются основные криптографические алгоритмы. Рассматриваются ставшие классическими помехоустойчивые коды – линейные, циклические, БЧХ. Приводятся алгоритмы проектирования таких кодов. В основу книги положен многолетний опыт преподавания авторами дисциплины «Дискретная математика» на факультете бизнес-информатика, ...
Добавлено: 19 августа 2016 г.
Гнатенко А. Р., Захаров В. А., Системная информатика 2020 Vol. 17 P. 21-32
Последовательные реагирующие системы, такие как контроллеры, системные драйверы, компьютерные интерпретаторы, работают с двумя потоками данных и преобразуют входные потоки данных (управляющие сигналы, инструкции) в выходные потоки управляющих сигналов (инструкции, данные). Конечные преобразователи широко используются в качестве подходящей формальной модели для подобных систем обработки информации. Поскольку вычисления преобразователей протекают во времени, темпоральная логика, очевидно, может использоваться ...
Добавлено: 9 ноября 2020 г.
В статье исследуется глобальная эволюция мирового сообщества как единой самоорганизующейся и саморазвивающейся системы (Мир-Системы) и выявляются основные характеристики и закономерности этой эволюции. При этом внимание фокусируется на рассмотрении цикличности эволюции, периодизации глобальной истории человечества, росте сложности и рождении технологических, социальных и культурных инноваций в результате прохождения кризисов. Исследование строится как междисциплинарное и опирается на результаты ...
Добавлено: 18 ноября 2013 г.
Фомичев М. И., Ульянов М. В., Головешкин В. А. и др., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 131-137
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности. ...
Добавлено: 19 августа 2017 г.
Захаров В. А., Жайлауова Ш. Р., Моделирование и анализ информационных систем 2017 Т. 24 № 4 С. 415-433
Стандартные схемы программ - это одна из наиболее простых моделей последовательных императивных программ, предназначенная для решения задач оптимизации и верификации программ. Мы рассматриваем разрешимое отношение логико-термальной эквивалентности стандартных схем программ и задачу минимизации их размера при условии сохранением отношения логико-термальной эквивалентности. Нами доказано, что эта задача является алгоритмически разрешимой. Далее показано, что стандартные схемы программ ...
Добавлено: 12 октября 2017 г.
Funchal : SciTePress, 2018
This book contains the proceedings of the 3rd International Conference on Complexity, Future Information Systems and Risk (COMPLEXIS 2018) which was organized and sponsored by the Institute for Systems and Technologies of Information, Control and Communication (INSTICC). This conference was technically co-sponsored by World Federation on Soft Computing (WFSC) and also held in cooperation with ...
Добавлено: 2 июня 2018 г.
Канович М. И., Ban Kirigin T., Nigam V. и др., Computer Languages, Systems & Structures 2014 No. 40 P. 137-154
Добавлено: 23 марта 2015 г.
Turkensteen M., Малышев Д. С., Гольденгорин Б. И. и др., Journal of Global Optimization 2017 Vol. 68 No. 3 P. 601-622
Добавлено: 10 декабря 2016 г.
Гнатенко А. Р., Захаров В. А., Моделирование и анализ информационных систем 2021 Т. 28 № 4 С. 356-371
К последовательным реагирующим системам относятся компьютерные программы и вычислительные устройства, которые обрабатывают потоки входных данных или сигналов управления и генерируют на выходе последовательности команд или результатов вычислений. Для проектирования таких систем полезно иметь формальные языки спецификаций, способные выражать отношения между входными и выходными потоками данных. В предшествующих работах нами было предложено семейство таких языков спецификаций, ...
Добавлено: 17 января 2022 г.
Захаров В. А., Моделирование и анализ информационных систем 2020 Т. 27 № 3 С. 260-303
Конечные преобразователи, двухленточные автоматы и биавтоматы - взаимосвязанные вычислительные модели, ведущие свое происхождение от концепции конечного автомата. В вычислениях этих машин проявляется много общих черт, и удивительно, что методы анализа, разработанные для одной из указанных моделей, не находят подходящего применения в других моделях. Целью данной статьи является разработка единой методики построения быстрых алгоритмов проверки эквивалентности ...
Добавлено: 28 сентября 2020 г.
Захаров В. А., Automatic Control and Computer Sciences (AC&CS), Switzerland 2021 Vol. 55 No. 7 P. 670-701
Добавлено: 17 января 2022 г.
Гнатенко А. Р., Захаров В. А., Automatic Control and Computer Sciences 2021 Vol. 55 No. 7 P. 776-785
Добавлено: 17 января 2022 г.
Захаров В. А., Новикова Т. А., Труды Института системного программирования РАН 2012 Т. 22 С. 435-455
Логико-термальная эквивалентность программ – это одно из наиболее слабых отношений эквивалентности программ, аппроксимирующих отношение функциональной эквивалентности и обладающих разрешающим алгоритмом. В данной статье предложена новая модификация алгоритма проверки логико-термальной эквивалентности программ, основанная на операции вычисления точной нижней грани в решетке конечных подстановок. Показано, что трудоемкость предложенного алгоритма оценивается величиной O(n6) , где n - размер ...
Добавлено: 30 сентября 2015 г.
Yenigün H., N.Yevtushenko, Kushik N. и др., Proceedings of the Institute for System Programming of the RAS 2018 Vol. 30 No. 1 P. 7-24
Добавлено: 9 октября 2019 г.
Захаров В. А., Жайлауова Ш. Р., В кн. : Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019). : М. : Изд-во механико-математического факультета МГУ, 2019. С. 272-274.
В данной статье мы продолжаем поиск и исследование новых классов недетерминированных автоматов-преобразователей с разрешимой проблемой эквивалентности. Цель исследования~--- провести как можно более точную и подробную демаркацию границы между разрешимыми и неразрешимыми случаями проблемы эквивалентности для рассматриваемой модели вычислений. Мы рассматриваем один класс недетерминированных автоматов, работающих над выходным алфавитом из одной буквы. Характерная особенность рассматриваемых автоматов-преобразователей ...
Добавлено: 17 октября 2019 г.