Department of Information Technology

A linear-time algorithm for the orbit problem over cyclic groups

Speaker

Anthony Widjaja Lin, Yale-NUS College, Singapore

Date and Time

Tuesday, June 11th, 2014 at 15:45.

Location

Polacksbacken, room 4306

Abstract

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.

Updated  2014-06-09 17:10:05 by Mohamed Faouzi Atig.