Translating XML Documents Through Dyck-Typed Regular Translation Elementary Formal Systems

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.