LTL synthesis can also be solved using the automata-theoretic approach. Besides, model checking MDP against LTL properties involving frequency operators also allows for an automata-theoretic approach, via deterministic generalized Rabin mean-payoff automata (DGRMA). Footnote 1 Recently, several approaches with specific LDBA were proved applicable to the quantitative setting and competitive with DGRA. However, other types of automata, such as deterministic Muller and deterministic parity automata (DPA) are typically larger than DGRA in terms of acceptance condition or the state space, respectively. In principle, all standard types of deterministic automata are applicable here except for deterministic Büchi automata (DBA), which are not as expressive as LTL. Instead, deterministic Rabin automata (DRA) have been mostly used and recently also deterministic generalized Rabin automata (DGRA). However, for the general quantitative questions, where the probability of satisfaction is computed, general limit-determinism is not sufficient. The prime example are the limit-deterministic (also called semi-deterministic) Büchi automata (LDBA) and the generalized LDBA (LDGBA). Even the qualitative question, whether a formula holds with probability 0 or 1, requires automata with at least a restricted form of determinism. Probabilistic LTL model checking cannot profit directly from NBA.
#Deterministic finite automaton to linear temporal logic verification#
For verification of non-deterministic systems, mostly non-deterministic Büchi automata (NBA) are used since they are typically very small and easy to produce. The size of the automaton is important as it directly affects the size of the product and thus largely also the analysis time, particularly for deterministic automata and probabilistic model checking in a very direct proportion. It proceeds in two steps: first, the formula is translated into a corresponding automaton second, the product of the system and the automaton is further analyzed. Automata-theoretic approach is a key technique for verification and synthesis of systems with linear-time specifications, such as formulae of linear temporal logic (LTL).
0 kommentar(er)
