TITLE: Cartesian product partitioning of multi-dimensional reachable state 

AUTHORS: Tugrul Dayar and Muhsin 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.    

KEYWORDS: Discrete geometry, orthogonal polytope decomposition, 
multi-dimensional system, reachable state space, Cartesian product 
partitioning, Markov chain