{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:08:06Z","timestamp":1767236886071},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:p> 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. In our main result, we derive the Chomsky-Sch\u00fctzenberger Theorem for such quantitative context-free languages, showing that each arises as the image of the intersection of a Dyck language and a recognizable language under a suitable morphism. Moreover, we show that quantitative context-free languages are expressively equivalent to a model of weighted pushdown automata. This generalizes results previously known only for semirings. We also investigate under which conditions quantitative context-free languages assume only finitely many values. <\/jats:p>","DOI":"10.1142\/s0129054114400176","type":"journal-article","created":{"date-parts":[[2015,2,25]],"date-time":"2015-02-25T06:32:14Z","timestamp":1424845934000},"page":"955-969","source":"Crossref","is-referenced-by-count":8,"title":["THE CHOMSKY-SCH\u00dcTZENBERGER THEOREM FOR QUANTITATIVE CONTEXT-FREE LANGUAGES"],"prefix":"10.1142","volume":"25","author":[{"given":"MANFRED","family":"DROSTE","sequence":"first","affiliation":[{"name":"Institute of Computer Science, Leipzig University, D-04109 Leipzig, Germany"}]},{"given":"HEIKO","family":"VOGLER","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Technische Universit\u00e4t Dresden, D-01062 Dresden, Germany"}]}],"member":"219","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"p_1","first-page":"111","volume":"1","author":"Autebert J.","year":"1997","journal-title":"Grammar"},{"key":"p_2","first-page":"143","volume":"14","author":"Bar-Hillel Y.","year":"1961","journal-title":"Z. Phonetik. Sprach. Komm."},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1145\/1805950.1805953"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2010.05.020"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.055"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111009069"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2009.09.003"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.11.008"},{"key":"p_24","first-page":"257","volume":"7","author":"Petre I.","year":"2009","journal-title":"Ch."},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2005.02.009"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(61)80020-X"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114400176","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:13:39Z","timestamp":1565190819000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114400176"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12]]},"references-count":11,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2015,2,24]]},"published-print":{"date-parts":[[2014,12]]}},"alternative-id":["10.1142\/S0129054114400176"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114400176","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12]]}}}