A note on the characterization of TL[EF]
In this note, we give a new proof for Bojanczyk and Walukiewicz's effective characterization of TL[EF] (the fragments of Computation Tree Logic (CTL), with EF modality only) following the Ehrenfeucht-Fraisse game approach. Then, we extend the proof to the effective characterization of TL[EFns] (F-ns is the non-strict "future" temporal operator, while F is the strict one). (c) 2006 Elsevier B.V. All rights reserved.
ehrenfeucht-fraisse game formal languages branching-time temporal logic tree languages