Partially ordered connectives and monadic monotone strict NP

DOI10.1007/s10849-008-9058-5zbMath1169.03023OpenAlexW1984910129MaRDI QIDQ1024818

Tero Tulenheimo, Lauri Hella, Merlijn Sevenster

Publication date: 17 June 2009

Published in: Journal of Logic, Language and Information (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10849-008-9058-5

zbMATH Keywords

constraint satisfaction problemsSNPgeneralized quantifiersHenkin quantifiersMMSNPpartially ordered connectives

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15) Logic with extra quantifiers and operators (03C80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Boolean dependence logic and partially-ordered connectives

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Henkin quantifiers and complete problems
• On the complexity of H-coloring
• Henkin and function quantifiers
• On branching quantifiers in English
• On digraph coloring problems and treewidth duality
• Second order logic and the weak exponential hierarchies
• Monadic generalized spectra
• On the Structure of Polynomial Time Reducibility
• Quantifiers vs. Quantification Theory
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• PARTIALLY ORDERED CONNECTIVES
• Hierarchies of Partially Ordered Connectives and Quantifiers
• Relativized logspace and generalized quantifiers over finite ordered structures
• The complexity of satisfiability problems
• Applications of Strict Π₁¹ predicates to infinitary logic
• Finite partially-ordered quantification
• Logical Approaches to Computational Barriers

This page was built for publication: Partially ordered connectives and monadic monotone strict NP