2026-07-20T11:27:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17433 2024-03-06T10:59:44Z ddc:004 open_access

New Analytic Techniques for Proving the Inherent Ambiguity of Context-Free Languages Koechlin, Florent Inherent ambiguity Infinite ambiguity Ambiguity Generating series Context-free languages Bounded languages This article extends the work of Flajolet [Philippe Flajolet, 1987] on the relation between generating series and inherent ambiguity. We first propose an analytic criterion to prove the infinite inherent ambiguity of some context-free languages, and apply it to give a purely combinatorial proof of the infinite ambiguity of Shamir’s language. Then we show how Ginsburg and Ullian’s criterion on unambiguous bounded languages translates into a useful criterion on generating series, which generalises and simplifies the proof of the recent criterion of Makarov [Vladislav Makarov, 2021]. We then propose a new criterion based on generating series to prove the inherent ambiguity of languages with interlacing patterns, like {a^nb^ma^pb^q | n≠p or m≠q, with n,m,p,q ∈ ℕ^*}. We illustrate the applicability of these two criteria on many examples. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florent Koechlin 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.41 urn:nbn:de:0030-drops-174331 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.41 eng https://creativecommons.org/licenses/by/4.0/legalcode