1 Ocak 2016 Dergi makalesi Açık Erişim

Dayar, Tugrul; Orhan, M. Can

MARC21 XML

<?xml version='1.0' encoding='UTF-8'?>
<record xmlns="http://www.loc.gov/MARC21/slim">
  <leader>00000nam##2200000uu#4500</leader>
  <datafield tag="245" ind1=" " ind2=" ">
    <subfield code="a">CARTESIAN PRODUCT PARTITIONING OF MULTI-DIMENSIONAL REACHABLE STATE SPACES</subfield>
  </datafield>
  <datafield tag="909" ind1="C" ind2="4">
    <subfield code="p">PROBABILITY IN THE ENGINEERING AND INFORMATIONAL SCIENCES</subfield>
    <subfield code="v">30</subfield>
    <subfield code="n">3</subfield>
    <subfield code="c">413-430</subfield>
  </datafield>
  <controlfield tag="001">56677</controlfield>
  <datafield tag="980" ind1=" " ind2=" ">
    <subfield code="a">user-tubitak-destekli-proje-yayinlari</subfield>
  </datafield>
  <datafield tag="520" ind1=" " ind2=" ">
    <subfield code="a">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.</subfield>
  </datafield>
  <datafield tag="650" ind1="1" ind2="7">
    <subfield code="2">opendefinition.org</subfield>
    <subfield code="a">cc-by</subfield>
  </datafield>
  <datafield tag="700" ind1=" " ind2=" ">
    <subfield code="u">Bilkent Univ, Dept Comp Engn, TR-06800 Ankara, Turkey</subfield>
    <subfield code="a">Orhan, M. Can</subfield>
  </datafield>
  <datafield tag="980" ind1=" " ind2=" ">
    <subfield code="b">article</subfield>
    <subfield code="a">publication</subfield>
  </datafield>
  <datafield tag="542" ind1=" " ind2=" ">
    <subfield code="l">open</subfield>
  </datafield>
  <datafield tag="100" ind1=" " ind2=" ">
    <subfield code="u">Bilkent Univ, Dept Comp Engn, TR-06800 Ankara, Turkey</subfield>
    <subfield code="a">Dayar, Tugrul</subfield>
  </datafield>
  <datafield tag="260" ind1=" " ind2=" ">
    <subfield code="c">2016-01-01</subfield>
  </datafield>
  <controlfield tag="005">20210316000730.0</controlfield>
  <datafield tag="909" ind1="C" ind2="O">
    <subfield code="o">oai:zenodo.org:56677</subfield>
    <subfield code="p">user-tubitak-destekli-proje-yayinlari</subfield>
  </datafield>
  <datafield tag="856" ind1="4" ind2=" ">
    <subfield code="z">md5:f5ebfca64f0121e7796ea02956e8f682</subfield>
    <subfield code="s">180</subfield>
    <subfield code="u">https://aperta.ulakbim.gov.trrecord/56677/files/bib-cefe0153-1cc8-4561-a35c-91959b98e34a.txt</subfield>
  </datafield>
  <datafield tag="540" ind1=" " ind2=" ">
    <subfield code="u">http://www.opendefinition.org/licenses/cc-by</subfield>
    <subfield code="a">Creative Commons Attribution</subfield>
  </datafield>
  <datafield tag="024" ind1=" " ind2=" ">
    <subfield code="a">10.1017/S0269964816000085</subfield>
    <subfield code="2">doi</subfield>
  </datafield>
</record>