The UvA-LINKER will give you a range of other options to find the full text of a publication (including a direct link to the full-text if it is located on another database on the internet).
De UvA-LINKER biedt mogelijkheden om een publicatie elders te vinden (inclusief een directe link naar de publicatie online als deze beschikbaar is in een database op het internet).
| Authors||L. Afanasiev, P. Blackburn, I. Dimitriou, B. Gaiffe, E. Goris, M.J. Marx, M. de Rijke|
|Title||PDL for Ordered Trees|
|Journal||Journal of Applied Non-Classical Logics|
|Faculty||Faculty of Science|
|Institute/dept.||FNWI: Informatics Institute (II)|
|Keywords||pdl; ordered trees; definability; expresivity; complexity|
|Classification||54.53 computer science: programming languages|
|Abstract||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 (eXtensible Markup Language) 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 (second-order) problems, like the boolean circuit and the frontier problem.
Use this url to link to this page: http://dare.uva.nl/en/record/165588
Contact us about this recordNotify a colleague
Add to bookbag