Oscillation Bounded Behaviors for Pushdown Automata

December 15, 2015

Damir Valput


Oscillation Bounded Behaviors for Pushdown Automata

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

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.