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

Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data Inferens Induktif Masa Polinomial Bahasa Graf TTSP daripada Data Positif

Ryoji TAKAMI, Yusuke SUZUKI, Tomoyuki UCHIDA, Takayoshi SHOUDAI

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Graf Dua-Terminal Siri Selari (TTSP, ringkasnya) digunakan sebagai model data dalam aplikasi untuk rangkaian elektrik dan masalah penjadualan. Kami mencadangkan graf istilah TTSP iaitu graf TTSP yang mempunyai pembolehubah berstruktur, iaitu corak graf di atas graf TTSP. biarlah TGTTSP menjadi set semua graf istilah TTSP yang label pembolehubahnya berbeza. Untuk graf istilah TTSP g in TGTTSP, bahasa graf TTSP bagi g, dilambangkan dengan L(g), ialah set semua graf TTSP yang diperoleh daripada g dengan menggantikan graf TTSP arbitrari untuk semua pembolehubah dalam g. Pertama, apabila graf TTSP G dan graf istilah TTSP g diberikan sebagai input, kami membentangkan algoritma pemadanan masa polinomial yang menentukan sama ada atau tidak L(g) mengandungi G. Masalah bahasa yang minimum untuk kelas LTTSP={L(g) | gTGTTSP} ialah, diberi set S daripada graf TTSP, untuk mencari graf istilah TTSP g in TGTTSP seperti itu L(g) adalah minimum antara semua bahasa graf TTSP yang mengandungi semua graf TTSP dalam S. Kedua, kami memberikan algoritma masa polinomial untuk menyelesaikan masalah bahasa minimum untuk LTTSP. Akhirnya, kami menunjukkannya LTTSP ialah masa polinomial boleh disimpulkan secara induktif daripada data positif.

Jawatankuasa
IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.181-190
Tarikh penerbitan
2009/02/01
Diumumkan
ISSN dalam talian
1745-1361
DOI
10.1587/transinf.E92.D.181
Jenis Manuskrip
Special Section PAPER (Special Section on Foundations of Computer Science)
kategori

Pengarang

Kata kunci

Contents [show]