Construction of a Dynamic Document Using Context-Free Pieces

Kenji Hanakawa

Hideaki Takeda

Toyoaki Nishida

Department of Electrical Engineering

Graduate School of Information Scienceand Computer Science

Nara Institute of Science and Technology

Osaka Prefectural College of Technology

8916-5 Takayama, Ikoma, Nara 630-01, Japan

26-12 Saiwaicho, Neyagawashi 630-01, Japan

ftakeda, nishidag@is.aist-nara.ac.jp

hanakawa@ecs.osaka-pct.ac.jp

Abstract

In this paper, we propose a system for shared writing and reading of documents suitable for computer network environment which is based on pieces of documents. Pieces of documents are statements about particular facts such as \The earth has a spherical surface".
In this system, writers can create document pieces andstore them into a common repository. Readers then canselect document pieces from it. However, the selected
documents are disjointed and hard to read. In order tomake them easy to understand, it is necessary to organize them according to semantic models on which human writing is based. We introduce two semantic models: Top-down Model and Context-strengthen Model.
We show how to create document pieces and how to construct a document from them with these models.

1. Introduction

Information, which is mainly presented in naturallanguage, can be categorized into two types. One is information about only facts, such as encyclopedias, technical manuals and textbooks. The other is information
including works of ction or subjective opinions, suchas novels, poems, tales and stories. We call the former
type \document", and study techniques for e ective creation, storing, distribution and using it.
Usually, all documents are written for expected readers by one or a small number of authors. Not only
conventional books, but also electrical web pages andon-line manuals are written in this way. We call these
documents \static documents".
It is impossible for an author to write a document
which matches every reader's requirements because they
can be various. Readers who can not get all necessary
information from one book need to read other books.

If the author could write documents for some variety ofreaders, these documents are ideal but would be expensive and not practical.
Recently, a large quantity of information is requiredfor our activities. Systems that can supply necessary
documents e ectively are needed. However, a simple combination of the static documents and computer
technologies is not useful because it can cause easily
redundancy and contradiction.
For instance, suppose skilled software engineers.
They usually do not read a programming reference manual from the rst page to the last page. As they alreadyknow most part of the programming language, they only
refer to speci c parts of the manuals. If they cannot
get all the information from a single manual, they will
read other manuals. As a result, they can get disjointed
fragments from some set of manuals. It is dicult tomerge such fragments because they can easily containsome statements about the same subject which contradict each other.
Most information consists of facts, which are universal truths or propositions accepted by all member of thecommunity. \The earth has a spherical surface" is an
example of fact. Textbooks and science or technology
documents contain these facts. Writing them must be
the common task of the community. However, in theconventional book-style authoring systems, writing isan activity of one or a small number of authors. Computing technology such as the Internet provides media
between writers and readers, but not among writers.
We have two hypotheses: A document consists of context-free pieces. I.e., thepieces can be understood independently without
knowing the context.

 A document can be constructed according to syn-tactic and semantic models, and it is then easy toread.

of any subsets extracted from the set are true. Therefore, when a user selects parts from the common repository by any searching technologies, all selected document pieces are true. They are also unique, because
elements of the set are unique. A repository can beconstructed from various types of pieces. For example,section and paragraph can be the units of a piece.
2.2. The dynamic document constructor

Figure 1. The dynamic document system

Based on these hypotheses, we propose a dynamic
document system which consists of common repositories
and document constructors.
A dynamic document is a non-static document created dynamically in response to readers' requirement.
Figure 1 outlines the concept of a dynamic document
and shows how the system works. Writers create document pieces and store them into the common repository.
When a reader inputs her/his search requirements, thesystem selects the relevant pieces from the repository
and constructs them into one document.
2. The dynamic document system
2.1. The common repository

