A formal specification of document processing

We propose a computational model of structured documents and their processing based on preferential attribute grammar schemes and grammar coordinations. Our grammar-based model can be viewed as a specification of composable structure transformations. The main novel features are declarative specification of preferential constraints, and specification of structure transformations at the level of meta-data through coordination schemes. The preferential constraints may express constraints to guide computations as in dynamic programming, as well as constraints to control declaratively the outcome of transformation. A coordination 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 processing), we focus on the document layout application in this work. Our first main result shows that when the coordination map satisfies the uniformity condition, the two grammars (of the layout coordination scheme) are syntactically coordinated in the sense that trees of the first grammar are always transformable to trees of the second grammar, while satisfying the constraints imposed by the coordination. We then show that the elementary uniformity is a decidable property when the coordination is regular, thereby establishing a decidable class of coordinated grammar schemes.