Complexity Results for First-Order Two-Variable Logic with Counting
Publication:4943858
DOI10.1137/S0097539797323005zbMath0956.03039OpenAlexW1971102936MaRDI QIDQ4943858
Wiesław Szwast, Leszek Pacholski, Lidia Tendera
Publication date: 19 March 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539797323005
computational complexityfirst-order logiccountingsatisfiability problemdecision problemNEXPTIME-completefirst-order sentences
Analysis of algorithms and problem complexity (68Q25) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (13)
This page was built for publication: Complexity Results for First-Order Two-Variable Logic with Counting