THE CHOMSKY-SCHÜTZENBERGER THEOREM FOR QUANTITATIVE CONTEXT-FREE LANGUAGES

DOI10.1142/S0129054114400176zbMath1315.68169OpenAlexW3022516416MaRDI QIDQ5247168

Heiko Vogler, Manfred Droste

Publication date: 23 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054114400176

zbMATH Keywords

homomorphismsvaluation monoidsDyck languagesweighted context-free grammarsweighted pushdown automatacontext-free step functions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Grammars and rewriting systems (68Q42)

Related Items

Weighted simple reset pushdown automata, Weighted iterated linear control, A unifying approach to algebraic systems over semirings, A Kleene theorem for weighted tree automata over tree valuation monoids, Weighted automata with storage, Weighted parsing for grammar-based language models over multioperator monoids, Approximate minimization of weighted tree automata

Cites Work

• Weighted automata and multi-valued logics over arbitrary bounded lattices
• Weighted finite automata over strong bimonoids
• Determinization of weighted finite automata over strong bimonoids
• Weighted automata and weighted logics
• Weighted pushdown systems and their application to interprocedural dataflow analysis
• Quantitative languages
• WEIGHTED AUTOMATA AND REGULAR EXPRESSIONS OVER VALUATION MONOIDS
• On the definition of a family of automata