IMDEA Software

Iniciativa IMDEA

Inicio > Eventos > Software Seminar Series > 2015 > Oscillation Bounded Behaviors for Pushdown Automata
Esta página aún no ha sido traducida. A continuación se muestra la página en inglés.

Damir Valput

martes 15 de diciembre de 2015

11:00am Meeting room 302 (Mountain View), level 3

Damir Valput, PhD Student, IMDEA Software Institute

Oscillation Bounded Behaviors for Pushdown Automata

Abstract:

I will present a measure, called oscillation, for behaviors of pushdown automata which are finite state automata with auxiliary stack storage. The key idea is to map behaviors onto well-parenthesized words. I then partition the class of well-parenthesized words following the nesting structure of well-parenthesized subwords. Given that pushdown automata and context-free grammars recognize context-free languages we can compare oscillation with known measures for parse trees of a context-free grammar. I establish that the notion of dimension for parse trees and the oscillation of runs are in linear relationship.