April 3, 2018
Elena Gutierrez
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?