### ?

## A Structural Lemma for Deterministic Context-Free Languages

P. 553-565.

Rubtsov A. A.

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), presented by Li and Vit ́anyi in 1995 and corrected by Glier in 2003. The structural lemma allows not only to prove that a language is not a DCFL, but discloses the structure of DCFLs Myhill-Nerode classes.

Keywords: колмогоровская сложностьKolmogorov complexityтеория автоматовautomata theoryформальные языкиformal languages

Publication based on the results of:

Rubtsov A. A., Vyalyi M., , in : Descriptional Complexity of Formal Systems. Vol. 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

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

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, Proceedings. Vol. 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., На правах рукописи, 2016

В диссертации исследуется задача регулярной реализуемости, которая состоит в проверке пересечения фиксированного языка (параметра задачи) с регулярным языком на входе задачи. Основная часть работа посвящена исследованию вычислительной сложности задачи для КС-фильтров. ...

Added: November 1, 2018

Rubtsov A. A., , in : Proceedings of Language and Automata Theory and Applications 2020. : Springer, 2020.

Formal grammars provide the way of formal language's description. The other way is describing a language by automata model. But not all classes of formal languages fit in the both ways of description. We provide a new way of formal language's description which is universal and combine the advantages of the both mentioned methods — a ...

Added: October 19, 2017

Avdoshin S. M., Набебин А. А., М. : ДМК Пресс, 2018

The textbook contains the basic information of formal logical systems. It is Boolean functions, Post’s theorem on functional completeness, the k-valued logic, derivatives of Boolean functions, axiomatic calculi for propositions, for predicates, for sequentions, for resolutions. Programming language Prolog and axiomatic programming language OBJ3 are introduced. Problems of monadic logic, of finite automata and of ...

Added: December 2, 2017

Rubtsov A. A., В кн. : Сборник научных трудов МФТИ "Модели и методы обработки информации". : Долгопрудный : МФТИ, 2016. С. 67-74.

В работе исследуются комбинаторные свойства детерминированных контекстно-свободных языков. Получена новая комбинаторная лемма, схожая по типу с леммами о накачке для КС-языков, а также получены комбинаторные свойства, следующие из модифицированной известной техники, опирающейся на Колмогоровскую сложность. ...

Added: October 20, 2018

Switzerland : Springer International Publishing, 2021

Added: September 28, 2021

Vereshchagin N., Theoretical Computer Science 2020 Vol. 809 P. 531-537