The purpose of the dynamic document system isworld wide information sharing. The common repository is a large scale distributed database system whichis connected with users by network. It's similar to an
digital library, but \book" which is a basic unit in libraries is not used here.
The necessary conditions of the common repository
are as follows:
1. All pieces are true.
2. All pieces are context independent.
3. All pieces are unique.
If there are two or more pieces that are contradictory
to each other, the authors need to discuss to nd out
which is true and put it in a repository.
The common repository is taken as a set of facts inwhich all elements are true. Consequently all elements

A user access the common repository using a clientsystem which inputs user's keywords and outputs a dynamic documents. The client system contains the dynamic document constructor.
The dynamic document constructor is a computer
program which constructs dynamic documents. It isbased on the basic assumption that documents written by human beings with syntactic and semantic constraints are easy to read. The constructor uses models of human writing: the Top-down Model and theContext-strengthen Model. Details of these models will
be discussed later in this paper.
3. Creation of context-free pieces

This study is based on the hypotheses that a document consists of context-free pieces. In this section, wediscuss methods for extracting these document pieces.
Generally speaking, it is dicult to understand themeaning of isolated parts extracted from documents,
because the loss of neighboring parts causes the loss ofcontext. There are two common phenomena involved
with contexts in the technical document: referring andellipsis. A part of a document can include pronouns
such as \it" and \this". Usually pronouns refer to preceding words or noun phrases, and meaning of the pronouns are equal to meaning of preceding words or nounphrases. Documents include ambiguous words or nounphrases caused by ellipsis which are disambiguated byadding the preceding words or noun phrases.
Document pieces are generated using the following
four processes.
1. Dividing: Divide a document into parts.
2. Completion: Add or substitute words to be understood independently.
3. Storing: Gather parts or paragraphs from morethan one documents and store them in one repository.
4. Unifying: Unify parts that have the same information.

1. Bash is the shell, or command language interpreter, that will appear in the GNU operating system.
2. The name (of Bash) is an acronym for the\Bourne-Again SHell", a pun on Steve Bourne, theauthor of the direct ancestor of the current UNIXshell /bin/sh.
3. Bash is an sh-compatible shell that incorporates
useful features from the Korn shell and the C shell.
4. It 0! Bash is ultimately intended to be a conformant implementation of the IEEE POSIX Shelland Utilities speci cation.
Figure 2. Avoiding of context dependency

At present these processes can be done only by human beings and not by computers. However, these processes are not tedious tasks for the original author.
We have experimented this method using a technicalmanual of Bash, the GNU shell. The manual is called\Bash's article.txt". Figure 2 is a typical example ofapplying the completion process to make pieces fromthe manual. In the gure, the words in parentheses areadded words, words on the left-hand side of an arrow
are removed words, and words on the right side of anarrow are substituted words. The subject of the second sentence, The name, is unidenti ed, and of Bash isadded next to it. The subject of the fourth sentence, It,
is also unidenti ed, and Bash is substituted for It.
Substitution and adding some words or noun phrases
can preserve original meaning and make the sentence
context free. This result shows that documents can bedivide into context free document pieces.
Our study has shown that sentences in the manual
could be translated into context-free one, except programming examples and explanations. As there areso many reference connections between them, we could
not transform them into document pieces. However, wecould make a document piece from a group of programming examples and explanations.
4. Construction of dynamic documents

Documents written by humans have contextual connections between parts. On the other hand, a set ofdocument pieces which have no connections is hard tounderstand. If a computer program constructs a document which has the same structure of documents written by humans, it can be easily understood. We thinkthat the structure is based on semantic models.
In the following sections, we will discuss two semanticmodels. One is the Top-down Model, in which relation
between the former sentence and the latter sentence isconsidered as one of the eight relations. This model isused for arranging sentences in paragraphs. The otheris the Context-strengthen Model in which the relation
between the upper element and the lower element is
considered as the relation between the stronger and theweaker context. This model is used for creating thestructure of a document. We will explain each model inthe following sections.
4.1. The Top-down Model

