×

Found 121 Documents (Results 1–100)

Constraint satisfaction problem: what makes the problem easy. (English) Zbl 07823032

Beliaev, Dmitry (ed.) et al., International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6–14, 2022. Volume 3. Sections 1–4. Berlin: European Mathematical Society (EMS). 1530-1552 (2023).
PDFBibTeX XMLCite
Full Text: DOI

On the relational width of first-order expansions of finitely bounded homogeneous binary cores with bounded strict width. (English) Zbl 1498.03071

Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8–11, 2020. New York, NY: Association for Computing Machinery (ACM). 958-971 (2020).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Temporal constraint satisfaction problems in fixed-point logic. (English) Zbl 1498.08003

Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8–11, 2020. New York, NY: Association for Computing Machinery (ACM). 237-251 (2020).
MSC:  08A70 03B70 08A40
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximate counting CSP seen from the other side. (English) Zbl 1499.68238

Rossmanith, Peter (ed.) et al., 44th international symposium on mathematical foundations of computer science, MFCS 2019, Aachen, Germany, August 26–30, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 138, Article 60, 14 p. (2019).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Dismantlability, connectedness, and mixing in relational structures. (English) Zbl 1503.08001

Baier, Christel (ed.) et al., 46th international colloquium on automata, languages, and programming, ICALP 2019, Patras, Greece, July 9–12, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 132, Article 29, 15 p. (2019).
PDFBibTeX XMLCite
Full Text: DOI

Expressive power, satisfiability and equivalence of circuits over nilpotent algebras. (English) Zbl 1510.68075

Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 17, 15 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

Consistency for counting quantifiers. (English) Zbl 1510.68031

Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 11, 13 p. (2018).
MSC:  68Q25 03B70 08A70
PDFBibTeX XMLCite
Full Text: DOI

Surjective H-colouring over reflexive digraphs. (English) Zbl 1485.68191

Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 96, Article 49, 14 p. (2018).
PDFBibTeX XMLCite
Full Text: DOI

Constraint satisfaction problems over numeric domains. (English) Zbl 1482.68162

Krokhin, Andrei (ed.) et al., The constraint satisfaction problem: complexity and approximability, Dagstuhl seminar 15301, July 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. Dagstuhl Follow-Ups 7, 79-111 (2017).
PDFBibTeX XMLCite
Full Text: DOI

Hybrid VCSPs with crisp and valued conservative templates. (English) Zbl 1457.68130

Okamoto, Yoshio (ed.) et al., 28th international symposium on algorithms and computation, ISAAC 2017, December 9–12, 2017, Phuket, Thailand. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 92, Article 65, 13 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI

The complexity of quantified constraints using the algebraic formulation. (English) Zbl 1441.68087

Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 27, 14 p. (2017).
MSC:  68Q25 08A70 68R07
PDFBibTeX XMLCite
Full Text: DOI arXiv

Time complexity of constraint satisfaction via universal algebra. (English) Zbl 1441.68093

Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 17, 15 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

A complexity dichotomy for poset constraint satisfaction. (English) Zbl 1402.68099

Vollmer, Heribert (ed.) et al., 34th symposium on theoretical aspects of computer science (STACS 2017), Hannover, Germany, March 8–11, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-028-6). LIPIcs – Leibniz International Proceedings in Informatics 66, Article 47, 12 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. (English) Zbl 1401.68108

Proceedings of the 2016 31st annual ACM/IEEE symposium on logic in computer science, LICS 2016, New York City, NY, USA, July 5–8, 2016. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4391-6). 615-622 (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Constraint satisfaction problems for reducts of homogeneous graphs. (English) Zbl 1388.68102

Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 119, 14 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Quantified constraint satisfaction on monoids. (English) Zbl 1369.68219

Regnier, Laurent (ed.) et al., 25th EACSL annual conference and 30th workshop on computer science logic, CSL’16, Marseille, France, August 29 – September 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-022-4). LIPIcs – Leibniz International Proceedings in Informatics 62, Article 15, 14 p. (2016).
PDFBibTeX XMLCite
Full Text: DOI

The complexity of constraint satisfaction problems (invited talk). (English) Zbl 1355.68111

Mayr, Ernst W. (ed.) et al., 32nd international symposium on theoretical aspects of computer science, STACS’15, Garching, Germany, March 4–7, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-78-1). LIPIcs – Leibniz International Proceedings in Informatics 30, 2-9 (2015).
MSC:  68Q25 08A70
PDFBibTeX XMLCite
Full Text: DOI

A new line of attack on the dichotomy conjecture. (English) Zbl 1304.68076

Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 725-734 (2009).
MSC:  68Q25 08A40 68Q17
PDFBibTeX XMLCite
Full Text: DOI Link

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

Software