Abstract
The independence of negative constraints is a recurring phenomenon in logic programming. This property has in fact a natural interpretation in the context of linear programming that we exploit here to address problems of canonical representations of positive and negative linear arithmetic constraints. Independence allows us to design polynomial time algorithms to decide feasibility and to generate a canonical form, thus avoiding the combinatorial explosion that the presence of negative constraints would otherwise induce. This canonical form allows us to decide by means of a simple syntactic check the equivalence of two sets of constraints and provides the starting point for a symbolic computation system. It has, moreover, other applications and we show in particular that it yields a completeness theorem for constraint propagation and is an appropriate tool to be used in connection with constraint based programming languages.
Research partially supported by NSF Grant CCR-8703086
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Bibliography
I. Adler, The Core of a Linear Program, Technical Report, Department of Operations Research, Berkeley
A. Borning, The Programming Language Aspects of THINGLAB, a Constraint Oriented Simulation Laboratory, ACM Transactions on Programming Languages and Systems 3 (1981) 252–387
G. Bradley, Equivalent Integer Programs, Proceedings of the Fifth International Conference on Operations Research, ed. J. Lawrence, Venice 1969
J. Canny, Some Algebraic and Geometric Computations in PSPACE, STOC, 1988
C.C. Chang and H.J. Keisler, Model Theory, North-Holland 1973
K. Clark, Logic Programming Schemes, Proceedings of 1988 FGCS Conference, Tokyo
A. Colmerauer, Equations and Inequations on Finite and Infinite Trees, Proceedings of 1984 FGCS Conference, Tokyo
A. Colmerauer, An Introduction to Prolog III, Technical Report, Groupe d'Intelligence Artificielle (1987)
E. Davis, Constraint Propagation, Artificial Intelligence 1988
R. Dechter and J. Pearl, Network-based Heuristics for Constraint Satisfaction Problems, Artificial Intelligence, 34 (1987) 1–38
M. Dincbas, P. Van Hentenryck, H. Simonis, A. Aggoun, T. Graf and F. Berthier, The Constraint Logic Programming Language CHIP, Proceedings of the 1988 FGCS Conference, Tokyo
M. Fox, Constraint Directed Search: A Case Study of Job-Shop Scheduling, Morgan Kaufmann, 1988
D. Grigor'ev and N. Vorobjov, Solving Systems of Polynomial Inequalities in Subexponential Time, Journal of Symbolic Computation 5 (1988) 37–64
T. Huynh and C. Lassez, A CLP(R) Options Analysis System, Proceedings of the 1988 Logic Programming Symposium
J. Jaffar and J.L. Lassez, Constraint Logic Programming, Proceedings of POPL 1987, Munich
J. Jaffar and S. Michaylov, Methodology and Implementation of a CLP System, Proceedings of the 1987 Logic Programming Conference, Melbourne, MIT Press
M.H. Karwan, V. Lofti, J. Telgen and S. Zionts, Redundancy in Mathematical Programming, Lecture Notes in Economics and Mathematical Systems 206, Springer-Verlag 1983
J.L. Lassez, M. Maher and K. Marriott, Unification revisited, Foundations of Deductive Databases and Logic Programming, J. Minker editor, Morgan Kaufmann 1988
J-L. Lassez and K. McAloon, Applications of a Canonical Form for Generalized Linear Constraints, Proceeding of FGCS 1988, Tokyo.
J. McClelland and D. Rumelhart, Explorations in Parallel Distributed Processing, MIT Press, 1988
J. Pearl, Constraints and Heuristics, Artificial Intelligence 1988
J. Renegar, A Faster PSPACE ALgorithm for Deciding the Existential Theory of the Reals, FOCS 1988, pp 291–285
A. Schrijver, Theory of Linear and Integer Programming, Wiley 1986
G. Steele and G. Sussman, CONSTRAINTS — A Language for Expressing Almost Hierarchical Descriptions, Artificial Intelligence 1980
M. Stefik, Planning with Constraints (MOLGEN: Part 1), Artificial Intelligence 16 (1984) 111–140
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lassez, J.L., McAloon, K. (1989). Independence of negative constraints. In: Díaz, J., Orejas, F. (eds) TAPSOFT '89. CAAP 1989. Lecture Notes in Computer Science, vol 351. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-50939-9_122
Download citation
DOI: https://doi.org/10.1007/3-540-50939-9_122
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-50939-4
Online ISBN: 978-3-540-46116-6
eBook Packages: Springer Book Archive