×

On the complexity of the model checking problem. (English) Zbl 1393.68078


MSC:

68Q25 Analysis of algorithms and problem complexity
03B70 Logic in computer science
06A15 Galois correspondences, closure operators (in relation to ordered sets)
08A70 Applications of universal algebra in computer science
68Q60 Specification and verification (program logics, model checking, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv Link

References:

[1] L. Barto, M. Kozik, and T. Niven, The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and hell), SIAM J. Comput., 38 (2009), pp. 1782–1802, . · Zbl 1191.68460
[2] M. Bodirsky, M. Hermann, and F. Richoux, Complexity of existential positive first-order logic, in Proceedings of the 5th Conference on Computability in Europe, 2009, pp. 31–36. · Zbl 1268.03048
[3] F. Börner, Total multifunctions and relations, in AAA60: Workshop on General Algebra, Dresden, 2000.
[4] F. Börner, A. A. Bulatov, H. Chen, P. Jeavons, and A. A. Krokhin, The complexity of constraint satisfaction games and QCSP, Inform. and Comput., 207 (2009), pp. 923–944. · Zbl 1188.68269
[5] A. Bulatov, P. Jeavons, and A. Krokhin, Classifying the complexity of constraints using finite algebras, SIAM J. Comput., 34 (2005), pp. 720–742, . · Zbl 1071.08002
[6] A. A. Bulatov, A dichotomy theorem for constraint satisfaction problems on a 3-element set, J. ACM, 53 (2006), pp. 66–120. · Zbl 1316.68057
[7] A. K. Chandra and P. M. Merlin, Optimal implementation of conjunctive queries in relational data bases, in Proceedings of the Ninth Annual ACM Symposium on Theory of Computing, J. E. Hopcroft, E. P. Friedman, and M. A. Harrison, eds., 1977, pp. 77–90.
[8] H. Chen, Quantified constraint satisfaction and 2-semilattice polymorphisms, in Proceedings of the 10th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Comput. Sci. 3258, M. Wallace, ed., Springer, 2004, pp. 168–181. · Zbl 1152.68546
[9] H. Chen, The complexity of quantified constraint satisfaction: Collapsibility, sink algebras, and the three-element case, SIAM J. Comput., 37 (2008), pp. 1674–1701, . · Zbl 1151.68025
[10] H. Chen, A rendezvous of logic, complexity, and algebra, ACM Comput. Surv., 42 (2009), 2.
[11] H. Chen, Meditations on quantified constraint satisfaction, in Logic and Program Semantics, Springer, 2012, pp. 35–49. · Zbl 1354.68113
[12] N. Creignou, S. Khanna, and M. Sudan, Complexity Classifications of Boolean Constraint Satisfaction Problems, SIAM, 2001, . · Zbl 0981.68058
[13] V. Dalmau, Some Dichotomy Theorems on Constant-Free Quantified Boolean Formulas., Tech. Report LSI-97-43-R., Departament LSI, Universitat Pompeu Fabra, Barcelona, 1997.
[14] T. Feder and M. Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory, SIAM J. Comput., 28 (1998), pp. 57–104, . · Zbl 0914.68075
[15] E. Grädel, P. G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Y. Vardi, Y. Venema, and S. Weinstein, Finite Model Theory and Its Applications, Texts Theoret. Comput. Sci. EATCS Ser., Springer, 2007. · Zbl 1133.03001
[16] P. Hell and J. Nešetřil, On the complexity of H-coloring, J. Combin. Theory Ser. B, 48 (1990), pp. 92–110.
[17] M. Hermann and F. Richoux, On the computational complexity of monotone constraint satisfaction problems, in Proceedings of the Third International Workshop on Algorithms and Computation, 2009, pp. 286–297. · Zbl 1211.68218
[18] W. Hodges, Model Theory, Encyclopedia Math. Appl. 42, Cambridge University Press, 1993.
[19] P. Jeavons, D. A. Cohen, and M. Gyssens, Closure properties of constraints, J. ACM, 44 (1997), pp. 527–548. · Zbl 0890.68064
[20] P. G. Kolaitis and M. Y. Vardi, Conjunctive-query containment and constraint satisfaction, J. Comput. System Sci., 61 (2000), pp. 302–332. · Zbl 0963.68059
[21] M. Krasner, Une généralisation de la notion de corps, J. Math. Pures Appl., 9 (1938), pp. 367–385. · JFM 64.0086.03
[22] N. A. Lynch, Log space recognition and translation of parenthesis languages, J. ACM, 24 (1977), pp. 583–590. · Zbl 0401.68051
[23] F. R. Madelaine and B. Martin, The complexity of positive first-order logic without equality, in Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009, pp. 429–437.
[24] F. R. Madelaine and B. Martin, A tetrachotomy for positive first-order logic without equality, in Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, M. Grohe, ed., 2011, pp. 311–320.
[25] F. R. Madelaine and B. Martin, The complexity of positive first-order logic without equality, ACM Trans. Comput. Log., 13 (2012), 5. · Zbl 1351.68119
[26] F. R. Madelaine and B. Martin, Containment, equivalence and coreness from CSP to QCSP and beyond, in Proceedings of the 18th International Conference on Principles and Practice of Constraint Programming, Springer, 2012, pp. 480–495.
[27] B. Martin, Dichotomies and duality in first-order model checking problems, in Logic and Theory of Algorithms, Springer, 2008, pp. 417–427. · Zbl 1142.68439
[28] B. Martin, First-order model checking problems parameterized by the model, in Logic and Theory of Algorithms, Lecture Notes in Comput. Sci. 5028, A. Beckmann, C. Dimitracopoulos, and B. Löwe, eds., Springer, 2008, pp. 417–427. · Zbl 1142.68439
[29] B. Martin, The lattice structure of sets of surjective hyper-operations, in Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Comput. Sci. 6308, D. Cohen, ed., Springer, 2010, pp. 368–382.
[30] B. Martin, QCSP on partially reflexive forests, in Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Comput. Sci. 6876, J. H.-M. Lee, ed., Springer, 2011, pp. 546–560. · Zbl 1401.68124
[31] B. Martin and F. R. Madelaine, Towards a trichotomy for quantified h-coloring, in Proceedings of the Second Conference on Computability in Europe, Lecture Notes in Comput. Sci. 3988, A. Beckmann, U. Berger, B. Löwe, and J. V. Tucker, eds., Springer, 2006, pp. 342–352. · Zbl 1145.68436
[32] B. Martin and J. Martin, The complexity of positive first-order logic without equality II: The four-element case, in Proceedings of the 24th International Workshop on Computer Science Logic, Lecture Notes in Comput. Sci. 6247, A. Dawar and H. Veith, eds., Springer, 2010, pp. 426–438. · Zbl 1287.68065
[33] T. Schaefer, The complexity of satisfiability problems, in Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, 1978, pp. 216–226. · Zbl 1282.68143
[34] M. Y. Vardi, The complexity of relational query languages (extended abstract), in Proceedings of the 14th Annual ACM Symposium on Theory of Computing, H. R. Lewis, B. B. Simons, W. A. Burkhard, and L. H. Landweber, eds., 1982, pp. 137–146.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.