Handbook of Weighted Automata - 9783642014918

Šīs rokasgrāmatas mērķis ir izcelt gan svērto automātu teoriju, gan lietojumus. Svērtie galīgie automāti ir klasiski nedeterminēti galīgi automāti, kuros pārejām ir svars. Šie svari var modelēt, piemēram, izmaksas, kas saistītas ar pārejas izpildi, tai nepieciešamo resursu vai laika daudzumu vai tās veiksmīgas izpildes varbūtību vai uzticamību. Pēc tam svērto galīgo automātu uzvedību var uzskatīt par funkciju (piemēroti definētu), kas ar katru vārdu saista tā izpildes svaru. Skaidrs, ka svarus var pievienot arī klasiskajiem automātiem ar bezgalīgām stāvokļu kopām, piemēram, nospiežamajiem automātiem, šis paplašinājums veido vispārējo svērto automātu jēdzienu. Lai ilustrētu svērto automātu daudzveidību, apskatīsim šādus scenārijus. Pieņemsim, ka kvantitatīvā sistēma ir modelēta ar klasisku automātu, kurā pārejām ir nozīme to izpildei nepieciešamo resursu apjomam. Tad ceļam nepieciešamo resursu daudzumu šajā svērtajā automātā iegūst vienkārši kā tā pāreju svaru summu. Dots vārds mūs varētu interesēt minimālais resursu apjoms, kas nepieciešams tā izpildei, ti, sekmīgiem ceļiem, realizējot doto vārdu. Šajā piemērā mēs varētu arī aizstāt resursus ar peļņu un pēc tam interesēties par maksimālo gūto peļņu, attiecīgi, ar doto vārdu.