University of Bremen Logo  
 
Research Group Theoretical Computer Science
 
HOME
TEAM
TEACHING
RESEARCH

Lehrveranstaltung im Sommersemester 2008

Formale Sprachen: Regelbasierte Bilderzeugung

Hauptstudiumskurs in Theoretischer Informatik

VAK 03-05-H-603.51, Kategorie V, 6 CP/MTG, 4 SWS


Dieser Kurs richtet sich an Studierende, die planen, ihre Abschlussarbeit in der Theoretischen Informatik zu schreiben und dabei intensiv mathematische Methoden zu verwenden oder im Bereich der regelbasierten Bilderzeugung ein bestehendes System zu erweitern bzw. neue Software zu entwickeln.

Inhaltlich setzt sich der Kurs mit regelbasierten Methoden der Bilderzeugung auseinander. Formal wird insbesondere die Erzeugung von Bäumen (d.h. Termen) mit Hilfe von Baum-Grammatiken und -Automaten und ihre Interpretation mit Hilfe von verschiedenen Bild-Algebren vorgestellt. Dabei werden eine Reihe allgemeiner Ideen aus der Theorie der Berechenbarkeit vertieft betrachtet wie z.B. die (Un-)Lösbarkeit von Entscheidungsproblemen oder Hierarchien von Sprachklassen. Beispiele der baumbasierten Bilderzeugung werden mit dem System TREEBAG von Frank Drewes umgesetzt.


Material


Literatur
(Angegebener Download aus dem Universitätsnetz möglich)

Buch:

  • Frank Drewes: Grammatical Picture Generation. A Tree-Based Approach. Springer, Texts in Theoretical Computer Science. An EATCS Series, 2006.
Veröffentlichungen zu baumbasierter Bilderzeugung:
  • Frank Drewes, Hans-Jörg Kreowski, Denis Lapoire: Criteria to Disprove Context-Freeness of Collage Languages. Theoretical Computer Science 290:1445-1458, 2003. (download)
  • Frank Drewes: Tree-Based Generation of Languages of Fractals. Theoretical Computer Science 262:377-414, 2001. (download)
  • Frank Drewes: Tree-Based Picture Generation. Theoretical Computer Science 246:1-51, 2000. (download)
  • Frank Drewes, Renate Klempien-Hinrichs: Picking Knots from Trees. The Syntactic Structure of Celtic Knotwork. In: M. Anderson, P. Cheng, V. Haarslev, editors, Proc. 1st Intl. Conference on Theory and Application of Diagrams 2000, Lecture Notes in Artificial Intelligence 1889, 89-104. Springer, 2000. (download)
  • Frank Drewes: TREEBAG - a Tree-Based Generator for Objects of Various Types. Report 1/98, Univ. Bremen, 1998. (download)
  • Frank Drewes: Treebag - Baum-basierte Generierung und Transformation von Objekten. In J. Dassow, R. Kruse (Hrsg.), Proc. Informatik '98, Informatik Aktuell, pages 47-56. 1998.
  • Frank Drewes: Language Theoretic and Algorithmic Properties of d-dimensional Collages and Patterns in a Grid. Journal of Computer and System Sciences 53:33-60, 1996. (download)
Veröffentlichungen zu Collagengrammatiken:
  • Renate Klempien-Hinrichs, Thomas Meyer, Carolina von Totth: Collage Grammars for Collision-Free Growing of Objects in 3D Scenes. In John L. Pfaltz, Manfred Nagl, Boris Böhlen (Eds.), Applications of Graph Transformations with Industrial Relevance: Second International Workshop (AGTIVE 2003), Lecture Notes in Computer Science 3062, pages 383-397. Springer, 2004. (download)
  • Frank Drewes, Sigrid Ewert, Renate Klempien-Hinrichs, Hans-Jörg Kreowski: Computing Raster Images from Grid Picture Grammars. Journal of Automata, Languages and Combinatorics 8:499-519, 2003.
  • Frank Drewes, Renate Klempien-Hinrichs, Hans-Jörg Kreowski: Table-Driven and Context-Sensitive Collage Languages. Journal of Automata, Languages and Combinatorics 8:5-24, 2003.
  • Frank Drewes, Hans-Jörg Kreowski: Picture generation by collage grammars. In H. Ehrig, G. Engels, H.-J. Kreowski, G. Rozenberg (Eds.), Handbook of Graph Grammars and Computing by Graph Transformation, volume 2, chapter 11, pages 397-457. World Scientific, 1999.
  • Frank Drewes, Hans-Jörg Kreowski: (Un-)Decidability of Geometric Properties of Pictures Generated by Collage Grammars. Fundamenta Informaticae 25:295-325, 1996.
  • Frank Drewes, Annegret Habel, Hans-Jörg Kreowski, Stefan Taubenberger: Generating self-affine fractals by collage grammars. Theoretical Computer Science 145:159-187, 1995. (download)


Voraussetzungen

  • Grundstudium Informatik, insbesondere die Lehrveranstaltungen Mathematik 1/2 und Theoretische Informatik 1/2.


Lehrveranstaltende

Prof. Dr. Renate Klempien-Hinrichs Dipl.-Inf. Caroline von Totth
Raum: OAS 3007 Raum: OAS 3006
Telefon: 218-8791 Telefon: 218-8792
rena@informatik... caro@informatik...


Zeit und Raum

Di 10 - 12 OAS 3000 Terminänderung!
Mi 13 - 15 OAS 3000 Beginn am 9.4.2008


Internes


Mail Address
University of Bremen
Dept. for Math. &
Computer Science

P.O. Box 330 440
28334 Bremen
Germany

Physical Address
Bibliothekstrasse 5
MZH 5130
28359 Bremen

Phone
++49(421)218 64451

Email (Secr.)
Helga Reinermann

helga@tzi.de