LEARNABILITY OF XML DOCUMENT TRANSFORMATION RULES USING TYPED EFSS

EFSs are logic programs expressing various formal languages. Typed EFSs are EFSs augmented by introducing types for variables. In this paper, we define a subclass of the typed EFSs, called DS-typed regular EFSs, to model XML documents. We show that the class of languages defined by DS-typed regular EFSs properly includes the class of languages defined by balanced grammars, one formal model of schemata of XML documents. We also define another subclass of the typed EFSs, called DS-typed regular TEFSs, which represent translation rules between languages defined by DS-typed regular EFSs. The DS-typed regular TEFSs can have local variables under some conditions. We prove that the class of translation rules defined by DS-typed regular TEFSs is learnable from positive examples under the restriction that the number of clauses in an EFS and the length of each clause are bounded by some constants. This restriction is essential since the class of translations is not learnable from positive examples without the restriction.