?
On the Minimization Problem for Sequential Programs
Automatic Control and Computer Sciences. 2017. Vol. 51. No. 7. P. 689-700.
Захаров В. А., Jaylauova S.
Переводчик: Захаров В. А.
Захаров В. А., Темербекова Г. Г., Моделирование и анализ информационных систем 2016 Т. 23 № 6 С. 741-753
Автоматы-преобразователи над полугруппами можно использовать в качестве модели последовательных реагирующих программ, работающих в постоянном взаимодействии со своим окружением. Получив очередную порцию данных, реагирующая программа выполняет некоторую последовательность действий и предъявляет результат. Такие программы возникают при проектировании компьютерных драйверов, алгоритмов, работающих в оперативном режиме, сетевых коммутаторов. Во многих случаях проблема верификации программ такого рода может быть ...
Добавлено: 13 октября 2016 г.
Захаров В. А., Temerbekova G., Системная информатика 2016 No. 7 P. 33-44
Добавлено: 13 октября 2016 г.
Захаров В. А., Temerbekova G., Automatic Control and Computer Sciences 2017 Vol. 51 No. 7 P. 523-530
Добавлено: 13 октября 2016 г.
Захаров В. А., Темербекова Г. Г., В кн. : Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.). : М. : Изд-во механико-математического факультета МГУ, 2016. С. 232-234.
Потоковые алгоритмы возникают при решении многих прикладных задач. В статье предложена модель потоковых программ- автоматов-преобразователей над полугруппами- и для нее была исследована проблема эквивалентности. В настоящей работе описан метод оптимизации потоковых программ. Этот метод является обобщением ранее известного подхода, предложенного в статье для минимизации автоматов-преобразователей. Решение задачи минимизации потоковых программ над группами представлено в статье ...
Добавлено: 13 октября 2016 г.
Захаров В. А., Труды Института системного программирования РАН 2015 Т. 27 № 2 С. 221-250
Автоматы-преобразователи с конечным числом состояний над полугруппами могут служить простой моделью последовательных реагирующих программ. Эти программы работают во взаимодействии с окружающей средой, получая на входе поток управляющих сигналов и выполняя последовательности действий. Как только программа достигает определенного состояния управления, она выдает на выходе текущий результат вычисления. Элементарные действия реагирующей программы можно рассматривать как порождающие элементы ...
Добавлено: 30 сентября 2015 г.
Захаров В. А., Джусупекова З., В кн. : Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.). : М. : Изд-во механико-математического факультета МГУ, 2016. С. 190-192.
Автоматы-преобразователи в качестве модели последовательных реагирующих программы используются в системном программировании, в компьютерной лингвистике, в криптографии, при проектировании микроэлектронных схем и др. Преобразователь принимает на входе последовательность сигналов и выполняет некоторую последовательность действий, преобразуя тем самым конечные слова входного алфавита в полугрупповое выражение, значения которых и являются результатами вычислений.
Мы рассматриваем автоматы-преобразователи над произвольной полугруппой $S$, ...
Добавлено: 13 октября 2016 г.
Zakharov V.A., Lecture Notes in Computer Science 2015 Vol. 9270 P. 208-221
Добавлено: 30 сентября 2015 г.
Vladislav Podymov, Fundamenta Informaticae 2016 Vol. 147 No. 2-3 P. 315-336
Добавлено: 9 октября 2016 г.
Захаров В. А., В кн. : Дискретные модели в теории управляющих систем: Х Международная конференция, Москва и Подмосковье, 23-25 мая 2018 г. : Труды. : МГУ, МАКС Пресс, 2018. С. 128-130.
Показано, каким образом задача проверки эквивалентности двухленточных детерминированных автоматов может быть сведена к задаче проверки эквивалентности слабо недетерминированных конечных автоматов-преобразователей, работающих над полугруппой префиксных регулярных языков с операцией конкатенации. ...
Добавлено: 14 июня 2018 г.
Захаров В. А., Жайлауова Ш. Р., В кн. : Проблемы теоретической кибернетики: XVIII международная конференция (Пенза, 19-23 июня 2017 г.). : М. : МГУ, МАКС Пресс, 2017. С. 84-87.
Эффективная разрешимость проблемы л-т эквивалентности дает возможность приступить к решению задачи минимизации - построения схемы программ наименьшего размера, л-т эквивалентной заданной схеме. Чтобы отыскать ее решение, заметим, что модель вычислений стандартных схем программ сходна модели вычислений автоматов-преобразователей, работающих над полугруппами. Ранее был предложен метод минимизации автоматов-преобра\-зо\-вателей, работающих над упорядоченными левосократимыми полугруппами. В данной заметке мы ...
Добавлено: 22 октября 2017 г.
Захаров В. А., Жайлауова Ш. Р., В кн. : Материалы XIII Международного семинара "Дискретная математика и ее приложения" имени академика О.Б. Лупанова (Москва, МГУ, 17-22 июня 2019). : М. : Изд-во механико-математического факультета МГУ, 2019. С. 272-274.
В данной статье мы продолжаем поиск и исследование новых классов недетерминированных автоматов-преобразователей с разрешимой проблемой эквивалентности. Цель исследования~--- провести как можно более точную и подробную демаркацию границы между разрешимыми и неразрешимыми случаями проблемы эквивалентности для рассматриваемой модели вычислений. Мы рассматриваем один класс недетерминированных автоматов, работающих над выходным алфавитом из одной буквы. Характерная особенность рассматриваемых автоматов-преобразователей ...
Добавлено: 17 октября 2019 г.
Vladislav Podymov, , in : CEUR Workshop Proceedings. Vol. 1492: Proceedings of the 24th International Workshop on Concurrency, Specification and Programming. Rzeszow, Poland, September 28-30, 2015.: CEUR Workshop Proceedings, 2015. P. 85-96.
Добавлено: 10 октября 2016 г.
Vladislav Podymov, , in : Concurrency, Specification & Programming. 24th International Workshop, CS&P 2015. Rzeszow, Poland, September 28-30, 2015. Proceedings. Vol. 2.: University of Rzeszow, 2015. P. 85-96.
Добавлено: 11 октября 2015 г.
Захаров В. А., Жайлауова Ш. Р., Моделирование и анализ информационных систем 2017 Т. 24 № 4 С. 415-433
Стандартные схемы программ - это одна из наиболее простых моделей последовательных императивных программ, предназначенная для решения задач оптимизации и верификации программ. Мы рассматриваем разрешимое отношение логико-термальной эквивалентности стандартных схем программ и задачу минимизации их размера при условии сохранением отношения логико-термальной эквивалентности. Нами доказано, что эта задача является алгоритмически разрешимой. Далее показано, что стандартные схемы программ ...
Добавлено: 12 октября 2017 г.
Захаров В. А., Новикова Т. А., В кн. : Дискретные модели в теории управляющих систем : IX Международная конференция, Москва и Подмосковье, 20-22 мая 2015 г.: Труды. : М. : МАКС Пресс, 2015. С. 173-176.
В статье предложена новая модель последовательных императивных программ, использующих средства работы с динамической памятью (указателями, списками и пр.) ...
Добавлено: 12 октября 2015 г.
Захаров В. А., Козлова Д. Г., В кн. : Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.). : М. : Изд-во механико-математического факультета МГУ, 2016. С. 204-206.
Характерная особенность моделей Крипке и большинства темпоральных логик (PLTL, CTL, PDL, mu-исчисление и др.), используемых в качестве формальных языков спецификации, состоит в том, что элементарные свойства вычислений зависят только от состояний модели, но не от вычислений, которыми достигаются состояния. Однако для стороннего наблюдателя поведение реагирующей системы проявляется в соответствии между последовательностями стимулов (сигналов), которыми внешняя ...
Добавлено: 13 октября 2016 г.
The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups
Birget J., Таламбуца А. Л., International Journal of Algebra and Computation 2022 Vol. 32 No. 6 P. 1261-1274
Добавлено: 9 декабря 2022 г.
Шитов Я. Н., / Cornell University. Series math "arxiv.org". 2014. No. 1406.2601.
Добавлено: 14 марта 2015 г.
Захаров В. А., Моделирование и анализ информационных систем 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 г.
Высоцкий Л. И., Жуков В. В., Шуплецов М. С., В кн. : Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС-2018). Вып. 1.: М. : ИППМ РАН, 2018. С. 30-37.
При обнаружении ошибок или изменении
спецификации
проектируемой
сверхбольшой
интегральной схемы (СБИС) на поздних этапах
маршрута проектирования откат на более ранние этапы
проектирования и их повторное выполнение очень часто
становится непрактичным в силу существенных
временных затрат. Для целей сокращения времени
проектирования
в
современные
маршруты
проектирования интегрируют специальные этапы
функциональной коррекции схемы (англ. Engineering
Change Order, ECO). В основе указанного подхода лежит
анализ уже спроектированной схемы и построение
небольшой подсхемы-заплатки, внедрение которой в уже
синтезированную ...
Добавлено: 10 ноября 2020 г.
Гнатенко А. Р., Захаров В. А., Моделирование и анализ информационных систем 2021 Т. 28 № 4 С. 356-371
К последовательным реагирующим системам относятся компьютерные программы и вычислительные устройства, которые обрабатывают потоки входных данных или сигналов управления и генерируют на выходе последовательности команд или результатов вычислений. Для проектирования таких систем полезно иметь формальные языки спецификаций, способные выражать отношения между входными и выходными потоками данных. В предшествующих работах нами было предложено семейство таких языков спецификаций, ...
Добавлено: 17 января 2022 г.
Авдошин С. М., Набебин А. А., М. : ДМК Пресс, 2017
Книга содержит необходимые сведения из универсальных и классических алгебр, системы аксиом для основных алгебраических структур (группоид, моноид, полугруппы, группы, частичные порядки, кольца, поля). Описываются основные криптографические алгоритмы. Рассматриваются ставшие классическими помехоустойчивые коды – линейные, циклические, БЧХ. Приводятся алгоритмы проектирования таких кодов. В основу книги положен многолетний опыт преподавания авторами дисциплины «Дискретная математика» на факультете бизнес-информатика, ...
Добавлено: 19 августа 2016 г.