On Classical Decidable Logics extended with Percentage Quantifiers and Arithmetics

Vortrag von Bartosz Bednarczyk

Veranstaltungsort: Online
Beginn: 25. November 2021 um 11:00
Ende: 25. November 2021 um 12:00
Event series: Research Seminar Logic and AI
iCal

The talk is based on my forthcoming FSTTCS'21 paper (https://iccl.inf.tu-dresden.de/web/Inproceedings3301/en) with the eponymous title, co-authored with my two bachelor students (Anna Pacanowska and Maja Orłowska) and my college Tony Tan from Taiwan.

In this work we investigated the extensions of classical decidable logics with percentage quantifiers, specifying how frequently a formula is satisfied in the indented model. We showed, surprisingly, that both the two-variable logic and the guarded fragment become undecidable under such extension, sharpening the existing results in the literature. Our negative results are supplemented by decidability of the two-variable guarded fragment with even more expressive counting, namely Presburger constraints. Our results can be applied to infer decidability of various modal and description logics, e.g. Presburger Modal Logics with Converse or ALCI, with expressive cardinality constraints.

The talk is online, link to the talk:

https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n