A FORMAL SPECIFICATION OF DOCUMENT PROCESSING

We propose a computational model of structured documents and their pro cessing based on preferential attribute grammar schemes and grammar co ordinations. Our grammar-based model can be viewed as a specification of composable structure transformations. The main novel features are d eclarative specification of preferential constraints, and specificatio n of structure transformations at the level of meta-data through coord ination schemes; The preferential constraints may express constraints to guide computations as in dynamic programming, as well as constraint s to control declaratively the outcome of transformation. A coordinati on is essentially a partial substitution map from the vocabulary of a grammar to languages over the vocabulary of another grammar. Although our grammar-based coordination schemes are designed to capture various types of document processing (such as view processing and query proce ssing), we focus on the document layout application in this work. Our first main result shows that when the coordination map satisfies the u niformity condition, the two grammars (of the layout coordination sche me) are syntactically coordinated in the sense that trees of the first grammar are always transformable to trees of the second grammar, whil e satisfying the constraints imposed by the coordination. We then show that the elementary uniformity is a decidable property when the coord ination is regular, thereby establishing a decidable class of coordina ted grammar schemes.