On "learning term rewriting systems from entailment"
Summary form only given. We study exact learning of term rewriting systems from entailment and refute a recent result by Arimura, Sakamoto and Arikawa about polynomial time learnability of k-variable linear tree translations (LTT (k)). It was incorrectly claimed that the length of derivations of LTT...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | |
| التنسيق: | article |
| منشور في: |
2003
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | https://eprints.kfupm.edu.sa/id/eprint/14218/1/14218_1.pdf https://eprints.kfupm.edu.sa/id/eprint/14218/2/14218_2.doc |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513384057143296 |
|---|---|
| author | Rao, M.R.K. |
| author2 | unknown |
| author2_role | author |
| author_facet | Rao, M.R.K. unknown |
| author_role | author |
| dc.creator.none.fl_str_mv | Rao, M.R.K. unknown |
| dc.date.none.fl_str_mv | 2003-07 2020 |
| dc.format.none.fl_str_mv | application/pdf application/msword |
| dc.identifier.none.fl_str_mv | https://eprints.kfupm.edu.sa/id/eprint/14218/1/14218_1.pdf https://eprints.kfupm.edu.sa/id/eprint/14218/2/14218_2.doc (2003) On "learning term rewriting systems from entailment". Computer Systems and Applications, 2003. Book of Abstracts. ACS/IEEE International conference, 1. |
| dc.language.none.fl_str_mv | en en |
| dc.publisher.none.fl_str_mv | IEEE |
| dc.relation.none.fl_str_mv | https://eprints.kfupm.edu.sa/id/eprint/14218/ |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Computer |
| dc.title.none.fl_str_mv | On "learning term rewriting systems from entailment" |
| dc.type.none.fl_str_mv | Article PeerReviewed info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/article |
| description | Summary form only given. We study exact learning of term rewriting systems from entailment and refute a recent result by Arimura, Sakamoto and Arikawa about polynomial time learnability of k-variable linear tree translations (LTT (k)). It was incorrectly claimed that the length of derivations of LTT (k) is bounded by a polynomial in the size of the initial term. This claim led to their result on polynomial time learnability of LTT (k). We present a simple system in the class of 1-variable linear tree translations that has a derivation of exponential length. We also discuss why it is difficult to syntactically separate the rewriting systems defining polynomial functions and the rewriting systems defining exponential functions. We then identify a few requirements for polynomial time learnability of rewriting systems and discuss how these requirements may be achieved. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | KFUPM_aa43b08169a1030fa2f328dcd2a421d8 |
| identifier_str_mv | (2003) On "learning term rewriting systems from entailment". Computer Systems and Applications, 2003. Book of Abstracts. ACS/IEEE International conference, 1. |
| language_invalid_str_mv | en |
| network_acronym_str | KFUPM |
| network_name_str | King Fahd University of Petroleum and Minerals |
| oai_identifier_str | oai::14218 |
| publishDate | 2003 |
| publisher.none.fl_str_mv | IEEE |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | On "learning term rewriting systems from entailment"Rao, M.R.K.unknownComputerSummary form only given. We study exact learning of term rewriting systems from entailment and refute a recent result by Arimura, Sakamoto and Arikawa about polynomial time learnability of k-variable linear tree translations (LTT (k)). It was incorrectly claimed that the length of derivations of LTT (k) is bounded by a polynomial in the size of the initial term. This claim led to their result on polynomial time learnability of LTT (k). We present a simple system in the class of 1-variable linear tree translations that has a derivation of exponential length. We also discuss why it is difficult to syntactically separate the rewriting systems defining polynomial functions and the rewriting systems defining exponential functions. We then identify a few requirements for polynomial time learnability of rewriting systems and discuss how these requirements may be achieved.IEEE2003-072020ArticlePeerReviewedinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/articleapplication/pdfapplication/mswordhttps://eprints.kfupm.edu.sa/id/eprint/14218/1/14218_1.pdfhttps://eprints.kfupm.edu.sa/id/eprint/14218/2/14218_2.doc (2003) On "learning term rewriting systems from entailment". Computer Systems and Applications, 2003. Book of Abstracts. ACS/IEEE International conference, 1. enenhttps://eprints.kfupm.edu.sa/id/eprint/14218/info:eu-repo/semantics/openAccessoai::142182019-11-01T14:04:46Z |
| spellingShingle | On "learning term rewriting systems from entailment" Rao, M.R.K. Computer |
| status_str | publishedVersion |
| title | On "learning term rewriting systems from entailment" |
| title_full | On "learning term rewriting systems from entailment" |
| title_fullStr | On "learning term rewriting systems from entailment" |
| title_full_unstemmed | On "learning term rewriting systems from entailment" |
| title_short | On "learning term rewriting systems from entailment" |
| title_sort | On "learning term rewriting systems from entailment" |
| topic | Computer |
| url | https://eprints.kfupm.edu.sa/id/eprint/14218/1/14218_1.pdf https://eprints.kfupm.edu.sa/id/eprint/14218/2/14218_2.doc |