ALGORITHMS OF SOLVING SYSTEMS OF LINEAR DIOPHANTINE EQUATIONS IN THE CONTEXT OF CONSTRAINT PROBLEM. PART 1

Authors

  • Сергій Лук'янович Кривий Kiev National University of Taras Shevchenko

Keywords:

Diofantine equations, constraint satisfaction problem

Abstract

The algorithms for computation of minimal supported set of solutions for systems of linear Diophantine homogeneous equations over set of natural numbers and basis of systems of linear Diophantine homogeneous and inhomogeneous equations in ring and field of remainders on modulo of a number. This algorithms consider in context of solving of general constraint satisfaction problem.

Author Biography

Сергій Лук'янович Кривий, Kiev National University of Taras Shevchenko

Doctor of Sciences, Professor of Information Systems Department of the Kiev National University of Taras Shevchenko. Scientific interests: discrete mathematics, automata theory of Petri nets, analysis of natural language texts.

References

Донец Г. А. Решение задачи о сейфе на (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.

Downloads

Issue

Vol. 17 No. 1 (2014)

Section

THEORETICAL BASES OF SOFTWARE ENGINEERING