• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • Национальный исследовательский университет «Высшая школа экономики»
  • Публикации ВШЭ
  • Статьи
  • Полиномиальный по времени алгоритм проверки логико-термальной эквивалентности программ
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Приоритетные направления
  • бизнес-информатика
  • государственное и муниципальное управление
  • гуманитарные науки
  • инженерные науки
  • компьютерно-математическое
  • математика
  • менеджмент
  • право
  • социология
  • экономика
по году
  • 2028
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • еще
Тематика
Новости
30 сентября 2026 г.
Ученые НИУ ВШЭ - Санкт-Петербург нашли способ ускорения нейросетей при помощи микролазеров
Ученые Международной лаборатории квантовой оптоэлектроники НИУ ВШЭ — Санкт-Петербург и Лазерного института Академии наук Шаньдунь (Китай) смогли напрямую сопоставить скорость микродисковых лазеров, работающих от оптической и электрической энергии. Результаты позволят оптимизировать работу источников излучения в фотонных чипах для нейросетей и дата-центров. Исследование опубликовано в журналеJournal of Lightwave Technology.
30 сентября 2026 г.
ВШЭ создала веб-приложение для оценки эффекта биочар-проектов
Центр цифровых технологий для природно-климатических проектов НИУ ВШЭ разработал веб-приложение для предварительной оценки проектов по производству биочара из растительных остатков и его внесению в почву. Инструмент позволяет рассчитать потенциальный объем производства биочара и углеродных единиц, определить необходимую площадь сельскохозяйственных земель, оценить объем инвестиций и ожидаемый экономический эффект проекта.
30 сентября 2026 г.
«Нужно быть готовым отстаивать свою позицию перед более опытными исследователями»
Татьяна Багриновцева занялась нейробиологией, потому что интересовалась устройством человеческого мозга. В интервью проекту «Молодые ученые Вышки» она рассказала о новой методике маркировки нейронов, работе с клеточными культурами и о любимом месте в Самаре — городской набережной.

 

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

Публикации
  • Книги
  • Статьи
  • Главы в книгах
  • Препринты
  • Верификация публикаций
  • Расширенный поиск
  • Правила использования материалов
  • Наука в ВШЭ

?

Полиномиальный по времени алгоритм проверки логико-термальной эквивалентности программ

