Dichotomies and Duality in First-order Model Checking Problems

Simple item page
dc.creatorMartin, Barnaby
dc.date2006-09-06
dc.date2006-11-28
dc.date.accessioned2026-07-07T07:23:47Z
dc.date.available2026-07-07T07:23:47Z
dc.descriptionWe study the complexity of the model checking problem, for fixed model A, over certain fragments L of first-order logic. These are sometimes known as the expression complexities of L. We obtain various complexity classification theorems for these logics L as each ranges over models A, in the spirit of the dichotomy conjecture for the Constraint Satisfaction Problem -- which itself may be seen as the model checking problem for existential conjunctive positive first-order logic.
dc.identifierhttps://arxiv.org/abs/cs/0609022
dc.identifierhttp://arxiv.org/abs/cs/0609022
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/116114
dc.subjectLogic in Computer Science
dc.subjectComputational Complexity
dc.titleDichotomies and Duality in First-order Model Checking Problems
dc.typetext

Files

Collections

arXiv