Computational Logic in 1999

Work within the Computational Logic group is organized in three streams: Computing with Logic, Computing with Language, and Computing with Information. During 1999, each of these streams gained full speed, both in terms of the number of people involved and in terms of research activities. By the second half of the year, a total of 12 people were directly involved with the group.

The Computing with Logic stream provides a natural setting for the group's focus on content, and, especially, for investigating the balance between representations of content and methods for manipulating content. One of the main foundational issues here is to determine how the expressive power of a description formalism is related to the computational costs of performing reasoning tasks within the formalism. Here, a step forward was made by Kurtonina and de Rijke when they fully mapped out the relative expressive power of a large family of description logics; the relationship between various classes of such logics were studied by Areces, Kerdiles, and de Rijke, using a variety of computational and logical criteria. A more direct way of understanding the balance between representations and efficiency is by experimentally comparing the computational properties of different representations. This line is being pursued by Ó Nuallá in in the setting of propositional logic, and by Areces, Gennari, Heguiabehere, and de Rijke in the setting of modal logic, where they exploited important semantic properties to optimize the performance of translation-based theorem provers. More practical concerns stemming from the area of telecommunications have been driving a related research question: How do we represent dynamic and possibly conflicting information from different sources in a controlled and efficient way? Accorsi, Areces, Bouma (KPN Research), and de Rijke have investigated two novel and complementary lines of attack here, one using constraint-based modeling techniques, the other based on satisfiability testing.

The Computing with Language stream saw the start of an NWO-funded project, called `Derive!', which is aimed at bringing recent advances in natural language processing and computational logic to bear on information extraction and retrieval; it addresses the problem of finding content in natural language documents. Christof Monz is the principal investigator on this project. At the same time, Monz and de Rijke worked on the use of shallow or light-weight natural language processing tools for the generation of back-of-the-book indexes; a prototype has been developed and is currently being set up by Bergo as the core of an experimental system, where domain-dependent knowledge is being acquired to aid in further improving the behavior of the system. Aiello, Monz, and Todoran (ISIS, UvA) explored combinations of natural language processing tools and spatial information for understanding the structure and content of scanned documents.

 

The plot shows how the new Layered translation of modal formulae into first-order logic devised by the Computational Logic Group improves the performance of a resolution theorem prover with respect to the standard relational translation. Both the needed CPU-time and number of clauses generated to find a proof have been greatly reduced. We display average behavior on test obtained using the random generator approved by TANCS (Tableaux Non Classical Systems Comparison).

The group's activities in the Computing with Information stream ranges from fundamental to experimental to applied. In 1999 a project on semistructured content was started, with funding from the British Council; the core idea of the project is to apply a modal logic perspective to specifying and constraining the graph-based datamodels underlying semistructured content; results obtained so far by Alechina and de Rijke include significantly lower complexity bounds for some common reasoning tasks, and improved algorithms to perform these tasks. Aiello, Areces and de Rijke worked on accessing visual content; they proposed a calculus aimed at enhancing image retrieval with the ability to perform spatial reasoning using `expensive' picture descriptions (common in content based image retrieval systems. In collaboration with Chidlovskii (Xerox), Ragetli and de Rijke worked on automatically generating information extractors for identifying relevant content in result pages of web-based search engines. And together with van Eijck they are studying the use of glossary-based navigation tools for exploring and organizing the contents of electronic handbooks; this work is part of the Logic and Language Links project funded by Elsevier Science which was started up during the second half of the year.