Logical Description of Monotone NP Problems
From MaRDI portal
Publication:4305345
DOI10.1093/logcom/4.4.337zbMath0809.68070OpenAlexW2091528516MaRDI QIDQ4305345
Publication date: 13 September 1994
Published in: Journal of Logic and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1093/logcom/4.4.337
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures ⋮ Graph properties checkable in linear time in the number of vertices ⋮ Positive First-order Logic on Words and Graphs ⋮ The price of query rewriting in ontology-based data access ⋮ Complete problems for monotone NP ⋮ Positive versions of polynomial time ⋮ Program schemes, arrays, Lindström quantifiers and zero-one laws ⋮ Context-sensitive transitive closure operators