TLA is a linear temporal logic introduced by Lamport 19 and based on the action-as-relation principle. They generalize the finite case by having a slightly different acceptance condition. have shown that LDBAs are easy to complement. Syntactically, Büchi automata are the same as finite-state automata, but designed for the acceptance of infinite words.
However, recent papers have shown that LDBAs were unjustly forgotten. The translations yield automata of asymptotically. The alternative path of translating the LTL formula into an equivalent fully deterministic Rabin automaton using Safra’s construction was considered a better option, mostly because it also solves the quantitative probabilistic model-checking problem (computing the probability of the executions that satisfy a formula). We present a unified translation of linear temporal logic (LTL) formulas into deterministic Rabin automata (DRA), limit-deterministic Büchi automata (LDBA), and nondeterministic Büchi automata (NBA).
The solution was to introduce LDBAs as a model in-between: as expressive as NBAs, but deterministic enough.Īfter these papers, LDBAs received little attention. While the complexity of translating future linear temporal logic (LTL) into automata on infinite words is well-understood, the size increase involved in turning automata back to LTL is. The automaton A is deterministic if j S 0 1 and j (s a) j 1 for all states s 2 S and symbols a. Representing temporal operators by first-order expressions enables temporal deduction to use the.
The problem faced by these authors was that fully nondeterministic Büchi automata (NBAs), which can capture all LTL-recognisable languages, cannot be used for probabilistic model checking, and deterministic Büchi automata (DBA), which could be used for probabilistic model checking, cannot capture all LTL-recognisable languages. This paper presents a deductive system for predicate temporal logic with induction. Limit-deterministic Büchi automata (LDBA, also known as semi-deterministic Büchi automata) were introduced by Courcoubetis and Yannakakis (based on previous work by Vardi) to solve the qualitative probabilistic model-checking problem: Decide if the executions of a Markov chain or Markov decision process satisfy a given LTL formula with probability 1.
0 kommentar(er)
