• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • Национальный исследовательский университет «Высшая школа экономики»
  • Публикации ВШЭ
  • Глава
  • On Emptiness and Membership Problems for Set Automata
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Приоритетные направления
  • бизнес-информатика
  • государственное и муниципальное управление
  • гуманитарные науки
  • инженерные науки
  • компьютерно-математическое
  • математика
  • менеджмент
  • право
  • социология
  • экономика
по году
  • 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
  • еще
Тематика
Новости
20 мая 2026 г.
«Еж» против «родственника»: ученые измерили, как мозг реагирует на неожиданные слова в живой речи
Российские нейрофизиологи с участием исследователей из НИУ ВШЭ показали, что изучать восприятие живой речи можно с помощью вызванных потенциалов. Они доказали, что метод применим не только к отдельным словам, но и к непрерывной речи. Оказалось, что слова, сильно отличающиеся по смыслу от предыдущего контекста, мозг обрабатывает дольше, а служебные слова анализирует в два этапа: сначала определяет их грамматическую роль, а затем на этой основе предсказывает следующее слово. Исследование опубликовано в журнале Frontiers in Human Neuroscience.
20 мая 2026 г.
Творческая работа как лекарство от выгорания
Творческая и доброжелательная атмосфера, новые методы в Международной лаборатории (впоследствии центре) социокультурных исследований привлекают молодых исследователей. За годы работы в Вышке они становятся учеными и преподавателями, известными в России и за рубежом. О своем пути в центре и в Вышке, исследованиях и роли наставников в научных успехах рассказали главный научный сотрудник ЦСКИ Зарина Лепшокова и ведущий научный сотрудник Екатерина Бушина.
19 мая 2026 г.
Физики НИУ ВШЭ выяснили, что происходит внутри устойчивого вихря
В атмосфере и в океане часто наблюдаются крупные вихри с характерными спиральными рукавами. Физики из НИУ ВШЭ объяснили, как они формируются и почему сохраняют свою структуру. Оказалось, что скорости в точках, расположенных вдоль одной дуги вихря, остаются связанными даже на больших расстояниях. При этом в направлении от центра вихря эта связь быстро ослабевает. Такие различия помогают объяснить образование рукавов и могут улучшить модели атмосферных и океанических течений. Результаты опубликованы в Physical Review Fluids.

 

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

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

?

On Emptiness and Membership Problems for Set Automata

P. 295–307.
Рубцов А. А., Вялый М. Н.
Язык: английский
Полный текст
DOI
Текст на другом сайте
Ключевые слова: Сложность вычисленийтеория автоматовautomata theoryComputational ComplexityFormal languagesформальные языки
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Теоретическая информатика (2018)

