• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Исследование функции высоты контекстно-свободных языков
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 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
  • More
Subject
News
May 22, 2026
HSE Graduates AI Project Wins at TECH & AI Awards
Daria Davydova, graduate of the HSE Graduate School of Business and Head of the AI Implementation Unit at the Artificial Intelligence Department of Alfa-Bank, received a prize at the TECH & AI Awards. She was awarded for the best AI solution for optimising business processes. The winners were determined as part of the VII Russian Summit and Awards on Digital Transformation (CDO/CDTO Summit & Awards).
May 20, 2026
HSE University Opens First Representative Office of Satellite Laboratory in Brazil
HSE University-St Petersburg opened a representative office of the Satellite Laboratory on Social Entrepreneurship at the University of Campinas in Brazil. The platform is going to unite research and educational projects in the spheres of sustainable development, communications and social innovations.
May 18, 2026
The 'Second Shift' Is Not Why Women Avoid News
Women are more likely than men to avoid political and economic news, but the reasons for this behaviour are linked less to structural inequality or family-related stress than to personal attitudes and the emotional perception of news content. This conclusion was reached by HSE researchers after analysing data from a large-scale survey of more than 10,000 residents across 61 regions of Russia. The study findings have been published in Woman in Russian Society.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Исследование функции высоты контекстно-свободных языков

С. 128–130.
Rubtsov A. A.
Language: Russian
Keywords: Сложность вычисленийтеория автоматов

In book

