As a guest user you are not logged in or recognized by your IP address. You have
access to the Front Matter, Abstracts, Author Index, Subject Index and the full
text of Open Access publications.
Dualization problems have been intensively studied in combinatorics, AI and pattern mining for years. Roughly speaking, for a partial order () and some monotonic predicate Q over P, the dualization consists in identifying all maximal elements of P verifying Q from all minimal elements of not verifying Q, and vice versa. The dualization is equivalent to the enumeration of minimal transversal of hypergraphs whenever () is a boolean lattice. In the setting of interesting pattern mining in databases, P represents a set of patterns and whenever P is isomorphic to a boolean lattice, the pattern mining problem is said to be representable as sets. The class of such problems is denoted by AS. In this paper, we introduce a weak representation as sets for pattern mining problems which extends the RAS class to a wider and significantly larger class of problems, called WRAS. We also identify EWRAS, an efficient subclass of WRAS for which the dualization problem is still quasi-polynomial. Finally, we point out that one representative pattern mining problem known not to be in RAS, namely frequent rigid sequences with wildcard, belongs to EWRAS. These new classes might prove to have large impact in unifying existing pattern mining approaches.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.