Precedence-inclusion patterns and relational learning

In this paper we introduce precedence-inclusion patterns, which are sets with a strictly partially ordered set of strict partial orders, along with some additional structure. The definition of these structures reflects how multiple partial orders interact in a number of situations such as in text, images, and video. In particular, precedence-inclusion patterns generalize constituent structure trees familiar to computational linguists. Our interest in these objects was initially sparked by their connection with problems of relational learning. We develop the general mathematical theory of precedence-inclusion patterns, we show that each finite set of finite precedence-inclusion relations has a minimal most specific generalization that is unique up to isomorphism, and we explain how this result relates to relational learning. © 2005 Elsevier B.V. All rights reserved.