CONCUR 2004 START ConferenceManager    

Characterizing EF and EX tree logics

Mikolaj Bojanczyk Igor Walukiewicz

Presented at Fifteenth International Conference on Concurrency Theory (CONCUR 2004), London, England, 31 August - 3 September, 2004


We characterize the expressive power of EX, EF and EX+EF logics. These are the fragments of CTL build using the respective operators. We give a forbidden pattern characterization of the languages definable in these logics. The characterizations give optimal algorithms for deciding if a given tree language is expressible in one of the three logics.

START Conference Manager (V2.47.4)