Advances in Logical Foundations of Computer Science

The field of logical foundations of computer science is witnessing significant developments, with a focus on enhancing the expressiveness and efficiency of various logical formalisms. Researchers are exploring new ways to encode and reason about complex data structures, such as arrays, and to develop more efficient decision procedures for fragments of set theory. Additionally, there is a growing interest in studying the complexity of constraint satisfaction problems over multisorted cores and the expressive power of disjunctive existential rules. Noteworthy papers in this area include: The Constraint Satisfaction Problem Over Multisorted Cores, which reduces the problem to computing the determinant of an integer-valued matrix, placing it in the complexity class DET. Finite Axiomatizability by Disjunctive Existential Rules, which characterizes the expressive power of disjunctive existential rules in terms of model-theoretic properties.

Sources

Encoding and Reasoning About Arrays in Set Theory

Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations

The Constraint Satisfaction Problem Over Multisorted Cores

Finite Axiomatizability by Disjunctive Existential Rules

Fitting Ontologies and Constraints to Relational Structures

On a Second-Order Version of Russellian Theory of Definite Descriptions

Built with on top of