Nested words, a model for recursive programs proposed by Alur and Madhusudan,have recently gained much interest. In this paper we introduce quantitativeextensions and study nested word series which assign to nested words elementsof a semiring. We show that regular nested word series coincide with seriesdefinable in weighted logics as introduced by Droste and Gastin. For this weestablish a connection between nested words and the free bisemigroup. Applyingour result, we obtain characterizations of algebraic formal power series interms of weighted logics. This generalizes results of Lautemann, Schwentick andTherien on context-free languages.
展开▼
