摘要：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.
