The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages

DOI10.1007/978-3-642-38771-5_19zbMATH Open1381.68114arXiv1208.3942OpenAlexW2147884289MaRDI QIDQ5300841FDOQ5300841

Authors: Manfred Droste, Heiko Vogler 

Publication date: 28 June 2013

Published in: Developments in Language Theory (Search for Journal in Brave)

Abstract: 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"utzenberger 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.

Full work available at URL: https://arxiv.org/abs/1208.3942

Recommendations

• The Chomsky-Schützenberger theorem for quantitative context-free languages
• Chomsky-Schützenberger-type characterization of multiple context-free languages
• Quotient and bounded context-free languages
• scientific article; zbMATH DE number 3238653
• Quotients of Context-Free Languages
• On the Chomsky and Stanley's homomorphic characterization of context-free languages
• scientific article; zbMATH DE number 871238
• Chomsky-Schutzenberger type characterizations based on contextual languages
• Context-free complexity of finite languages
• On the formalization of some results of context-free language theory

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Cited In (13)

• Title not available (Why is that?)
• The Chomsky-Schützenberger theorem for quantitative context-free languages
• Quotient and bounded context-free languages
• Non-erasing Variants of the Chomsky–Schützenberger Theorem
• Monoid automata for displacement context-free languages
• The conjecture of Fliess on commutative context-free languages
• THE BENFORD-NEWCOMB DISTRIBUTION AND UNAMBIGUOUS CONTEXT-FREE LANGUAGES
• Weighted symbolic automata with data storage
• Characterizations of recognizable weighted tree languages by logic and bimorphisms
• Weighted automata with storage
• Weighted automata
• A Necessary and Sufficient Condition for Chomsky-Productions Over Partially Ordered Symbol Sets
• Weighted iterated linear control

This page was built for publication: The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300841)