 | EasyChair Smart Slide | User guide |
| Home |
Title:On the Complexity of Model Checking for Temporal Equilibrium Logic
Conference:LPNMR 2026
Tags:Complexity analysis, Model checking, Nonmonotonic logics and Temporal logics
Abstract:
Given an interpretation and a formula written in a logic , the problem of model checking (MC) for is the problem of determining whether is a model of . In this work, the computational complexity of MC for temporal equilibrium logic (TEL), a temporal extension of ASP, is investigated. The complexity of the universal and the existential variant of MC for TEL over Kripke structures, and of MC over linear traces, is determined. The complexity of these problems when the set of temporal operators, the temporal height or the implication height of the input formula is restricted is also determined.
On the Complexity of Model Checking for Temporal Equilibrium Logic
On the Complexity of Model Checking for Temporal Equilibrium Logic
