2026-08-21T18:34:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27385 2026-08-21T14:42:37Z ddc:004 open_access

The Art of Balance: Many Facets of Dyck Recognition (Invited Talk) Starikovskaya, Tatiana Formal language recognition Dyck languages Boolean matrix multiplication pattern matching graph algorithms The Dyck language, consisting of well-balanced parenthesis sequences, is one of the central objects in formal language theory. The Dyck languages appear naturally in numerous applications: balanced-parenthesis encodings succinctly represent rooted trees, programming languages rely heavily on nested structures, and structured data formats such as XML often utilize a notion of balanced parenthesis sequences. Dyck languages also arise in computational biology. RNA and DNA secondary structures can often be viewed as "almost balanced" sequences, so understanding the behaviour of the Dyck languages is often an important building block for designing algorithms on such sequences. In this talk, I will survey several recent developments in Dyck language recognition, highlighting surprising connections to different areas of TCS, including regular language recognition, Boolean matrix multiplication, pattern matching, and graph algorithms. I will also discuss some of the major open questions in the area. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tatiana Starikovskaya 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.4 urn:nbn:de:0030-drops-273852 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.4 eng https://creativecommons.org/licenses/by/4.0/legalcode