--- _id: '3871' abstract: - lang: eng text: 'Nondeterministic weighted automata are finite automata with numerical weights oil transitions. They define quantitative languages 1, that assign to each word v; a real number L(w). The value of ail infinite word w is computed as the maximal value of all runs over w, and the value of a run as the supremum, limsup liminf, limit average, or discounted sum of the transition weights. We introduce probabilistic weighted antomata, in which the transitions are chosen in a randomized (rather than nondeterministic) fashion. Under almost-sure semantics (resp. positive semantics), the value of a word v) is the largest real v such that the runs over w have value at least v with probability I (resp. positive probability). We study the classical questions of automata theory for probabilistic weighted automata: emptiness and universality, expressiveness, and closure under various operations oil languages. For quantitative languages, emptiness university axe defined as whether the value of some (resp. every) word exceeds a given threshold. We prove some, of these questions to he decidable, and others undecidable. Regarding expressive power, we show that probabilities allow its to define a wide variety of new classes of quantitative languages except for discounted-sum automata, where probabilistic choice is no more expressive than nondeterminism. Finally we live ail almost complete picture of the closure of various classes of probabilistic weighted automata for the following, provide, is operations oil quantitative languages: maximum, sum. and numerical complement.' acknowledgement: This research was supported in part by the Swiss National Science Foundation under the Indo-Swiss Joint Research Programme, by the European Network of Excellence on Embedded Systems Design (ArtistDesign), by the European projects Combest, Quasimodo, and Gasics, by the PAI program Moves funded by the Belgian Federal Government, and by the CFV (Federated Center in Verification ) funded by the F.R.S.-FNRS. alternative_title: - LNCS author: - first_name: Krishnendu full_name: Chatterjee, Krishnendu id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Laurent full_name: Doyen, Laurent last_name: Doyen - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 citation: ama: 'Chatterjee K, Doyen L, Henzinger TA. Probabilistic weighted automata. In: Vol 5710. Springer; 2009:244-258. doi:10.1007/978-3-642-04081-8_17' apa: 'Chatterjee, K., Doyen, L., & Henzinger, T. A. (2009). Probabilistic weighted automata (Vol. 5710, pp. 244–258). Presented at the CONCUR: Concurrency Theory, Bologna, Italy: Springer. https://doi.org/10.1007/978-3-642-04081-8_17' chicago: Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Probabilistic Weighted Automata,” 5710:244–58. Springer, 2009. https://doi.org/10.1007/978-3-642-04081-8_17. ieee: 'K. Chatterjee, L. Doyen, and T. A. Henzinger, “Probabilistic weighted automata,” presented at the CONCUR: Concurrency Theory, Bologna, Italy, 2009, vol. 5710, pp. 244–258.' ista: 'Chatterjee K, Doyen L, Henzinger TA. 2009. Probabilistic weighted automata. CONCUR: Concurrency Theory, LNCS, vol. 5710, 244–258.' mla: Chatterjee, Krishnendu, et al. Probabilistic Weighted Automata. Vol. 5710, Springer, 2009, pp. 244–58, doi:10.1007/978-3-642-04081-8_17. short: K. Chatterjee, L. Doyen, T.A. Henzinger, in:, Springer, 2009, pp. 244–258. conference: end_date: 2009-09-04 location: Bologna, Italy name: 'CONCUR: Concurrency Theory' start_date: 2009-09-01 date_created: 2018-12-11T12:05:37Z date_published: 2009-09-01T00:00:00Z date_updated: 2021-01-12T07:52:50Z day: '01' ddc: - '000' - '005' department: - _id: KrCh doi: 10.1007/978-3-642-04081-8_17 ec_funded: 1 file: - access_level: open_access checksum: af973ddbcf131b8810c6bff2c055ff56 content_type: application/pdf creator: system date_created: 2018-12-12T10:09:46Z date_updated: 2020-07-14T12:46:20Z file_id: '4771' file_name: IST-2012-52-v1+1_Probabilistic_Weighted_Automata.pdf file_size: 200161 relation: main_file file_date_updated: 2020-07-14T12:46:20Z has_accepted_license: '1' intvolume: ' 5710' language: - iso: eng month: '09' oa: 1 oa_version: Submitted Version page: 244 - 258 project: - _id: 25F1337C-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '214373' name: Design for Embedded Systems - _id: 25EFB36C-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '215543' name: COMponent-Based Embedded Systems design Techniques publication_status: published publisher: Springer publist_id: '2304' pubrep_id: '52' quality_controlled: '1' scopus_import: 1 status: public title: Probabilistic weighted automata type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 5710 year: '2009' ...