On simulation and trace inclusion

Speaker(s)

Marek Grabowski

Affiliation

Uniwersytet Warszawski

Date

May 19, 2010, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---