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.