December 15, 2015
Damir Valput
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.