We have examined paragraphs and have identi ed
the following 8 categories of connection between two
succeeding : concrete, feature, attribute, example, element, item, association and sequence.
These categorical connections, except sequence, areabstracted as connections between a superior concept
and an inferior concept and the former sentence is thesuperior sentence. We call the constraint on these categories \Top-down Model".
We have used the following steps for arranging sentences which are extracted from some paragraphs in
Bash's article.
1. divide an original paragraph into sentences.
2. identify connections between the sentences.
3. construct a tree using the connections.
4. atten the tree structure to a list of sentences usingthe Depth First Search algorithm.
We have generated some sequences of sentences andcon rmed all of them are readable and one of them isequal to the original paragraphs.
The document construction based on The Top-Down
Model needs ability of identi cation of the top-down
connection between sentences. As we have not developed this ability, we can not implement the automatic
document construction.
4.2. The Context-strengthen Model

A sentence is considered the most basic unit of document pieces. However, it is too small to manage practically. As the Top-down Model needs understanding of
natural language statements, currently it's dicult tomake a dynamic document constructor with this model.
We propose another semantic model with which a machine can sort paragraphs and create sections, subsections, paragraphs and so on.
Documents are constructed of elements of several levels, such as sections, subsections and items. Therefore,
documents are considered as tree structures where elements are represented as nodes. Relations between

Table 1. Paragraphs and their concepts

subject ofparagraphscanf
fscanfprintffprintfgets
fgetsputs
fputs

functionconcepts included in paragraphfunctionfunctionfunctionfunctionfunctionfunctionfunctionfunction

input
input
outputoutputinput
input
outputoutputwith format
with format
with format
with format
without format
without format
without format
without format

stdio
streamstdio
streamstdio
streamstdio
streamstdio function

stream function

gets

 ifx

