# Algorithm to translate a deterministic Büchi automaton to LTL (when possible)

Linear temporal logic and deterministic Büchi automata are incomparable: DBA cannot express $FGa$, and LTL cannot express "at least each odd letter is 'a'". But sometimes it is interesting to know whether the language of a DBA can be expressed in LTL.

I need an algorithm that decides whether a language of a given DBA is describable in LTL. Do you know algorithms for that?

## migrated from math.stackexchange.comJul 14 '12 at 2:09

This question came from our site for people studying math at any level and professionals in related fields.

• We conjecture that the other direction is decidable (convert formula to NBA, apply power-set construction, check equivalence) but have had no idea about the one you want so far. – Raphael Mar 5 '12 at 17:15
• I am not sure if it's possible at all, but I'd like to note that by Buchi automata people usually mean NBA (which is more expressive than DBA). NBA is also strictly more expressive than LTL. – Daniil Apr 8 '12 at 10:35
• @Daniil from you reference (First Order Definable languages): "We also show that aperiodicity (i.e., first-order definability (LTL difinability)) of a regular ∞-language can be decided in polynomial space".nice ref! – Ayrat Apr 9 '12 at 19:29
• @Ayrat, thanks, it's indeed a good introduction, I was very happy when I found it. There is also a whole book on infinite words. Unfortunately, I haven't got around to reading it yet. – Daniil Apr 10 '12 at 15:11
• Equivalence of Büchi automata and linear $\mu$-calculus might provide some interesting insights. – Gilles Jul 14 '12 at 13:08

You may find the algorithm in Diekert and Gastin's paper, Section 12. It works for both NBW and DBW (provided that you have the $\omega$-expression), and this can be decided in polynomial time.