Труды Института системного программирования РАН. 2012. Т. 22. С. 435–455.
Захаров В. А., Новикова Т. А.
Логико-термальная эквивалентность программ – это одно из наиболее слабых отношений эквивалентности программ, аппроксимирующих отношение функциональной эквивалентности и обладающих разрешающим алгоритмом. В данной статье предложена новая модификация алгоритма проверки логико-термальной эквивалентности программ, основанная на операции вычисления точной нижней грани в решетке конечных подстановок. Показано, что трудоемкость предложенного алгоритма оценивается величиной O(n6) , где n - размер анализируемых программ. Полученная верхняя оценка сложности задачи проверки логико-термальной эквивалентности программ существенно меньше ранее известных полиномиальных оценок сложности указанной задачи.
Научное направление: Компьютерные науки
Приоритетные направления: компьютерно-математическое
Язык: русский
Текст на другом сайте
Ключевые слова: эквивалентностькомпозициякомпьютерная программа алгоритмическая сложностьподстановкаантиунификация
Похожие публикации
Inverse quickest path problem on networks under weighted l_\infty norm
Qian X., Guan X., Zhang B. и др., Journal of Global Optimization 2026
Добавлено: 27 сентября 2026 г.
Navigating Complexity: Statistical Methods, Data Analysis, and Machine Learning for Actionable Insights
Switzerland: Springer Cham, 2026.
Добавлено: 25 сентября 2026 г.
An early warning system for emerging markets
Краевский А. А., Соколовский Е. И., Prokhorov A., Emerging Markets Review 2026 No. 74 P. 1–19
Добавлено: 25 сентября 2026 г.
Экспериментальное сравнение HTTP/2 и HTTP/3 в условиях программно моделируемой сетевой деградации
Дубич Е. В., Щагин Д. В., Славянский форум 2026 № 2 (52) С. 560–565
В статье сравниваются протоколы HTTP/2 и HTTP/3 при передаче статических файлов в условиях программно моделируемой сетевой деградации. Эксперимент показал, что HTTP/3 не является универсально более быстрым, но устойчивее проявляет себя при росте задержки и потерь пакетов. ...
Добавлено: 25 сентября 2026 г.
Synthesis of Acyclic Models for Processes Without Repeating Events
Joulitov A.K., Lomazova I.A., Proceedings of the Institute for System Programming of the RAS 2026 Vol. 38 No. 4(2) P. 215–224
В майнинге процессов (process mining) графы непосредственного следования (Directly-Follows Graph, DFG) популярны благодаря своей простоте и наглядности. Однако, если процесс является ациклическим, но содержит параллельные события, стандартные алгоритмы построения DFG-моделей могут генерировать «ложные» циклы, которыe не представлены в журнале событий. Такие циклы мешают анализу информационных процессов, значительно снижая интерпретируемость и точность (precision) модели. Эта проблема ...
Добавлено: 24 сентября 2026 г.
Анализ протокола выработки общего ключа для управления микросхемой интеллектуальной карты
Добрина Д. Н., Нестеренко А. Ю., Прикладная дискретная математика. Приложение 2026 № 19 С. 151–159
Работа содержит результаты формального анализа криптографических механизмов, входящих в состав проекта методических рекомендаций «Защищенный универсальный протокол передачи данных и управления микросхемой интеллектуальной карты» (протокол SECUNDA). Получена формальная модель и перечень трудноразрешимых математических задач, трудоёмкостью решения которых можно оценить стойкость используемых криптографических механизмов. ...
Добавлено: 24 сентября 2026 г.
Discovering object-centric Petri nets with parametric arcs
I.I. Sergeev, I.A. Lomazova, Modeling and Analysis of Information Systems 2026 Vol. 33 No. 3 P. 394–419
Объектно-ориентированный process mining сформировался как эффективная парадигма анализа событийных данных, включающих несколько взаимодействующих бизнес-объектов. Существующие методы обнаружения моделей часто опираются на объектно-ориентированные сети Петри с фиксированными кратностями дуг, что ограничивает их способность представлять параметрические закономерности потребления и производства ресурсов, а также отражать количественные зависимости между взаимодействующими типами объектов. В данной работе предлагается метод обнаружения объектно-ориентированных ...
Добавлено: 24 сентября 2026 г.
Hybrid Graph Retrieval-Augmented Language Agents for Collaborative Recommendation
Ivan Bulychev, Савченко А. В., AI 2026 Vol. 7 No. 9 Article 380
Добавлено: 24 сентября 2026 г.
Risks and the image of the future in the study of AI technologies prospects
Снегирев А. Ю., Сычев С. В., Futures 2026 Vol. 183 P. 1–22
Добавлено: 23 сентября 2026 г.
Choosing Between AI Responses: How Valence, Arousal, and Dominance Shape User Preference
Паршаков П. А., Паклина С. Н., International Journal of Human-Computer Interaction 2026 P. 1–17
Добавлено: 23 сентября 2026 г.
A Two-Stage Deep Reinforcement Learning Framework for Radio Resource Management and Network Slicing in 5G Heterogeneous Networks
Андраби У. М., Wadood E., Ojha S. K. и др., IEEE Access 2026 Vol. 14 P. 103358–103375
Добавлено: 23 сентября 2026 г.
LLM-assisted writing and citation advantage: evidence from scientific publications before and after ChatGPT release
Паклина С. Н., Паршаков П. А., Elena Rapoport, Scientometrics 2026 P. 1–26
Добавлено: 23 сентября 2026 г.
Label-Free Quantification in the Crux Toolkit
Кертес-Фаркаш А., Аквей Ф. Л., Journal of Proteome Research 2026 Vol. 25 P. 3764–3768
Добавлено: 23 сентября 2026 г.
Risk Assessment Models for Heated Tobacco Products
Maddalena L., Yildiz B., Del Vecchio Blanco F. и др., Risk Analysis 2026 Vol. 46 No. 4 P. 1–26
Добавлено: 22 сентября 2026 г.
Segmentation of the Iris and Pupil of the Human Eye in Images from an Infrared Camera
Aleksei Samarin, Alexander Savelev, Aleksei Toropov и др., Pattern Recognition and Image Analysis 2024 Vol. 34 No. 3 P. 855–862
Добавлено: 21 сентября 2026 г.
A Model Based on Universal Filters for Image Color Correction
Aleksei Samarin, Назаренко А. А., Alexander Savelev и др., Pattern Recognition and Image Analysis 2024 Vol. 34 No. 3 P. 844–854
Добавлено: 21 сентября 2026 г.
Streptococci Recognition in Microscope Images Using Taxonomy-based Visual Features
Aleksei Samarin, Alexander Savelev, Aleksei Toropov и др., Optical Memory and Neural Networks (Information Optics) 2024 Vol. 33 P. 424–434
Добавлено: 21 сентября 2026 г.
On calibration of remote sensing retrievals of ecosystem respiration (Reco) with tower measurements over,Russian forests and wetlands
Shabanov N., Kuricheva O., Kurbatova J. и др., / Series Working Papers SSRN "Department of Economics Ca’ Foscari University of Venice". 2026.
Добавлено: 21 августа 2026 г.
Three Algorithms for Merging Hierarchical Navigable Small World Graphs
Пономаренко А. А., / Series Computer Science "arxiv.org". 2025.
Добавлено: 30 июля 2026 г.
Growth in noncommutative algebras and entropy in derived categories
Пионтковский Д. И., / Series arXiv "math". 2026.
Добавлено: 23 июня 2026 г.
Multilinear nilalgebras and the Jacobian theorem
Пионтковский Д. И., / Series arXiv "math". 2025.
Добавлено: 23 июня 2026 г.
ML-based Fast Simulation of FARICH Responses
Шипилов Ф. А., Barnyakov A., Ivanov A. и др., / Series Physics "arxiv.org". 2026.
Добавлено: 19 мая 2026 г.
Natural hazard database from Internet publications: text mining with a large language model
Деркачева А. А., Сакиркина М. А., Краев Г. Н. и др., /. 2026.
Добавлено: 28 апреля 2026 г.
Algorithmic overlaps as thermodynamic variables: from local to cluster Monte Carlo dynamics in critical phenomena
Пиле Я. Э., Deng Y., Щур Л. Н., / Series arXiv "math". 2026. No. 2604.10254.
Добавлено: 20 апреля 2026 г.
  • О ВЫШКЕ
  • Цифры и факты
  • Руководство и структура
  • Устойчивое развитие в НИУ ВШЭ
  • Преподаватели и сотрудники
  • Корпуса и общежития
  • Закупки
  • Обращения граждан в НИУ ВШЭ
  • Фонд целевого капитала
  • Противодействие коррупции
  • Сведения о доходах, расходах, об имуществе и обязательствах имущественного характера
  • Сведения об образовательной организации
  • Людям с ограниченными возможностями здоровья
  • Единая платежная страница
  • Работа в Вышке
  • ОБРАЗОВАНИЕ
  • Лицей
  • Довузовская подготовка
  • Олимпиады
  • Прием в бакалавриат
  • Вышка+
  • Прием в магистратуру
  • Аспирантура
  • Дополнительное образование
  • Центр развития карьеры
  • Бизнес-инкубатор ВШЭ
  • Образовательные партнерства
  • Обратная связь и взаимодействие с получателями услуг
  • НАУКА
  • Научные подразделения
  • Исследовательские проекты
  • Мониторинги
  • Диссертационные советы
  • Защиты диссертаций
  • Академическое развитие
  • Конкурсы и гранты
  • Внешние научно-информационные ресурсы
  • РЕСУРСЫ
  • Библиотека
  • Издательский дом ВШЭ
  • Книжный магазин «БукВышка»
  • Типография
  • Медиацентр
  • Журналы ВШЭ
  • Публикации
  • http://www.minobrnauki.gov.ru/
    Министерство науки и высшего образования РФ
  • https://edu.gov.ru/
    Министерство просвещения РФ
  • https://elearning.hse.ru/mooc
    Массовые открытые онлайн-курсы
  • НИУ ВШЭ1993–2026
  • Адреса и контакты
  • Условия использования материалов
  • Политика обработки персональных данных
  • Правила применения рекомендательных технологий в НИУ ВШЭ
  • Карта сайта
Редактору