### ?

## Re-pairing brackets

P. 312-326.

Chistikov D., Mikhail Vyalyi

Keywords: combinatoricsautomata theory one-counter automataParikh imageDyck languagebalanced parentheses

Publication based on the results of:

### In book

Association for Computing Machinery (ACM), 2020

Olshanski G., / Cornell University. Series arXiv "math". 2017.

Let Sym denote the algebra of symmetric functions and Pμ(⋅;q,t) and Qμ(⋅;q,t) be the Macdonald symmetric functions (recall that they differ by scalar factors only). The (q,t)-Cauchy identity
∑μPμ(x1,x2,…;q,t)Qμ(y1,y2,…;q,t)=∏i,j=1∞(xiyjt;q)∞(xiyj;q)∞
expresses the fact that the Pμ(⋅;q,t)'s form an orthogonal basis in Sym with respect to a special scalar product ⟨⋅,⋅⟩q,t. The present paper deals with the inhomogeneous \emph{interpolation} ...

Added: December 26, 2017

Springer, 2020

This book constitutes the proceedings of the 15th International Computer Science Symposium in Russia, CSR 2020, held in Yekaterinburg, Russia, in June 2020.
The 25 full papers and 6 invited papers were carefully reviewed and selected from 49 submissions. The papers cover a broad range of topics, such as: algorithms and data structures; computational complexity, including ...

Added: September 4, 2020

МГУ, МАКС Пресс, 2018

The proceedings of the tenth international conference "Discrete Models in Control Systems Theory" (Moscow and Moscow Region, May 23-25, 2018) includes 100 papers on such topics as discrete functional systems, properties of discrete functions, synthesis and complexity of control systems, reliability, control and diagnostics of control systems, automata, graph theory, combinatorics, coding theory, mathematical methods ...

Added: June 14, 2018

Cham : Birkhäuser, 2021

Is published at every edition of EuroComb which is one of the leading conferences in the area worldwide
Presents the most recent achievements in this conference
Collects the extended abstracts of the accepted contributions to EuroComb21 ...

Added: September 8, 2021

Fesler R., / Cornell University. Series arXiv "math". 2023.

We are building a theory of simple Hurwitz numbers for the reflection groups B and D parallel to the classical theory for the symmetric group. We also study analogs of the cut-and-join operators. An algebraic description of Hurwitz numbers and an explicit formula for them in terms of Schur polynomials are provided. We also relate ...

Added: September 9, 2023

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

Bezrukavnikov R., Finkelberg M. V., / Cornell University. Series math "arxiv.org". 2012. No. 1208.3696.

Mark Haiman has reduced Macdonald positivity conjecture to a statement about geometry of the Hilbert scheme of points on the plane, and formulated a generalization of the conjectures where the symmetric group is replaced by the wreath product $S_n\ltimes (Z/r Z)^n$. He has proven the original conjecture by establishing the geometric statement about the Hilbert ...

Added: February 6, 2013

М. : МАКС Пресс, 2017

The collection represents proceedings of the XVIII international conference “Problems of Theoretical Cybernetics” (Penza, 19–23 June, 2017), that is sponsored by Russian Foundation for Basic Research (project N 17-01-20217-г). The conference subject area includes: control systems synthesis, complexity, reliability, and diagnostics; automata; computer languages and programming; graph theory; combinatorics; coding theory; theory of pattern recognition; ...

Added: August 25, 2017

Providence : AMS, 2023

This book is a translation from Russian of Part III of the book Mathematics via Problems: From Olympiads and Math Circles to Profession. Part I, Algebra, and Part II, Geometry, have been published in the same series.
The main goal of this book is to develop important parts of mathematics through problems. The authors tried to put together sequences ...

Added: March 3, 2024

Gurvich V., Boros E., Kazuhisa M. et al., Discrete Applied Mathematics (Нидерланды) 2018 Vol. 239 P. 1-14

