Partial order programming (extended abstract)

ABSTRACT

We introduce a programming paradigm in which statements are constraints over partial orders. A partial order programming problem has the form minimize u subject to u1 ⊒ v1, u2 ⊒ v2, ··· where u is the goal, and u1 ⊒ v1, u2 ⊒ v2, ··· is a collection of constraints called the program. A solution of the problem is a minimal value for u determined by values for u1, v1, etc. satisfying the constraints. The domain of values here is a partial order, a domain D with ordering relation ⊒. The partial order programming paradigm has interesting properties: It generalizes mathematical programming and also computer programming paradigms (logic, functional, and others) cleanly, and offers a foundation both for studying and combining paradigms. It takes thorough advantage of known results for continuous functionals on complete partial orders, when the constraints involve expressions using only continuous and monotone operators. The semantics of these programs coincide with recent results on the relaxation solution method for constraint problems. It presents a framework that may be effective in modeling, or knowledge representation, of complex systems.

REFERENCES

• 1: K. Mani Chandy, Parallel program design: a foundation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 2: Colmerauer, A., "Equations and Inequations on Finite and Infinite Trees," Proc. lntnl. Conf. on Fifth Generation Computer Systems (FGCS'84), pp. 85-99, North- Holland, Tokyo, November 1984.
• 3: Cox, P.T. and T. Pietrzykowski, "Surface Deduction: a uniform mechanism for logic programming," Proc. Symposium on Logic Programming, pp. 220-227, IEEE Computer Society #636, Boston, 1985.
• 4: Dijkstra, E.W. and C.S. Scholten, "Termination Detection for Diffusing Computations," Information Processing Letters, vol. 11, no. 1, pp. 1-4, 29 August 1980.
• 5: M H van Emden, Quantitative deduction and its fixpoint theory, Journal of Logic Programming, v.30 n.1, p.37-53, April 1986
• 6: Isaacson, E. and H.B. Keller, Analysis of Numerical Methods, J. Wiley & Sons, New York, 1966. (Chapter 9, Section 2: Solution of Laplace Difference Equations.)
• 7: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 8: Alan K. Mackworth , Eugene C. Freuder, The complexity of some polynomial network consistency algorithms for constraint satisfaction problems, Artificial Intelligence, v.25 n.1, p.65-74, Jan. 1985 [doi>10.1016/0004-3702(85)90041-4]
• 9: Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
• 10: Parker, D.S., "Partial Order Programming," Technical Report CSD-870067, UCLA Computer Science Dept., Los Angeles, CA 90024-1596, 1987.
• 11: Parker, D.S. and R.R. Muntz, "A Theory of Directed Logic Programs and Streams," in Logic Programming, ed. R.A. Kowalski, K,A. Bowen, pp. 620-650, MIT Press, August 1988.
• 12: David Lorge Parnas, A generalized control structure and its formal definition, Communications of the ACM, v.26 n.8, p.572-581, Aug. 1983 [doi>10.1145/358161.358168]
• 13: Vaughan Pratt, Modeling concurrency with partial orders, International Journal of Parallel Programming, v.15 n.1, p.33-71, Feb. 1986 [doi>10.1007/BF01379149]
• 14: Zimmermann, U., Linear and Combinatorial Optimization in Ordered Algebraic Structures, N~rth-H~lland' New York, 1981. Annals of Discrete Mathematics, vol. I0.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.1 Specifying and Verifying and Reasoning about Programs
          Subjects: Logics of programs

General Terms:
Algorithms, Languages, Theory