Subject: PEM talk by Claus Brabrand on Wednesday, August 19 - 'Analyzing
Ambiguity of Context-Free Grammars'
From: "H.J.S. Basten" 
To: pem-list
Date: Mon, 17 Aug 2009 13:36:23 +0200

Dear all,

You are hereby cordially invited for the next PEM talk by Claus
Brabrand, titled 'Analyzing Ambiguity of Context-Free Grammars'. Claus
is visiting us this week from the IT University of Copenhagen, Denmark.

Abstract:

It has been known since 1962 that the ambiguity
problem for context-free grammars is undecidable.
Ambiguity in context-free grammars is a recurring
problem in language design and parser generation,
as well as in applications where grammars are used
as models of real-world physical structures.

We observe that there is a simple linguistic
characterization of the grammar ambiguity problem,
and we show how to exploit this to conservatively
approximate the problem based on local regular
approximations and grammar unfoldings.

As an application, we consider grammars that occur
in RNA analysis in bioinformatics, and we
demonstrate that our static analysis of context-
free grammars is sufficiently precise and
efficient to be practically useful.


Date: Wednesday 19 August 2009, 10am
Location: Room L302 (in the new building), CWI Amsterdam.

** Due to renovations the CWI building has to be entered through the
Nikhef building, located at Science Park 105.


We hope to see you all on Thursday!

Kind regards,

Bas Basten