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

April 3, 2018

Elena Gutierrez


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

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

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?