Unranked tree languages

摘要

Conventionally, tree languages have been studied under the restriction that a symbol may appear in a tree only with a fixed number of descendants (the rank of the symbol). This limitation runs contrary to the proposed uses of tree languages in syntactic pattern recognition and in mathematical linguistics. This paper presents tree languages over an unranked alphabet, unranked tree languages, where a symbol may appear in trees with an arbitrary number of descendants. In general, most properties of regular sets, including the closure properties under boolean operations, can be extended to tree languages over a ranked alphabet; but several important properties cannot be extended to unranked tree languages. The properties of unranked tree languages, grammars, and automata and the similarities and differences with conventional tree languages, grammars, and automata are analyzed. It is proved that unranked tree languages are not closed under complement, but are closed under relative complement. An algorithm is presented to construct an automation to recognize the relative complement of the languages recognized by two automata.