Институт системного программирования им. В.П. Иванникова РАН


О проблеме эквивалентности потоковых программ.

Авторы

Захаров В.А.

Аннотация

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

Издание

Труды Второй Международной научно-технической конференции «Компьютерные методы и технологии», Белгород, 3-6 октября 2011, 2011, Белгородский государственный университет Белгород, с. 34-37.

Научная группа

Теоретическая информатика

Все публикации за 2011 год Все публикации