Труды 56-й научной конференции МФТИ: Всероссийской научной конференции «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе» , Всероссийской молодежной научно-инновационной конференции «Физико-математические науки: актуальные проблемы и их решения»
Т. 1: Управление и прикладная математика. , Долгопрудный: МФТИ, 2013.
Similar publications
The discrete Fourier transform over the binary finite field
Sergei Valentinovich Fedorenko, IEEE Access 2023 Vol. 11 P. 62771–62779
The novel methods for binary discrete Fourier transform (DFT) computation over the finite field have been proposed. The methods are based on a binary trace calculation over the finite field and use the cyclotomic DFT. The direct DFT computational complexity has been reduced due to using the binary trace function over the finite field and ...
Added: July 19, 2023
Исследование задачи регулярной реализуемости
Rubtsov A. A., На правах рукописи, 2016.
В диссертации исследуется задача регулярной реализуемости, которая состоит в проверке пересечения фиксированного языка (параметра задачи) с регулярным языком на входе задачи. Основная часть работа посвящена исследованию вычислительной сложности задачи для КС-фильтров. ...
Added: November 1, 2018
A Structural Lemma for Deterministic Context-Free Languages
Rubtsov A. A., , in: Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings.: Cham: Springer, 2018. P. 553–565.
We present a new structural lemma for deterministic con- text free languages. From the first sight, it looks like a pumping lemma, because it is also based on iteration properties, but it has significant distinctions that makes it much easier to apply. The structural lemma is a combinatorial analogue of KC-DCF-Lemma (based on Kolmogorov complexity), ...
Added: September 12, 2018
On Emptiness and Membership Problems for Set Automata
Rubtsov A. A., Vyalyi M., , in: Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, ProceedingsVol. 10846.: Springer, 2018. P. 295–307.
We consider a computational model which is known as set automata. The set automata are one-way finite automata with an additional storage—the set. There are two kinds of set automata—the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by Kutrib et al. in 2014 in [2, 3]. In this ...
Added: June 21, 2018
Теория и реализация языков программирования
Серебряков В. А., Гончар Д. Р., Rubtsov A. A. et al., МФТИ, 2017.
Содержит программу, список литературы и задачи одноимённого курса, читаемого студентам факультета управления и прикладной математики МФТИ (ГУ). Задачи могут быть использованы в качестве упражнений на семинарских занятиях, заданий, экзаменационного материала, а также при самостоятельном освоениии курса. ...
Added: October 20, 2017
О задачах регулярной реализуемости для контекстно-свободных языков
Vyalyi M., Rubtsov A. A., Проблемы передачи информации 2015 Т. 51 № 4 С. 47–59
We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance ...
Added: February 14, 2016
О вычислительной сложности языков, распознаваемых автоматами со словарём (Set Automata)
Rubtsov A. A., В кн.: Труды IX Международной конференции "Дискретные модели в теории управляющих систем".: М.: МАКС Пресс, 2015. С. 207–210.
В работе исследована вычислительная сила детерминированных и недетерминированных автомтаов со словарём. ...
Added: August 25, 2015
О возможностях и ограничениях автоматов со словарём (Set Automata)
Rubtsov A. A., В кн.: Труды 57-й научной конференции МФТИ — Всероссийской научной конференции с международным участием «Актуальные проблемы фундаментальных и прикладных наук в области физики», Всероссийской молодежной научной конференции с международным участием «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе».Т. 1: Управление и прикладная математика.: М.: МФТИ, 2014. С. 123–125.
В работе приведены примеры различных языков, распознаваемых автоматами со словарём и исследована их вычислительная сложность. ...
Added: August 25, 2015
Regular Realizability Problems and Context- Free Languages
Rubtsov A. A., Vyalyi M., , in: Descriptional Complexity of Formal SystemsVol. 9118.: Switzerland: Springer, 2015. P. 256–267.
We investigate regular realizability (RR) problems, which are the prob- lems of verifying whether intersection of a regular language – the input of the problem – and fixed language called filter is non-empty. In this pa- per we focus on the case of context-free filters. Algorithmic complexity of the RR problem is a very coarse ...
Added: August 25, 2015
Теория автоматов. Часть 3. Арифметика ЭВМ
Birukov I., М.: МГИЭМ, 2010.
Курс «Теория автоматов» является одним из фундаментальных курсов для дальнейшего изучения всех дисциплин, связанных с аппаратной частью ЦВМ. Данный курс формировался постепенно, складываясь из предшествующих ему курсов: «Арифметические и логические основы цифровых автоматов» и «Прикладная теория цифровых автоматов». Автор долгое время читал предыдущие курсы и в настоящее время читает этот курс. За время чтения лекций ...
Added: February 25, 2015
Теория автоматов. Часть 2. Логическое проектирование схем с памятью
Birukov I., М.: МГИЭМ, 2012.
Курс «Теория автоматов» является одним из фундаментальных курсов для дальнейшего изучения всех дисциплин, связанных с аппаратной частью ЦВМ. Данный курс формировался постепенно, складываясь из предшествующих ему курсов: «Арифметические и логические основы цифровых автоматов» и «Прикладная теория цифровых автоматов». Автор долгое время читал предыдущие курсы и в настоящее время читает этот курс. За время чтения лекций ...
Added: February 25, 2015
Теория автоматов. Часть 1. Логическое проектирование комбинационных схем
Birukov I., М.: МГИЭМ, 2010.
Курс «Теория автоматов» является одним из фундаментальных курсов для дальнейшего изучения всех дисциплин, связанных с аппаратной частью ЦВМ. Данный курс формировался постепенно, складываясь из предшествующих ему курсов: «Арифметические и логические основы цифровых автоматов» и «Прикладная теория цифровых автоматов». Автор долгое время читал предыдущие курсы и в настоящее время читает этот курс. За время чтения лекций ...
Added: February 25, 2015
Алгоритмическая разрешимость задач о поведении автоматов на сверхсловах
Vyalyi M., Rubtsov A. A., Дискретный анализ и исследование операций 2012
Работа посвящена двум алгоритмическим задачам, связанным с анализом поведения конечного автомата при чтении сверхслова (бесконечной последовательности): достигает ли автомат принимающего состояния и достигает ли он принимающего состояния бесконечно часто. Первая задача возникает при анализе моделей обобщённого недетерминизма, а вторая – при анализе разрешимости монадических теорий второго порядка. Получены новые условия разрешимости для этих задач. Доказано, что всякая задача ...
Added: October 17, 2014
Исследование задачи регулярной реализуемости для контекстно-свободных языков.
Rubtsov A. A., В кн.: Проблемы теоретической кибернетики. Материалы XVII международной конференции.: Каз.: Отечество, 2014. С. 246–248.
В работе исследуется задача регулярной реализуемости: алгоритмическая задача проверки непустоты пересечения регулярного языка на входе и фиксированного языка-фильтра, который является параметром задачи, — в случае контекстно-свободного фильтра. ...
Added: October 17, 2014
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit