An efficient algorithm for the solution of hierarchical networks of constraints
- 193 Downloads
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.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.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
- 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.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.Habel A., Kreowski H. J., "Some structural aspects of hypergraph languages generated by hyperedge replacement", Internal Report, Univ. Bremen, Oct. 1985.Google Scholar
- 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
- 13.Rossi F., "Specifica mediante reti di vincoli gerarchiche", Master Thesis, Computer Science Dept., Univ. of Pisa, Italy, June 1986.Google Scholar
- 14.Seidel R., "A new method for solving constraint satisfaction problems", Proc. IJCAI 1981, pp.338–342.Google Scholar
- 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.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