## Séminaire Algorithmique |

Le séminaire a lieu **le mardi à 11 h 45** (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

# Résumé du séminaire du Mardi 8 Avril 2003

*Reconstructing Propositional Calculus in Database Semantics*

## par Roland Hausser (Universität Erlangen-Nürnberg)

This talk presents a reconstruction of propositional calculus as a simplified version of natural language used for communication. This requires a number of changes with respect to the traditional approach,

First, the method must be changed from the meta-language
definitions of old logic to a declarative specification for
computer software. Second, the *realist ontology* of old
logic, treating meaning as a direct relation between sentences and
the *world* (defined as a set-theoretic model) must be
replaced by a functional system comprising an agent's cognitive
operations. Third, the syntax of propositional calculus must be
adapted to the time-linear nature of language. Fourth, the truth
conditional semantics of propositional calculus must be integrated
into the time-linear process of communication.

The latter task requires solutions to the following problems: First, whether an expression like p & ~p... is contradictory cannot be decided in a time-linear interpretation until the continuation, e.g., p & ~p v q..., is known; second, using truth conditions for checking consistency must avoid the SAT problem, which is known to be computationally intractable.

The reconstruction is presented as the declarative specification of a computer program, comprising (i) a data structure for storing formulas of propositional calculus as concatenated propositions, and (ii) LA-grammars for conceptualization, production, and interpretation. Written at a high level of abstraction, the reconstruction provides a comparison between the metalan\-guage-based approach of traditional logic and the procedural model of communication of database semantics.

Short vita : Professor Roland Hausser heads the Department of Computational Linguistics at the University Erlangen-Nürnberg in Germany. He has worked in formal semantics, grammar algorithms, and human-computer communication. Publications include several books, the latest foundations of Computational Linguistics, as well as papers in the AI Journal and the Journal of Theoretical Computer Science.