On simulation and trace inclusion

Prelegent(ci)

Marek Grabowski

Afiliacja

Uniwersytet Warszawski

Termin

19 maja 2010 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

Simulation preorder and trace inclusion between transition systems as
examples of branching and
linear time problems. The talk will be devoted to the case when the
two systems are given as a kind
of product of finite-state ones. The definition of the product depends on a kind of synchronization
allowed. We considered few different modes of synchronization.

It is widely acknowledged that the linear time is 'harder' than the
branching time - I'll show some
examples to justify this claim. Then I'll give an example in which the
opposite holds, thus
demonstrating that relation between linear and branching time is more
complex than expected.

I'll mention some open problems at the end of the talk.

---