Leonid Libkin Livres

Finite model theory, rooted in mathematical logic and computer science, explores applications in database theory, computational complexity, and formal languages, with recent connections to formal methods, verification, and artificial intelligence. Its origins trace back to Trakhtenbrot's 1950 result, which established that validity over finite models is not recursively enumerable, highlighting a failure of completeness. This proof technique, which encodes Turing machine computations as finite structures, was later employed by Fagin to demonstrate the equivalence between the class NP and existential second-order logic, offering a machine-independent view of a key complexity class. In 1982, Immerman and Vardi expanded this field by showing that a fixed point extension of first-order logic captures the complexity class PTIME, leading to logical characterizations of other significant complexity classes, a pursuit known as descriptive complexity. Additionally, finite model theory has influenced the evolution of relational databases; by the late 1970s, the relational model emerged as the dominant framework, with basic query languages primarily based on first-order predicate calculus or its minor extensions.

Focusing on the complexities of data exchange, this work explores how to effectively transform data from a source schema to a target schema while maintaining semantic consistency. It addresses both relational and XML contexts, highlighting key tasks such as schema mappings, target instance materialization, and query rewriting. Additionally, it delves into metadata management, examining operations like schema mapping composition and inverses. The discussion extends to XML-specific challenges, including consistency issues and the need for stricter mapping and query constraints for efficient data handling.

Provides a summary of the key developments of a decade of research into the area of data exchange.

Edited in collaboration with FoLLI, the Association of Logic, Language and Information this book constitutes the refereed proceedings of the 20th Workshop on Logic, Language, Information and Communication, WoLLIC 2013, held in Darmstadt, Germany, in August 2013. The 17 contributed papers presented together with 6 invited lectures were carefully reviewed and selected from 30 submissions. The scope of the workshop spans the theoretical and practical aspects of formal logic, computing and programming theory, and natural language and reasoning.