2012/08/20 by Manfred Droste, Droste, Manfred, Heiko Vogler +1
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL
paper · pdf · doi:10.48550/arxiv.1208.3942
This new version combines a conference and a journal paper of the authors on the same topic, see references [15,16], and supplements them by a few additional examples and more detailed proofs. It also corrects a mistake in Theorem 7.7 of the first arxiv version (the property sequential was missing)
arxiv created 2016/03/03 · arxiv updated 2016/03/04
Weighted automata model quantitative aspects of systems like the consumption of resources during executions. Traditionally, the weights are assumed to form the algebraic structure of a semiring, but recently also other weight computations like average have been considered. Here, we investigate quantitative context-free languages over very general weight structures incorporating all semirings, average computations, lattices, and more. In our main result, we derive the fundamental Chomsky-Schützenberger theorem for such quantitative context-free languages, showing that each arises as the image of a Dyck language and a regular language under a suitable morphism. Moreover, we show that quantitative context-free language are expressively equivalent to a model of weighted pushdown automata. This generalizes results previously known only for semirings. We also investigate when quantitative context-free languages assume only finitely many values.