This paper presents a novel model of co-reference knowledge, which is based on the distinction of (i) a model of a common reality, (ii) a model of an agent's opinion about reality, and (iii) a model of agents' opinions if they talk about the same object or not. Thereby it is for the first time possible to describe consistently the evolution of the agent's knowledge and its relative consistency, and to formally study algorithms for managing co-reference knowledge between multiple agents if they have the potential to lead to higher states of consistency, independent from the particular mechanism to recognize co-reference. As an example, a scalable algorithm is presented based on monitoring atomic knowledge increments and an abstract notion of belief ranking. The presented approach has a wide potential to study the formal properties of current methods to find co-reference, and to lead to new methods for the global management of co-reference knowledge.

We study the problem of determining a concise, quantifier-free monadic predicate for a given set of objects in a given interpretation. We address both DNF and CNF predicates, as well as important sub-languages thereof. The problem is formalized as the search of a minimal element in a set of predicates equipped with a binary relation. We show that the problem has always a solution, that finding a minimal solution is always hard, but much harder when neither the given set of objects nor its complement are the extent of a formal concept (in the sense of Formal Concept Analysis).

Research on multimedia information retrieval (MIR) has recently witnessed a booming interest. A prominent feature of this research trend is its simultaneous but independent materialization within several fields of computer science. The resulting richness of paradigms, methods and systems may, on the long run, result in a fragmentation of efforts and slow down progress. The primary goal of this study is to promote an integration of methods and techniques for MIR by contributing a conceptual model that encompasses in a unified and coherent perspective the many efforts that are being produced under the label of MIR. The model offers a retrieval capability that spans two media, text and images, but also several dimensions: form, content and structure. In this way, it reconciles similarity-based methods with semantics-based ones, providing the guidelines for the design of systems that are able to provide a generalized multimedia retrieval service, in which the existing forms of retrieval not only coexist, but can be combined in any desired manner. The model is formulated in terms of a fuzzy description logic, which plays a twofold role: (1) it directly models semantics-based retrieval, and (2) it offers an ideal framework for the integration of the multimedia and multidimensional aspects of retrieval mentioned above. The model also accounts for relevance feedback in both text and image retrieval, integrating known techniques for taking into account user judgments. The implementation of the model is addressed by presenting a decomposition technique that reduces query evaluation to the processing of simpler requests, each of which can be solved by means of widely known methods for text and image retrieval, and semantic processing. A prototype for multidimensional image retrieval is presented that shows this decomposition technique at work in a significant case.

A Terminological Logic is presented as an information retrieval model, with a four-valued semantics that gives to its inference relation the avour of relevance, that is a strict connection in meaning between the premises and the conclusion of the arguments licensed by the logic. The logic also permits the expression of meta-knowledge enforcing a closed-world reading of the knowledge concerning specified individuals and primitive concepts. A Gentzen-style, sound and complete calculus for reasoning in the logic is given, thus establishing the basis for an information retrieval engine.

A logical model of images is presented, as a theoretical foundation of information systems allowing the retrieval of images on the basis of their form (typically via visual queries) and content. The proposed model offers a multiple representation of images, extending along three dimensions: form, content and abstraction. At each dimensions, a first-order logic is postulated as a representation and reasoning tool, and one specific logic is introduced for the first of these dimensions, the one dealing with the form of images. A query on images is modelled along the same three dimensions and by means of the same logics. This allows us to model the image retrieval process by the relation of classical logical implication, i.e. an image is retrieved if it logically implies the query.

Images are a communication medium, hence objects of a linguistic nature having a form and a content. The form of an image is the image appearance and is understood as depicting a scene, the image content. The relationship between the form of an image and its content is established through a process of interpretation, capturing the meaning of the image form. Any information need on images can, and indeed has to, be seen as addressing either the image form, or its content, or the relationship between them. Consequently, any general, domain independent image retrieval facility should be based on a model supporting all these aspects of images. An image retrieval model, based on classical logic, is proposed which fulfills this basic requirement. 1 Introduction Information systems o#ering images serve nowadays an increasingly wide community of users. In order to cope with the requirements of their users, these systems must provide a sophisticate retrieval capability, which, while abstractin...

According to recent research, the task of Information Retrieval (IR) can successfully be described as the extraction, from a given document base, of those documents d that, given a query q, make the formula d -> q valid, where d and q are formulae of the chosen logic and ``->'' denotes the brand of logical implication formalized by the logic in question. In this paper, although essentially subscribing to this view, we propose that the logic to be chosen for this endeavour be a Terminological Logic (TL): according to this view the IR task becomes that of singling out those documents d such that q subs d, where d and q are terms} of the chosen TL and ``subs'' denotes subsumption between terms. We argue that TLs are particularly suitable for modelling IR; we do this by showing that they can successfully be employed in representing documents under a variety of aspects (e.g. structural, layout, content), in representing queries and in representing domain and lexical knowledge. The fact that a single logical language can be used for all these representational endeavours ensures that all these sources of knowledge will participate in the retrieval process in a principled way. In this paper we introduce MIRTL, a TL for modelling IR according to the above guidelines; its syntax, formal semantics and inferential algorithm are described.

Data fragmentation is an important aspect of distributed database design, in which portions of relations, tailored to the specific needs of local applications, are defined to be further allocated to the sites of the computer network supporting the database system. In this paper we present a theory of fragmentation with overlapping fragments to study the complexity of the problems involved in checking the completeness of a fragmentation schema and in querying and updating a fragmented relation. We analyze these problems from the complexity viewpoint and present sound and complete algorithms for their solution.