IMDEA Software

IMDEA initiative

Home > Events > Software Seminar Series > 2015 > Oscillation Bounded Behaviors for Pushdown Automata

Damir Valput

Tuesday, December 15, 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.