How can I translate a Büchi automaton A to LTL(linear temporal logic) if $L(A)$ is definable in the LTL? 


MY idea is : Büchi automaton $A$ ===> QPTL ===> LTL


I know that given any Buchi automaton, we can translate it to QPTL(Quantified Propositional Temporal Logic), formally speaking, For every B¨uchi automaton A over $Σ=2^{AP}$, there exists a QPTL formula $ϕ$ such that $models(ϕ)=L(A)$, and we can decide in PSPACE whether the accepted language $L⊆Σ^∞$ of a given B¨uchi automaton $A$ is aperiodic. It's well known that $L$ is aperiodic iff L is definable in the LTL, so we can use this algorithm to check whether $L(A)$ is definable in the LTL.


but how can I translate QPTL to LTL???


thanks!!



Translate a buchi automaton to LTL
You can always go through the $\omega$-semigroup. It might not be the most straightforward algorithm, but at least it should work.


You can find details in <http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DG-WT08.pdf>


The principle is to translate your automaton into an $\omega$-semigroup, via the transition matrices for instance.
Then you can minimize this $\omega$-semigroup. If $L(A)$ is LTL-definable this should give you an aperiodic semigroup.
You can then apply the proof that aperiodic implies LTL-definable, in order to get an LTL formula for your language.


