PDL for ordered trees

Loredana Afanasiev , Patrick Blackburn (1) , Ioanna Dimitriou , Bertrand Gaiffe (1) , Evan Goris , Maarten Marx , Maarten Rijke

1 LANGUE ET DIALOGUE - Human-machine dialogue with a significant language component

This paper investigates the complexity and expressive power of a language of propositional dynamic logic proposed by Marcus Kracht. The language has four basic programs, corresponding to the child, parent, and left- and right- sibling relations in trees. The paper concentrates on expressivity issues. In particular, it investigates which first-order and second-order properties the language can express.

Mots clés: logics of trees; propositional dynamic logic

Loredana Afanasiev, Patrick Blackburn, Ioanna Dimitriou, Bertrand Gaiffe, Evan Goris, et al.. PDL for ordered trees. Journal of Applied Non-Classical Logics, 2005, 15 (2), pp.115--135. ⟨inria-00001206⟩