2026-07-25T00:03:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25081 2026-02-09T08:05:58Z ddc:004 open_access

Unboundedness Problems for Formal Languages (Invited Talk) Zetzsche, Georg Decidability formal languages unifying frameworks downward closure separability Informally, unboundedness problems are decision problems that ask about the existence of infinitely many words (satisfying certain properties) in a formal language. For example: Is a given language infinite? Or: Does a given language have super-polynomial growth? These came into focus in recent years because of their connections to downward closure computation and separability problems. Although unboundedness problems may seem difficult at first, it turns out that there are techniques that are at the same time conceptually very simple, but also apply to a surprisingly wide variety of language classes. The talk will survey recent results (and techniques) concerning unboundedness problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Georg Zetzsche 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.2 urn:nbn:de:0030-drops-250810 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.2 eng https://creativecommons.org/licenses/by/4.0/legalcode