• 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
July 24, 2026
‘I Like Self-Fulfilling Prophecies
Andrey Vorchik studies happiness, delivers popular science lectures, and believes that science should address social issues as well. In an interview for the Young Scientists of HSE University project, he spoke about how emotions influence decision-making, the Bermuda Triangle formed by the bathroom, refrigerator, and bed, and the ideal formula for education.
July 24, 2026
'Physics Is What the World Is Literally Built On'
Physicist Nina Dzhanayeva, recipient of a Vladimir Potanin Foundation scholarship, focuses her research on nanophotonics. In this interview for the HSE Young Scientists project, she discusses nanowells, scientific intuition, and how physics can help in making frangipane cream puffs.
July 20, 2026
Scientists Create Open Dataset for Studying Concentration
A team of Russian researchers, including scientists from HSE University–St Petersburg, has developed the first open multimodal dataset containing recordings of brain activity, heart function, and video observations to help researchers understand what happens in the human brain during deep concentration. In the future, the dataset could accelerate the development of neural interfaces, rehabilitation technologies, and AI systems. The article has been published in Scientific Data.

 

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

?

Переходные явления в неразложимых стохастических КС-грамматиках

С. 74–75.
Durandin O., Жильцова Л. П.
Language: Russian
Text on another site
Keywords: формальные грамматикипереходные вероятностиautomata theoryФормальные языки и грамматикиformal grammar

In book

