Basic Analysis of Structure Rewriting Systems

Speaker(s)

Łukasz Kaiser (Aachen)

Date

Feb. 18, 2009, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

A single state of an analyzed system has, in practice, often a complex structure in itself, while in theory it is usually simple in some sense, e.g. it can be a tree. We show how the interpretation of structures of bounded clique-width in the binary tree allows to apply tree automata to the analysis of a basic kind of systems where states are arbitrary relational structures. A few new questions emerge for more general systems, and we discuss them as well.

---