Springer (2003)Ĭhandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. Lecture Notes in Computer Science, vol. 2747, pp.
DETERMINISTIC FINITE AUTOMATON TO LINEAR TEMPORAL LOGIC FULL
Springer (2010)īoker, U., Lehtinen, K., Sickert, S.: On the translation of automata to linear temporal logic (2022),, full versionĬerná, I., Pelánek, R.: Relating hierarchy of temporal properties to model checking. 143–163 (2018)īoker, U., Kupferman, O.: The quest for a tight translation of Büchi to co-Büchi automata.
Mathematical Systems Theory 29(3), 191–226 (1996)īojańczyk, M.: Languages recognised by finite semigroups, and their generalisations to objects such as trees and graphs, with an emphasis on definability in monadic second-order logic (2020)īoker, U.: Why these automata types? In: Proc. Keywordsīirget, J.C.: Two-way automata and length-preserving homomorphisms. In particular, it can be used to translate an LTL formula recognising a safety language to a formula belonging to the safety fragment of LTL (over both finite and infinite words). Furthermore, our translation preserves the acceptance condition of the automaton in the sense that it turns a looping, weak, Büchi, coBüchi or Muller automaton into a formula that belongs to the matching class of the syntactic future hierarchy. To our knowledge, this is the first elementary bound on this translation. Our main contribution consists of a translation of general counter-free deterministic \(\omega \)-regular automata into LTL formulas of double exponential temporal-nesting depth and triple exponential length, using an intermediate Krohn-Rhodes cascade decomposition of the automaton.
Our first contribution consists of tight bounds for LTL over a unary alphabet: alternating, nondeterministic and deterministic automata can be exactly exponentially, quadratically and linearly more succinct, respectively, than any equivalent LTL formula. In particular, there is no known elementary bound on the complexity of translating deterministic \(\omega \)-regular automata to LTL. 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 not.
0 kommentar(er)
