- Об институте
- Инновации
- Структура
- Отдел "Архитектуры вычислительных систем"
- Отдел "Информационных систем"
- Отдел "Компиляторных технологий"
- Отдел "Системного программирования"
- Отдел "Системной интеграции и прикладных программных комплексов"
- Отдел "Теоретической информатики"
- Отдел "Технологий программирования"
- Ученый совет
- Диссертационный совет
- Центр верификации ОС Linux
- Исследовательский центр доверенного искусственного интеллекта
- Центр компетенции по параллельным и распределенным вычислениям
- Образование
- Издания
- Новости
- Лицензии
О проблеме эквивалентности потоковых программ.
Авторы
Захаров В.А.
Аннотация
Потоковые алгоритмы, работающие в оперативном режиме, получают на вход конечные последовательности запросов, которые они должен обработать и в заключение принять некоторое решение, не зная заранее, какие запросы могут поступить на очередном шаге вычисления. Нами предложена пропозициональная математическая модель потоковых программ, работающих в оперативном режиме, и исследована проблема эквивалентности для этих программ. Используя теоретико-автоматный подход к решению этой проблемы, разработанный ранее для последовательных программ, мы покажем, как решить задачу проверки эквивалентности потоковых программ за полиномиальное время.
Издание
Труды Второй Международной научно-технической конференции «Компьютерные методы и технологии», Белгород, 3-6 октября 2011, 2011, Белгородский государственный университет Белгород, с. 34-37.