I am reading the seminal paper "On the temporal analysis of fairness" by Gabbay, Pnueli, Shelah, Stavi, available at


In Section 3, completeness of a set of axioms for LTL is established. I am struggling to prove the first (crucial) Lemma on page 172, which is basically unproven therein.(Same with many other statements in that section, but their proofs can be reconstructed.) Does there exist an extended version of the above mentioned paper? Contacting the (still living) authors failed. Help would be appreciated.

  • 1
    $\begingroup$ Don't read ancient papers. If you are looking for a modern treatment of some results on temporal logic, consult an appropriate handbook or a book on temporal logics. A good reference list is available here: mimuw.edu.pl/~vbarany/TL_course.html $\endgroup$ Sep 7, 2022 at 17:31
  • $\begingroup$ Ironically, one of the references in the list of papers suggested by B. Bednarczyk is "The temporal analysis of fairness" (an "ancient" but seminal paper.....). None of the others seems to address in detail the completeness issue of LTL. $\endgroup$
    – sbarra
    Sep 7, 2022 at 18:13
  • $\begingroup$ What kind of result are you looking for? Expressive completeness of LTL? It's not clear from your question. You may also check the slides: cmi.ac.in/~kumar/words/LTLSlides.pdf $\endgroup$ Sep 7, 2022 at 19:01
  • $\begingroup$ This paper is indeed particularly hard to read. Can you perhaps distill exactly what you're trying to prove, i.e., the necessary definitions and claims? (so that people don't have to go through the whole thing). Also, perhaps this would be relevant: dl.acm.org/doi/fullHtml/10.1145/3387109 $\endgroup$
    – Shaull
    Sep 8, 2022 at 6:02
  • 1
    $\begingroup$ @sbarra if you write down what you're trying to prove, perhaps it would be easier for us to have a look. $\endgroup$
    – Shaull
    Sep 9, 2022 at 4:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.