notesum.ai

Published at December 10

The Complexity of HyperQPTL

cs.LO

Released Date: December 10, 2024

Authors: Gaëtan Regaud¹, Martin Zimmermann²

Aff.: ¹ENS Rennes, Rennes, France; ²Aalborg University, Aalborg, Denmark

Arxiv: http://arxiv.org/pdf/2412.07341v1

Logic	Satisfiability	Finite-state satisfiability	Model-checking
$\mathrm{LTL}$	PSpace-complete	PSpace-complete	PSpace-complete
$\mathrm{Hyper\-LTL}$	$\Sigma_{1}^{1}$ -complete	$\Sigma_{1}^{0}$ -complete	Tower-complete
$\mathrm{Hyper^{2}LTL}$	T3A-equivalent	T3A-equivalent	T3A-equivalent
$\mathrm{Hyper^{2}LTL_{\mathrm{mm}}}$	T3A-equivalent	T3A-equivalent	T3A-equivalent
$\mathrm{lfp\text{-}{Hyper^{2}LTL_{\mathrm{mm}}}}$	$\Sigma_{1}^{2}$ -complete/	T2A-equivalent	T2A-equivalent
	$\Sigma_{1}^{1}$ -complete (CW)
$\mathrm{Hyper\-QPTL}$	T2A-equivalent	$\Sigma_{1}^{0}$ -complete	Tower-complete
$\mathrm{Hyper\-QPTL^{+}}$	T3A-equivalent	T3A-equivalent	T3A-equivalent