• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Books
  • Descriptional Complexity of Formal Systems
  • 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
October 7, 2026
‘Our Team Consists of True Leaders in Their Respective Academic Disciplines
The HSE International Centre of Decision Choice and Analysis studies a wide range of methods for analysing decision-making and possible scenarios for the development of natural, socio-economic, and political phenomena using various mathematical models. The application of advanced mathematical methods to forecasting helps to prevent negative outcomes and avoid erroneous decisions. The HSE News Service spoke to the centre’s director, Prof. Fuad Aleskerov, about its work.
October 6, 2026
International N5 Symposium ‘Neural Networks and Nonlinearity in Nizhny Novgorod Brings Together Scientists from Russia and Serbia
The International N5 Symposium ‘Neural Networks and Nonlinearity in Nizhny Novgorod’ was held at the Nizhny Novgorod House of Scientists from September 23 to 26. The event was organised by HSE University–Nizhny Novgorod and the Nizhny Novgorod House of Scientists, with the participation of Sberbank and the Institute of Physics Belgrade. The symposium was held for the second time: the first conference took place in 2025 and attracted considerable interest from the academic community.
October 5, 2026
‘The Climate Transition Is Not Necessarily a Limitation for Business
Linara Khadimullina works in the field of low-carbon development. In an interview with the Young Scientists of HSE project, she spoke about why nature is not just a beautiful backdrop, her research on the role of sustainable corporate governance in reducing greenhouse gas emissions, and growing plants as a source of inspiration.

 

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

?

Descriptional Complexity of Formal Systems

Vol. 9118. Switzerland : Springer, 2015.
Under the general editorship: J. Shallit, A. Okhotin
Chapters
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
Language: English
DOI
Text on another site
Keywords: automata theoryDescriptional ComplexityFormal languages
Descriptional Complexity of Formal Systems
Similar publications
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.
We present a computational model for Parsing Expression Grammars (PEGs). The predecessor of PEGs top-down parsing languages (TDPLs) were discovered by A. Birman and J. Ullman in the 1960-s, B. Ford showed in 2004 that both formalisms recognize the same class named Parsing Expression Languages (PELs). A. Birman and J. Ullman established such important properties ...
Added: November 24, 2024
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
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
Материалы 5-й Российской школы-семинара "Синтаксис и семантика логических систем"
Улан-Удэ: Издательство Бурятского госуниверситета, 2017.
The collection represents proceedings of the 5th school-seminar "Syntax and Semantics of Logic Systems" (Ulan-Ude, 08.08.2017 - 12.08.2017). The conference subject area includes: theory of models and universal algebra; theory of boolean and finite-valued functions; formal languages and logic calculus; mathematical logic in education. ...
Added: September 22, 2017
When are description logic knowledge bases indistinguishable?
Botoeva E., Zakharyaschev M., Kontchakov R. et al., , in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015.: Palo Alto: AAAI Press, 2015. P. 4240–4246.
Deciding inseparability of description logic knowledge bases (KBs) with respect to conjunctive queries is fundamental for many KB engineering and maintenance tasks including versioning, module extraction, knowledge exchange and forgetting. We study the combined and data complexity of this inseparability problem for fragments of Horn-ALCHI, including the description logics underpinning OWL 2 QL and OWL ...
Added: September 18, 2017
Tractable interval temporal propositional and description logics
Zakharyaschev M., Artale A., Kontchakov R. et al., , in: Proceedings of the National Conference on Artificial Intelligence.: American Association for Artificial Intelligence (AAAI) Press, 2015. P. 1417–1423.
We design a tractable Horn fragment of the Halpern-Shoham temporal logic and extend it to interval-based temporal description logics, instance checking in which is P-complete for both combined and data complexity. ...
Added: September 18, 2017
Proceedings of the National Conference on Artificial Intelligence
American Association for Artificial Intelligence (AAAI) Press, 2015.
Added: September 18, 2017
Conservative rewritability of description logic TBoxes
Konev B. Y., Lutz C., Wolter F. et al., , in: 25th International Joint Conference on Artificial Intelligence.: [б.и.], 2016. P. 1153–1159.
We investigate the problem of conservative rewritability of a TBox T in a description logic (DL) L into a TBox T' in a weaker DL L'. We focus on model-conservative rewritability (T' entails T and all models of T are expandable to models of T'), subsumption-conservative rewritability (T' entails T and all subsumptions in the ...
Added: September 18, 2017
25th International Joint Conference on Artificial Intelligence
[б.и.], 2016.
Added: September 18, 2017
Theoretically optimal datalog rewritings for OWL 2 QL ontology-mediated queries
Bienvenu M., Kikot S., Kontchakov R. et al., , in: International Workshop on Description Logics, DL 2016Issue 1577.: [б.и.], 2016. P. 1–13.
We show that, for OWL 2 QL ontology-mediated queries with (i) ontologies of bounded depth and conjunctive queries of bounded treewidth, (ii) ontologies of bounded depth and bounded-leaf tree-shaped conjunctive queries, and (iii) arbitrary ontologies and bounded-leaf tree-shaped conjunctive queries, one can construct and evaluate nonrecursive datalog rewritings by, respectively, LOGCFL, NL and LOGCFL algorithms, ...
Added: September 18, 2017
Inseparability and conservative extensions of description logic ontologies: A survey
Zakharyaschev M., Botoeva E., Konev B. Y. et al., , in: 12th International Summer School on Reasoning Web Summer School, RW 2016Issue 9885.: [б.и.], 2017. P. 27–89.
The question whether an ontology can safely be replaced by another, possibly simpler, one is fundamental for many ontology engineering and maintenance tasks. It underpins, for example, ontology versioning, ontology modularization, forgetting, and knowledge exchange. What ‘safe replacement’ means depends on the intended application of the ontology. If, for example, it is used to query ...
Added: September 18, 2017
  • 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