Recently, weighted ??-pushdown automata have been introduced by Droste, ??sik, Kuich. This new type of automaton has access to a stack and models quantitative aspects of infinite words. Here, we consider a simple version of those automata. The simple ??-pushdown automata do not use ?μ-transitions and have a very restricted stack access. In previous work, we could show this automaton model to be expressively equivalent to context-free ??-languages in the unweighted case. Furthermore, semiring-weighted simple ??-pushdown automata recognize all ??-algebraic series. Here, we consider ??-valuation monoids as weight structures. As a first result, we prove that for this weight structure and for simple ??-pushdown automata, B??chi-acceptance and Muller-acceptance are expressively equivalent. In our second result, we derive a Nivat theorem for these automata stating that the behaviors of weighted ??-pushdown automata are precisely the projections of very simple ??-series restricted to ??-context-free languages. The third result is a weighted logic with the same expressive power as the new automaton model. To prove the equivalence, we use a similar result for weighted nested ??-word automata and apply our present result of expressive equivalence of Muller and B??chi acceptance.
展开▼
