27.06.2013 - Sean Buckheister (16:00!)

Time 16:00
Room 34-420


Parikh's theorem beyond pushdown automata


Parikh's theorem is a well-known result from formal language theory which proves that all context-free languages have commutative images of a specific form, where two words are indistinguishable in the commutative image if they differ only in symbol ordering. Valence automata are a modification of pushdown automata, where instead of a stack an arbitrary monoid may be used as storage. In this work, monoids defined by graphs are studied and characterized by whether or not an extension of Parikh's theorem holds for valence automata with such monoids as storage.

termine/ss13/1306272.txt · Last modified: 24.06.2013 16:46 by paddy