Multi-Valued Automata and Their Applications
Kupferman Orna · NATO science for peace and security series. D, Information and communication security · 2010
Standard automata accept or reject input words. Accordingly, an automaton induces a mapping from Σ* to the binary set {true,false}. The course will introduce multi-valued automata, which induce mappings from Σ* to richer sets of values. We will focus on lattice automata, which map input words to values from a lattice, and weighted automata, which map input words to(the set of real numbers). We describe applications of lattice automata in abstraction and model checking of multi-valued logics, and describe applications of weighted automata in the competitive analysis of online algorithms.