Loading [MathJax]/extensions/tex2jax.js

Applications and complexity of logics in semiring team semantics

Project: Research

Participants

  • Arne Meier (Principal Investigator)
  • Heribert Vollmer (Project staff)
  • Timon Barlag (Project staff)
  • Nicolas Frederik Hamlet Fröhlich (Project staff)
  • Vivian Holzapfel (Project staff)
  • Laura Strieker (Project staff)

External collaborative partners

Details

StatusActive
Start/end date1 Jan 202431 Dec 2025

Funding

Description

The research project focuses on analysing the complexity of fundamental decision problems in logic with semiring team semantics. One of the main aspects is model checking, which determines whether a given formula is satisfied in a model with certain teams. Furthermore, the problem of counting the number of teams that satisfy a given formula is also investigated. These questions have already been thoroughly investigated, where the complexity of model checking for semirings is potentially influenced by the existence theory of the semirings. It can be analysed using BSS machines or circuits over semirings.

Another goal of the project is to investigate the complexity and axiomatizability of the implication problem for dependencies within different semiring classes. This involves a general semiring interpretation for dependencies, as formulated in an extended form of first-order predicate logic. This framework allows the analysis of generalised implication problems and thus provides an approximation for usually complex set-theoretic or multi-set-theoretic problems.

The project also deals with the application of semiring team semantics in the area of database repair and consistent query evaluation. Databases can become inconsistent for various reasons, meaning that integrity constraints are not satisfied. One solution is to perform minimal adjustments to achieve a similar database that satisfies the constraints. The semiring context allows the definition of various distance metrics based on semiring values that measure the closeness to a satisfied constraint.

In summary, the project has four main objectives: determining the complexity of model checking logics with Semiring Team semantics, estimating the counting complexity for these logics, analysing the implication problems with regard to dependencies with Semiring Team semantics, and investigating the complexity of database repairs and consistent query evaluation in the context of these semantics.

???details???

Funding type

Funding scheme