Language Theoretic and Algorithmic Properties ofd-dimensional Collages and Patterns in a Grid

摘要

Language theoretic aspects and algorithmic properties of particular classes of context-free collage languages and of patterns generated by iterated function systems are studied. These classes are defined by restricting the allowed transformations to a sort of similarity transformations called grid transformations. It turns out that, thanks to this restriction, the language classes have nice closure properties, and non-trivial questions concerning the generated pictures can be decided.