• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Books
  • Заметки и задачи о регулярных языках и конечных автоматах
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 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
  • More
Subject
News
September 25, 2026
AI Users Earn Up to 41.8% More Than Non-Users
Research conducted by economists at HSE University has revealed a significant correlation between the regular use of GenAI in the workplace and higher pay among Russian employees. The study found that individuals who frequently use GenAI in their professional activities earn notably more than those who reject these new tools or resort to them occasionally. The salary premium for highly qualified specialists reaches 41.8%. The article was published in the Voprosy Ekonomiki journal.
September 24, 2026
‘Feedback and Constructive Criticism Are Essential in Our Profession
Vincent Fardeau, Associate Professor at HSE ICEF, has reached a major career milestone: he recently published his paper ‘Asymmetric Thin Markets’ in the Journal of Financial Economics, successfully passed his major academic review, and received tenure. In this interview, Vincent discusses the story behind the paper, explains the concept of asymmetric thin markets, and shares his advice for young scholars aiming to publish in top-tier journals.
September 22, 2026
Personal Interest in Doctoral Thesis Topic Most Important for Confidence in Successful Defence
A researcher at HSE University analysed data on 1,539 doctoral students from 161 Russian universities to identify which features of a thesis topic are associated with academic success and engagement. The most important factor was found to be personal interest in the research topic, which was associated with almost all key aspects of doctoral programme experience—from engaging with the academic supervisor to research activity and confidence about successfully defending the thesis. The findings have been published in Higher Education.

 

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

?

Заметки и задачи о регулярных языках и конечных автоматах

