Translating XML Documents Through Dyck-Typed Regular Translation Elementary Formal Systems
Authors:
- Noriko SugimotoNSNoriko Sugimoto
- Kouichi HirataKHKouichi Hirata
- 1 September 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 218-223
Abstract
While a Dyck-typed regular translation elementary formal system (a Dyck-typed RTEFS, for short) can formulate the translations between XML documents, it cannot be learnable from positive examples if the number of clauses is unbounded and one of the operations as tag-renaming, tag-deleting and tag-adding, which we call tag-operating Dyck-typed RTEFSs, is allowed. In this paper, first we formulate the derivation procedure for Dyck-typed RTEFSs and provide the condition that it is complete. Next, we introduce determinate tag-operating Dyck-typed RTEFSs and show that they are learnable from positive examples even if the number of clauses is unbounded. Furthermore, we introduce k-composite TEFSs as a composition of k determinate tag-operating Dyck-typed RTEFSs, and show that they are also learnable from positive examples.Keywords
This publication has 8 references indexed in Scilit:
- Formal properties of XML grammars and languagesActa Informatica, 2002
- Generating languages by a derivation procedure for elementary formal systemsInformation Processing Letters, 1999
- Constructive learning of translations based on dictionariesLecture Notes in Computer Science, 1996
- Short note: procedural semantics and negative information of elementary formal systemThe Journal of Logic Programming, 1992
- Learning elementary formal systemTheoretical Computer Science, 1992
- Inductive inference of monotonic formal systems from positive dataNew Generation Computing, 1991
- Foundations of Logic Programming1987
- Language identification in the limitInformation and Control, 1967