I was introduced to the elegance of automata-theoretic constructions through Prof. Vardi's seminal work on automata over infinite words and infinite trees and their role in decision procedures for temporal logics. In this talk, I will describe ongoing work on developing a theory of regular languages over series-parallel graphs motivated by distributed data stream applications. These graphs, besides sequential composition, allow both ordered ranked parallelism and unordered unranked parallelism. The latter feature means that in the corresponding automata, the transition function needs to account for an arbitrary number of predecessors by counting each type of state only up to a specified constant, thus leading to a notion of counting complexity that is distinct from the classical notion of state complexity. The resulting theory turns out to be robust: we show that both deterministic and non-deterministic automata have the same expressive power, which can be equivalently characterized by Monadic Second-Order logic as well as the graded mu-calculus, and questions such as membership, emptiness, and equivalence are all decidable.