Handbook of Weighted Automata - 9783642014918

Celem tego podręcznika jest przedstawienie zarówno teorii, jak i zastosowań automatów ważonych. Ważone automaty skończone to klasyczne niedeterministyczne automaty skończone, w których przejścia noszą wagi. Wagi te mogą modelować np. koszt wykonania przejścia, ilość zasobów lub czasu potrzebnych na to, czy też prawdopodobieństwo lub niezawodność jego pomyślnego wykonania. Zachowanie ważonych automatów skończonych można wówczas uznać za funkcję (odpowiednio zdefiniowaną) wiążącą z każdym słowem wagę jego wykonania. Oczywiście wagi można również dodawać do klasycznych automatów z nieskończonymi zbiorami stanów, takich jak automaty ze stosem. To rozszerzenie stanowi ogólną koncepcję automatów ważonych. Aby zilustrować różnorodność automatów ważonych, rozważmy następujące scenariusze. Załóżmy, że system ilościowy modelowany jest przez klasyczny automat, w którym przejścia niosą jako wagi ilość zasobów potrzebnych do ich wykonania. Następnie ilość zasobów potrzebnych na ścieżkę w tym automacie ważonym otrzymuje się po prostu jako sumę wag jego przejść. Mając dane słowo, może nas interesować minimalna ilość zasobów potrzebnych do jego wykonania, czyli pomyślnych ścieżek realizujących dane słowo. W tym przykładzie moglibyśmy również zastąpić zasoby zyskiem i wtedy interesować się będzie maksymalnym zyskiem realizowanym odpowiednio przez dane słowo.