Solving linear, min and max constraint systems using CLP based on relational interval arithmetic.

*(English)*Zbl 0902.68028Summary: Many real problems can be treated as constraint satisfaction problems (CSPs), a type of problem for which efficient tools have been developed. Computing the maximum timing separations between the events of a timing specification falls into this category. In particular, CLP (BNR) is a constraint logic programming language which seems well suited to the problem, allowing to draw from the advantages of both CSPs and logic programming. Consistency techniques used for solving general CSPs usually produce approximate answers (partial consistency). However, for some specific timing specifications, that is, systems of strictly linear constraints, systems of either max-only or min-only constraints, and systems where linear and either max or min constraints intermix, we show that global consistency can be achieved using CLP based on relational interval arithmetic.

##### MSC:

68N17 | Logic programming |

##### Keywords:

constraint satisfaction problems##### Software:

Algorithm 97
PDF
BibTeX
Cite

\textit{P. Girodias} et al., Theor. Comput. Sci. 173, No. 1, 253--281 (1997; Zbl 0902.68028)

Full Text:
DOI

##### References:

[1] | Alefeld, G.; Herzberger, J., Introduction to interval computations, (1983), Academic Press New York |

[2] | Amon, T.; Borriello, G., An approach to symbolic timing verification, (), 410-413 |

[3] | Amon, T.; Hulgaard, H.; Borriello, G.; Burns, S., Timing analysis of current systems, () |

[4] | F. Benhamou and W.J. Older. Applying interval arithmetic to real, integer and Boolean constraints, J. Logic Programming, forthcoming. · Zbl 0882.68032 |

[5] | Brozowski, J.A.; Gahlinger, T.; Mavaddat, F., Consistency and satisfiability of waveform timing specifications, Networks, 21, 91-107, (1991) · Zbl 0713.90042 |

[6] | Cleary, J.G., Logical arithmetic, Future comput. systems, 2, 2, 125-149, (1987) |

[7] | Colmerauer, A., An introduction to prolog III, Comm. ACM, 33, 7, 69-90, (July 1990) |

[8] | Dechter, R., From local to global consistency, (), 231-237 |

[9] | Deville, Y.; Henteryck, P.V., An efficient arc consistency algorithm for a class of CSP problems, (), 325-330 |

[10] | Floyd, R.W., Algorithm 97: shortest path, Cacm, 5, 6, 345, (June 1962) |

[11] | Gahlinger, T., Coherence and satisfiability of waveform timing specifications, () · Zbl 0713.90042 |

[12] | Jaffar, J.; Lassez, J.L., Constraint logic programming, (), 111-119 |

[13] | Jaffar, J.; Maher, M., Constraint logic programming: a survey, J. logic programming, 19/20, 503-581, (1994) |

[14] | Jeavons, P.; Cohen, D.; Gyssens, M., A unifying framework for tractable constraints, (), 276-291 |

[15] | Jyu, H.F.; Devadas, S.; Keutzer, K.W., Statistical timing analysis of combinational logic circuits, IEEE trans. on very large scale integration (VLSI) systems, 1, 2, 126-137, (June 1993) |

[16] | Khordoc, K.; Dufresne, M.; Cerny, E.; Babkine, P.-A.; Silburt, A., Integrating behaviour and timing in executable specifications, (), 385-402 |

[17] | Leler, W., Constraint programming languages: their specification and generation, (1988), Addison-Wesley Reading, MA |

[18] | Lhomme, O., Consistency techniques for numeric csps, () · Zbl 1015.68178 |

[19] | Mackworth, A., Consistency in networks of relations, Artificial intelligence, 8, 1, 99-118, (1977) · Zbl 0341.68061 |

[20] | McMillan, K.; Dill, D., Algorithms for interface timing verification, (), 48-51 |

[21] | Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Information science, 7, 2, 95-132, (1974) · Zbl 0284.68074 |

[22] | Moore, R.E., Interval analysis, (1966), Prentice-Hall Englewood Cliffs, NJ · Zbl 0176.13301 |

[23] | Moore, R.E., Methods and applications of interval analysis, Studies in applied matthematics, (1979), Philadelphia · Zbl 0417.65022 |

[24] | Older, W.; Vellino, A., Constraint arithmetic on real intervals, (), 175-195 |

[25] | Van Beek, P., On the minimality and decompsability of constraint networks, (), 447-452 |

[26] | Vanbekbergen, P.; Goossens, G.; De Man, H., Specification and analysis of timing constraints in signa transitions graphs, (), 302-306 |

[27] | Vandecasteele, H.; De Schreye, D., Implementing a finite-domain CLP-language on top of prolog: a transformation approach, (), 84-98 |

[28] | Van Hentenryck, P., Constraint satisfaction in logic programming, () · Zbl 0782.68028 |

[29] | Walkup, E.A.; Borriello, G., Interface timing verification with applications to synthesis, () |

[30] | Waltz, D.L., Generating semantic descriptions from drawings of scenes with shadows, () |

[31] | Warshall, S., A theorem on Boolean matrices, Jacm, 9, 11-12, (1962) · Zbl 0118.33104 |

[32] | Yen, T.Y.; Ishii, A.; Casavant, A.; Wolf, W., Efficient algorithms for interface timing verification, () |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.