XML documents and, more generally, semistructured data, can be seen as labelled graphs. In this paper we set a correspondence between such graphs and the models of a language of hybrid multimodal logic. This allows us to characterize a schema for semistructured data as a formula of hybrid multimodal logic, and instances of the schema as models of this formula. We also investigate how to express in such a logic integrity constraints on semistructured data, in particular some classes of constraints (...) widely considered in the literature. The contribution of this work is twofold: 1) We generalize the notion of schema, by proposing a definition of schema were references are “well typed”. 2) We formalize semistructured data, schema for semistructured data and integrity constraints in a unique framework, namely hybrid multimodal logic. (shrink)

We study a modal system ¯T, that extends the classical (prepositional) modal system T and whose language is provided with modal operators M inn (nN) to be interpreted, in the usual kripkean semantics, as there are more than n accessible worlds such that.... We find reasonable axioms for ¯T and we prove for it completeness, compactness and decidability theorems.

We prove the canonical models introduced in [D] do not exist for some graded normal logics with symmetric models, namelyKB°, KBD°, KBT°, so that we define a new kind of canonical models, the general ones, and show they exist and work well in every case.

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. (shrink)