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
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) | g ∈ TGTTSP} 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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Salinan
Ryoji TAKAMI, Yusuke SUZUKI, Tomoyuki UCHIDA, Takayoshi SHOUDAI, "Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 2, pp. 181-190, February 2009, doi: 10.1587/transinf.E92.D.181.
Abstract: Two-Terminal Series Parallel (TTSP, for short) graphs are used as data models in applications for electric networks and scheduling problems. We propose a TTSP term graph which is a TTSP graph having structured variables, that is, a graph pattern over a TTSP graph. Let TGTTSP be the set of all TTSP term graphs whose variable labels are mutually distinct. For a TTSP term graph g in TGTTSP, the TTSP graph language of g, denoted by L(g), is the set of all TTSP graphs obtained from g by substituting arbitrary TTSP graphs for all variables in g. Firstly, when a TTSP graph G and a TTSP term graph g are given as inputs, we present a polynomial time matching algorithm which decides whether or not L(g) contains G. The minimal language problem for the class LTTSP={L(g) | g ∈ TGTTSP} is, given a set S of TTSP graphs, to find a TTSP term graph g in TGTTSP such that L(g) is minimal among all TTSP graph languages which contain all TTSP graphs in S. Secondly, we give a polynomial time algorithm for solving the minimal language problem for LTTSP. Finally, we show that LTTSP is polynomial time inductively inferable from positive data.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.181/_p
Salinan
@ARTICLE{e92-d_2_181,
author={Ryoji TAKAMI, Yusuke SUZUKI, Tomoyuki UCHIDA, Takayoshi SHOUDAI, },
journal={IEICE TRANSACTIONS on Information},
title={Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data},
year={2009},
volume={E92-D},
number={2},
pages={181-190},
abstract={Two-Terminal Series Parallel (TTSP, for short) graphs are used as data models in applications for electric networks and scheduling problems. We propose a TTSP term graph which is a TTSP graph having structured variables, that is, a graph pattern over a TTSP graph. Let TGTTSP be the set of all TTSP term graphs whose variable labels are mutually distinct. For a TTSP term graph g in TGTTSP, the TTSP graph language of g, denoted by L(g), is the set of all TTSP graphs obtained from g by substituting arbitrary TTSP graphs for all variables in g. Firstly, when a TTSP graph G and a TTSP term graph g are given as inputs, we present a polynomial time matching algorithm which decides whether or not L(g) contains G. The minimal language problem for the class LTTSP={L(g) | g ∈ TGTTSP} is, given a set S of TTSP graphs, to find a TTSP term graph g in TGTTSP such that L(g) is minimal among all TTSP graph languages which contain all TTSP graphs in S. Secondly, we give a polynomial time algorithm for solving the minimal language problem for LTTSP. Finally, we show that LTTSP is polynomial time inductively inferable from positive data.},
keywords={},
doi={10.1587/transinf.E92.D.181},
ISSN={1745-1361},
month={February},}
Salinan
TY - JOUR
TI - Polynomial Time Inductive Inference of TTSP Graph Languages from Positive Data
T2 - IEICE TRANSACTIONS on Information
SP - 181
EP - 190
AU - Ryoji TAKAMI
AU - Yusuke SUZUKI
AU - Tomoyuki UCHIDA
AU - Takayoshi SHOUDAI
PY - 2009
DO - 10.1587/transinf.E92.D.181
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2009
AB - Two-Terminal Series Parallel (TTSP, for short) graphs are used as data models in applications for electric networks and scheduling problems. We propose a TTSP term graph which is a TTSP graph having structured variables, that is, a graph pattern over a TTSP graph. Let TGTTSP be the set of all TTSP term graphs whose variable labels are mutually distinct. For a TTSP term graph g in TGTTSP, the TTSP graph language of g, denoted by L(g), is the set of all TTSP graphs obtained from g by substituting arbitrary TTSP graphs for all variables in g. Firstly, when a TTSP graph G and a TTSP term graph g are given as inputs, we present a polynomial time matching algorithm which decides whether or not L(g) contains G. The minimal language problem for the class LTTSP={L(g) | g ∈ TGTTSP} is, given a set S of TTSP graphs, to find a TTSP term graph g in TGTTSP such that L(g) is minimal among all TTSP graph languages which contain all TTSP graphs in S. Secondly, we give a polynomial time algorithm for solving the minimal language problem for LTTSP. Finally, we show that LTTSP is polynomial time inductively inferable from positive data.
ER -