Abstract
Criteria of compatibility of a system of linear Diophantine equations, strict inequations, and nonstrict inequations are considered. Upper bounds for components of a minimal set of solutions and algorithms of construction of minimal generating sets of solutions for all types of systems are given. These criteria and the corresponding algorithms for constructing a minimal supporting set of solutions can be used in solving all the considered types of systems and systems of mixed types.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
J. Lloyd, Foundations of Logic Programming, Springer-Verlag, New York (1987).
B. Buchberger, G. Collins, and R. Loos (eds.), Computer Algebra: Symbolic and Algebraic Computations [Russian translation], Mir, Moscow (1986).
F. Baader and J. Ziekmann, “Unification theory,” in: Handbook of Logic in Artificial Intelligence and Logic Programming, University Press, Oxford (1994), pp. 1–85.
R. Allen and K. Kennedy, “Automatic translation of a FORTRAN program to a vector form,” ACM Trans. on Programming Languages and Systems, 9, No. 4, 491–542 (1987).
E. Contenjean and H. Devie, “Solving systems of linear Diophantine equations,” in: Proc. 3rd Workshop on Unification, University of Kaiserslautern, Lambrecht (1989).
L. Pottier, “Minimal solution of linear Diophantine systems: bounds and algorithms,” in: Proc. 4th Intern. Conf. on Rewriting Techniques and Applications, Como, Italy (1991), pp. 162–173.
E. Domenjoud, “Outils pour la deduction automatique dans les theories associatives-commutatives,” Ph. D. Thesis, Universite de Nancy I (1991).
S. A. Stepanov, “Diophantine equations,” Algebra, Mathematical Logic, Number Theory, and Topology, Trans. MIAN, 168, 31–45 (1984).
M. Clausen and A. Fortenbacher, “Efficient solution of linear Diophantine equations,” J. Symbolic Computation, 8, Nos. 1, 2, 201–216 (1989).
J. F. Romeuf, “A polynomial algorithm foar solving systems of two linear Diophantine equations,” TCS, 74, No. 3, 329–340 (1990).
M. Filgueiras and A. P. Tomas, “A fast method for finding the basis of nonnegative solutions to a linear Diophantine equation,” J. Symbolic Computation, 19, No. 2, 507–526 (1995).
H. Comon, “Constraint solving on terms: Automata techniques (Preliminary lecture notes),” Intern. Summer School on Constraints in Computational Logics, Gif-sur-Yvette, France, (1999).
R. Alur and D. L. Dill, “A theory of timed automata,” TCS, 126, 183–235 (1994).
S. L. Kryvyi, “A criterion of compatibility of systems of linear Diophantine equations over the set of natural numbers,” Dop. NAN Ukr., No. 5, 107–112 (1999).
S. L. Kryvyi, “Methods of solution and criteria of compatibility of systems of linear Diophantine equations over the set of natural numbers, Kibern. Sist. Anal., No. 4, 12–36 (1999).
S. L. Kryvyi, V. V. Bura, N. A. Borak, and A. V. Chugayenko, “Implementation of algorithms of checking the compatibility of systems of linear Diophantine equations over the set of natural numbers,” USiM, No. 3, 26–32 (1999).
E. Contejan and F. Ajili, “Avoiding slack variables in solving linear Diophantine equations and inequations,” Theor. Comp. Sci., 173, 183–208 (1997).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kryvyi, S.L. Compatibility of Systems of Linear Constraints over the Set of Natural Numbers. Cybernetics and Systems Analysis 38, 17–29 (2002). https://doi.org/10.1023/A:1015531813214
Issue Date:
DOI: https://doi.org/10.1023/A:1015531813214
- system of linear Diophantine equations
- homogeneous linear Diophantine equations
- nonhomogeneous linear Diophantine equations
- system of linear Diophantine constraints
- homogeneous linear Diophantine constraints
- nonhomogeneous linear Diophantine constraints
- linear Diophantine inequations
- homogeneous linear Diophantine inequations
- criteria of compatibility
- truncated set of solutions