В книге

Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings
Vol. 10846. , Springer, 2018.
Похожие публикации
Computational Model for Parsing Expression Grammars
Alexander Rubtsov, Chudinov N., , in: 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024).: Leibniz International Proceedings in Informatics (LIPIcs), 2024. Ch. 80 P. 80:1–80:13.
Добавлено: 24 ноября 2024 г.
On efficient algorithms for bottleneck path problems with many sources
Kirill V. Kaymakov, Dmitry S. Malyshev, Optimization Letters 2024 Vol. 18 P. 1273–1283
Добавлено: 18 апреля 2024 г.
A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
Малышев Д. С., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791–801
Добавлено: 16 февраля 2024 г.
Безопасные информационные технологии. Сборник трудов XII международной научно-технической конференции "Безопасные информационные технологии"
М.: Московский государственный технический университет им. Н.Э. Баумана, 2023.
Сборник содержит тезисы докладов, представленных на международной научно-технической конференции "Безопасные информационные технологии" (БИТ-2023), проходившей 1-2 ноября 2023 г. в Москве в МГТУ им. Н.Э.Баумана. Тезисы публикуются в редакции научных руководителей или в авторской редакции при наличии ученой степени. ...
Добавлено: 16 февраля 2024 г.
Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering with a Covering Axiom
Герасимова О. А., Макаров И. А., Severin N., IEEE Access 2023 Vol. 11 P. 88074–88086
The problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontology constraints increases. Logic-based methods use theoretical constructions to obtain efficient rewritings ...
Добавлено: 5 января 2024 г.
ЗАДАЧНИК ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Дехтярь М. И., Дудаков С. М., Карлов Б. Н., Тверь: Тверской государственный университет, 2021.
Учебное пособие адресовано изучающим курс дискретной математики, прежде всего, студентам младших курсов, обучающимся по направлениям укрупненных групп 01.03.00 "Математика и механика", 02.03.00 "Компьютерные и информационные науки", 09.03.00 "Информатика и вычислительная техника". Настоящий сборник задач является пособием для практических занятий по некоторым разделам дискретной математики и может быть использован преподавателями и студентами для подготовки к семинарским  занятиям и ...
Добавлено: 12 ноября 2023 г.
Мещеряков М.В. Сухарев Л.А. Практикум по теории конечных автоматов и формальных языков- Саранск : Изд-во Мордов. ун-та, 2018.-224с.
Мещеряков М. В., Сухарев Л. А., Саранск: Изд-во Мордовского университета, 2018.
Книга является вводным курсом по теории формальных языков и конечных автоматов. В ней представлен основной материал дициплины, относящийся к математическим основам ряда синтаксических методов инорматики и программирования. Книга предназначена для студентов бакалавриата по направлениям подготовки: фундаментальная информатика и информационные технологии, прикладная математика и информатика, программная инженерия ...
Добавлено: 12 октября 2023 г.
The discrete Fourier transform over the binary finite field
Sergei Valentinovich Fedorenko, IEEE Access 2023 Vol. 11 P. 62771–62779
Добавлено: 19 июля 2023 г.
Complexity function and complexity of validity of modal and superintuitionistic propositional logics
Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566–1595
Добавлено: 6 января 2023 г.
Some cases of polynomial solvability of the edge coloring problem that are generated by forbidden 8-edge subcubic forests
Малышев Д. С., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2022 Vol. 16 P. 276–291
Добавлено: 31 декабря 2022 г.
On a Countable Family of Boundary Graph Classes for the Dominating Set Problem
G. S. Dakhno, D. S. Malyshev, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 1 P. 25–31
Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Если это множество конечно, то он называется конечно определенным. Понятие граничного класса является полезным инструментом анализа вычислительной сложности задач на графах в семействе конечно определенных классов. Задача о доминирующем множестве для заданного графа состоит в ...
Добавлено: 6 декабря 2022 г.
Comparing the Computational Complexity of Monomials and Elements of Finite Abelian Groups
Кочергин В. В., Moscow University Mathematics Bulletin 2022 Vol. 77 No. 3 P. 113–119
Добавлено: 29 октября 2022 г.
Complexity of finite-variable fragments of propositional temporal and modal logics of computation
Рыбаков М. Н., Shkatov D., Theoretical Computer Science 2022 Vol. 925 P. 45–60
Добавлено: 12 мая 2022 г.
An intractability result for the vertex 3-colourability problem
Malyshev D. S., Приставченко О. В., Optimization Letters 2022 Vol. 16 P. 1403–1409
Добавлено: 25 февраля 2022 г.
On computational complexity of set automata
Рубцов А. А., Вялый М. Н., Information and Computation 2021 Vol. 281 Article 104797
Добавлено: 2 февраля 2022 г.
Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning
Захарьящев М. В., Kontchakov R., Ryzhikov V. и др., The International Joint Conference on Artificial Intelligence (IJCAI), 2020.
Добавлено: 6 ноября 2021 г.
Automata Under Effective Observation
Бабаш А. В., , in: Proceedings of the 10th International Scientific and Practical Conference named after A. I. Kitov "Information Technologies and Mathematical Methods in Economics and Management (IT&MM-2020)"/, Moscow, Russia, October 15-16, 2020Vol. 2830.: CEUR Workshop Proceedings, 2021. P. 337–359.
A trapdoor cipher is a cipher whose algorithm contains some hidden structure (a trapdoor) providing the existence of a subliminal information channel. In cryptographic practice, there could be situations when a constructed cipher may contain some critical defect (a trapdoor) whose identification can significantly weaken the cryptographic strength of this cipher. In this paper, we ...
Добавлено: 2 ноября 2021 г.
Developments in Language Theory: 25th International Conference, DLT 2021, Porto, Portugal, August 16–20, 2021, Proceedings
Switzerland: Springer International Publishing, 2021.
Добавлено: 28 сентября 2021 г.
No-Rainbow Problem and the Surjective Constraint Satisfaction Problem
Жук Д. Н., , in: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).: [б.и.], 2021. P. 1–7.
Добавлено: 8 сентября 2021 г.
Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP
Barto L., Brady Z., Bulatov M. и др., , in: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).: [б.и.], 2021. P. 1–13.
Добавлено: 8 сентября 2021 г.
On 3-colouring of graphs with short faces and bounded maximum vertex degree
Сироткин Д. В., Малышев Д. С., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760–766
Добавлено: 5 июня 2021 г.
Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
Развенская О. О., Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2021 Vol. 15 No. 1 P. 97–117
Добавлено: 23 апреля 2021 г.
  • О ВЫШКЕ
  • Цифры и факты
  • Руководство и структура
  • Устойчивое развитие в НИУ ВШЭ
  • Преподаватели и сотрудники
  • Корпуса и общежития
  • Закупки
  • Обращения граждан в НИУ ВШЭ
  • Фонд целевого капитала
  • Противодействие коррупции
  • Сведения о доходах, расходах, об имуществе и обязательствах имущественного характера
  • Сведения об образовательной организации
  • Людям с ограниченными возможностями здоровья
  • Единая платежная страница
  • Работа в Вышке
  • ОБРАЗОВАНИЕ
  • Лицей
  • Довузовская подготовка
  • Олимпиады
  • Прием в бакалавриат
  • Вышка+
  • Прием в магистратуру
  • Аспирантура
  • Дополнительное образование
  • Центр развития карьеры
  • Бизнес-инкубатор ВШЭ
  • Образовательные партнерства
  • Обратная связь и взаимодействие с получателями услуг
  • НАУКА
  • Научные подразделения
  • Исследовательские проекты
  • Мониторинги
  • Диссертационные советы
  • Защиты диссертаций
  • Академическое развитие
  • Конкурсы и гранты
  • Внешние научно-информационные ресурсы
  • РЕСУРСЫ
  • Библиотека
  • Издательский дом ВШЭ
  • Книжный магазин «БукВышка»
  • Типография
  • Медиацентр
  • Журналы ВШЭ
  • Публикации
  • http://www.minobrnauki.gov.ru/
    Министерство науки и высшего образования РФ
  • https://edu.gov.ru/
    Министерство просвещения РФ
  • http://www.edu.ru
    Федеральный портал «Российское образование»
  • https://elearning.hse.ru/mooc
    Массовые открытые онлайн-курсы
  • НИУ ВШЭ1993–2026
  • Адреса и контакты
  • Условия использования материалов
  • Политика конфиденциальности
  • Правила применения рекомендательных технологий в НИУ ВШЭ
  • Карта сайта
Редактору