M. : МФТИ, 2019.
Rubtsov A. A.
Priority areas: IT and mathematics
Language: Russian
Full text
Keywords: конечные автоматыформальные языки
Заметки и задачи о регулярных языках и конечных автоматах
Similar publications
On calibration of remote sensing retrievals of ecosystem respiration (Reco) with tower measurements over,Russian forests and wetlands
Shabanov N., Kuricheva O., Kurbatova J. et al., / Series Working Papers SSRN "Department of Economics Ca’ Foscari University of Venice". 2026.
The carbon balance of an ecosystem is the difference between Gross Primary Productivity (GPP) and Ecosystem Respiration (Reco) as expressed by Net Ecosystem Exchange (NEE). While remote sensing retrievals of GPP have reached maturity, Reco estimation remains underexplored and ultimately cast bias on NEE. Here we present an end-to-end multi-scale analysis of the mechanism of ...
Added: August 21, 2026
Three Algorithms for Merging Hierarchical Navigable Small World Graphs
Ponomarenko A., / Series Computer Science "arxiv.org". 2025.
This paper addresses the challenge of merging hierarchical navigable small world (HNSW) graphs, a critical operation for distributed systems, incremental indexing, and database compaction. We propose three algorithms for this task: Naive Graph Merge (NGM), Intra Graph Traversal Merge (IGTM), and Cross Graph Traversal Merge (CGTM). These algorithms differ in their approach to vertex selection ...
Added: July 30, 2026
Growth in noncommutative algebras and entropy in derived categories
Piontkovski D., / Series arXiv "math". 2026.
A noncommutative projective variety is defined, following Artin and Zhang, by a graded coherent algebra 𝐴. The category of coherent sheaves is then the quotient qgr(𝐴) of the category of finitely presented graded modules by the subcategory of torsion modules. We consider the categorical and polynomial entropies of the Serre twist, that is, of the ...
Added: June 23, 2026
Multilinear nilalgebras and the Jacobian theorem
Piontkovski D., / Series arXiv "math". 2025.
If a symmetric multilinear algebra is weakly nil, then it is Engel. This result may be regarded as an infinite-dimensional analogue of the well-known Jacobian theorem, which states that if a polynomial mapping has a polynomial inverse, then its Jacobian matrix is invertible. This refines a theorem of Gerstenhaber and partially answers a question posed ...
Added: June 23, 2026
ML-based Fast Simulation of FARICH Responses
Shipilov F., Barnyakov A., Ivanov A. et al., / Series Physics "arxiv.org". 2026.
A fast simulation of the detector response is a vital task in high-energy physics (HEP). Traditional Monte-Carlo methods form the backbone of modern particle physics simulation software but are computationally expensive. We present a machine-learning-based approach to fast simulation of the Focusing Aerogel Ring Imaging Cherenkov (FARICH) detector response. Given a particle track and momentum, ...
Added: May 19, 2026
Natural hazard database from Internet publications: text mining with a large language model
Derkacheva A., Sakirkina M., Kraev G. et al., /. 2026.
Comprehensive data on natural hazards and their consequences are crucial for effective for risk assessment, adaptation planning, and emergency response. However, many countries face challenges with fragmented, inconsistent, and inaccessible data, particularly regarding local-scale events. To address this data gap in Russia, we developed an end-to-end processing pipeline that scrapes news from various online sources, ...
Added: April 28, 2026
Algorithmic overlaps as thermodynamic variables: from local to cluster Monte Carlo dynamics in critical phenomena
Pilé I., Deng Y., Shchur L., / Series arXiv "math". 2026. No. 2604.10254.
We investigate the spatial overlap of successive spin configurations in Markov chain Monte Carlo simulations using the local Metropolis algorithm and the Svendsen-Wang and Wolff cluster algorithms. We examine the dynamics of these algorithms for two models in different universality classes: the Ising model and the Potts model with three components. The overlap of two ...
Added: April 20, 2026
Using predefined vector systems to speed up neural network multimillion class classification
Gabdullin N., Androsov I., / Series Computer Science "arxiv.org". 2026.
Label prediction in neural networks (NNs) has O(n) complexity proportional to the number of classes. This holds true for classification using fully connected layers and cosine similarity with some set of class prototypes. In this paper we show that if NN latent space (LS) geometry is known and possesses specific properties, label prediction complexity can ...
Added: April 2, 2026
Iterative Ricci-Foster Curvature Flow with GMM-Based Edge Pruning: A Novel Approach to Community Detection
Sorokin K., Beketov M., Онучин А. et al., / arxiv.org. Серия cs.SI "Social and Information Networks ". 2025.
Community detection in complex networks is a fundamental problem, open to new approaches in various scientific settings. We introduce a novel community detection method, based on Ricci flow on graphs. Our technique iteratively updates edge weights (their metric lengths) according to their (combinatorial) Foster version of Ricci curvature computed from effective resistance distance between the ...
Added: January 15, 2026
Implementing Transport Coding in OMNeT++ for Message Delay Reduction
Petrovanov I., Sergeev A., / Series Computer Science "arxiv.org". 2025. No. 2512.18332.
Transport coding reduces message delay in packet-switched networks by introducing controlled redundancy at the transport layer:  original packets are encoded into  coded packets, and the message is reconstructed after the first  successful deliveries, effectively shifting latency from the maximum packet delay to the -th order statistic. We present a concise, reproducible discrete-event implementation of transport coding in OMNeT++, including ...
Added: December 24, 2025
Hessian-based lightweight neural network for brain vessel segmentation on a minimal training dataset
Меньшиков И. А., Бернадотт А. К., Elvimov N. S., / Series arXie "Statistical mechanics". 2025.
Accurate segmentation of blood vessels in brain magnetic resonance angiography (MRA) is essential for successful surgical procedures, such as aneurysm repair or bypass surgery. Currently, annotation is primarily performed through manual segmentation or classical methods, such as the Frangi filter, which often lack sufficient accuracy. Neural networks have emerged as powerful tools for medical image ...
Added: December 1, 2025
Вопросы определимости
Semenov A., В кн.: Всемирный конгресс (26–30 июня 2023 г., Москва). Теория систем, алгебраическая биология, искусственный интеллект: математические основы и приложения: Избранные труды.: М.: [б.и.], 2023. С. 390–405.
Added: March 13, 2024
Безопасные информационные технологии. Сборник трудов XII международной научно-технической конференции "Безопасные информационные технологии"
М.: Московский государственный технический университет им. Н.Э. Баумана, 2023.
Сборник содержит тезисы докладов, представленных на международной научно-технической конференции "Безопасные информационные технологии" (БИТ-2023), проходившей 1-2 ноября 2023 г. в Москве в МГТУ им. Н.Э.Баумана. Тезисы публикуются в редакции научных руководителей или в авторской редакции при наличии ученой степени. ...
Added: February 16, 2024
ЗАДАЧНИК ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
Дехтярь М. И., Dudakov S., Карлов Б. Н., Тверь: Тверской государственный университет, 2021.
Учебное пособие адресовано изучающим курс дискретной математики, прежде всего, студентам младших курсов, обучающимся по направлениям укрупненных групп 01.03.00 "Математика и механика", 02.03.00 "Компьютерные и информационные науки", 09.03.00 "Информатика и вычислительная техника". Настоящий сборник задач является пособием для практических занятий по некоторым разделам дискретной математики и может быть использован преподавателями и студентами для подготовки к семинарским  занятиям и ...
Added: November 12, 2023
Мещеряков М.В. Сухарев Л.А. Практикум по теории конечных автоматов и формальных языков- Саранск : Изд-во Мордов. ун-та, 2018.-224с.
Мещеряков М. В., Сухарев Л. А., Саранск: Изд-во Мордовского университета, 2018.
The book is an introductory course on the theory of formal languages and finite automata. It presents the main material of diciplina related to the mathematical foundations of a number of syntactic methods of inormatics and programming. The book is intended for undergraduate students in the following fields of study: fundamental computer science and information ...
Added: October 12, 2023
On Interpretations in Büchi Arithmetics
Zapryagaev A., / Series arXiv "math". 2022.
Büchi arithmetics BA_n, n >= 2, are extensions of Presburger arithmetic with an unary functional symbol V_n(x) denoting the largest power of n that divides x. Definability of a set in BA_n is equivalent to its recognizability by a finite automaton receiving numbers in their n-ary expansion. We show that Büchi arithmetics BA_n and BA_m ...
Added: December 5, 2022
Математическое моделирование дискреционной политики разграничения доступа
Синцова К. А., Журнал "Inside", Россия, Санкт-Петербург 2021 № 5 С. 52–60
The work solves the problem of constructing and proving a mathematical model of an information security tool with a discretionary type of access. The author tried to structure the previously accumulated knowledge in the field of information security, as well as supplement it with mathematical calculations, which helped to make the construction and proof of the model more ...
Added: December 3, 2021
Об одной модели безопасного функционирования компьютерных систем
Galatenko A. V., Кузовихина В. А., Программная инженерия 2021 № 3 С. 150–156
We propose an automata model of computer system security. A system is represented by a finite automaton with states partitioned into two subsets: "secure" and "insecure". System functioning is secure if the number of consecutive insecure states is not greater than some nonnegative integer k. This definition allows one to formally reflect responsiveness to security ...
Added: June 16, 2021
Расшифровка сигналов с помощью конечных автоматов: применение к играм с неполной информацией
Kreps V. L., Gavrilovich M., Математическая теория игр и ее приложения 2019 Т. 11 № 1 С. 21–38
Matrix games with incomplete information on both sides and public signal on the state of game represented by random binary code of fixed length are considered. Players are computationally bounded and are only able to play strategies to finite automata of different sizes: m for Player 1 and n for Player 2 where m ≫ ...
Added: May 31, 2019
Исследование задачи регулярной реализуемости
Rubtsov A. A., На правах рукописи, 2016.
В диссертации исследуется задача регулярной реализуемости, которая состоит в проверке пересечения фиксированного языка (параметра задачи) с регулярным языком на входе задачи. Основная часть работа посвящена исследованию вычислительной сложности задачи для КС-фильтров. ...
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
Constructing Regular Expressions from Real-life Event Logs
Tarantsova P. D., Kalenkova A. A., , in: Analysis of Images, Social Networks and Texts. 7th International Conference AIST 2018.: Springer, 2018. P. 274–280.
Process mining is a new discipline aimed at constructing process models from event logs. Recently several methods for the discovery of transition systems from event logs were introduced. Considering these transition systems as finite state machines classical algorithms for deriving regular expressions can be applied. Regular expressions allow representing sequential process models in a hierarchical way, using sequence, choice, and iterative ...
Added: October 15, 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
  • 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