Дискретные модели в теории управляющих систем : IX Международная конференция, Москва и Подмосковье, 20-22 мая 2015 г.: Труды
М.: МАКС Пресс, 2015.
Similar publications
Automata Under Effective Observation
Babash A. V., , 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 ...
Added: November 2, 2021
Developments in Language Theory: 25th International Conference, DLT 2021, Porto, Portugal, August 16–20, 2021, Proceedings
Switzerland: Springer International Publishing, 2021.
Added: September 28, 2021
Re-pairing brackets
Chistikov D., Mikhail Vyalyi, , in: LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science. Saarbrücken, Germany. July, 2020.: Association for Computing Machinery (ACM), 2020. P. 312–326.
Added: September 4, 2020
Minimizing Deterministic Timed Finite State Machines
Bresolin D., Tvardovskii A., Nina Yevtushenko et al., , in: IFAC-PapersOnLine (T.V.51.Вып 7).: Elsevier, 2018. P. 486–492.
Timed automata and timed finite state machins (TFSMs) have been proposed to represent more accurately the behaviour of systems in continuous time. Recently, we introduced a model of TFSMs that extends the expressive power of FSMs by introducing a single clock, timed guards which restrict when the input/output transitions may happen, and timeouts on the ...
Added: November 1, 2018
Обобщение иерархии Хомского
Rubtsov A. A., В кн.: Труды X международной конференции "Дискретные модели в теории управляющих систем". Москва и Подмосковье, 23-25 мая 2018 г.: М.: МАКС Пресс, 2018. С. 234–237.
Иерархия Хомского — хорошо известная иерархия формальных языков, основанная на формальных грамматиках. Однако эта иерархия покрывает лишь четыре класса формальных языков: регулярные, контекстно-свободные, контекстно-зависимые и рекурсивно-перечислимые. В этой работе мы обобщаем понятие формальной грамматики. ...
Added: October 20, 2018
Комбинаторные леммы для детерминированных контекстно-свободных языков
Rubtsov A. A., В кн.: Сборник научных трудов МФТИ "Модели и методы обработки информации".: Долгопрудный: МФТИ, 2016. С. 67–74.
В работе исследуются комбинаторные свойства детерминированных контекстно-свободных языков. Получена новая комбинаторная лемма, схожая по типу с леммами о накачке для КС-языков, а также получены комбинаторные свойства, следующие из модифицированной известной техники, опирающейся на Колмогоровскую сложность. ...
Added: October 20, 2018
Алгоритмы синтаксического разбора для текстовых динамически настраиваемых предметно-ориентированных языков
Lyadova L. N., Sukhov A., Медведева Е. Ю., Информационные технологии 2018 Т. 24 № 10 С. 648–656
Over time an increasing number of software packages have provided users with domain-specific languages designed to customize the system in accordance with changing operating conditions and user needs. However, it is necessary to create language workbenches for such languages. The authors suggested an approach to developing toolkits for creating textual dynamically customizable domain-specific languages that ...
Added: October 17, 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
Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings
Cham: Springer, 2018.
This volume of Lecture Notes in Computer Science contains the papers presented at the 22nd International Conference on Developments in Language Theory (DLT 2018) organized by the Algorithmic “Oritatami” Self-Assembly Laboratory as part of the 100th Anniversary Commemorative Events of University of Electro-Communications (UEC) in Fuchu, Tokyo, Japan, during September 10–14, 2018. The DLT conference series is one ...
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
Annual Workshop on Formal Approaches to Slavic Linguistics: The Urbana-Champaign Meeting 2017
Michigan Slavic Publications, 2020.
Added: April 19, 2018
CEUR Workshop Proceedings. Vol-1975
CEUR-WS.org, 2017.
Added: January 26, 2018
Теоретические основы, используемые для построения инструментов анализа языков программирования на примере языка Perl
Вендин А. С., В кн.: Научные исследования: теория, методика и практика. Сборник материалов Международной научно-практической конференции. 2017.: Чебоксары: Общество с ограниченной ответственностью "Центр научного сотрудничества "Интерактив плюс", 2017. С. 281–283.
In this work are considered a theoretical basis, which can help approach the implementation of the tool for analyze the source code of the program in Perl. ...
Added: December 12, 2017
Теория и реализация языков программирования
Серебряков В. А., Гончар Д. Р., Rubtsov A. A. et al., МФТИ, 2017.
Содержит программу, список литературы и задачи одноимённого курса, читаемого студентам факультета управления и прикладной математики МФТИ (ГУ). Задачи могут быть использованы в качестве упражнений на семинарских занятиях, заданий, экзаменационного материала, а также при самостоятельном освоениии курса. ...
Added: October 20, 2017
On Computational Complexity of Set Automata
Rubtsov A. A., Vyalyi M., , in: Developments in Language Theory 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings.: Cham: Springer, 2017. P. 332–344.
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 M. Kutrib, A. Malcher, M. Wendlandt in ...
Added: September 5, 2017
Developments in Language Theory 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings
Cham: Springer, 2017.
The 21st International Conference on Developments in Language Theory (DLT 2017) was organized by the Department of Mathematics of the University of Liège, Belgium, during August 7–11, 2017. The DLT conference series is one of the major international conference series in language theory and related areas. The DLT conference was established by G. Rozenberg and A. ...
Added: September 5, 2017
О преобразовании контекстно-свободных грамматик в грамматики Ламбека
Kuznetsov S., Труды Математического института им. В.А. Стеклова РАН 2015 Т. 290 С. 72–79
Рассматриваются контекстно-свободные грамматики и грамматики Ламбека, обогащенные семантической разметкой. Такие грамматики не только отвечают на вопрос, принадлежит ли данное слово описываемому грамматикой формальному языку, но и, если ответ положителен, приписывают слову <img /> -терм, отвечающий семантическому значению (“смыслу”) слова. Представлена модификация предложенного В. Бушковским непосредственного преобразования контекстно-свободных грамматик в форме Хомского в грамматики Ламбека, сохраняющая ...
Added: October 23, 2016
О преобразовании грамматик Ламбека с одним делением в контекстно-свободные грамматики
Kuznetsov S., Труды Математического института им. В.А. Стеклова РАН 2016 Т. 294 С. 141–151
Описан способ построения по грамматике Ламбека с одним делением контекстно-свободной грамматики, задающей тот же язык, размер которой ограничен полиномом от размера исходной грамматики. Известные ранее конструкции Бушковского и Пентуса приводили к экспоненциальному росту размера грамматики. ...
Added: October 23, 2016
  • 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