Some computational properties of a model for electronic documents
Trevor J. M. Bench-Capon, Paul E.S. Dunne · Electronic Publishing - Origination, Dissemination and Design · 1989
SUMMARY Differing types of documents exhibit varying structures. These may arise, at one level, because of the material comprising the text ‐ thus textbooks will be organized differently from research papers ‐ and at a lower level as a result of the layout conventions by which the text is formatted. These structuring regimes may be seen as defining a set of constraints which a document within a specific class must satisfy. In this paper we examine the model recently proposed in Reference [1] which is used for representing and modifying electronic documents. This employs simple graph grammars as a means of translating changes in the document structure into modifications to the computer representation. The aim of this approach is to provide computer support which will allow the appropriate structural conventions to be preserved while the document is being edited. We consider the following problem with this method: given a set of ‘constraints’ which the document must satisfy and a collection of rules prescribing how the document representation may be modified, how does one prove that only documents which obey the constraints can be generated by repeated applications of the rules? We describe one way in which this question can be more precisely formulated and call this the consistency checking problem. It is shown that, in general, this problem cannot be solved. We then outline how, for practical applications, the consistency checking problem may be solved for certain special cases.