Оптимизирующие преобразования потоковых программ

Захаров Владимир Анатольевич; Темербекова Гульгайша Габидуловна

Глава

Оптимизирующие преобразования потоковых программ

С. 232-234.

Захаров В. А., Темербекова Г. Г.

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

Язык: русский

Текст на другом сайте

Ключевые слова: конечный автомат-преобразователь полугруппа задача минимизации

Публикация подготовлена по результатам проекта: Проектирование и анализ поведения распределенных процессно-ориентированных информационных систем(2016)

В книге

Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.)

М.: Изд-во механико-математического факультета МГУ, 2016.

Metric for the total tardiness minimization problem

Коренев П., Lazarev A. A. In bk.: . P. 134-139.

Добавлено: 20 октября 2014

Темпоральная логика для верификации автоматов-преобразователей

Захаров В. А., Козлова Д. Г. В кн.: Материалы XII Международного семинара "Дискретная математика и её приложения" имени академика О.Б. Лупанова (Москва, МГУ, 20-25 июня 2016г.). М.: Изд-во механико-математического факультета МГУ, 2016. С. 204-206.

Характерная особенность моделей Крипке и большинства темпоральных логик (PLTL, CTL, PDL, mu-исчисление и др.), используемых в качестве формальных языков спецификации, состоит в том, что элементарные свойства вычислений зависят только от состояний модели, но не от вычислений, которыми достигаются состояния. Однако для стороннего наблюдателя поведение реагирующей системы проявляется в соответствии между последовательностями стимулов (сигналов), которыми внешняя среда воздействует на систему, и откликов (действий), которые вырабатывает или исполняет система в ответ на внешние воздействия. Поэтому при верификации некоторых видов реагирующих систем элементарными свойствами становятся множества конечных последовательностей действий. Это обстоятельство должно быть также учтено при разработке формального языка спецификаций поведения таких систем. В данной статье рассмотрена задача формальной верификации реагирующих систем, моделируемых конечными автоматами-преоб\-разователями. Для спецификации их поведения предложен новый вариант темпоральной логики линейного времени LTL-FL (LTL with Formal Languages). Формальные языки (множества конечных слов фиксированных алфавитов) в формулах LTL-FL используются для представления элементарных свойств вычислений, а также для параметризации темпоральных операторов. Установлено, что задача проверки выполнимости формул регулярного фрагмента FL-LTL на конечных автоматах преобразователях разрешима.

Добавлено: 13 октября 2016

Алгоритм проверки эквивалентности линейных унарных рекурсивных программ на упорядоченных полугрупповых шкалах

Подымов В. В. Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика. 2012. № 4. С. 37-43.

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

Добавлено: 29 сентября 2015

Об эквивалентности ограниченно недетерминированных автоматов-преобразователей над полугруппами

Захаров В. А. В кн.: Материалы XVII международной конференции "Проблемы теоретической кибернетики". Каз.: Отечество, 2014. С. 100-102.

Показано, что задача проверки k-значности конечного автомата-преобразователя, работающего над полугруппой, вложимой в разрешимую группу, может быть решена за время, полиномиальное относительно размера автомата.

Добавлено: 13 октября 2015

Алгебраическая спецификация программных систем

Набебин А. А., Тарасиков А. С. М.: ИНЭК, 2012.

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

Добавлено: 18 июля 2012

Полугруппы разложений на множители и неприводимые компоненты пространства Гурвица

Вик. С. Куликов Известия РАН. Серия математическая. 2011. Т. 75. № 4. С. 49-90.

Определена естественная структура полугруппы (изоморфной полугруппе разложений на множители единицы в симметрической группе) на множестве неприводимых компонент пространства Гурвица отмеченных накрытий степени d проективной прямой P^1 с фиксированными типами ветвлений. Доказано, что эта полугруппа является конечно определенной. Исследована также проблема, когда наборы типов ветвления однозначно определяют соответствующие неприводимые компоненты пространства Гурвица. В частности, полностью описано множество неприводимых компонент пространства Гурвица трехлистных накрытий проективной прямой.

Добавлено: 21 января 2015

Дискретная математика. Модулярная алгебра, криптография, кодирование.

Авдошин С. М., Набебин А. А. М.: ДМК Пресс, 2017.

Книга содержит необходимые сведения из универсальных и классических алгебр, системы аксиом для основных алгебраических структур (группоид, моноид, полугруппы, группы, частичные порядки, кольца, поля). Описываются основные криптографические алгоритмы. Рассматриваются ставшие классическими помехоустойчивые коды – линейные, циклические, БЧХ. Приводятся алгоритмы проектирования таких кодов. В основу книги положен многолетний опыт преподавания авторами дисциплины «Дискретная математика» на факультете бизнес-информатика, на факультете компьютерных наук Национального исследовательского университета Высшая школа экономики и на факультете автоматики и вычислительной техники Национального исследовательского университета Московский энергетический институт. Книга предназначена для студентов бакалавриата, обучающихся по направлениям 09.03.01 «Информатика и вычислительная техника», 09.03.02 «Информационные системы и технологии», 09.03.03 «Прикладная информатика», 09.03.04 «Программная инженерия», а также для ИТ-специалистов и разработчиков программных продуктов.

Добавлено: 19 августа 2016

Equivalence Checking Problem for Finite State Transducers

Zakharov V.A. Lecture Notes in Computer Science. 2015. Vol. 9270. P. 208-221.

Добавлено: 30 сентября 2015

A semigroup identity for tropical 3x3 matrices

Shitov Y. arxiv.org. math. Cornell University, 2014. No. 1406.2601.

Добавлено: 14 марта 2015