An efficient algorithm for the solution of hierarchical networks of constraints

  • Ugo Montanari
  • Francesca Rossi
Part II Technical Contributions
Part of the Lecture Notes in Computer Science book series (LNCS, volume 291)


Networks of constraints are a simple model, useful for describing large classes of problems in picture recognition and scene analysis, in the representation of physical systems and in the specification of software systems.

We consider particular classes of networks of constraints called hierarchical networks. A class of hierarchical networks is included in the language generated by a context free, hyperarc rewriting grammar. For such classes of networks, an efficient solution algorithm is given. The sequential version of the algorithm has a time complexity which is linear in the size of the given network, while the parallel version is logarithmic, provided that the syntactic tree is balanced.

Our restriction to hierarchical networks of constraints is not critical; in fact such networks occur often in practice since they are naturally generated by decomposition system design methods.


  1. 1.
    Balzer R., "A 15 year perspective on automatic programming", IEEE Transaction on Software Engineering SE-11(11), Nov.1985, pp.1257–1268.Google Scholar
  2. 2.
    Balzer R., Goldman N., Wile D., "Operational specification as the basis for rapid prototyping", in Proc. of the Second Software Engineering Symposium: Workshop on Rapid Prototyping, ACM SIGSOFT, April 1982.Google Scholar
  3. 3.
    Bobrow D. G., "Qualitative reasoning about physical system: an introduction", Artificial Intelligence 24, 1984, pp. 1–5.CrossRefGoogle Scholar
  4. 4.
    De Kleer J., "How circuits work", Artificial Intelligence 24, 1984, pp. 205–280.CrossRefGoogle Scholar
  5. 5.
    De Kleer J., Brown J. S., "A qualitative reasoing based on confluences", Artificial Intelligence 24, 1984, pp. 7–83.CrossRefGoogle Scholar
  6. 6.
    Ehrig H., "Introduction to the algebraic theory of graph grammars (a survey)", Proc. Int. Workshop on Graph Grammars, LNCS 73, Springer Verlag, Claus, Ehrig, Rozenberg ed., Bad Honnef, Nov. 1978, pp.1–69.Google Scholar
  7. 7.
    Habel A., Kreowski H. J., "On context-free graph languages generated by edge replacement", Proc. Int. Workshop on Graph Grammars, LNCS 153, Springer Verlag, Ehrig, Nagl, Rozenberg ed., Haus Ohrbeck, Oct. 1982, pp.143–158.Google Scholar
  8. 8.
    Habel A., Kreowski H. J., "Some structural aspects of hypergraph languages generated by hyperedge replacement", Internal Report, Univ. Bremen, Oct. 1985.Google Scholar
  9. 9.
    Lucas, "On the versatility of knowledge rapresentation", in: E. Neuhold, ed., Proc. IFIP Working Conference "The role of abstract models in information processing", Wien, Jan. 1985, North Holland.Google Scholar
  10. 10.
    Mackworth A. K., "Consistency in networks of relations", Artificial Intelligence 8, 1, 1977, pp. 99–118.CrossRefGoogle Scholar
  11. 11.
    Mackworth A. K., Freuder E. C., "The complexity of some polynomial network consistency algorithms for constraints satisfaction problems", Artificial Intelligence 25, 1985, pp. 65–74.CrossRefGoogle Scholar
  12. 12.
    Montanari U., "Networks of constraints: fundamental properties and application to picture processing", Information Sciences 7, 1974, pp. 95–132.CrossRefGoogle Scholar
  13. 13.
    Rossi F., "Specifica mediante reti di vincoli gerarchiche", Master Thesis, Computer Science Dept., Univ. of Pisa, Italy, June 1986.Google Scholar
  14. 14.
    Seidel R., "A new method for solving constraint satisfaction problems", Proc. IJCAI 1981, pp.338–342.Google Scholar
  15. 15.
    Sussman G. J., Steele G. L. Jr., "CONSTRAINTS — A language for expressing almost-hierarchical descriptions", Artificial Intelligence 14, 1980, pp.1–39.CrossRefGoogle Scholar
  16. 16.
    Waltz D. L., "Understanding line drawings of scenes with shadows", in: Winston P. H., ed., The psychology of computer vision, Mc Graw-Hill, New York 1975, pp.19–91.Google Scholar
  17. 17.
    Waltz D. L., "Automata theoretic approach to visual processing", in Yeh R. T. ed., Applied computation theory, Englewood Cliffs, N.J., Prentice-Hall, 1975.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1987

Authors and Affiliations

  • Ugo Montanari
    • 1
  • Francesca Rossi
    • 1
    • 2
  1. 1.Dipartimento di InformaticaUniversità di PisaPisaItaly
  2. 2.Selenia S.p.A.RomaItaly

Personalised recommendations