Structuring documents efficiently

Documents are typically marked up to enable rendering and to facilitate reuse. However, retargetting a document often requires pervasive changes to the markup. Power et al. have proposed a new level of representation called document structure which captures just those aspects of graphical organisation that are significant for conveying meaning. These document structures can be generated automatically from rhetorical structures, abstract representations of the meaning of a text. The mapping is highly indeterminate, being governed by a large number of interacting constraints. We present a constraint programming approach to the problem, and report on early experiments with an implementation in Prolog.