(UN-)DECIDABILITY OF GEOMETRIC PROPERTIES OF PICTURES GENERATED BY COLLAGE GRAMMARS

Article type: Research Article

Authors: Drewes, F. | Kreowski, H.-J.

Affiliations: Universität Bremen, Fachbereich 3, D-28334 Bremen (Germany) E-mail: {drewes,kreo}@informatik.uni-bremen.de

Abstract: Collage grammars are based on hyperedge replacement in a geometric environment and provide context-free syntactic devices for the generation of picture languages. An intriguing question is which geometric properties of the generated pictures can be decided by inspecting the generating collage grammars. The results presented in this paper address the question in two respects. (1) The decidability results known for hyperedge replacement grammars generating graph languages, based on the notion of compatibility, can be carried over to collage grammars. Unfortunately, compatible properties seem rare in the geometric setting. In this paper three concrete ones are presented. (2) In some other cases being only a minor extensions of situations for which compatibility is obtained, we can prove undecidability results.

DOI: 10.3233/FI-1996-253407

Journal: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 295-325, 1996