Satisfiability problem for modal logic with global counting operators coded in binary is \textsc{NExpTime}-complete

DOI10.1016/J.IPL.2012.09.007zbMath1259.03054OpenAlexW2029164961MaRDI QIDQ1941691

Michał Zawidzki, Dmitry Tishkovsky, Renate A. Schmidt

Publication date: 21 March 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2012.09.007

zbMATH Keywords

computational complexity modal logic finite model property theory of computation counting quantifiers tiling problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modal logic (including the logic of norms) (03B45) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

This page was built for publication: Satisfiability problem for modal logic with global counting operators coded in binary is \textsc{NExpTime}-complete