VOL.30, PP.413-430, 2016.  

TITLE: Cartesian product partitioning of multi-dimensional 
reachable state spaces

AUTHORS: Tugrul Dayar and M. Can Orhan

ABSTRACT: Markov chains (MCs) are widely used to model systems 
which evolve by visiting the states in their state spaces 
following the available transitions. When such systems are 
composed of interacting subsystems, they can be mapped to a 
multi-dimensional MC in which each subsystem normally 
corresponds to a different dimension. Usually the reachable 
state space of the multi-dimensional MC is a proper subset of 
its product state space, that is, Cartesian product of its 
subsystem state spaces. Compact storage of the matrix 
underlying such a MC and efficient implementation of analysis 
methods using Kronecker operations require the set of 
reachable states to be represented as a union of Cartesian 
products of subsets of subsystem state spaces. The problem of 
partitioning the reachable state space of a three or higher 
dimensional system with a minimum number of partitions into 
Cartesian products of subsets of subsystem state spaces is 
shown to be NP-complete. Two algorithms, one merge based the 
other refinement based, that yield possibly non-optimal 
partitionings are presented. Results of experiments on a set 
of problems from the literature and those that are randomly 
generated indicate that, although it may be more time and 
memory consuming, the refinement based algorithm almost 
always computes partitionings with a smaller number of 
partitions than the merge-based algorithm. The refinement 
based algorithm is insensitive to the order in which the 
states in the reachable state space are processed, and in 
many cases it computes partitionings that are optimal.