АЛГОРИТМИ РОЗВ'ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ ДІОФАНТОВИХ РІВНЯНЬ В КОНТЕКСТІ ПРОБЛЕМИ ВИКОНУВАНОСТІ ОБМЕЖЕНЬ. Ч. 2
Ключові слова:
Діофантові рівняння, виконуваність обмежень, критерій сумісностіАнотація
Запропоновано алгоритми побудови мінімальної породжуючої множини розв’язків систем лінійних однорідних рівнянь в множині натуральних чисел і базису множини розв’язків системи лінійних однорідних і неоднорідних діофантових рівнянь у кільцях і полях лишків за модулем деякого числа. Ці алгоритми розглядаються в контексті розв’язання проблеми виконуваності системи обмежень.Посилання
Донец Г. А. Решение задачи о сейфе на (0,1)-матрицах // КиСА. – 2002. – № 1. – С. 98 – 105.
Донец Г. А., Самер И. М. Альшаламе Решение задачи о построении линейной мозаики. Теория оптимальных решений. – К.: Ин-т кибернетики им. В. М. Глушкова НАН Украины. – 2005. – С. 15 – 24.
Крывый С. Л. Алгоритмы решения систем линейных диофантовых уравнений в целочисленных областях // КиСА. – 2006. – № 2. – С. 3 – 17.
Крывый С. Л. Алгоритмы решения систем линейных диофантовых уравнений в целочисленных областях // Кибернетика и системный анализ. – 2006. – № 2. – С. 3 – 17.
Крывый С. Л. Алгоритмы решения систем линейных диофантовых уравнений в полях вычетов // Кибернетика и системный анализ. – 2007. – № 2. – С. 15 – 23.
Крывый С.Л. О некоторых методах решения и критериях совместности систем линейных диофантовых уравнений в области натуральных чисел. // Кибернетика и системный анализ. – 1999. – N 4. – С. 12 – 36.
Крывый С. Л. Критерий совместности систем линейных диофантовых уравнений над множеством натуральных чисел // Допов. НАНУ. – 1999. – № 5. – С.107 – 112.
Крывый С.Л. О некоторых методах решения и критериях совместности систем линейных диофантовых уравнений в области натуральных чисел // КиСА. – 1999. – № 4. – С. 12 – 36.
Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии. – М.: МЦНМО. – 2002. – 103 с.
Чугаенко А.В. О реализации TSS-алгоритма // Управляющие системы и машины. – 2007. – N 3. – С. 14 – 26.
Baader F., Ziekmann J. Unification theory Handbook of Logic in Artificial Intelligence and Logic Programming. – Oxford University Press. – 1994. – P. 1 – 85.
Allen R., Kennedy K. Automatic translation of FORTRAN program to vector form // ACM Transactions on Programming Languages and systems. – 1987. – V. 9, N4. – P. 491 – 542.
Contejan E., Ajili F. Avoiding slack variables in the solving of linear diophantine equations and inequations // Theoretical Comp. Science. – 1997. – V. 173. – P. 183 – 208.
Pottier L. Minimal solution of linear diophantine systems: bounds and algorithms // In Proc. of the Fourth Intern. Conf. on Rewriting Techniques and Applications. –Como. – Italy. – 1991. – P. 162 – 173.
Domenjoud E. Outils pour la deduction automatique dans les theories associativescommutatives // Thesis de Doctorat d'Universite: Universite de Nancy I. –1991.
Clausen M., Fortenbacher A. E_cient solution of linear diophantine equations // J. Symbolic Computation. – 1989. – V. 8, N. 1,2. – P. 201 – 216.
Romeuf J. F. A polinomial Algorithm for Solvin systems of two linear Diophantine equations // TCS. – 1990. – 74, N3. – P. 329 – 340.
Filgueiras M.,Tomas A.P. A Fast Method for Finding the Basis of Non-negative Solutions to a Linear Diophantine Equation // J. Symbolic Computation. – 1995. – 19, N2. – P. 507 – 526.
Comon H. Constraint solving on terms: Automata techniques (Preliminary lecture notes) // Intern. Summer School on Constraints in Computational Logics: Gif-sur-Yvette, France, September 5 – 8. – 1999. – 22 p.
Bulatov A. H-coloring dichotomy revisited. Theoretical Computer Science. – 2005. – V. 349. – N 1. – P. 31 – 39.
Bulatov A., Krokhin A., Jeavons P.G. Classifying the complexity of constraints using finite algebras // SIAM Journ. Computing. – 2005. – v. 34. – N 3. – P. 720 – 742.
Creignou N., Khanna S., Sudan M. Complexity Classification of Boolean Constraint Satisfaction Problems // SIAM Monographs on Discrete Mathematics and Applications: Society for Industrial and Applied Mathematics. Philadelphia. PA. – 2001. – V. 7. – 347 p.
Drakengren T., Jonsson P. A complete classification of tractability in Allen's algebra relative to subsets of basic relations // Artificial Intelligence. – 1998. – V. 106. – P. 205 – 219.
Jeavons P.G. Constructing constraints // In Proceed. 4th Intern. Conf. on Constraint Programming – CP'98 (Pisa,October 1998). – 1998. – V. 1520. – Lecture Notes in Comput. Science: Springer-Verlag. – P. 2 – 16.
Jeavons P.G. On the algebraic strukture of combinatorial problems. Theoretical Computer Science. – 1998. – V. 200. – P. 185 – 204.
Jeavons P.G., Cohen D.A., Gyssens M. Closure properties of constraints // Journ. of the ACM. – 1997. – V. 44. – P. 527 – 548.
Jeavons P.G., Cohen D.A., Gyssens M. How to determine the expressive power of constraints. Constraints. – 1999. – V. 4. – P. 113 – 131.
Krokhin A., Jeavons P.G., Jonsson P. Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra // Journ. of the ACM. – 2003. – V. 50. – P. 591 – 640.
Krokhin A., Jeavons P.G., Jonsson P. Constraint satisfaction problems on intervals and lengths // SIAM Journ. On Discrete Mathematics. – 2004. – V. 17. – P. 453 – 477.
Nebel B., Burkert J. Reasoning about temporal relations: a maximal tractable subclass of Allen's interval algebra // Journal of the ACM. – 1995. – V. 42. – P. 43 – 66.
Renz J., Nebl B. On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus // Artificial Intelligence. – 1999. – V.108. – P. 69 – 123.
Cooper M. C., Cohen D.A., Jeavons P.G. Caracterising tractable constraints // Artificial Intelligence. – 1994. – V. 65. – P. 347 – 361.
Schaefer T. J. The Complexity of satisfability problems // In Propc. 10-th ACM Symposium on Theory of Computing, STOC'78. 1978. – P. 216 – 226.
Papadimitriou C.H. Computational complexity. Addison-Wesley. – 1994. – 462 p.
Poschel R., Kaluznin L.A. Funktionen und Relationenalgebren. DVW. Berlin. – 1979. – 262 p.
Post E.L. The two-valued iterative systems of mathematical logic. Annals Mathematical Studies. – Princeton University Press. – 1941. – 26 p.
Szendrei A. Clones in universal algebras // Seminares de Mathematigues Superieures. University of Montreal. – 1986. – P. 253 – 262.
