IMDEA Software

IMDEA initiative

Home > Events > Software Seminar Series > 2018 > Weighted Context-free Grammars: Does Parikh's Theorem still hold?

Elena Gutierrez

Tuesday, April 3, 2018

10:45am Meeting room 202 (Hill View), level 2

Elena Gutierrez, PhD Student, IMDEA Software Institute

Weighted Context-free Grammars: Does Parikh's Theorem still hold?

Abstract:

The celebrated Parikh’s Theorem states that every context-free language is equivalent to a regular language when we ignore the ordering of symbols in the words. In this work I study under which conditions we can extend this result to the more general scenario where grammar rules are augmented with a weight and thus, each word in the language carries the weight it “costs” to generate it. An extension of the result to the weighted setting has the potential to enable a richer analysis of certain systems. For instance, one can reason about event-driven programs with asynchronous methods where each event has an associated energy cost and answer questions such as, what is the minimal energy budget to serve a given sequence of events?