A Pitch Rich with Width-Witchcraft – Model-Theoretic Criteria for Decidable Query Entailment

Talk by Sebastian Rudolph

Location: APB room 3027
Start: 20. April 2023 at 11:00 am
End: 20. April 2023 at 12:00 pm
Event series: Research Seminar Logic and AI
iCal

Abstract: Decidability of inferencing is commonly considered a very important property of logic-based knowledge representation formalisms, required for the algorithmization and automation of reasoning. Yet, oftentimes, the corresponding (un)decidability arguments are idiosyncratic and do not shed much light on the underlying principles governing the divide.

In my talk, I will review generic model-theoretic criteria for decidability of querying in fragments of first-order logic. I will describe a general framework by means of which decidability of query entailment can be established based on the existence of countermodels with certain structural properties. These properties depend on the ontology and query language used and range from finite domain over forest-like shape to width-finiteness employing width notions like treewidth and cliquewidth.

The talk will take place in a hybrid fashion, physically in the APB room 3027, and online through the link:

https://bbb.tu-dresden.de/b/pio-zwt-smp-aus