Anthony Widjaja Lin

Date: 17:00, Tuesday, July 8, 2014
Speaker: Anthony Widjaja Lin
Venue: TU Wien

The orbit problem is at the heart of symmetry reduction methods for
model checking concurrent systems. It asks whether two given
configurations in a concurrent system (represented as finite sequences
over some finite alphabet) are in the same orbit with respect to a
given finite permutation group (represented by their generators)
acting on this set of configurations. It is known that the problem is
in general as hard as the graph isomorphism problem, which is widely
believed to be not solvable in polynomial time. In this talk, we
consider the restriction of the orbit problem when the permutation
group is cyclic (i.e. generated by a single arbitrary permutation), an
important restriction of the orbit problem. The main result is a
linear-time algorithm for this subproblem.

Posted in RiSE Seminar