Handbook of Weighted Automata - 9783642014918

Šio vadovo tikslas – pabrėžti svertinių automatų teoriją ir pritaikymą. Svertiniai baigtiniai automatai yra klasikiniai nedeterministiniai baigtiniai automatai, kuriuose perėjimai turi svorius. Šie svoriai gali modeliuoti, pvz., išlaidas, susijusias su perėjimu, tam reikalingų išteklių ar laiko kiekį arba sėkmingo jo įvykdymo tikimybę ar patikimumą. Svertinių baigtinių automatų elgesys gali būti laikomas funkcija (tinkamai apibrėžta), susiejančia su kiekvienu žodžiu jo vykdymo svorį. Akivaizdu, kad svoriai taip pat gali būti pridėti prie klasikinių automatų su begalinių būsenų rinkiniais, tokiais kaip nuspaudimo automatai, šis plėtinys sudaro bendrą svertinių automatų koncepciją. Norėdami iliustruoti svertinių automatų įvairovę, panagrinėkime šiuos scenarijus. Tarkime, kad kiekybinė sistema yra modeliuojama klasikiniu automatu, kuriame perėjimai kaip svoriai turi išteklių, reikalingų jų vykdymui, kiekį. Tada resursų kiekis, reikalingas keliui šiame svertiniame automate, gaunamas tiesiog kaip jo perėjimų svorių suma. Pateikus žodį, mus gali sudominti minimalus resursų kiekis, reikalingas jo vykdymui, ty sėkmingiems keliams realizuoti duotą žodį. Šiame pavyzdyje išteklius taip pat galėtume pakeisti pelnu ir tada domėtis maksimaliu gautu pelnu, atitinkamai, duotu žodžiu.