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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | article |
| Published: |
2003
|
| Subjects: | |
| Online Access: | https://eprints.kfupm.edu.sa/id/eprint/14218/1/14218_1.pdf https://eprints.kfupm.edu.sa/id/eprint/14218/2/14218_2.doc |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|