The purpose of this paper is to answer two questions left open in [B. Durand, A. Shen, and N. Vereshchagin, Descriptive Complexity of Computable Sequences, Theoretical Computer Science 171 (2001), pp. 47--58]. Namely, we consider the following two complexities of an infinite computable 0-1-sequence $\alpha$: $C^{0'}(\alpha )$, defined as ...

Added: January 17, 2020

Milovanov A., , in : Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015. Vol. 9139.: Springer, 2015. P. 339-349.

Antistochastic strings are those strings that do not have any reasonable statistical explanation. We establish the follow property of such strings: every antistochastic string x is “holographic” in the sense that it can be restored by a short program from any of its part whose length equals the Kolmogorov complexity of x. Further we will ...

Added: June 27, 2016

Milovanov A., Theory of Computing Systems 2017 Vol. 61 No. 2 P. 521-535

Algorithmic statistics is a part of algorithmic information theory (Kolmogorov complexity theory) that studies the following task: given a finite object x (say, a binary string), find an `explanation' for it, i.e., a simple finite set that contains x and where x is a `typical element'. Both notions (`simple' and `typical') are defined in terms ...

Added: June 27, 2016

Bienvenu L., Muchnik A., Shen A. et al., Limit complexities revisited [once more] / Cornell University. Series math "arxiv.org". 2012. No. 1204.0201.

The main goal of this article is to put some known results in a common perspective and to simplify their proofs. We start with a simple proof of a result of Vereshchagin saying that lim supnC(x|n) equals C0′(x). Then we use the same argument to prove similar results for prefix complexity, a priori probability on binary ...

Added: December 14, 2013

Bauwens B. F., Blinnikov I., , in : Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings. Vol. 12159.: Springer, 2020. P. 130-141.

It is known that the normalized algorithmic information distance is not computable and not semicomputable. We show that for all 𝜀<1/2, there exist no semicomputable functions that differ from N by at most 𝜀. Moreover, for any computable function f such that |lim𝑡𝑓(𝑥,𝑦,𝑡)−N(𝑥,𝑦)|≤𝜀 and for all n, there exist strings x, y of length n such that ...

Added: February 5, 2021

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, 2020. Vol. 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

Rubtsov A. A., В кн. : Труды 57-й научной конференции МФТИ — Всероссийской научной конференции с международным участием «Актуальные проблемы фундаментальных и прикладных наук в области физики», Всероссийской молодежной научной конференции с международным участием «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе». Т. 1: Управление и прикладная математика.: М. : МФТИ, 2014. С. 123-125.

В работе приведены примеры различных языков, распознаваемых автоматами со словарём и исследована их вычислительная сложность. ...

Added: August 25, 2015

Shen A., Vereshchagin N., , in : Computability and Complexity. : Berlin : Springer, 2017. P. 669-737.

Algorithmic statistics has two different (and almost orthogonal) motivations. From the philosophical point of view, it tries to formalize how the statistics works and why some statistical models are better than others. After this notion of a "good model" is introduced, a natural question arises: it is possible that for some piece of data there ...

Added: October 26, 2018

Rubtsov A. A., В кн. : Труды 56-й научной конференции МФТИ: Всероссийской научной конференции «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе» , Всероссийской молодежной научно-инновационной конференции «Физико-математические науки: актуальные проблемы и их решения». Т. 1: Управление и прикладная математика.: Долгопрудный : МФТИ, 2013. С. 128-130.

В работе исследована инвариантная характеристика автоматных преобразований (преобразований, заданных deterministic finite state transducer ) — функция высоты. ...

Added: October 17, 2014

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

Milovanov A., , in : 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) Leibniz International Proceedings in Informatics (LIPIcs). : Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2016. Ch. 54. P. 1-13.

Algorithmic statistics considers the following problem: given a binary string
x
(e.g., some
experimental data), find a “good” explanation of this data. It uses algorithmic information
theory to define formally what is a good explanation. In this paper we extend this framework in
two directions.
First, the explanations are not only interesting in themselves but also used for prediction: we
want to ...

Added: June 27, 2016

Milovanov A., , in : Computer Science – Theory and Applications: 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28–July 2, 2021, Proceedings. : Springer, 2021. Ch. 17. P. 283-295.

We combine Solomonoff’s approach to universal prediction with algorithmic statistics and suggest to use the computable measure that provides the best “explanation” for the observed data (in the sense of algorithmic statistics) for prediction. In this way we keep the expected sum of squares of prediction errors bounded (as it was for the Solomonoff’s predictor) ...

Added: August 11, 2021

Shen A., Uspensky V. A., Vereshchagin N., American Mathematical Society, 2017

Added: October 12, 2017

Bauwens B. F., Shen A., Journal of Symbolic Logic 2013 Vol. 79 No. 2 P. 620-632

Added: October 2, 2015

Milovanov A., , in : Computer Science – Theory and Applications: 12th International Computer Science Symposium in Russia (CSR 2017). Vol. 10304.: Luxemburg : Springer, 2017. P. 232-244.

Algorithmic statistics studies explanations of observed data that are good in the algorithmic sense: an explanation should be simple i.e. should have small Kolmogorov complexity and capture all the algorithmically discoverable regularities in the data. However this idea can not be used in practice because Kolmogorov complexity is not computable.
In this paper we develop algorithmic ...

Added: October 15, 2017