Abstract
A positive temporal template (or a positive temporal constraint language) is a relational structure whose relations can be defined over a dense linear order of rational numbers using a relational symbol ≤, logical conjunction and disjunction.
We provide a complexity characterization for quantified constraint satisfaction problems (QCSP) over positive temporal languages. The considered QCSP problems are decidable in LOGSPACE or complete for one of the following classes: NLOGSPACE, P, NP, PSPACE. Our classification is based on so-called algebraic approach to constraint satisfaction problems: we first classify positive temporal languages depending on their surjective polymorphisms and then give the complexity of QCSP for each obtained class.
The complete characterization is quite complex and does not fit into one paper. Here we prove that QCSP for positive temporal languages is either NP-hard or belongs to P and we give the whole description of the latter case, that is, we show for which positive temporal languages the problem QCSP is in LOGSPACE, and for which it is NLOGSPACE-complete or P-complete. The classification of NP-hard cases is given in a separate paper.
Work partially supported by Polish Ministry of Science and Education grant 3 T11C 042 30.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832–843 (1983)
Bodirsky, M.: Constraint Satisfaction Problems with Infinite Domains. PhD thesis, Humboldt-Universität zu Berlin (2004), http://www2.informatik.hu-berlin.de/~bodirsky/publications/diss.html
Bodirsky, M., Chen, H.: Qualitative temporal and spatial reasoning revisited. In: Duparc, J., Henzinger, T.A. (eds.) CSL 2007. LNCS, vol. 4646. Springer, Heidelberg (2007)
Bodirsky, M., Chen, H.: Quantified equality constraints. In: 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), Proceedings. IEEE Computer Society Press, Los Alamitos (2007)
Bodirsky, M., Kára, J.: A fast algorithm and lower bound for temporal reasonning, http://www2.informatik.hu-berlin.de/~bodirsky/en/publications.php
Bodirsky, M., Kára, J.: The complexity of equality constraint languages. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) CSR 2006. LNCS, vol. 3967, pp. 114–126. Springer, Heidelberg (2006)
Bodirsky, M., Kára, J.: The complexity of temporal constraint satisfaction problems. In: Ladner, R.E., Dwork, C. (eds.) Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 29–38. ACM, New York (2008)
Boerner, F., Bulatov, A., Jeavons, P., Krokhin, A.: Quantified constraints: Algorithms and complexity. In: Proceedings of CSL and the 8th Kurt Gödel Colloquium. LNCS. Springer, Heidelberg
Bulatov, A.A.: A dichotomy theorem for constraints on a three-element set. In: Proceedings 43rd IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp. 649–658 (2002)
Charatonik, W., Wrona, M.: Quantified positive temporal constraints. In: Kaminski, M., Martini, S. (eds.) CSL 2008. LNCS, vol. 5213, pp. 94–108. Springer, Heidelberg (2008)
Cohen, D., Jeavons, P.: The complexity of constraints languages. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming. Elsevier, Amsterdam (2006)
Feder, T., Vardi, M.Y.: Monotone monadic SNP and constraint satisfaction. In: Proceedings of 25th ACM Symposium on the Theory of Computing (STOC), pp. 612–622 (1993)
Fisher, M., Gabbay, D., Vila, L.: Handbook of Temporal Reasoning in Artificial Intelligence. Elsevier, Amsterdam (2005)
Hodges, W.: A shorter model theory. Cambridge University Press, Cambridge (1997)
Jeavons, P.G., Cohen, D.A., Gyssens, M.: Closure properties of constraints. Journal of the ACM 44, 527–548 (1997)
Krokhin, A., Jeavons, P., Jonsson, P.: A complete classification of complexity in Allens algebra in the presence of a non-trivial basic relation. In: Proceedings of the 17th International Joint Conference on Artificial Intelligence, pp. 83–88. Morgan Kaufmann, San Francisco (2001)
Möhring, R.H., Skutella, M., Stork, F.: Scheduling with and/or precedence constraints. SIAM J. Comput. 33(2), 393–415 (2004)
Renz, J., Nebel, B.: Qualitative spatial reasoning using constraint calculi. In: Aiello, M., Pratt-Hartmann, I., van Benthem, J. (eds.) Handbook of Spatial Logics. Springer, Heidelberg (2007)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings 10th ACM Symposium on Theory of Computing, STOC 1978, pp. 216–226 (1978)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Charatonik, W., Wrona, M. (2008). Tractable Quantified Constraint Satisfaction Problems over Positive Temporal Templates. In: Cervesato, I., Veith, H., Voronkov, A. (eds) Logic for Programming, Artificial Intelligence, and Reasoning. LPAR 2008. Lecture Notes in Computer Science(), vol 5330. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-89439-1_38
Download citation
DOI: https://doi.org/10.1007/978-3-540-89439-1_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-89438-4
Online ISBN: 978-3-540-89439-1
eBook Packages: Computer ScienceComputer Science (R0)