PDL for ordered trees

Patrick Blackburn
Roskilde University
This paper is about a special version of PDL, proposed by Marcus Kracht, for reasoning about sibling ordered trees. It has four basic programs corresponding to the child, parent, left- and right-sibling relations in such trees. The original motivation for this language is rooted in the field of model-theoretic syntax. Motivated by recent developments in the area of semi-structured data, and, especially, in the field of query languages for XML documents, we revisit the language. This renewed interest comes with a special focus on complexity and expressivity aspects of the language, aspects that have so far largely been ignored. We survey and derive complexity results, and spend most of the paper on the most important open question concerning the language: what is its expressive power? We approach this question from two angles: Which first-order properties can be expressed? And which second-order properties? While we are still some way from definitive answers to these questions, we discuss two first-order fragments of the PDL language for ordered trees, and show how the language can be used to express some typical problems, like the boolean circuit and the frontier problem.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.3166/jancl.15.115-135
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 43,694
Through your library

References found in this work BETA

Modal Logic.Patrick Blackburn, Maarten de Rijke & Yde Venema - 2002 - Cambridge University Press.
Dynamic Logic.Lenore D. Zuck & David Harel - 1989 - Journal of Symbolic Logic 54 (4):1480.
Handbook of Philosophical Logic.Dov Gabbay & Franz Guenthner (eds.) - 1989 - Kluwer Academic Publishers.

View all 11 references / Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Game Trees For Decision Analysis.Prakash P. Shenoy - 1998 - Theory and Decision 44 (2):149-171.
Gregory Trees, the Continuum, and Martin's Axiom.Kenneth Kunen & Dilip Raghavan - 2009 - Journal of Symbolic Logic 74 (2):712-720.
Canonical Simplification of Finite Objects, Well Quasi-Ordered by Tree Embedding.Thomas C. Brown - 1979 - Dept. Of Computer Science, University of Illinois at Urbana-Champaign.
Editors' Introduction.Patrick Blackburn & Maarten de Rijke - 1996 - Notre Dame Journal of Formal Logic 37 (2):161-166.
On Scott and Karp Trees of Uncountable Models.Tapani Hyttinen & Jouko Väänänen - 1990 - Journal of Symbolic Logic 55 (3):897-908.


Added to PP index

Total views
84 ( #96,624 of 2,264,513 )

Recent downloads (6 months)
8 ( #150,306 of 2,264,513 )

How can I increase my downloads?


My notes

Sign in to use this feature