C1 = C2 [ fxg;
2 U; x 2= C2 ;

then C1 is stronger than C2 :C1 = C0 [ fxg; C2 = C0 [ fy g;
2 U; x 2= C0 ;y 2 U; y 2= C0 ;

 ifx

and y is an abstracted concept f rom x;
then C1 is stronger than C2 :The following rules can be found by observing realdocuments. If an element E2 contain another element
E1, the context of E1 must be stronger than the contextof E2. A leaf of the tree that is a selected document
piece has context of concepts which are represented by
keywords included in them.
We will show applying the Context-strengthen Modelto a C programming textbook. When paragraphs which
explain input-output functions of C are selected, eachparagraph has a super class concept such as function
and its attribute concepts such as input, with format
and stdio as shown in Table 1. Then, elements of thedocument can be created as combination of these concepts. Connecting these elements according to the rule,
tree structures can be constructed.

Figurefscanf
puts

3.

An

Item

stream function
without-format

stdio function
without-format

scanf

Subsection

stream function
with-format

stdio function
with-format

printfupper level elements and lower level elements are represented as links. The meaning of \element" used here issimilar to \non-terminal symbol" on natural language
processing.
Each element has its own context. In this section, theword \context" has a slightly di erent meaning from theprevious sections. Context is a constraint that limits
the elements which can be put under it. Context isalso considered as the ability given by a set of concepts.
So, a context can be represented by a set of nouns (ornoun phrases) which is basically equal to the headingof the elements. However, sometimes some of them areomitted.
We de ne the order relations of contexts C1, C2
which are subsets of U which consists of all the concepts involved with selected document pieces.

SectionParagraphfgets
fprintf

examplefputs

applying

theContext-strengthen Model

Figure 3 shows an example of the tree structure.
Rectangles used in the gure represent elements of thedocument and labels represent context sets.
The document has one section function and two subsections stdio function and stream function. These subsections have concept sets added stdio or stream to function. By adding concepts, context of the subsections
become stronger than context of the section. The document also has four items and eight paragraphs. Theelements of item level and paragraph level also havestronger concepts than their superior elements.
If some elements have concept sets including unique
words, de nition of abstract relations among thesewords are needed. We use abstraction graph that consist of abstraction links which are directed links representing abstraction connections. An abstraction connection is a connection between an instance and a classor between a sub-class and a super-class or between aconcept and an attribute of it.
For example, if converter is substituted for finput,function, with formatg and formatter is substituted forfoutput, function, with formatg, we need to de ne con-nections of meaning of these words. Figure 4 shows
an example of abstraction graph in that function is asuper-class of both converter and formatter, with format
is attribute of both, input is an attribute of converterand output is an attribute of formatter.
Figure 5 shows another example of tree structure.
Both of the tree structures in Figure 3 and 5 are reasonable and documents based on them are easy to read.

functioninputoutput

converterwith format

formatter

Figure 4. An abstraction graphfunction

input function

Sectionoutput function

without rigorousness. We have developed some systems
using this technique [2]. Their aim is to share information among persons in a group. The weakness of information structure causes exible knowledge developing
and using by a group.
In this study, we unify two types of abstraction link:
between sub-class(instance) and super-class(class) andbetween object and its attribute. Uni ed links are also
weak structures which have lack of information. However, they are sucient for the dynamic document constructor. We think the method can reduce the cost ofdeveloping abstraction graphs.

Subsection

6. Conclusion
converterItemformatter
output function
without-format

input function
without-format

scanf

gets
fscanfprintffgets

Paragraphputs
fprintf

fputs

Figure 5. Another example applying theContext-strengthen Model

5. Related work

The aim of this study is computer-aided knowledge
sharing. This theme has been researched by many researchers for example see [1]. However, knowledge intheir research is machine readable knowledge. Therefore they are represented in logical expressions. Knowledge in this study is human readable and represented
in natural language.
For sharing of human readable knowledge, digital libraries have been developed. However, they are thestatic document systems and have problems we pointed
in section 1.
A schema for stories has studied [3]. It is also basedon syntactic and semantic models. Our approach ofmodeling natural language text is similar to it. However, the research with stories aims to understand meaningful connections between sentences of stories. As connections between sentences of documents has functionsof structuring but does not have functions of adding
meaning to sentences, we can divide it into pieces.
Our model is simpler and easier to implement than themodel for stories.
The abstraction graph uses a technique named \weakinformation structure" that reduce the cost of knowledge developing by allowing knowledge representing

In this paper, we proposed a dynamic document system that can create a document dynamically and only
contains the information which a user needs. This system will reduce the redundancy and the contradictionthat a static document has. A dynamic document system consists of a common repository which contains
context-free document pieces. A context-free document
piece is expression in natural language which is understandable without context. We showed that contextfree document pieces can be made by splitting a staticdocument.
In order to construct a dynamic document, we proposed two semantic models. The rst models is Topdown Model based on connection between two succeeding sentences. We showed a technical document can beconstructed by eight categories of connection.
The second model is Context-strengthen Model
which considers a document as a tree structure of sections, subsections, and so on. Connected nodes of thetree structure have relation of order of context strength.
With this model, a computer can sort paragraphs andcreate sections, subsections and items.
We are implementing the Context-strengthen Model,
and will apply it to an interactive generator of HTMLtextbooks which can t various learners. Using thesystem, we will con rm documents generated with themodel are easy to read.
References[1] R. V. Guha. Representation of defaults in Cyc. In Proc.
AAAI-90, pages 608{614, 1990.
[2] H. Maeda, M.Kajihara, H. Adachi, A. Sawada,H. Takeda, and T. Nishida. A system for community information sharing and its evaluation at an international
conference. In Conference on Know ledge-Based Intel ligent Electronic Systems (KES'98), pages 405{410, 1998.
[3] D. Rumelhart. Notes on a schema for stories. In Representation and Understanding: Studies in Cognitive Science, pages 211{236. Academic Press, New York, 1975.