Moore's generalization of the game of Nim is played as follows. Given two integer parameters $n, k$ such that $1 \leq k \leq n$, and $n$ piles of tokens. Two players take turns. By one move a player reduces at least one and at most $k$ piles. The player who makes the last move wins. ...

Added: October 26, 2017

Pham S. K., Antipov D., Sirotkin Alexander et al., Journal of Computational Biology 2013 Vol. 20 No. 4 P. 359-371

One of the key advances in genome assembly that has led to a significant improvement in contig lengths has been improved algorithms for utilization of paired reads (mate-pairs). While in most assemblers, mate-pair information is used in a post-processing step, the recently proposed Paired de Bruijn Graph (PDBG) approach incorporates the mate-pair information directly in ...

Added: March 21, 2014

Gamard G., Richomme G., Shallit J. et al., Information Processing Letters 2017 Vol. 118 P. 58-63

Added: October 10, 2017

Switzerland : Springer International Publishing, 2021

Added: September 28, 2021

Beisegel J., Chudnovsky M., Gurvich V. et al., , in : Algorithms and Data Structures. WADS 2019. Lecture Notes in Computer Science. Vol. 11646.: Springer, 2019. P. 126-139.

A vertex v in a graph G is said to be avoidable if every induced two-edge path with midpoint v is contained in an induced cycle. Generalizing Dirac’s theorem on the existence of simplicial vertices in chordal graphs, Ohtsuki et al. proved in 1976 that every graph has an avoidable vertex. In a different generalization, Chvátal et al. gave in 2002 a characterization of graphs ...

Added: October 26, 2021

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

Ignatov D. I., , in : FCA4AI 2023 What can FCA do for Artificial Intelligence 2023 Proceedings of the 11th International Workshop "What can FCA do for Artificial Intelligence?" co-located with the 32nd International Joint Conference on Artificial Intelligence (IJCAI 2023) Macao, S.A.R. China; August 20, 2023. Vol. 3489.: CEUR-WS.org, 2023. P. 47-56.

The paper aims at not only counting how many basic choice functions exist on a finite set of alternatives (all, non-empty, single-element valued) but shows how to do this with the help of Formal Concept Analysis. Moreover, we introduce the contextual representation of a choice function by considering the formal context of its map from ...

Added: November 23, 2023

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

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

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

Bogomolov F. A., Kulikov V. S., Central European Journal of Mathematics 2013 Vol. 11 No. 2 P. 254-263

The article contains a new proof that the Hilbert scheme of irreducible surfaces of degree m in ℙ m+1 is irreducible except m = 4. In the case m = 4 the Hilbert scheme consists of two irreducible components explicitly described in the article. The main idea of our approach is to use the proof ...

Added: November 21, 2012

Kryuchkova S. E., В кн. : Метафизика креативности. Вып. 5.: М. : Перо, 2011. С. 33-45.

В работе рассматривается основные идеи работы «Ars magna» испанского схоласта, логика и математика Р.Луллия, который на платоновско-герметической основе разрабатывал искусство выведения с логической необходимостью из исходных понятий любых истин. Подробно рассматривается методика автоматического комбинирования понятий, составляющих из себя начало всякого знания. Показано, что «логическая машина» Луллия представляет собой попытку построения глобального, всеобщего концептуального символического механизма, ...

Added: February 17, 2013

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

Burman Y. M., Fesler Raphaël, / Cornell University. Series math "arxiv.org". 2022.

Ribbon decomposition is a way to obtain a surface with boundary (compact, not necessarily oriented) from a collection of disks by joining them with narrow ribbons attached to segments of the boundary. Counting ribbon decompositions gives rise to a "twisted" version of the classical Hurwitz numbers (studied earlier in \cite{CD} in a different context) and ...

Added: October 20, 2022

Braverman A., Michael Finkelberg, / Cornell University. Series math "arxiv.org". 2014.

In this note, we extend the results of arxiv:1111.2266 and arxiv:1203.1583 to the non simply laced case. To this end we introduce and study the twisted zastava spaces. ...

Added: February 5, 2015