• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • Национальный исследовательский университет «Высшая школа экономики»
  • Публикации ВШЭ
  • Глава
  • Regular Realizability Problems and Context- Free Languages
  • 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
  • еще
Тематика
Новости
28 мая 2026 г.
«Мне нравятся самосбывающиеся пророчества»
Андрей Ворчик изучает счастье, читает научпоп-лекции и хочет, чтобы наука занималась в том числе общественными проблемами. В интервью проекту «Молодые ученые Вышки» он рассказал о том, как эмоции влияют на принятие решений, Бермудском треугольнике из ванной, холодильника и кровати и идеальной формуле образования.
28 мая 2026 г.
Карманные деньги, интерес и семья: что влияет на экономическую грамотность студентов
Экономическая грамотность студентов зависит не только от профильного образования, но и от интереса к экономике, учебной среды и финансовых практик в семье. Так, студенты, получавшие карманные деньги нерегулярно, в среднем лучше справляются с тестами по экономической грамотности, чем их сверстники с постоянной финансовой поддержкой. Это показало исследование НИУ ВШЭ на выборке более 1100 студентов из пяти российских университетов. Результаты работы опубликованы в журнале Cakrawala Pendidikan.
27 мая 2026 г.
Нейросетевое отображение как метод создания математических моделей
Ученые НИУ ВШЭ в Нижнем Новгороде и Белградского института физики (Сербия) совместно изучают возможности применения методов машинного обучения и использования нейросетей в исследованиях нелинейной динамики. О международном проекте «Вышке.Главное» рассказала его руководитель от ВШЭ, ведущий научный сотрудник Лаборатории топологических методов в динамике факультета информатики, математики и компьютерных наук НИУ ВШЭ в Нижнем Новгороде Наталия Станкевич.

 

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

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

?

Regular Realizability Problems and Context- Free Languages

P. 256–267.
Рубцов А. А., Вялый М. Н.
Язык: английский
Полный текст
Ключевые слова: Сложность вычисленийтеория автоматовautomata theoryконтекстно-свободные языкиComputational ComplexityFormal languagesформальные языки

В книге

Descriptional Complexity of Formal Systems
Vol. 9118. , Switzerland: Springer, 2015.
Похожие публикации
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
  • Адреса и контакты
  • Условия использования материалов
  • Политика конфиденциальности
  • Правила применения рекомендательных технологий в НИУ ВШЭ
  • Карта сайта
Редактору