1 Ocak 2017 Konferans bildirisi Açık Erişim

Altun, Omer Faruk; Atam, Kamil Tolga; Karahoda, Sertac; Kaya, Kamer

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">Synchronizing Heuristics: Speeding up the Slowest</subfield>
  </datafield>
  <datafield tag="024" ind1=" " ind2=" ">
    <subfield code="a">10.1007/978-3-319-67549-7_15</subfield>
    <subfield code="2">doi</subfield>
  </datafield>
  <controlfield tag="001">45045</controlfield>
  <datafield tag="980" ind1=" " ind2=" ">
    <subfield code="a">user-tubitak-destekli-proje-yayinlari</subfield>
  </datafield>
  <datafield tag="520" ind1=" " ind2=" ">
    <subfield code="a">Computing a shortest synchronizing word of an automaton is an NP-hard problem. Therefore, heuristics are used to compute short synchronizing words. SYNCHROP is among the best heuristics in the literature in terms of word lengths. The heuristic and its variants such as SYNCHROPL have been frequently used as a baseline to judge the quality of the words generated by the new heuristics. Although, its quality is good, the heuristics are significantly slow especially compared to much cheaper heuristics such as Greedy and Cycle. This makes them infeasible for large-scale automatons. In this paper, we show how one can improve the time performance of SYNCHROP and its variants by avoiding unnecessary computations which makes these heuristics more competitive than they already are. Our experimental results show that for 2500 states, SYNCHROP can be made 70-160x faster, via the proposed optimizations. In particular, for 2500 states and 32 letters, the SYNCHROP execution reduces to 66 s from 4745 s. Furthermore, the suggested optimizations become more effective as the number of states in the automata increase.</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">Sabanci Univ, Fac Engn &amp; Nat Sci, Comp Sci &amp; Engn, Istanbul, Turkey</subfield>
    <subfield code="a">Atam, Kamil Tolga</subfield>
  </datafield>
  <datafield tag="700" ind1=" " ind2=" ">
    <subfield code="u">Sabanci Univ, Fac Engn &amp; Nat Sci, Comp Sci &amp; Engn, Istanbul, Turkey</subfield>
    <subfield code="a">Karahoda, Sertac</subfield>
  </datafield>
  <datafield tag="700" ind1=" " ind2=" ">
    <subfield code="a">Kaya, Kamer</subfield>
  </datafield>
  <datafield tag="980" ind1=" " ind2=" ">
    <subfield code="b">conferencepaper</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">Sabanci Univ, Fac Engn &amp; Nat Sci, Comp Sci &amp; Engn, Istanbul, Turkey</subfield>
    <subfield code="a">Altun, Omer Faruk</subfield>
  </datafield>
  <datafield tag="711" ind1=" " ind2=" ">
    <subfield code="a">TESTING SOFTWARE AND SYSTEMS (ICTSS 2017)</subfield>
  </datafield>
  <datafield tag="260" ind1=" " ind2=" ">
    <subfield code="c">2017-01-01</subfield>
  </datafield>
  <controlfield tag="005">20210315212952.0</controlfield>
  <datafield tag="909" ind1="C" ind2="O">
    <subfield code="o">oai:zenodo.org:45045</subfield>
    <subfield code="p">user-tubitak-destekli-proje-yayinlari</subfield>
  </datafield>
  <datafield tag="856" ind1="4" ind2=" ">
    <subfield code="z">md5:14edcda36fa75159edc73049bcc19140</subfield>
    <subfield code="s">145</subfield>
    <subfield code="u">https://aperta.ulakbim.gov.trrecord/45045/files/bib-92a31ce3-9cf5-4df9-838e-e70e82aa195c.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>
</record>