Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-23T09:45:45.906Z Has data issue: false hasContentIssue false
  • English
  • Français

CARTESIAN PRODUCT PARTITIONING OF MULTI-DIMENSIONAL REACHABLE STATE SPACES

Published online by Cambridge University Press:  18 May 2016

Tuǧrul Dayar  and
M. Can Orhan
Tuǧrul Dayar
Affiliation:
Department of Computer Engineering, Bilkent University, TR-06800 Bilkent, Ankara, Turkey E-mail: [email protected]; [email protected]
M. Can Orhan
Affiliation:
Department of Computer Engineering, Bilkent University, TR-06800 Bilkent, Ankara, Turkey E-mail: [email protected]; [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 30 , Issue 3: Erol Gelenbe's 70th Birthday , July 2016 , pp. 413 - 430
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.
Copyright
Copyright © Cambridge University Press 2016

References

1.Adelson-Velskii, G.M. & Landis, E.M. (1962). An algorithm for the organization of information. Soviet Mathematics Doklady 3: 1259–1263.Google Scholar
2.Baumann, H., Dayar, T., Orhan, M.C., & Sandmann, W. (2013). On the numerical solution of Kronecker-based infinite level-dependent QBD processes. Performance Evaluation 70: 663–681.CrossRefGoogle Scholar
3.Bournez, K., Maler, O., & Pnueli, A. (1999). Orthogonal Polyhedra: Representation and Computation, in: Hybrid Systems: Computation and Control. Lecture Notes in Computer Science, Heidelberg: Springer, vol. 1569, pp. 46–60.Google Scholar
4.Buchholz, P. (1999). Structured analysis approaches for large Markov chains. Applied Numerical Mathematics 31: 375–404.CrossRefGoogle Scholar
5.Buchholz, P. (1999). Hierarchical structuring of superposed GSPNs. IEEE Transactions on Software Engineering 25: 166–181.Google Scholar
6.Buchholz, P. & Dayar, T. (2004). Comparison of multilevel methods for Kronecker-based Markovian representations. Computing 73: 349–371.CrossRefGoogle Scholar
7.Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. (2009). Introduction to Algorithms, 3rd ed.Cambridge: The MIT Press.Google Scholar
8.Dayar, T. (2012). Analyzing Markov Chains using Kronecker Products: Theory and Applications. New York: Springer.Google Scholar
9.Software for computing Cartesian product partitioning of multi-dimensional reachable state spaces. (2013). http://www.cs.bilkent.edu.tr/~tugrul/software.html Accessed 6 June 2015Google Scholar
10.Dayar, T. & Orhan, M.C.Cartesian product partitioning of multi-dimensional reachable state spaces. Technical Report, BU-CE-03013, December 2013, Department of Computer Engineering, Bilkent University, Ankara, Turkey.Google Scholar
11.Dielissen, V.J. & Kaldewaij, A. (1991). Rectangular partition is polynomial in two dimensions but NP-complete in three. Information Processing Letters 38: 1–6.Google Scholar
12.Ferrari, L., Sankar, P.V. & Sklansky, J. (1984). Minimal rectangular partitions of digitized blobs. Computer Vision, Graphics, and Image Processing 28, 58–71.Google Scholar
13.Garey, M.R. & Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco: Freeman.Google Scholar
14.Jain, A., Sahni, S., Palta, J., & Dempsey, J. (2003). Partitioning 3D phantoms into homogeneous cuboids. International Journal of Foundations of Computer Science 14: 905–931.Google Scholar
15.Keil, J.M. (eds). (2000). Polygon Decomposition. In: Sack, J.R., Urrutia, J. Handbook of Computational Geometry, Amsterdam: Elsevier, pp. 491–518.Google Scholar
16.Maehara, H. (1989). Note on induced subgraphs of the unit distance graph E n. Discrete and Computational Geometry 4: 15–18.CrossRefGoogle Scholar
17.Paige, R. & Tarjan, R.E. (1987). Three partition refinement algorithms. SIAM J. Comput. 16: 973–989.CrossRefGoogle Scholar
18.Soltan, V. & Gorpinevich, A. (1993). Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles. Discrete and Computational Geometry 9: 57–79.Google Scholar
19.Stewart, W.J. (1994). Introduction to the Numerical Solution of Markov Chains. Princeton: Princeton University Press.Google Scholar
20.Ziegler, G.M. (1995). Lectures on Polytopes. New York: Springer.Google Scholar