IMDEA Software

Iniciativa IMDEA

Inicio > Eventos > Software Seminar Series > 2018 > Weighted Context-free Grammars: Does Parikh's Theorem still hold?
Esta página aún no ha sido traducida. A continuación se muestra la página en inglés.

Elena Gutierrez

martes 3 de abril de 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?