Two criteria to prove the inherent ambiguity of bounded context-free languages

Prelegent(ci)

Florent Koechlin

Afiliacja

LORIA

Termin

1 marca 2023 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

A context-free language is inherently ambiguous if any grammar recognizing it is ambiguous, i.e. there is a word that is generated in two different ways. Deciding the inherent ambiguity of a context-free language is a difficult problem, undecidable in general. The first examples of inherently ambiguous languages were discovered in the 1960s, using iteration techniques on derivation trees. They belonged to a particular subfamily of context-free languages, called bounded context-free languages.

Although they made it possible to prove the inherent ambiguity of several languages, as for example the language L = a^n b^m c^p with n=m or m=p, iteration techniques are still very laborious to implement, are very specific to the studied language, and seem even sometimes unadapted. For instance, the relative simplicity of the proof of inherent ambiguity of L completely collapses by replacing the constraint "n=m or m=p" by "n≠m or m≠p".

In this talk, I will present two useful criteria based on generating series to prove easily the inherent ambiguity of many bounded context-free languages, extending on a recent criterion developed by Makarov in 2021. These languages, which have a rational generating series, resisted both the classical iteration techniques developed in the 1960’s and the analytic methods introduced by Philippe Flajolet in 1987.

---