Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

An Efficient Pattern Matching Algorithm for Unordered Term Tree Patterns of Bounded Dimension Algoritma Padanan Corak Yang Cekap untuk Corak Pokok Jangka Tidak Tertib Dimensi Terhad

Takayoshi SHOUDAI, Tetsuhiro MIYAHARA, Tomoyuki UCHIDA, Satoshi MATSUMOTO, Yusuke SUZUKI

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Istilah ialah corak graf akiklik yang disambungkan (pokok tidak tertib tidak berakar) dengan pembolehubah berstruktur, yang merupakan senarai tertib satu atau lebih bucu yang berbeza. Pembolehubah istilah mempunyai label pembolehubah dan boleh digantikan dengan pokok arbitrari dengan penggantian hyperedge mengikut label pembolehubah. Dimensi sebutan ialah bilangan maksimum bucu dalam pembolehubahnya. Sebutan dikatakan linear jika setiap label pembolehubah di dalamnya berlaku tepat sekali. biarlah T menjadi pokok dan t istilah linear. Dalam kertas kerja ini, kami mengkaji masalah padanan corak graf (GPMP) untuk T and t, yang menentukan sama ada atau tidak T diperoleh daripada t dengan menggantikan pembolehubah dalam t dengan beberapa pokok. Mula-mula kita tunjukkan bahawa GPMP untuk T and t adalah NP-lengkap jika dimensi bagi t adalah lebih besar daripada atau sama dengan 4. Seterusnya kami memberikan algoritma masa polinomial untuk menyelesaikan GPMP bagi pepohon darjah sempadan dan sebutan linear dimensi sempadan. Akhir sekali kami menunjukkan bahawa GPMP untuk pokok darjah arbitrari dan sebutan linear dimensi 2 boleh diselesaikan dalam masa polinomial.

Jawatankuasa
IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1344-1354
Tarikh penerbitan
2018/09/01
Diumumkan
ISSN dalam talian
1745-1337
DOI
10.1587/transfun.E101.A.1344
Jenis Manuskrip
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
kategori

Pengarang

Takayoshi SHOUDAI
  Kyushu International University
Tetsuhiro MIYAHARA
  Hiroshima City University
Tomoyuki UCHIDA
  Hiroshima City University
Satoshi MATSUMOTO
  Tokai University
Yusuke SUZUKI
  Hiroshima City University

Kata kunci

Contents [show]