Algebarski pristup problemu zadovoljenja ograničenja
Ključne reči:
Problem zadovoljenja ograničenja, Klonovi operacija
Apstrakt
U ovom radu bavićemo se jednim NP-kompletnim problemom - problemom zadovoljenja ograničenja ili, skraćeno, CSP (od engleskog Constraint Satisfaction Problem), koji se određenim restrikcijama može sveti na P-problem.
Reference
[1] Burris S., Sankappanavar H. P., A Course in Universal Algebra, New York, 1981.
[2] Bulatov A. A., Krokhin A. A., Jeavons P., Constraint Satisfaction Problems and Finite Algebras, ICALP 2000: 272--282.
[3] Cohen D., Cooper M.C., Jeavons P., Constraint, Consistency and Closure, Artificial Intelligence, 101:251--265, 1998.
[4] Jeavons P., On the Algebraic Structure of Combinatorial Problems, Theoretical Computer Science, 200:185-204, 1998.
[5] Zhuk D., The Proof of CSP Dichotomy Conjecture, https://arxiv.org/abs/1704.01914
[6] Barto L., Krokhin A., Willard R., Polymorphisms, and How to Use Them, http://drops.dagstuhl.de/-opus/volltexte/2017/6959/pdf/DFU-Vol7-15301-1.pdf
[7] Barto L., Kozik M., Absorption in Universal Algebra and CSP, The Constraint Satisfaction Problem, Dagstuhl Follow-Ups 7, Schloss Dagstuhl - Leibniz- Zentrum fuer Informatik, 2017: 45-77.
[8] Janičić P., Matematička logika u računarstvu, Beograd, 2008.
[9] Aichhinger E., Basics of clone theory, http://www.algebra.unilinz.ac.at/Students/UniversalAlgebra/s11/clonebasics2.pdf
[10] Grulović M., Osnovi teorije grupa, Novi Sad, 1997.
[11] Börner F., Basics of Galois connections, Complexity of Constraints, volume 5250 of Lecture Notes in Computer Science, Springer, 2008.
[2] Bulatov A. A., Krokhin A. A., Jeavons P., Constraint Satisfaction Problems and Finite Algebras, ICALP 2000: 272--282.
[3] Cohen D., Cooper M.C., Jeavons P., Constraint, Consistency and Closure, Artificial Intelligence, 101:251--265, 1998.
[4] Jeavons P., On the Algebraic Structure of Combinatorial Problems, Theoretical Computer Science, 200:185-204, 1998.
[5] Zhuk D., The Proof of CSP Dichotomy Conjecture, https://arxiv.org/abs/1704.01914
[6] Barto L., Krokhin A., Willard R., Polymorphisms, and How to Use Them, http://drops.dagstuhl.de/-opus/volltexte/2017/6959/pdf/DFU-Vol7-15301-1.pdf
[7] Barto L., Kozik M., Absorption in Universal Algebra and CSP, The Constraint Satisfaction Problem, Dagstuhl Follow-Ups 7, Schloss Dagstuhl - Leibniz- Zentrum fuer Informatik, 2017: 45-77.
[8] Janičić P., Matematička logika u računarstvu, Beograd, 2008.
[9] Aichhinger E., Basics of clone theory, http://www.algebra.unilinz.ac.at/Students/UniversalAlgebra/s11/clonebasics2.pdf
[10] Grulović M., Osnovi teorije grupa, Novi Sad, 1997.
[11] Börner F., Basics of Galois connections, Complexity of Constraints, volume 5250 of Lecture Notes in Computer Science, Springer, 2008.
Objavljeno
2019-01-30
Sekcija
Matematika u tehnici
