”o‘v-.
I
u
‘

 

:[HESES

'02;

Date

A ‘4;

w...“ 1"- n.\ _“3';

LIBRARY 1
Michigan Stan:
University

 

This is to certify that the
thesis entitled
REPRESENTATION AND PROCESSES

OF PEDAGOGIC KNOWLEDGE

presented by

HAROLD CHARLES GROSSMAN

has been accepted towards fulfillment
of the requirements for

Ph. D. degree in mm;—

Science

 

 

wflyfiz

Major professor

3-520- 75/

 

0-7 639

 

 

 

OVERDUE FINES:

25¢ per du per item
RETUMING LIBRARY MATERIALS
——-————__.

Place in book return to rerun
charge from circulation rec:

 

REPRESENTATION AND PROCESSES
OF PEDAGOGIC KNOWLEDGE

BY

HAROLD CHARLES GROSSMAN

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Computer Science

1978

ABSTRACT
REPRESENTATION AND PROCESSES
OF PEDAGOGIC KNOWLEDGE

BY

Harold Charles Grossman

Computer-based, generative instructional systems
have increased in occurrence as innovative methods of
instruction are developed. While generative instructional
systems are capable of the production of many problems,
the systems cannot solve these problems. The knowledge
representation and processes of these systems do not
cover more than one subject area. This research develops
a representation and processes for any pedagogic subject
area that can be expressed as a set of transformations.

A pedagogic knowledge representation is defined for
a task-oriented subject area. The thrust of the subject
area is the application of algorithms to data structures.
Three relations, simple transform, transform, and subset,
are identified. A diagram calculus is developed to identify
all transformations in a representation. A functional
automaton, whose language is the set of all functional
compositions in a representation, is derived from a
representation.

Pedagogic path, dependency, and partial ordering of
concepts are derived from a representation. Trivial,
simple, complex, complete, and extrinsic problems are

defined and discussed relative to a pedagogic

HAROLD CHARLES GROSSMAN
representation. A solution planning sequence which
solves problems independent of the problem generation
process is shown to compute the answer to the stated

problem.

ACKNOWLEDGMENTS

The author wishes to expresses his particular
appriciation to Richard J. Reid, his academic advisor
and chairman of his doctoral committee, who generously
gave his time and encouraging advice throughout the
research that lead to this work. The author would also
like to thank Martin Keeney, Carl Page, Lewis Greenberg,
and Jacob Plotkin for their participation in the doctoral
committee and their numerous suggestions for improving

the research.

ii/HI

FIGURE

11.3.3
11.4.3

11.4.4
11.4.5

III.2.12
III.7.1

III.7.2

LIST OF FIGURES

Digital Circuits Concept Tree .

Pi U~Pj . . . . . . . . . . . .

Pi '/° Pj . . . . . . . . . . .

Pedagogic, Functional Diagram .
Pedagogic, Functional Diagram of
"Angles" . . . . . . . . . . a .
Functional Automaton of "Angles"

PAGE

24
29

29
29

46

71
71

CHAPTER I

INTRODUCTION

The notion of a generative, computer-assisted,
instructional system has attracted some attention.
Carbonell(2), Vickers(35), Ramani and Newell(24), Brown
and Burton(l), and Koffman and Perry(10), among others,
have reported on such generative systems. The endeavor
at hand is not to devise another specialized generative
instructional system but to devise powerful and general
mechanisms to represent a large class of such generative
systems.

The current view in the field of artificial intelligence
is that intelligence will result when information and
processes of an appropriate form and content are constructed.
The attempt at construction of such processes is to be
complemented in artificial intelligence by studying their
actual and potential structure, and the structure of the
uinformation that they incorporate or might incorporate.

The research that is reported in this dissertation is the
application of the field of artificial intelligence to

the problem of a general representation of pedagogic
knowledge in a large class of generative, computer-assisted,

instructional systems.

1.1 Overview

A traditional computer-assisted, instructional

 

 

system is a collection of computer programs that simulate
one of the numerous activities associated with teaching.

A generative, computer-assisted, instructional system

 

 

 

is an instructional system that performs the instructional
activities from some representation of the knowledge
contained in the subject area. The exact form and
processes of the information contained in these represen-
tations differ from system to system and from subject area
to subject area. Most generative instructional systems
use ad hoc techniques that are devoid of identifiable
form or process. By studying those generative instructional
systems that do contain some form or process, a general
representation of the knowledge contained in these systems
may emerge.

The generative instructional systems can be categorized
into two classes via their design and usage. The first

class contains the attribute question-answer systems.

 

In these systems a question is asked pertinent to some
attribute of a concept in the given subject area. The
answer is typically one word or a short English phrase.
The answer can also be computed from the representation
of the knowledge in the subject area. Thus the attribute
question-answer systems have sufficient knowledge and
processes to ask meaningful attribute-type questions,
relative to the subject area, and to answer similar

questions posed to the system about the subject area.

3
The second class of generative systems is called

problem generators. The problems generated by these

 

systems require the application of an algorithm upon the
data structures that are produced by the system. The
answers to the generated problems are not determined by
the knowledge representation that is incorporated in

the system. The answers, if they are computed by the
system, are computed by special purpose routines. These
routines are associated with the generation of the problem
and possess none of the typical problem solving abilities
necessary for a solution that is independent of the problem
generation process. Unlike the first class of generative
instructional systems, the problem generators do not use

a representation of the knowledge in a subject area to
solve problems within that subject area.

The subject area of a problem generating system is

 

a collection of facts and actions that are modelled by the
activities which are simulated by the particular system.

A task-oriented subject area is a subject area that is

 

viewed from the data structures representing concepts

within the subject area and the algorithms that manipulate
those structures. The intrinsic elements of a task-oriented
subject area are the data structures and the algorithmic
actions that transform one data structure into another.

The second class of generative instructional systems

covers task-oriented subject areas.

1.2 Historical Vista

The usage of computers in assisting in the education
of students is attracting some attention, as new and
innovative, alternative approaches to the traditional
models of instruction are being developed. This usage
has developed in two major areas. The first area deals
with teaching students new material about a given subject
area. These instructional systems are the traditional
computer aided instructional systems. The second major
area is primarily concerned with the usage of computers
to test students. This latter area has mainly concentrated
on the construction of tests from a large data file of
questions.

Recent inclusion of artificial intelligence techniques
in specific generative instructional systems have yielded
a superior, more natural interaction between the student
and the particular system. This development has attracted
some researchers in the artificial intelligence area of
computer science and may yield some interesting results
with the application of artificial intelligence techniques
to the various aspects of constructing meaningful problems
within a given task-oriented subject area.

The more traditional computer aided instructional
systems, such as PLANIT, COURSEWRITER, and PLATO, use

an §§_hoc-frame-oriented approach as described by Carbonell(Z).

 

In this approach instructional material is stored in a
data base that consists of many frames of specific pieces

of text and questions. The frames include correct answers,

S
and frequently, anticipated wrong answers, keywords, and

branching. The data base is entered in advance by the
constructor of the instructional system. Essentially
once the system is specified, the instruction is identical
for each student. All of the traditional computer aided
instructional systems lack the dynamics of a normal,
instructional interaction between student and teacher.

To more closely model a typical teaching situation,
Carbonell(Z) designed and implemented a computer aided
instructional system called SCHOLAR. Carbonell described

SCHOLAR as an information-structure-oriented, computer

 

aided instructional system, because SCHOLAR is based on

the utilization of an information network of facts, concepts,
and procedures. By using the knowledge as specified in an
information-structure-oriented knowledge representation,
SCHOLAR can generate text, questions, and corresponding
answers. SCHOLAR can also utilize its information-
structure-oriented network to solve questions formulated

by the student. Thus a mixed initiative dialogue between
the student and instructional system more appropriately
simulates the student-teacher interaction.

The second category of computer-assisted instructional
systems is a more recent development of using a computer to
assist in the construction of tests. Several such systems
have been in existence at Michigan State University since
1971. One widely known test construction program is the
Prosser exam generator(22), designed and/developed by

F. Prosser of Indiana University. This exam generator

6

allows for the selection of questions from a data file
either randomly or by instructor specified codes. The
questions are printed on the left side of the printout
page while the answers to those questions are printed on
the right side of the page. The answers are computed
before hand and stored along with the questions on a data
file. Using this banking and retrieval mode of operation,
the composition of a test or homework exercise can be
automated along with answers to permit checking of student
responses.

Vickers(35) proposed using a syntax-semantic approach
for building questions which would involve the construction
of valid and invalid FORTRAN variable names, expressions, and
statements. The syntax-semantic approach, as described by
Vickers, involved the writing of specific routines for each
kind of question, i.e. one routine would construct valid,
invalid, real, or integer variable names. The resulting
system is expandable by writing new routines for each
additional type of question to be built.

Izquierdo(8) and Whitlock(36) extended the original
syntax-semantic ideas of Vickers to a general purpose
routine that uses a set of productions to construct the
desired question. This latter approach provides a flexible
approach to the generation of questions and begins to
identify some possible forms and processes necessary for
the construction of a large class of questions.

Ramani and Newell(24) investigated the design and

implementation of a problem generating system that constructs

7

programming assignments from an abstract representation
of the problem. Design strategies utilizing grammar-like
mechanisms to put together the compatible elements to
create an acceptable problem structure are described.
Attention is given to the mechanisms necessary for
controlling the generation of coherent English cover
stories; of problems involving specified concepts in a
given subject area; and making use of information available
about the concepts involved in the subject area. Other
strategies discussed by Ramani and Newell are: generalized
good problems to produce useful variants of problems; the
use of reasoning about actions in a task area to recognize
good problem situations; and the design of surface details
to create problems having a given abstract structure.
Brown and Burton(l) describe a computer-assisted
instructional system that is called SOPHIE. The problem
situation in SOPHIE has a student trouble-shooting a
particular piece of faulty electronic equipment, namely
a Heathkit IP-28 regulated power supply. The student can
ask for various measurements, make hypothetical changes,
and ask for a list of possible faulty electronic components
that is consistent with prior measurements. A backward
working specialist and a forward working deduction system
are used to develop a list of faulty components. SOPHIE
also incorporates a semantically oriented predictive
parser to carry out a natural language dialog with the
student.

Koffman and Perry(10) report on an intelligent computer

8

aided instructional monitor and generative tutor that they
have developed at the University of Connecticut. The tutor
has a simplified English interface with the student and
produces problems from some form of representation of the
subject area. The exact form of the knowledge representation
is not clearly specified. The knowledge may be directly
programmed in the routines that generate and solve the
problems in the system. The solutions of the generated
problems are computed by specific LISP routines. The LISP
routines do not have the ability to solve a problem that

is not generated by the tutor.

Earl Sacerdoti(28) at Stanford Research Institute is
developing a methodology for an organization of plans of
actions for a computer based consultant. The computer
based consultant is an expert on the assembly and disassembly
of an air compressor. The plans for working on an air
compressor are built in a representation called a procedural
net. Although immediate application of the ideas and
techniques being developed by Sacerdoti to the solution
of problems in a task-oriented subject area are not clear,
the class of activities of formulating plans and carrying
those plans to their conclusion is in the category of the
kinds of actiVities that an answer formulator for a
problem generating system would have to possess.

Several areas of artificial intelligence research
are tangential to the development of a knowledge representation
that is suitable for a large class of problem generating

systems. Novak(18,l9) has developed a computer program,

9
ISAAC, which solves physics problems stated in English. The

knowledge representation that Novak uses is a canonical
object frame which is similar to a semantic network form of
representation. de Kleer(5) describes a program, NEWTON,
that employs multiple strategies in the solution of
classical mechanics problems. Sussman(32) describes a
problem solver for electrical design- The solution technique
is stated in terms of "problem solving by debugging
almost-right plans." Sussman's belief is that the creation
and removal of bugs is an unavoidable part of the process
of solving a complex problem.

The application of artificial intelligence techniques
to instructional systems of the attribute question-answer
category enhances the performance and interaction of these
systems. A more natural student-teacher interaction that
closely models the typical instructional environment is
the direct result of the inclusion of artificial intelligence
techniques. Such systems appear to be superior to their

non-artificial intelligence counterparts.

I.3 Context of Research

The goals of artificial intelligence researchers are
diverse, so it is necessary before going too far to
understand how the present work is related to artificial
intelligence's major subareas. Nilsson(16) has divided
the field of artificial intelligence into a number of
research areas, of which four are designated core areas,

and the rest, first-level applications areas. The four

10

core areas are: common-sense reasoning, deduction, and
problem solving; modeling and representation of knowledge;
heuristic search; and artificial intelligence systems and
languages. The present effort is in the second category
but also touches on the first category. The principal
approach of research in those areas is the building of
understanding systems that embody knowledge about some
subject area, that are able to manipulate that knowledge,
including problem solving, and that are able to exhibit
communicative behavior to demonstrate their abilities and
the content of knowledge that they contain.

A number of past efforts of constructing generative
instructional systems have dealt with various aspects of
some of the problems encountered in building understanding
systems(l,2,8,9,10,l8,l9,24,27,35,36). None have dealt
with the form of the representation of the knowledge
content for more than one subject area. Only two generative
instructional systems contain the ability to solve their
own questions independent of the generation process(l,2).

Several lines of research that are relevant to various
components of generative instructional understanding systems
can be mentioned: problem-solving techniques and solving
simple puzzles using means-ends analysis and heuristic
search; the representation and subsequent use of structured
knowledge in semantic networks; and the use of ad hoc
problem solving procedures along with the use of predicate
calculus notation and general uniform proof procedures.

In addition to the necessary scope limitations of

11

many of the results of research in the past, there are

some broader respects in which the research is inadequate
for attacking the larger aim of building knowledge
representations for generative instructional understanding
systems. The effectiveness of any single representation
over a diverse set of subject areas has not been demonstrated.
To aim at such a representation is desirable at least from
the standpoint of parsimony, though parsimony might turn
out to be unachievable. In dealing with knowledge
representations, each system represents its own task domain
without attempting to address any of the typical examples
of the other systems, or to deal with specific problems
(representational and processing) in the other approaches.
This results in a collection of systems covering a number
of task areas but whose interactions and overlaps are quite
unknown. As a result it is difficult to determine if
particular research is a real advance.

Very few systems have a coherent approach to one of
the primary problems of the area, the knowledge interaction
problem. SCHOLAR and SOPHIE are examples of systems that
do address the knowledge interaction problem. This problem
can be partially approached by asking how knowledge is
applied when appropriate, how its appropriateness is
recognized so that it can be brought to bear, and how it
.interacts with other pieces of knowledge in ensuring a
correct result when single pieces of knowledge or single
knowlege sources are insufficient by themselves.

There are a number of essential properties, from a

12

conceptual standpoint, of a knowledge representation if

it is to be used effectively for a generative instructional
understanding system. Moore and Newell(12) give a list of
dimensions on which understanding systems are to be
evaluated. This list includes representation, assimilation,
efficiency, accommodation, action, directionality, depth

of understanding, and error. Without elaborating on the
definitions of these dimensions, it can be seen that these
are high-level properties of a system. Rather than using
those traits directly, Rychener(27) suggests that it is
more useful to focus on the representation, and see how the
various traits imply desirable properties for the system.
The following list of properties of knowledge representations
has emerged, though it is not to be put into direct
correspondence with the list of eight dimensions suggested
by Moore and Newell.

Knowledge within the structure should have the
following characteristics:

1. Encodability - knowledge should be easily mapped
from an external form to the form in the understanding
system; ultimately, the encoding should be accomplished
via an automaton.

2. Inspectability - content of knowledge already
encoded should be readily derivable; this is the converse
of encodability, and perhaps could also be called
extractability.

3. Accessibility - knowledge should be accessible

in some form for application when it is appropriate; this

13

need not be as complete an operation as for inspection;
when knowledge is accessed or applied, its own nature is
not evident as is its effect.

4. Operability - knowledge must be amenable to such
operations as mapping, forming analogies, generalizing,
optimizing, reformulating, deducing, and inducing.

5. Flexibility - knowledge should have a number of
alternative forms, for instance along the procedural-
declarative aspect.

6. Organizability - there should be a variety of
potential control organizations, according to the demands
of various kinds of content knowledge.

7. Provability - there should be a way to guarantee
correctness or perhaps consistency of the encoding, in
some informal sense; this may include being able to
justify the presence of some knowledge by knowing how it

has been found necessary for some behavior.

1.4 Goals

The main goal of this dissertation is to establish
a knowledge representation and processes for a large class
of generative instructional systems in a task-oriented
subject area. Just as all artificial intelligence research
projects, by necessity, have been restrictive, the current
effort is restricted to representations and processes for
a pedagogic subject area.

The subject area is viewed from the concepts that

compose the subject area. The concepts are represented by

14

data structures and algorithms. The knowledge that will
be represented is algorithms and data structures that are
the concepts in a pedagogic subject area. In the remainder
of this Work we will call a formal task-oriented subject
area, a subject area, and by that mean a pedagogic subject
area composed of concepts that are represented by algorithms
and data structures.

A direct benefit of developing a general representation
of the pedagogic knowledge content in a subject area is
that all generative instructional systems could use the
same representation schema. The constant schema would
permit experimental comparisons of different systems
possible with the measurement of such properties as
smartness or flexibility. Other benefits would be greater
emphasis of the processes that are involved in generative
instructional systems and a basis for departure of future
work in this area.

The processes that complement the representation
in a generative understanding system, as described by
Ramani and Newell(24), can be grouped into three areas.
The representation and processes must be sufficiently
rich to 1) answer pedagogic questions about an encoded subject
area, 2) construct complete, meaningful problems from an
encoded subject area, and 3) construct a sequence of problem
solving steps from which an answer to any possibly generated
problem from a given representation could be computed.

The first capability provides the means for extraction

of the knowledge content within a given representation.

15
Without this ability the constructor of an encoded subject

area would be unable to justify to himself, herself, or

others that the encodement was complete with respect to

any criteria. The first capability also permits a measurement
of pedagogic aspects of a specific representation.

The more interesting capabilities are the second and
third ones. These abilities provide a basis from which to
address questions such as: what is a good, meaningful,
complete problem; when can a problem be solved; can a
paraphrase of another problem be identified; does the
construction of problems from a given representation have
any analogy to the human process of construction of
problems; and do the problem solving steps have any analogy
to the human process of problem solving. The major
thrust of this work is the development of a theoretical

foundation to address the above questions.

1.5 Organization

The remainder of the dissertation is organized into
four chapters. Chapter II is a study of various knowledge
representations that have been used in artificial
intelligence research and in generative instructional
systems. Representations including syntax-semantic-like
forms, semantic networks, and concept trees are viewed
relative to the goals outlined in chapter I.

Chapter III is the development of a knowledge
representation in terms of a set of primitive relations

and the composition of those relations. Mathematical-like

16
properties of the primitive relations and their combinations

are included. Several subject areas are encoded into the
developed representation.

Chapter IV presents pedagogic implications that are
derivable from a representation. A problem is defined
relative to the developed representation and a meta-grammar
is presented to determine complete problems. A problem
solution sequence is shown to solve complete problems
in a given representation. Chatper V concludes the work

and suggests some extensions to the present research.

CHAPTER II

LITERATURE REVIEW

Several alternative representations have been used to
represent the knowledge content in a computer-assisted
instructional system. Grammar-like mechanisms have been
the most prolific with respect to systems whose main
thrust is the generation of problems(8,10,24,33,35,36).
Semantic networks have been used in several instructional
systems as a knowledge representation(1,2,24). Concept
trees have played a central role in several instructional
systems as a means for describing a pedagogic ordering
of concepts within a subject area(9,10). None of these
mechanisms have been used for both the construction of

problems and the solution of problems in a subject area.

11.1 Grammatical Representations

The simplest generative representation for problems
is an extension of the "slot-and-filler scheme" as it is
called in linguistics. In this scheme a problem is
expressed as a set of problem frames incorporating variables.
Each problem frame has a specification of the admissible
values that the variables or slots of the frame may assume.
The specification for the slots are either in the form of-

numerical limits or a set of admissible values for each
17

18
variable.

The slot-and-filler scheme can be enriched in two
directions. Uhr(33) reports one direction which is to
implement computationally defined relations between the
variables of a problem frame. By choosing certain
independent variables randomly, either within the permitted
range of values or from sets of admissible values, the
remaining variables could be computed from these randomly
chosen variables. The computational relations would
ensure that a meaningful problem is constructed from a
compatible selection of values for the variables in the
problem frame.

The second direction of enriching the slot-and-filler
scheme involves the use of a context-free grammar. Using
a context-free grammar, the problem frames are the language
of the grammar. Thus unlike the slot-and-filler schemes
using the problem frames described above, the grammar-like
schemes are not limited to regular languages. The
grammar-like schemes have been used in the context of
problem generation for synthesizing data structures having
phrase structure.

Simple programs that use grammar-like schemes to
generate questions in artificial intelligence (developed
by Newell and Robertson) and in cognitive psychology
(developed by Waterman) have been in use at Carnegie-Mellon
University since 1971(24). The generations produced by
these programs are always grammatically and semantically

correct with respect to natural language theory. Most but

19

not all questions generated are meaningful within themselves.
The grammar-like generation schemes could also include
probability assignments that allow certain choices of
syntactic and semantic structures to be more or less

frequent than other choices. This allows some control on
the generated structure so that favorite problem structures
are more likely.

Enumerative schemes, such as the above, derive their
power from a basic device that is the classification of a
set of phrases into different subsets of syntactically
and semantically similar items.\ The problem frames and
context-free grammar schemes are not sufficiently rich to
express the knowledge content of a subject area to both
generate and solve problems from the same representation.

Implicit representation of knowledge in grammar—like
systems provides only two devices to ensure coherence of
the generated problem: co-occurrence of symbols in the
grammar rewrite rules which ensures co-occurrence of
complementary parts of the problem; and set membership
which enables semantically and syntactically equivalent

°items to be distributed in the problem in an identical
manner. An inherent limitation with grammar-like systems
is the absence of an explicit representation of the
knowledge content of the kind found in practically every

artificial intelligence research project.

20

11.2 Semantic Networks

Carbonell(2) chose to use semantic networks as the
knowledge representation in his instructional system
SCHOLAR. Carbonell developed SCHOLAR's representation
from earlier work that Quillian(23) first reported in
1966. Quillian used semantic networks to model human
memory and natural language comprehension. Carbonell
extended Quillian's work to develop a knowledge represen-
tation that would pose questions to a student, check the
studentls answer, and most importantly answer student
posed questions.

The particular dialect of semantic networks that
Carbonell used is described as an organization of units
of information in terms of their natural language meanings
and relationships. Each unit of information may refer
to other units within the set of information units. Each
unit may also refer to other units which refer to other
units or itself. Carbonell called this particular semantic
network, a "semantic information network."

The units of information are nodes in the computer
implementation of the knowledge representation. There are
two kinds of nodes which are labeled type nodes and token
nodes. In Carbonell's usage of semantic networks, a type
node is a unit pointing to an informational, multi—level
list of pointers to other units. Words referring to other

nodes in the body of the unit are token nodes. Each token

 

node represents a pointer to the corresponding type node,

i.e. the unit with that word as a name. By using type

21

and token nodes, information is not necessarily duplicated,
since it is stored only once at the type node. This type
of knowledge representation is recursive and leads to
circularities which do not represent a serious difficulty
and are not necessarily undesirable.

Each unit may be thought of as pieces of information
to which is associated a name. There is no one-to-one
correspondence between units and names. Each unit is
composed of three elements. The first element of each
property is the name of the property or attribute. The
second is a set of tags used by the executive routine.

The third element is the value of the attribute. A value
can be either a set of attributes of a pointer to a unit
or a set of units modified by other attributes.

By encoding a subject area such as the geography of
South America in the above semantic network, answering
and asking questions about the subject area involves
following pointers and type nodes until the appropriate
token node is found. Thus all of the properties of a given
subject area are abstracted to generalized attributes.

For instance, some of the attributes relative to geography
are population, size, cities in a country, countries in

a continent, language of a country, and principle industries
in a country. To answer questions such as "Name a country
in South America?" or "What language is spoken in
Argentina?," the appropriate attribute link (countries in a
continent, language of a country, respectively) from one

unit (South America, Argentina, respectively) to the answer

22
(Argentina, Spanish, respectively) is followed. This

category of question and answer producer is very analogous
to the question and answering systems developed for natural
language processing of which some of the most notable

are those by Schank(29) and Woods(39).

An internal representation of the knowledge in a
subject area provides the flexibility to generate questions
and answer questions about a subject area. The semantic
network with its value-attribute-value representation
allows for the generation or answering of attribute
types of questions. For attribute types of questioning
and answering, the semantic information network as a

knowledge representation is a quite adequate structure.

II.3 Concept Tree

Koffman(9) develops the idea of a concept tree to
specify the order of presentation of course concepts via
a generative instruction system. The nodes of a concept
tree represent the course concepts and the branches of the
tree represent one of two relations that are defined later.
The concept tree represents the constructor's interpretation
of the relationship between course concepts. Obviously,
concept trees are not unique for a given subject area, just
as different people interpret course concepts differently.
The plateau upon which a given concept is placed indicates
that concept's relative degree of complexity within the
subject area. The concept tree for a digital circuits

course, as developed by Koffman, is shown in Figure 11.3.3.

23

The relations between the nodes of the tree can be
defined as follows:

Definition II.3.l Concept A is a prerequisite of

 

concept B, denoted as .-.——->—- , means that concept
A should be mastered before concept B.

The normal order of presentation and learning of a
given concept would be all of the prerequisite concepts
followed by the given concept. Notice that the relation

"is a prerequisite of" is a transitive relation such that

if ..—->.._. and .-—>—— , then
[El—w].

Definition II.3.2 Concept A is a prerequisite of

 

concept B and concept A may be used as a subconcept by B,

denoted as , means that concept A should

be mastered before concept B and that when solving a

 

problem involving concept B, solution techniques involving
concept A might be used as a series of sub-tasks.
While Koffman does not mention any relational

properties, the latter relation appears to be transitive

such that if and ,
then u .

By using the above relations, Koffman constructs a
concept tree for a given subject area. His instructional
system uses the constructed tree to select appropriate
concepts for the student to learn. In general, all

concepts on a given plateau are mastered before advancing

24

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

state table word problem sequential
sequential ~r-——>-—— to state circuit
circuit table analysis
single flip-flop
flip-flop := analysis
(D,JK,or SR) flip_flop
design
A ,
I
Karnaugh tabluar :<. prime A
maps minimization implicant I
\ \ \ ‘6 selection i |
' V \ \
\ \ \ \ l
\ \ \\ \ I
complement binary combinational
racti n multiplication design

 

 

 

 

 

 

 

 

 

 

or

 

 

 

 

I
l
A» \\ i 'i
l
i complement bin-oct-hex /
i in bin-oct-hex addition tables
/ \

l i L

/ \

 

 

 

 

 

 

 

 

 

 

 

 

numbers ,, I
/
A ‘4w/7/ 4,
l
l I / / l /

decimal to bin-oct-hex register register
bin-oct-hex to decimal "anding" "oring"
conversion conversion

 

 

 

 

 

Digital Circuits Concept Tree

Figure 11.3.3

25
to the next higher level plateau. The second relation

between course concepts begins to identify the importance
of problem solving by using a knowledge representation

of the subject area. Koffman does not use the relation

in solving problems that his instructional system generates.

Obviously, the concept tree in Figure 11.3.3 is not a tree

in the mathematical sense

II.4 Abstract Problems

Koffman and Perry(10) introduce the idea of a basic
abstract problem as a structure representing certain
subclasses of a given collection of problems.

Definition II.4.l An abstract problem is a triple

 

of the form ((unknown), (data), (relation)) where (unknown)
is a list of variables whose values are sought as the
solution to a problem represented, (data) is a list of
input variables, and (relation) defines a function which
assigns unique values to the unknowns for each list of
idata values.

A basic abstract problem is assumed to be solvable.
A complex abstract problem is one that is constructed
from several basic abstract problems. Each basic abstract
problem will have a corresponding problem solver or solution
method. The problem solver is determined by the problem
generator. A complex abstract problem will be solvable
by using a combination of the problem solvers associated

with its basic abstract problem constituents.

26

Definition II.4.2 A problem generation and solving

 

system is described by a triple (C, R, S) where R is a
representation for the class of problems C which can be
solved by the solution method S.

Koffman and Perry(10) indicate that the power of such
a system can be measured by the size and variety of C. The
power can be increased by l) enlarging C while keeping S
fixed, 2) enlarging C while extending S, or 3) decreasing
the degree of specialization required of the user to
implement S while keeping C and S (the method) fixed.

As an example, let (Ci, Ri’ Si) be a collection where
C1 is a subclass of problems represented by Ri and solvable
by 31' The subclass of problems, Ci' deals mainly with a
particular concept in a course. Ri could be a generative

grammar or a generation routine which generates problems

dealing with Ci' Si solves the generated problems and

monitors the student's solution. A generative instructional
system can be extended by adding more basic elements.

By defining relations on the basic elements, a structure
such as a concept graph similar to Koffman's(9) concept

tree can be identified.

The predicate of an abstract problem ((unknown),

 

(data), (function)) is the predicate PR such that PR((unknown),
(data)) is true if and only if the value(s) of the (unknown)
are the value(s) given by the function defined by (function)
when evaluated on (data). Predicates can be used for formal

proofs concerning abstract problems. If the predicate of

27

a problem can be proven from the predicates of basic
abstract problems, the structure of the solution in terms
of basic solution procedures is determined by the proof.

The constructions on abstract problems involve set
theoretic and functional operations via Koffman and
Perry's(10) schema. Constructions include subproblem,
specialization, generalization, analogy, transformation,
union (or concatenation), composition, cascade, and domain
dependent constructions. The constructions are implemented
as operators which apply on the one hand to sublists Ri
and on the other hand to solution routines Si' The main
syntactic generative operations are union, composition,
cascade, and certain kinds of transformations. Subproblem
is a decomposition techniques which yields, ultimately,
basic problems. Specialization, generalization, and
analogy are special cases of transformation.

Let Pi and Pj be two abstract problems with

_ i i _ j 3'
Pi - ((Y ). (x ). (81)) and Pj - ((Y ), (x ), (sj))

with predicates PRi = ((Yl), (x1)) and PRj = ((YJ), (x3)),
respectively. The union or concatentaion of Pi and Pj'
denoted-Pi u pj. is defined to be <(<Y1)U(Y3). (<x1)U<x3)).

(SPi U Pj)) where SPi U Pj is a solution routine for all

the problems represented. SP U P is determined by the
i j

conjunction of PRi and PRj, i.e. PRi((Y1), (X1))AI

PRj((Y3), (XJ)). "U", union, on the variables indicates

28
set union. The superscript denotes a list of variables.

Diagrammatically, the union of Pi and Pj is shown in
Figure 11.4.3.

Let Pi and Pj be the same as before except that Y1

is a single element, Yi' and (Yi) 9 (X3). Pj - Pi’ the

composition of Pi and Pj' is defined to be ((Yj), ((X1)U

j _ . .
((X ) (Yi)))' (SP. , Pi)) where SPj . P1 13 determined by

the predicate PRiHYi). (xl)) /\ PRj((YJ). ((Yi)U((x3)-
(Yi)))). Diagrammatically, Pj - Pi is given in Figure

II.4.4.
The cascade operation is a generalization of both

the union and composition operations. Let Pi = ((Yl),
(X1), (81)) and P3. = ((Yj), (X3), (Sj)) and also assume
that (Y1)() (X3) is not empty. Pj °/- Pi’ the cascade of

Pi and 123., is defined to be (I(Yj)UI(Yi)-(<Yi)n(xj))>).

((xi)U((xj)-((Yi)n<xj)))). (s ,/, P.)> where s
l

P. °/° P.

P .
j l

J
is determined by the predicate PRi((Yi), (Xi))/\ PRj((Yj),
(I(Yiwxj))u<(xj)-<(Yi)mxj))m. The cascade of Pi

and Pj is illustrated in Figure 11.4.5.

Another natural relation which can hold among abstract

problems is that of a map or transformation. Let Pi and Pj
be defined as before. A map from Pi to Pj is a pair

(fl, f2) where f1: (Yi)———>-(Yj) and f2: (Xi)-—a>-(Xj)

29

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

l /
j _ XI, 3
P U P.
1 J

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

XJ-Y. I, l
l
P ° P .
1 3
Figure 11.4.4
i >Y1- (Ylnxj)
X
pj =%YJ
x3- (Ylnxj) /’

 

 

 

Figure II.4.5

30
such that if PRi((Y1), (x1)) is true then PRj(fl((Y1)),

f2((X1))) is also true. If Pi is an abstract problem
and f = (f1, f2) is a pair of functions such that PRi((Yl),
(x1)) is true implies that PRi(fl((Y1)), f2((xl))) is

true, then the construction by map gives the abstract

1 i
problem f(Pi) = (<f1((Y ))). f2<(x ))). (31)). If the

condition on the predicate does not hold, it will be
necessary to modify Si to obtain a new solution routine.

The shortcomings of semantic networks is that the
attribute in the value-attribute-value link is difficult
to generalize to any task-oriented subject area. The
necessary attributes have been identified for the specific
subject area "mechanics"(5,18,l9). However, the generalization
of these or other attributes to any task—oriented subject
area seems difficult.

The syntax-predicate representation that is developed by
Koffman and Perry(10) has several shortcomings. The
representation does not allow the discovery of additional
knowledge from the original encoded subject area. The
solution of a problem does not solve a problem but just
provides an answer in conjunction with the generation of
a problem. The solution procedure of complex problems,

i.e. S is not shown to solve the stated problem, is

O. '
Pj/Pi
not shown what it is, and is not shown how to compute it.
The manipulation of knowledge and the processes of the
syntax-predicate representation are shortcomings with

Koffman and Perry's representation.

CHAPTER III

REPRESENTATION OF PEDAGOGIC KNOWLEDGE

A representation of pedagogic knowledge is presented
for subject areas that are composed of declarative and
procedural concepts. Three binary relations, "simple
transform," "transform," and "subset," are used in the
description of a knowledge representation. A diagram
calculus is developed to construct pedagogic, functional
diagrams from a graphical representation of the simple
transform and subset relations. Elements of the transform
relation are discovered by manipulations of the diagrams.

A functional automaton is developed which accepts
all functional compositions of a pedagogic knowledge
representation. Non-repetitive functional compositions
are computed from a matrix-type calculation. The chapter

is concluded with an example subject area "angles."

III.l Relations

Definition III.l.l A subject area is identified by

 

a finite non-empty set C of concepts. C = D U P where
D is a non-empty set of declarative concepts and P is a

non-empty set of basic procedural concepts. A declarative

 

concept is a set data structure. A procedural concept pk

 

is an (n, m) recursive function where the domain of pk
31

32

consists of n-tuples and the range of pk consists of m-tuples.

Notationally, an element of a set is denoted by a small
letter and a subscript, e.g. an element of P is pk.

Examples of declarative concepts are a set of regular
grammars, a set of directed graphs, and a set of Turing
machines. A set will be named by the objects in that set,
e.g. a set of regular grammars will be called "regular
grammar." Examples of procedural concepts are the mapping
of a context-free grammar into a grounded context-free
grammar, the mapping of a graph into a path between two
nodes in the graph, and the mapping of a push-down automata
into the language of the push-down automata. Each element
of P will be denoted by a name that represents the mapping,
e.g. the mapping of a context-free grammar into a grounded
context-free grammar will be called "grounding."

The procedural concepts are more important than the
declarative concepts. The center of activity of this
research is the procedural concepts or algorithms that
determine the problems which can be formulated in C.

Three relations are identified with respect to C.

Definition III.1.2 A functional t from P to binary

relations, called simple transform, is defined as follows:

 

II‘

n I
t(pk) = {( H d., H dj) I di' dj 8 D for l i a n and

d., and
3

m
a
a.
H
m

L...I
u
a
n:
s
n.

'0

w

":1:
o.

II=15

l j l

B

n I
H d. :— domain pk, and II dj

E range p l
1 1 3:1 k

33
Graphically, an element of t(pk) is denoted by

d d

The brace may be omitted if the domain or range of pk
is a single declarative concept.

The relation t describes all basic functional
relationships between the procedural and declarative
concepts in C. An implicit assumption is that the
complete domain and range of pk is not necessarily known.
All that is known about pk is at least one subset of the
domain and one subset of the range. The relation t(pk)
does not necessarily contain all pairs of elements in C.

Example III.1.3 Consider the transformation
called "directly produces" which maps a "sentential form"
of a grammar into a "sentential form" of that grammar.
The concepts in the example are

C = {directly produces(DP), sentential form(SF)}
where the abbreviations of the concepts are enclosed
in parenthesis. The procedural concept is

P = {directly produces(DP)},
and the declarative concept is

D = {sentential form(SF)}.

The transformation is

DP: SF—a-SF .

Then by Definition III.1.2

t(DP) = {(SF, SF)}.

34

The graphical representation is

SF DP >r SF

 

The above example illustrates a single declarative concept
in the domain and range of a procedure.

Example III.1.4 A second example involves the
declarative concepts

D = {syntax tree(ST), grammar(G), sentential form(SF),

left-most canonical derivation(LMCD)}

and the procedural concepts

P = {structuring(S), derivation sequences(DS)}.
The transformations are

S: ST —e>-G X SF
and

DS: ST X G -fi>-LMCD .
Then by Definition III.1.2

t(S) = {(ST, 6 x SF)}
and

t(DS) = (ST X G, LMCD) .
The graphical representation is

G ST

ST r— and DS r- LMCD .
SF G

 

 

The example depicts multiple declarative concepts in the
domain and range of procedural concepts.
Example III.1.5 Another example involves the

declarative concepts

D = {left linear grammar(LLG), right linear grammar(RLG),

35

language(L), sentential form(SF), finite state
acceptor(FSA)}
and the procedural concept
P = {grammar intersecting(GI)}.
The mapping is
GI: LLG X RLG —+> L X SF X FSA .
Then
t(GI) = {(LLG x RLG, L x SF x FSA)}.

The element is represented by

L
LLG
—_._v,_
SF .
RLG GI
FSA

The above example displays multiple declarative concepts in
the range and domain of a procedural concept.
Definition III.1.6 A binary relation S on D,
called subset, is defined as follows:
S = {(di' dj) I died.j where di’ dj 6 D}.

Graphically, an element of S is represented by

Subset, as usual, is not reflexive or symmetric but is
transitive.

Example III.1.7 Let the declarative concepts in
C be

D = {phrase structure grammar(PSG), context-sensitive

grammar(CSG), context-free grammar(CFG), linear

36

grammar(LG), regular grammar(RG)}.

Then
S = {(CSG, PSG), (CFG, PSG), (LG, PSG), (RG, PSG),
(CFG, CSG), (LG, CSG), (RG, CSG), (LG, CFG),
(RG, CFG), (RG, LG)}.

For notational purposes the functional composition
of basic procedural concepts, pk's, is denoted by a

small letter with no subscript, e.g. pk p. is denoted

1

If p: d——> e and q: e ——> f, then the functional

by p.

composition q pzd —+>-f.

Definition III.1.8
P = {q I q s P or q is the composition of elements in P}
Definition III.1.9
n n m .
DOM(p) = { n di | ( n di' n d.) c t(pn) for p = pl 92 - -
i=1 i=1 j=l 3
. . pn, and p c P}
Definition III.1.10
m . n m .
RNG(P) = {.5 dj I (.H di’ .3 dj) 6 t(pl) for P = P1 P2
j-l i=1 j—l

. . pn, and p c P}

Definition III.1.ll

relations,

called transform,

A functional T from P to binary

is defined as follows:

 

n m
T(p) =
i=1 3

n

m, and H d. s
. 1
l=1

m .
and H d.'2
i=1 3

11d.) | d.

, dj 8 D for l t i e n and

1

domipl for donkm) 5 DOM(p),

rngf(p)'for rngf(p) e RNG(p)}.

37
Graphically, an element of T(p) is denoted by

The relation T is described by t, S, and P.
Obviously, t S T.
Example III.1.12 Consider the declarative concepts
D = {context-free grammar(CFG), regular grammar(RG),
context-free language(CFL), context-sensitive
language(CSL)}.
the procedural concept
P = {language determination(LD)},
and the transformation
LD: CFG —>—CFL .
(CFG, CFL) is in t(LD) and (RG, CFG) and (CFL, CSL) are in
S. By Definition III.1.ll
T(LD) = {(CFG, CFL), (RG, CFL), (CFG, CSL), (RG, CSL)}.
The above example illustrates the sub-domain and super-
range aspects of Definition III.1.11. The additional mappings
identified are; LD: RG-——+—CFL ; LD: CFG ——>-CSL ; and
LD: RG -—>- CSL.
Example III.1.13 As an additional example of the
functional T, consider the concepts
D = {context-free grammar(CFG), context-sensitive
grammar(CSG), derivation sequence(DS), left-most
canonical derivation(LMCD), right-most canonical

derivation(RMCD), syntax tree(ST), sentential

38

form(SF), sentence(S)},
P = {sequence structuring(SS), grammar induction(GI)},
and the transformations
SS: 08 X CFG ——>-ST X 8
GI: ST X S —d> CFG
GI SS: DS X CFG ->-CFG
Then

t(SS)

{(DS x CFG, ST x S)}

t(GI) {(ST x S, CFG)}

S = {(CFG, CSG), (S, SF), (RMCD DS), (LMCD, DS)}
From t, S, and the functional composition GI 85, the

following elements are identified by Definition III.1.ll:

T(SS) = {(05 x CFG, ST x S). (RMCD x CFG, ST x S),
(LMCD x CFG, ST x S), (DS x CFG, ST x SF),
(RMCD x CFG, ST x SF), (LMCD x CFG, ST x SF)}.

T(GI) = {(ST x S, CFG), (ST x S, CSG)}, and

T(GI SS) = {(DS x CFG, CFG), (LMCD x CFG, CFG),

(RMCD X CFG, CFG), (DS X CFG, CSG),

(LMCD x CFG, CSG), (RMCD x CFG, CSG)}.
Functional composition, sub-domain, and super-range are
illustrated in the example. From the initial three
mappings an additional eleven mappings have been identified.

Definition III.1.14 The relational composition

 

of T(p) and T(q), denoted as T(p) o T(q), is defined by

n m g r u
T(p) o T(q) = {( n di, n d.) | ;3 n ak such that
i=1 j=l 3 k=l
n r n r n m I
( H di' H dk) e T(p) and ( H d , H d.)
i=1 k=l k=1 j=l 3

39
c T(q)}.

Relational composition of T is related to functional
composition by T(p) o T(q) e T(q p).

The operation of finding elements of t and S for a
given T is at best a guess among many candidates. Let

tl(p) = {(dZI d3)! (d2; d4)}p and

S ={(d1, d2)}.

Then

T1(P) = {(dZI d3)! (d1: d3): (d1, d4), (d2! d4)}.
Also let

t2(P) = {(dZI d3), (d1: d3)}r and

S = {(d3, d4)}.
Then

T2(p) = {(dzr d3): (d1: d3): (d1: d4): (d2! d4)}-

However T1(p) and T2(p) are the same.

 

Definition III.1.15 A pedagogic knowledge

representation is a 4-tuple <D, P, t, S>.

 

III.2 Diagram Construction
The graphical representation of the relations simple

transform and subset is called an elementary diagram.

 

Elementary diagrams are combined to form a diagram. The
parts of a diagram that are elementary diagrams are called

diagram segments. An operation is a general rule that

 

 

describes the manner in which the elementary diagrams and
diagram segments are manipulated.
The eight operations below are called construction

operations because of the building nature of the operations.

40

In the description of the eight operations below, the first

two diagrams are elementary diagrams or diagram segments;

the last diagram is the results of combining the first

two diagrams. The eight construction operations are:

Operation III.2.l

I I II
d1 d1 d1 d1
I -———s» ' , i -————e— °
. p I C q C
' I II
dn dm dm d r
I , II
d1 d1 d1
yields . ——15—>— . —7;——>- .
. . I . II
an am ar

The interpretation of the resulting diagram is that

I
i d. and that q: H d
1 j-l 3 j=

, r
- —-d>-H d

1 k 1

k .

'U
":15

o.
Izna

Operation III.2.2

d. d.
IL: r1:
dj dk
d.
1
yields dj
dk

The resulting diagram indicates that dk c d. c di

Operation
d1
dk
d

n
yields

 

41

111.2.3
d1 dk
—————" I
p . i
I
d dr
m
d1
I
d1
r—dk 17"“ -
a
m
a
n
m
dr

The resulting diagram indicates that

X

p: (11 . . .

x d

X

k
and that
p: d1 X . . x dr x ,
Operation III.2.4
d1
d -——-—->
r P
d

I
. . x dn-—+>-d1 x . . . x d

. x dn-——=>--dl x . x d
I
d1 dk
.' J\
d dr
m

42

 

dk

d1

' I

. d1
yields \-—%:dr ———E——%» .

. d

m
d
n

The interpretation of the resulting diagram is that

I I
o o x d ""_+ d x o o o X d
n l m

p: d1 X . , , x dr x

Operation III.2.5

 

‘31
d . '
l . dk
o I
. -——E——€>' dk r {L
dn . dr
. I
d
m
I
d1
d1 .
o I
yields . ——-E—%F dk-—x
dn
dm
A
dr

The resulting diagram indicates that

p:d1X...an—9-d1><...><dk><...xd

43
Operation III.2.6

 

d1
d1 . ak
: -————->— d' ,
p If
an ar
a
m
dk
d1
d1 .
yields : —————>- d'3F—I
p r
a I
n
d
m

The interpretation of the resulting diagram is that

I I
p:le...an——:—dlx...Xdrx...xdm

and that
I I I
p: d1 x . . . x dn——er-d1 x . . . x dk x . . . X dm
Operation III.2.7
I I
d1 di dl
I ———>— I '
. P . ,
I .I II
dn dj di dl
' --———5—
. q .
dJ dr
.I
d

 

l
. u
d1 di
YiEIdS . —p—-> . —(i-——>'
. . .
d d.
n 3
d
m

The resulting diagram indicates that

n j , m
p: H du-—4>- H d and that q: H
u=l v=i k=

Operation III.2.8

 

al a1

.I .I

dl ai dj
I P r I
I
a d.
n J
.I
a

d1
(11 di (11
yields . ———p—->- . —-—(i—->'
. . I . II
dn dj dI
. I
d
m

I j I r II

. H
(1k and that q. _.dv'—-)' H dr .
1 v—1 w=l

'U
":25
a.
ll :18

Definition III.2.9 A pedagogic, functional diagram
is a diagram constructed by any composition of Operations
111.2.1 through III.2.8.

Example III.2.10 Consider the declarative concepts

D = {derivation sequence(DS), sentence(S), sentential

form(SF), syntax tree(ST), regular grammar(RG),
context-free grammar(CFG)},
the procedural concepts

P = {grammar induction(GI), sequence structuring(SS)},

and the mappings

GI: S x ST ——>CFG

and
SS: DSXCFG—erST .
Then
t(GI) = {(s x ST, CFG)}
t(SS) = {(DS x CFG, S x ST)}

46
S = {(RG, CFG), (S, SF)}

The above relational elements are depicted in Figure

 

111.2.11.
S DS' 5
GI " CFG SS 5
ST CFG ST
CFG SF
RG S

Elementary Pedagogic, Functional Diagrams

Figure III.2.ll

The elementary diagrams in Figure III.2.ll are
combined by Operations III.2.l through III.2.8 to result

in the diagram in Figure III.2.12.

 

SF
DS S
SS ’ GI ” CFG
CFG ST {L
l R.

R6
Pedagogic, Functional Diagram

Figure III.2.12

47
111.3 Diagram Implication

The pedagogic, functional diagrams are used to
discover elements in T by the manipulations that are
described in this section. The construction of a
pedagogic, functional diagram involves combinations of
elements from t and S under the Operations III.2.l through
III.2.8. The elements in T that are identified from a
given diagram are those elements specified by t and S in
the construction of that diagram.

Before presenting operations to identify elements in
T, an operation of a reductive nature is presented.

Operation III.3.l A pedagogic, functional diagram

segment of the form

l

d.
l
a.
J:
dk

is replaced by the diagram segment

The latter diagram segment represents the relational
compOSTtion of S(dk, dj) and S(dj, di).
The following four operations along with the above

operation are used to identify elements in T.

48

Operation III.3.2 The diagram segment

1 l
. -—-->- .
pk .
I
d d
n m
is replaced by
d1 d1
Pk .
d d
n m
n m , n m ,
( H di' H d.) is an element of T(pk) since ( H di' H d.)
i=1 j=l 3 i=1 j=1 3
is an element of t(pk) and t(pk) E T(pk).
Operation III.3.3 The diagram segment
I II
d1 d1 d1
I II
dn dm dr

is replaced by

l l
I q P E .
dn dr
_ n r n
where q and p are elements in P. ( H d., H d ) is an
i=1 1 k=1 k

element of T(q p) since T(p) o T(q) c T(q p).

49

Operation III.3.4 The diagram segment
d1
d1
dk ===§=ég>
d
m
d dn
r

d1
. dl
dk p % ° and
. d
m
n
(d1 X . X dk X . . X dn' d1 X .
I
(d1 X . X dr x . . . x dn' dl x .

elements in T(p) by Definition III.1.ll.

x dk

discovered in Operation III.3.2.

x . . . X d , d. X
n

1

d1

. al

ar -===§==§>

. d
m

a

n

. x dm) and
I
. x d ) are
m
The element

I
. x d ) is also
m

Operation III.3.5 The diagram segment
I I
(d1 dk
dl .
. I'.
. ==—p—=> Idr
d
n

 

is replaced by the two diagram segments

50

d1 d1
d1 . dl .
o I 0 I
‘ p g dr and ' p ; dk
a . a i
n n
. I . I
dm dm
I I I
(d1 X . . . X dn, d1 X . . . X dr X . . . X dm) and
(d1 X . . . X dn' d; X . . . X d; X . . . X dé) are

elements in T(p) by Definition III.1.ll. The element

1 X . . . X dn' d; X . . . X d; X . . . X d%) is also

(d
discovered in Operation III.3.2.

Operations III.3.l through III.3.5 are called
"discovery operations” since each operation either
identifies or leads to the identification of new
knowledge in C. The new knowledge is either an additional
element in S or additional transformations that might
not have been in the original representation. The
additional transformations are depicted as additional
elements in T either as new procedural concepts from
Operation III.3.3 or as new domains and/or ranges of
procedural concepts from Operations III.3.4 and III.3.5.

Operations III.3.l, III.3.3, III.3.4, and III.3.5
may lead to disjoint diagrams.

Example III.3.6 Consider the pedagogic,

functional diagram

51

 

 

which will result in the diagram

C3‘1

L

 

 

 

 

\ \
d 2 d 2 d
pl J\ p2
d3

after applying Operation III.3.2 twice. Operation III.3.l
will yield the disjoint diagram

d1

 

 

 

 

\\ \\
’7’ d2 .z“ d5

pl 92

d3

Operation III.3.3 will yield the disjoint diagram

d1

L

\\
d2 d4 - d

1

d3

 

All elements in T that are in a given pedagogic,
functional diagram can be discovered by a finite number

of compositions of Operations III.3.l through III.3.5.

52

Since all pedagogic, functional diagrams are finite,

every combination of operations can be applied to the

original diagram yielding every possible element in T that

can be discovered by the Operations III.3.l through III.3.5.
Example III.3.7 Consider the pedagogic, functional

diagram in Figure III.2.12. After two applications of

Operation III.3.2, the diagram is

SF

==€Eé§> ==ifié=%;’ CFG .

RG
The elements discovered are (DS X CFG, S X ST) 6 T(SS)
and (S X ST, CFG) 5 T(GI).

Examining the diagram segment

DS 8
SS E

CFG ST

RG

and applying Operation III.3.4, the diagram segment is
replaced by two diagram segments resulting in two

diagrams, namely

53

DS S

CFG ST KL

 

 

 

 

 

 

RG
and SF
DS S
\x E;
SS i GI ; CFG .
RG ST rL
RG

The elements (DS X CFG, S X ST) and (DS X RG, S X ST)
are discovered to be members of T(SS).

From the diagram segments

SF SF

DS S DS S
SS % and SS %

CFG ST RG ST

under Operation III.3.5, (DS X CFG, S X ST), (DS X CFG,
SF X ST), (DS X RG, S X ST), and (OS X RG, SF X ST) are
discovered to be elements in T(SS). The diagrams

DS S

\
SS % GI /’ CFG '

CFG ST

 

 

54
DS SF S

CFG ST ST J\

 

 

 

 

 

 

RG
DS 8
\ \
SS 2; GI //’ CFG , and
RG ST KL
RG
08 SF S

 

 

#95:? a > CFG
RG ST ST J\
RG
are the results of the application of Operation III.3.5.
The second and fourth diagrams are disjoint.
From the first and third diagrams, immediately above,
the diagrams

DS DS

\\
GI SS CFG and GI SS 77 CFG ,

CFG J\ RG

RG RG

 

 

respectively, result from Operation III.3.3. (DS X CFG,
CFG) and (DS X RG, CFG) are discovered to be elements in
T(GI SS).

There are alternative compositions of Operations
III.3.1 through III.3.5 that will discover the same elements
as the above example. Summarizing the above example, the

following elements in T were discovered from Figure III.2.12:

55

T(SS) = {(DS x CFG, S x ST), (DS x RG, S x ST),
(DS x CFG, SF x ST), (DS x RG, SF x ST)}
T(GI) = {(S x ST, CFG)}

T(GI SS) = {(05 x CFG, CFG), (OS X RG, CFG)}

III.4 Functional Automaton
The discovery operations of Section 111.3 identify
elements in T that are present in a specific pedagogic,
functional diagram. All possible diagrams would need to
be constructed to identify all elements in T from the
given t's and 8's. To construct all diagrams would require
all possible combinations of Operations III.2.l through
III.2.8 applied to the elements in t and S. Some diagrams
might be countably infinite. An alternative description
of all elements in T is desirable for computational reasons.
The alternative description that is developed in this
section is called a functional automaton.

Definition III.4.1 A finite functional automaton

 

M over an alphabet Z is a S-tuple <K, Z, 6, go, F>, where

K is a finite, non-empty set of states, 2 is a finite input

alphabet, 5 is a mapping of K X 2 into K, q0 in K is the

initial state, and F s K is the set of final states.
Notationally, the mapping 6: k. X o. —~>-km is

l J
denoted by 6(ki, oj) = km and is represented graphically by

e so

where ki, km S K and o. c X. The initial state and final

 

56
state are represented graphically by

and © ,

* *
The domain of 6 is extended to K X Z , where 2

respectively.

is the set of all strings of finite length composed of

symbols from Z and also including the empty string, by
5(q: E) = q
6(q, ax) = 6(6(q, x), a)

for each x c 2*, a c 2, g c K, and c is the empty string.
Since 6 and 8 agree wherever 6 is defined, 6 will be used
for both 6 and 6 without any confusion.

Definition III.4.2 A sentence x is accepted by
M if 6(q0, x) = p for some p in F.

Definition III.4.3 The language of M, denoted
L(M), is defined by
L(M) = {x I 6(qo, x) is in F}.

Example III.4.4 Consider the functional automaton

M where M is
a b c

o .1 s o

 

 

 

A sentence in L(M) is "cba." This is shown by

6(qo. cba) 6(6(q0. ba). C)
6(6(6(q0, a), b), c)

<5 (5 (ql, b), c)

S7
6(q2, C)

Since 6(qo, cba) is in q4 which is a final state in M,

"cba" is a sentence accepted by the automaton. L(M) is

c ( b c a )* b a.
Let dr be a set composed of all domains and ranges
of elements in P. Let DR be a set composed of all domains,
sub-domains, ranges, and super-ranges of elements in P.
DR is computed from dr by Algorithm III.4.5.
Algorithm III.4.5 Domain-Range Extensions

The final wi is DR.

i. i = 1

ii. wi = dr

iii. 1 = i + 1

iv. wi = wi-l U {Y | Y = y1 x . . . x dk x . . . x yn,
Z = Yl X . . . x dj x . . . x yn, Z c wi-l’
(dk, dj) 6 S}

v. Repeat steps iii and iv until wi = w.

vi. i = i + 1

II
N

vii. w. = w._1 U {Z I Z

(dk, dj) 6 8}
viii. Repeat steps vi and vii until wi = wi_1
Step iv computes the sub-domains, and step vii computes the
super-ranges. If (X, Y) c T(p), then X and Y are in DR.
A functional automaton <K, Z, 6, go, F> that can be

used to identify all functional compositions in C is

58
defined by

K = DR,
q0 = DRi where DRi 8 DR,

F = {DR. , . . . , DR. | DR. 5 DR for
31 3n 3k

k = l, o o o p n}:
6(DRi, pk) = DRj 1f (DRi, DRj) c T(pk) for
pk e P.

The language of <DR, P, 6, DRi' {DRj , . . . , DRj}> is
l n

the set of all functional compositions that map DRi into

DR. for k = l, . . . , n.
3k

Example III.4.6 Consider the following relations:

T(pl) = {(D, t)}
T(pz) = {(t. 0)}
T(p3) = {(S X r! t)}

T(P4) = {(s Xr, t)}
where the declarative concepts are
D = {angle in degrees(D), angle in radians(t),
radius(r), arc length(s), sector area(S)}.
The procedural concepts p1, p2, p3, and p4 are the mappings
pl:D—>t; p2:t—>D; p3:SXr—-’-t;and
p4 : s X r —e>-t , respectively.
dr = {D, t, S x r, s x r}
Since S is empty, DR = dr.
K = {D, t, S X r, s X r}

2

{p1, pz. p3. p4}

59
6(D, p1) = t 6(8 X r. p3)

ll
d

l
”-

6(t, p2) = D 6(s x r. p4)

The graphical representation of M is

 

If S X r is the initial state and D is the final state,
the language of the automaton is p2 ( pl p2 )* p3. Thus
T(p2 p3) = {(S X r. D)}; T(p2 pl 92 p3) = {(S X r, D)};
T(p2 pl p2 p1 p2 p3) = {(S X r, D)}; etc. By considering
all combinations of elements in DR as initial states and
final states of a functional automaton, all elements in

T are represented by the functional automaton.

III.S Non-Repetitive Functional Compositions

For computational reasons and later usage of the
functional compositions, a direct calculation of all
non-repetitive functional compositions and corresponding
elements in T from elements in t and S is developed.

Definition III.5.l A composition of basic functions

 

pk . . . pk is non-repetitive if and only if for

P
kl 2 n

every basic function in the composition pk e pk for
i J

i # j and i, j = l, . . . , n.
The remainder of this section develops an algorithmic

procedure to calculate all non-repetitive functional

compositions.

60

Let dr be a set composed of all domains and ranges of
elements in P. Let DR be a set composed of all domains,
sub-domains, ranges, and super-ranges of elements in P.

DR is computed by Algorithm III.4.5.

Let M ) be an n by n function matrix whose rows

t(pk

and columns are ordered identically by the elements in

DR and where n is the number of elements in DR. Mt(p )
k

is defined by

pk 1f (DRi’ DRj) e t(Pk)

( )

Mt(pk) 1.3 =

0 otherwise
pk + pr as an element of a function matrix means that
‘: . . : . .. u+u '
pk DR1-—er DRJ and that pr DRl-——‘>--DRJ The 1n
pk + pr is a formal symbol. + is commutative, i.e.

+ is associative, i.e.

pk + pr is identical to pr + pk’
(pk + pr) + pv is identical to pk + (pr + pv).
The addition of two function matrices, Mt(pk) and
Mt(Pr)' is denoted as ”t(pk) + Mt(pr) and is defined by
pk + pr if (Mt(pk))i'j = pk
and (Mt(pr))i,j = pr
pk if (Mt(pk))i.j = pk and
(Mt(Pk)+Mt(Pr))i.j z (”t(pr)’i.j = 0
pr if (Mt(pk))i,j = 0 and
I (”t(pr))i,j = pr

 

61

Let Mt represent all basic functional transformations.

Mt is defined by

M = Z M where P has m elements.

t i 1 t(Pi)

Let MS be an n by n Boolean matrix whose rows and

M is

columns are ordered identically to those of Mt' S

defined by

1 if DRi c: DRj
0 otherwise

A

Let MS be the transitive closure of MS(7).
The multiplication of an element from a Boolean matrix,

MS’ with an element from a function matrix, M is defined

t,
by
pk 1f (MS)i,j = l and (Mt)x,y = pk
0 otherwise
and (”s’i.j (Mt’x.y = ‘Mt’x.y (”S’i.j

The multiplication of a Boolean matrix, MS, with a function

t' 15 denoted as MSMt or MtMS and 1s def1ned as

usual matrix multiplication.

matrix, M

The basic functions, their domains, sub-domains,
ranges, and super-ranges are represented by MT which is
determined by the formula

MT = Mt + MSMt + MtMS + MSMtMS

Mt represents all basic functional relations. MSMt

represents all sub-domains of the functional relations.

MtMs represents all super-ranges of the functional

relations. MSMtMS represents all sub-domains, and

62

super-ranges of the functional relations.
The above formula simplifies via

MT = Mt + MtMS + MSMt + MSMtMS

= Mt(I + MS) + MSMt(I + Ms) where I IS
the identity matrix

= M M? + M M MR where MR is the reflexive

t S t S S
closure of M i.e. MR = I + M
S' S S
— A AR
_ "R "R
' MSMtMS

The multiplication of two elements from the function

matrices M1 and M2 is defined by

2 q.p. if (M ). . = X p. and
i,j j 1 l 1,] i 1
(M )- (M ) = _
l 1'] 2 le (M2)x,y - :2; qj
0 otherwise

The multiplication of two function matrices is defined as
usual matrix multiplication.
The non-repetitive functional compositions of

basic functions are represented by the expression

Each power of MT represents the number of basic functions
in the functional composition. Elements in T are identified
immediately from the above expression.

Example III.5.2 Consider the pedagogic, functional

63
diagram in Figure III.2.ll. The figure depicts the

elements (DS X CFG, S X ST) e t(SS), (S X ST, CFG) c t(GI),
and (RG, CFG) and (S, SF) c S. The domains and ranges are
dr = {DS X CFG, S X ST, CFG}.
From Algorithm III.4.5
DR = {DS x CFG, S x ST, CFG, DS x RG, SF x ST}.
The following matrices are computed:

M

t
DS S DS SF
x x x x
CFG ST CFG RG RG ST
OS X CFG 0 SS 0 O O 0
S X ST 0 0 GI 0 0 O
CFG O 0 0 O O 0
DS X RG 0 0 0 0 O 0
RG 0 O O 0 0 0
SF X ST 0 O O 0 O 0
R
MS
DS S DS SF
x x x x
CFG ST CFG RG RG ST
DS X CFG 1 0 0 O 0 0
S X ST 0 l 0 0 O l
CFG 0 O l 0 0 0
DS X RG 1 0 0 1 0 0
RG 0 0 l 0 l 0

SF X ST 0 O 0 O O 1

64
M

T

DS 8 DS SF

X X X X

CFG ST CFG RG RG ST
DS X CFG 0 SS 0 0 0 SS
8 X ST 0 0 GI 0 O O
CFG 0 0 0 0 O 0
DS X RG 0 SS 0 0 0 SS
RG 0 0 0 0 O 0
SF X ST 0 0 0 O 0 0
Mi

DS S DS SF

X X X X

CFG ST CFG RG RG ST
DS X CFG 0 0 GI SS 0 0 0
S X ST 0 0 0 0 0 0
CFG 0 0 O 0 0 0
DS X RG 0 0 GI SS 0 0 0
RG 0 0 0 0 0 0
SF X ST 0 0 0 O O 0
Mg, Mg, M3, and Mg are all zero. The non-repetitive

compositions are represented by

65

g 1
i=1 MT
as 3 DS SF
x x x x
CFG ST CFG RG RG ST
DS x CFG 0 SS GI SS 0 0 SS
S x ST 0 0 c1 0 o o
CFG o o o o o 0
DS X RG 0 SS GI SS 0 0 SS
RG 0 o o o o 0
SF x ST 0 o o o o o

The elements in T that can be directly read from the

matrix are:

T(SS) = {(DS X CFG, S X ST), (DS X CFG, SF x ST),
(DS X RG, S X ST), (DS X RG, SF x ST)},
T(GI) = {(S X ST, CFG)},

T(GI SS) = {(DS X CFG, CFG), (DS x RG, CFG)}.
The same elements were also discovered under Operations

III.3.1 through III.3.5.

III.6 Identification of t and S

The identification of elements of t and S is most
easily accomplished from instructional material in the
chosen subject area. The instructional material with the
greatest wealth of information is homework assignments,
examinations, and one or more textbooks in the subject
area. The usefulness of the homework assignments and
examinations is that the problems represented in the

homework assignments and examinations are the basic

66

functional transformations. These basic functions are
the elements in P. The elements in P immediately describe
the relation t.

Most declarative concepts will be specified by the
basic functions from their domains and/or ranges.
Additional declarative concepts will be found in textual
material. The textual material will be most helpful in
the identification of elements in S.

The procedural and declarative concepts in the subject
area "angles" in Section III.7 were discovered from
instructional material(13).

Example III.6.1 An example problem(l3-p3l4) is
"Find the length of an arc of a circle of radius 6
inches and with a central angle of H/6 radians." The
procedure that solves this problem is found in the back
of the text and is to multiply the angle in radians (n/6)
by the radius (6) to obtain the arc length (n). Let p1
be the above procedure. Then p1: r x t —q>-s where r
is the radius, t is the angle in radians, and s is the
arc length. Obviously, (r x t, s) c t(pl). Usually, the
procedures are not given and will have to be identified
by the builder of a pedagogic knowledge representation.
The declarative concepts "angle in radians," "radius,"
and "arc length" are identified from the domain and range
of p1.

Examples are another good place to discover procedural
and declarative concepts.

Example III.6.2 Example 3(13-p312) in part states

67
"This means then that an angle of D degrees is (n/180)D

radians." Applying one's own knowledge about the subject
area and some algebra, two procedural concepts are described.
The procedures are p2: D-—e»-r and p3: r -4>-D where r
is the angle in radians and D is the angle in degrees. The
relational elements (D, t) e t(pz) and (r, D) c t(p3) are
directly identified from p2 and p3, respectively. The

two declarative concepts "angle in radians" and "angle in
degrees" are identified from the domain and range of p2

and p3.

Identifying elements in S is a more difficult task.
Often an intuitive understanding of the subject area is
necessary. From textual material(13-p313) a discussion of
the calculation of arc length from the radius and central
angle leads to the fact that the circumference is a
specific instance of the arc length. Thus (circumference,
arc length) a S.

The preceeding expository in this section describes
the identification of elements in D, P, t, and S. Process
III.6.3 is not a formal procedure but is an initial
approach than an inexperienced builder of a pedagogic
knowledge representation might employ.

Process III.6.3 Identifying Elements in t and S

1. Collect all the problems possible in the given
subject area. Problems most likely will be found in
tests, exams, quizzes, worksheets, homework sets, textbooks,
class notes, etc.

ii. Apply any prerequisite knowledge or one's own

68

knowledge about the subject area to construct additional
problems. These additional problems enhance the problems
from step i in that they involve new algorithms.

iii. For each problem found in step i and ii, identify
a procedure that will solve the stated problem. The
identified procedure is a basic function. The procedures
form P. The functional relation t(pk) is immediately
specified by the basic function pk.

iv. Using the declarative concepts in the domains and
ranges of the procedures found in step iii and any other
declarative concepts in the subject area, identify elements
in S.

V. Repeat steps 1, ii, iii, and iv until t and S
are satisfactory for the purpose at hand.

Process III.6.3 is intended as a guide to building
a first pedagogic knowledge representation. As additional
pedagogic knowledge representations are constructed,

individual techniques will most likely be developed.

III.7 An Example Subject Area

The chosen subject area for this example is "angles"
where angles are viewed with respect to circles and some
of the other concepts associated with a circle.

The declarative concepts with their abbreviations in
parentheses are:

D = {arc length(s), radius(r), angle in radians(t),

circumference(c), angle in degrees(D), circle

area(A), sector area(S), diameter(d)}.

69

The procedural concepts in the "angles" subject area
are expressed in the form of several formulas. The
procedural concepts immediately identified from the
given formulas(l3) are

P = {p1: D-—4» t, p2: r X t -+>-S, p3: c-—e»-r,

p4: r —A>-A, p5: r X t -+>-S, p6: d-—e» r}.

The procedural concepts possess no knowledge specific
to any subject area. Applying one's own knowledge about
the subject area, in this instance algebraic knowledge,
additional procedural concepts are identified. As an
example of the application of algebraic knowledge in this
subject area, consider the algebraic formula to calculate
the arc length. The formula is s = rt where r, t, and
s are the radius, angle in radians, and arc length,
respectively. In algebraic terms if a student was given
values for any two of the above three variables, the third
variable could be computed. The procedure for computing
the arc length, p2, only computes the arc length.
Intuitively, one would also expect the ability to compute
the radius from a given angle and arc length. After all,
a simple algebraic manipulation of the above formula
would make the necessary procedure readily available.

The independence of procedural concepts and subject
areas is an extremely beneficial feature of the
representation. The beneficial effect is that any assumed
knowledge is clearly emphasized and identified in the
specification of additional procedural concepts in a

subject area.

70
After applying algebraic manipulations to the above

six procedures, an additional eight procedures are
identified. The basic procedures for the example subject
area are:

P={pl: D-—->-t, p2: rXt——>-s, p3: c—>-—r,
p4:r-—->—A, p5: rXt——>-—S, p6:d——>—r,
p7:t——>-D,p8: sxr—->-t,p9: sxt—v—r,
p10: r-—+>-c, p11: A —+>-r, p12: S x r —+>-t,
p13: 8 x t-—er-r, p14: r -e>-d}.

The following relations are immediately identified:

t(pl) = {(D, t)} t(pz) = {(r x t, s)}
t(p3) = {(c. r)} t(p4) = {(r. A)} ‘
t(ps) = {(r X t. 8)} t(p6) = {(d, r)}
t(p7) = {(t, 0)} t(p8) = {(s x r, t)}
t(pg) = {(s X t. r)} t(plo) = {(r. o)}
t(p11) = {(A, r)} t(Plz) = {(s x r, t)}
t(p13) = {(s x t, r)} t(p14) = {(r, d)}

Two elements in S are identified from elements in D.

S = {(A, S), (C, 5)}

Many pedagogic, functional diagrams can be constructed
under Operations III.2.l through III.2.8. One of these
diagrams in represented in Figure III.7.l. The discovery
Operations III.3.1 through III.3.5 can be used to identify
elements in T from the diagram in Figure III.7.l. This
example will not demonstrate such a process.

The domains and ranges of P are
dr = {D, t, r X t, s, c, r, A, S, d, s X r, s X t,

S x r, S x t}.

71

t 95 S
S -——).r
c .__.. ——->-t p13
p r r p12
3 ——->—S
t p2
.————q>-r ————A>-.A -————q> r —————e..c
pa P4 p11 p10
D———->—t
pl
Pedagogic, Functional Diagram of "Angles"
Figure III.7.1
p8 er
P
p3 c X r
o a p12
S x

 

Functional Automaton of "Angles"

Figure III.7.2

72
Algorithm III.4.5 yields

DR = {D, t, r X t, s, c, r, A, S, d, s X r, s X t,
S x r, S x t, c x r, c X t, A X r, A x t}.

A functional automaton for the subject area "angles" can
be constructed. Such an automaton is shown in Figure
III.7.2. Functional compositions can be read directly
from the automaton. For example, the relation T(p) =
{(r, A)} where r is the initial state and A is the final
state. The compositions p4, p4p3plop11p4, p4p6p14,
p4p3p10p6pl4, and p4p11p4p11p4 are some of the possible
compositions for p. I

All non-repetitive functional compositions for this
example are given in Appendix A. The functional automaton
in Figure III.7.2 can be used to verify the entries in
the matrix. Consider the element that represents all
non-repetitive mappings of the diameter of a circle
into the circumference of a circle. There are two
non-repetitive functional compositions that map "d" into
"c," namely plOPG and p10p11p4p6. There are fourteen
non-repetitive compositions that map the radius of a circle

into itself.

CHAPTER IV

PEDAGOGIC REPRESENTATION PROCESSES

The performance of a pedagogic knowledge representation
is measured by the representation's ability to determine
or display pedagogic aspects, its ability to enumerate
problems, and its ability to answer problems. The
representation's pedagogic aspects are stated in terms
of a pedagogic ordering of concepts. The idea of a
connected representation is presented along with an
analysis schema to determine the connected parts of a
representation.

Several types of problems are identified. A meta-
grammar, whose sentential forms represent all possible
problems for a given representation, is derived from the
elements in the relational T. Complete and extrinsic
problems are defined and discussed relative to the
meta-grammar.

A solution planning sequence is constructed independent
of the problem generation process. Another meta-grammar,
whose sentential forms represent all solution planning
sequences, is constructed from a representation. The
execution of a solution planning sequence is shown to

solve the stated problem.

73

74

IV.1 Connected Representation

The concepts in a pedagogic representation are
connected to other concepts by the elements in t and S.
The relation PATH can be thought of as a single step
relation in a pedagogic representation.

Definition IV.1.1 A binary relation PATH on C,

called pedagogic path, is defined as follows:

 

PATH = {(ci, cj) I 1) (c., Ci) 3 S for C1' cj c C, or

3 n m
I I
2) :3 dk, dr such that ( H dk' H dr) 5 t(pw)
k=1 r=l
for pw 6 P, dk' dr 8 D for l E k e n and 1 t r E m,
ci = dr' and cj = dk, or
n m ,
3) 33 dk’ pw such that ( H dk’ H dr) 8 t(pw)
k-l r—l
I
for pw 8 P, dk’ dr 8 D for l S k e n and 1 e r‘e m,
I
cj = dr, and ci = pw}.

Definition IV.l.2 A connected pedagogic knowledge

 

representation is a set CR which is composed of elements

 

from C such that for every pair of elements in CR, (ci, cj),

A A , . .
j' ci) e PATH where PATH 13 the trans1t1ve

closure of PATH.

(Ci, cj) or (c

To find the connected parts of a pedagogic represen—
tation, a Boolean matrix MPATH is constructed from PATH.
The n rows and columns of MPATH are ordered identically

by elements in C where n is the number of elements in C.

MPATH 1s def1ned by
1 if (01’ cj) c PATH

(MPATH)i,j

0 otherwise

75

By taking the transitive closure of the symmetric

closure of the reflexive closure(7) of M

A

R S . . . .
((MPATH) ) , all undirected p0531b1e paths 1n the pedagog1c

PATH' denoted by

representation are obtained. The reflexive closure
(MPATH)R includeseach concept on any path emanating from

R S

itself. The symmetric closure ((M ) ) makes each path

PATH
A

undirected. The transitive closure((MPATH)R)S includes

all concepts that can be reached from a given concept.

/\
R S

If ((MPATH) )
connected pedagogic representation. If the matrix has

is all 1's, then there is only one

0's in it, then more than one connected representation

is present. The number of connected representations and

the concepts in each are computed by Algorithm IV.1.3.
Algorithm IV.1.3 Connected Representation

The set wi contains the concepts in the ith connected

representation, and 1 counts the number of connected

representations.

ii. i = i + 1

iii. Arbitrarily choose a concept from C, call it

/\
-: R S _
cc, such that (((MPATH) ) )Cc’ cc — l
/\
iv w = {c I ((( )R)S) = 1 for all '}
‘ i j MpATH cc. cj 3
/\
R S _
' j

vi.

76

Repeat steps ii, iii, iv, and v until the matrix

is all 0's.

Example

A pedagogic,

t(Pl) =

t(pz) =

t(P3)

S = {(d

elements is

The relation PATH

PATH = {(dz'

MPATH 15
d1
a1 0
d2 1
a3 1
a4 0
d5 0
d6 0
d 0

(d3 I
(d6 I

d2 d3
0 o
o o
o o
o o
o o
o o
o o

IV.1.4 Consider the relations

{(d1. d2 x d3)}
{(d4 x d1, d3)}

{(d5. d6). (d6. d7)}

4. d2), (d7. d5)}

functional diagram composed of the above

is

d4): (d5: d7): (P1: d2): (p1: d3): (d2: d1):
d1): (P2: d3): (d3: d4)! (P3, d6): (p3! d7):
as). (d7. d6)}.

77

MPATH cont1nued

al 1 1 1 1 o o o 1 1 0
a2 1 1 1 1 o o o 1 1 0
d3 1 1 1 1 o o o 1 1 0
a4 1 1 1 1 o o o 1 1 0
a5 0 o o o 1 1 1 o o 1
a6 0 o o o 1 1 1 o o 1
d7 0 o o o 1 1 1 o o 1

Algorithm IV.1.3 yields

w]. = {dlr d2! d3! d4: pl! p2}
and
{d }.

d d

“’2: 5' 6' 7'93
The representation contains two connected parts. Thus the
above representation is disjoint since it has more than
one connected part.

A disjoint representation implies a disjoint subject

area. A disjoint subject area suggests that the concepts

78

in one of the connected representations are not related
in any instructional manner to the concepts in other
connected representations. It is desirable to have a
single connected pedagogic representation where every
declarative and procedural concept is related to other

declarative and/or procedural concepts in the representation.

IV.2 Pedagogic Dependencies
The elements in t and S can be used to determine if

one concept is dependent on another concept.

 

Definition IV.2.1 A concept C1 is pedggogically

dependent on concept cj if cj must be mastered before ci

 

where ci, cj e C.
To master a declarative concept means that the
general data structure of the declarative concept can be
stated and that many specific instances of that general
structure can be stated. To master a procedural concept
means that the declarative concepts in the domain and range
of the procedure have been mastered and that the transformation
of many specific domains into their corresponding ranges
has been performed.
Definition IV.2.2 A binary relation PD on C, called

pedagogic dependency, is defined as follows:

 

PD = PATH U {(01, cj) I (ci, cj) c s for ci, cj e c}.

The pedagogic dependency implies that the element

The

(di, dj) S t(pk) 1s mastered 1n the order di' d

3" pk'

element (61’ dj) 8 S 1mpl1es that either di’ dj or dj' di

are pedagogically dependent on each other. Either di or dj

79

can be mastered first. The former sequence di' dj is called
the bottom-up approach. The latter sequence dj' di is
called the top-down approach. The top-down approach
introduces the most general declarative concept first
followed by more specific declarative concepts. This has
the effect of giving the "Big Picture" of a subject area.

A pedagogic dependency matrix M is used to find the

PD
pedagogically dependent concepts. The n rows and columns
of MPD are ordered 1dent1ca11y by elements 1n C. MPD 15
defined by

(MPD)i,j = i

1 if (ci, cj) e PD

0 otherwise

If (MPD)i,j = 1, then cj is an 1mmed1ate prerequ1s1te of ci.

By taking the transitive closure of MPD' MPD’ all

pedagogic dependencies in C are obtained. If (MPD)i j = l,
I

then cj is a prerequisite of ci, Conversely, if
(MPD)i,j = 1, then ci pedagog1cally depends on cj. For

each concept cj such that (MPD)i,j = l, cj should be
presented and mastered before ci is encountered in the

subject area.

A

MPD indicates all prerequisites of a concept, and,
conversely, all concepts for which a given concept is a
prerequisite. For notational purposes, (M)* j denotes

I

(M) for all i. (MPD)* j indicates all concepts that
I

1.1
depend on C3. and all concepts for which cj is a prerequisite.

A

(MP ). * indicates all concepts upon which c. is dependent
D 1, 1

80

and all concepts that are a prerequisite of ci.

MPD is a useful tool in the implementation of a
generative instructional system. If a student is allowed
to choose the next material that he or she wants to learn
in a generative instructional system, MPD and a student's
history vector can be used to determine accessibility to
the desired concept. The student's history vector is a
binary vector where each element represents a concept in
the subject area.

Let H be a binary vector of the student's historical
accomplishments. H is ordered identically to the ordering
of the columns of MPD' H is defined by

1 if ci has been mastered by the student

(Hli =

0 otherwise
By using an approach factor, either a top-down or a
bottom-up approach to presenting the concepts in a subject

area can be achieved. Let MAF be a Boolean matrix whose

n rows and columns are ordered identically to M For

PD'
a top-down approach

MAF = I‘V’M

where I is the identity matrix and M is the transpose of

(Di-3 (DI-3

S
approach

M which is defined in Section 111.5. For a bottom-up

MAP = I‘V MS .

If a student wants to next learn and master concept Ci'

then he or she would be permitted such access if

81

_ A

H /\ (MPD A MAF)i,*
is all zeros where H and MAP are the complement of H and
MAF’ respectively. If the conjunction does have concepts

not mastered, H, and that are prerequisite concepts of the

A
choosen concept Ci' (MPD/\ MAF)i,*' then those preclud1ng

concepts are identified as 1's in the conjunction. The
precluding concepts could be displayed to the student for
a new selection.

Example IV.2.3 Suppose the pedagogic representation
is represented by the diagram

d

2
———4>.d
P1 1
d
3
Then
PD = {(plp d1): (d1: d2): (dll d3)! (d3! d4)! (d4! d3)!
(p2. d4). (d4. d5)}
“pp
d1 d2 d3 d4 d5 Pl p2
d1 0 l 1 0 0 0 0
d2 0 O 0 0 0 O 0
d3 0 0 O 1 O 0 0
d4 0 O l 0 l 0 0
d5 0 0 0 0 0 0 0
pl 1 0 0 0 0 0 0

82

From MPD d2 and d5 do not have any prerequisite concepts.

Assume a bottom-up approach. Then

MAF

d1 d2 d3 d4 d5 p1 p2
al 1 o o o o o 0
a2 0 1 o o o o 0
d3 0 o 1 o o o 0
a4 0 o 1 1 o o 0
d5 0 o o o 1 o o

””~‘:T
MPD/\ MAP

d1 d2 d3 d4 d5 p1 p2
al 0 1 1 1 1 o 0
a2 0 o o o o o 0
d3 0 o o 1 1 o 0
d4 0 o o o 1 o 0
d5 0 o o o o o o

The following concepts must be mastered before access to

the indicated concept would be permitted:

mastered concepts access concept
d5 d4
d4, d5 d3
d2, d3, d4, d5 d1
d

1' d2, d3, d4, d5 p1

83
If H = 0 O 0 0 l 0 0, then a student has mastered only

d5. If the student wants to learn d4 next, access is
permitted to <14 because the access expression is all 0's.
However, if the student wants to learn d3 next, access is
not permitted because the expression contains a l and is
0 0 0 l O 0 0. Thus d4 needs to be mastered before access
is permitted to d3.
IV.3 Pedagogic Ordering

A pedagogic ordering of concepts in C is a partial
ordering. A partial ordering represents an order of
presentation of the concepts in the ordering. Such an
order of presentation is called an outline. An outline is
not intended to represent a best or optimal ordering of

concepts.

Definition IV.3.1 A pedagogic partial ordering

 

is the sequence cl, c2, . . . , cn such that 3 c3. for each
ci where (ci, cj) 6 PD for ci, cj e C and l a j < i S n.

If for all ci, cj c C and l e j 4 i g n (ci, cj) 5 PD,
then the partial ordering c1, . . . , cn is a strict
partial ordering. Such a strict partial ordering of a
subject area is highly unlikely.

Algorithm IV.3.2 determines a pedagogic partial
ordering of concepts that preceed the chosen concept in
a pedagogic partial ordering. Algorithm IV.3.5 determines
a pedagogic partial ordering of concepts which succeed

the chosen concept. Algorithm IV.3.7 combines the two

partial orderings to yield an outline containing the

84

chosen concept.

Algorithm IV.3.2 Pedagogic Dependencies
Let 01 be a pedagogic partial ordering upon which the
arbitrarily chosen concept cC is pedagogically dependent.

1. Push cC on the stack and set i = 1.

ii. For each (pk, cc) 5 PD, push pk on the stack.
Push cc on the stack. Delete the relational element
(pk, cc) from PD.

iii. For each (cc, cj) 8 PD, push cj on the stack.
Delete the relational element (cc, cj) from PD.

iv. 1 = i + 1

v. If i is greater than the number of elements in
the stack, then go to vii, else go to vi.

vi. Set cc to be the concept at the ith position in
the stack. Go to ii.

vii. Pop the top element c from the stack. If

t

ct is not already in 01, then add ct

in which the concepts are popped from the stack.

to O1 in the order

viii. Repeat step vii until the stack is empty.
Example IV.3.3 The pedagogic dependency relations are
PD = {(12, 2), (2, 1), (l, 2), (2, 3), (3, 2), (4, 2),
(2, 5), (6, 5), (5, 6), (5, 7), (7, 5), (ll, 7):
(7, 9), (13, 5). (5, 3), (8, 6), (6, 10)]u
Algorithm IV.3.2 yields the following partial pedagogic

orderings for the indicated concepts:

85

concept pedagogic partial ordering
8 2, 5, 3, l, 4, 12, 9, 7, ll, 6, 13, 10, 8
7 2, l, 3, 5, 4, 12, 10, 6, 8, 7, l3, 9, ll
2 9, 5, ll, 7, 10, 6, 8, 3, 13, 2, l, 4, 12
2 5, 10, 6, 8, 9, 7, ll, 2, 3, 13, l, 12, 4

Algorithm IV.3.5 Pedagogically Dependent
Let 02 be a pedagogic partial ordering of concepts that
are pedagogically dependent on the arbitrarily chosen
concept cc.

i. Push cc on the stack and set i = 1.

ii. For each (cj, cc) 8 PD, push cj on the stack.
Delete the relational element (cj, cc) from PD.

iii. 1 = i + 1

iv. If i is greater than the number of elements in
the stack, then go to vi, else go to v.

th

v. Set c to the concept at the i position in the

c
stack. Go to ii.

vi. Invert the stack making the top of the stack the
bottom and the bottom the top.

vii. Pop the top element ct from the stack. If ct

is not in 02, add c to O2 in the order in which the concepts

t
are popped from the stack.
viii. Repeat step vii until the stack is empty.
Example IV.3.6 Consider the pedagogic dependency
relation in Example IV.3.3. The following pedagogic

partial orderings for the chosen concepts via Algorithm

IV.3.5 are:

86

concept pedagogic partial ordering
8 8
7 7, 5, 2, 6, 13, 12, l, 3, 4, 8, ll
2 2, 12, l, 3, 4, 5, 6, 7, l3, 8, 11

The partial orderings that result from Algorithms
IV.3.2 and IV.3.5 can be combined to yield a pedagogic
partial ordering for all concepts in 01 and 02' If
01 and 02 contain all the concepts in C, an outline for
presenting and mastering the concepts in C can be constructed.
Algorithm IV.3.7 computes such an outline.

Algorithm IV.3.7 An Outline
Let O1 and 02 be the partial orderings computed by
Algorithm IV.3.2 and Algorithm IV.3.5, respectively.

Let 0 be an outline for the concepts in 01 and 02'

i. Catenate O1 and O2 to form 0, O = 01, 02.

ii. If 0 = 01' . . . , Oi' cj, °i+2’ . . . , On’ then
cj is deleted from 0 if cj = ok for some 1 t k e 1.

Example IV.3.8 Consider the pedagogic dependency
relation in Example IV.3.3. An outline for the chosen

concept 8 or 2 is 2, 5, 3, l, 4, 12, 9, 7, ll, 6, 13, 10,

8, or 5, 10, 6, 8, 9, 7, ll, 2, 3, 13, l, 12, 4, respectively.

IV.4 Problems

Definition IV.4.1 A problem is described by the
2-tuple <G, A> where G and A are subsets of D.

G is called the "given" component, and A is called the
"asked for" component.

Example IV.4.2 An example of a problem is

87
<{FORTRAN DO-LOOP program segment}, {FORTRAN IF program

segment}> where FORTRAN DO-LOOP program segment is
DO 100 I=l,50
A(I)=2*I
100 CONTINUE
and FORTRAN IF program segment is
I=0
200 I=I+l
A(I)=2*I
IF(I.LT.SO) GO TO 200 .
An English directive for the problem could be
"Compute an equivalent FORTRAN IF program segment for the
given FORTRAN DO-LOOP program segment given below:
DO 100 I=l,50
A(I)+2*I
100 CONTINUE ."
Several types of problems can be identified. Each
of these types are useful in determining if a given problem
is solvable. A trivial problem is one in which no procedure
is required to solve the problem.

Definition IV.4.3 A trivial problem is a problem

 

<G, A> where 3 9i such that for each aj (gi, aj) c S
for all aj c A, gi c G, and S is the transitive closure
of S.
In the trivial type of problem the "asked for" is the
"given." The "given" is a more specific instance of the

more general "asked for." The answer to such a problem

is the "given" and requires no computation. Trivial

88
problems are said to be solvable by the empty procedure.

Trivial problems are almost never given in homework
assignments or on quizzes.

Definition IV.4.4 A simple problem is a problem

 

n n m

<G, A> where E] H gi such that ( H gi, H a.) c T(pk)
i=1 i=1 j=1 3

where 9i 6 G for 1 e i e n, A = {aj for 1 e j‘é m}, and

pch.

Simple problems can be solved by the application of
the one procedure to the declarative concepts in G resulting
in the declarative concepts in A. All simple problems can
be solved since the solving information is directly
encoded in T. As an observation of homework assignments
and quizzes, most problems that a student is given are
simple problems that require the recognition of the one
correct procedure to apply to the "given" data structure.

Definition IV.4.5 A complex problem is a problem

 

<G, A> that is not a trivial or simple problem.
Complex problems cannot be solved by the application
of a single procedure.
Definition IV.4.6 A problem <G, A> is solvable
if there exists procedures in P that will map elements in
G into all elements in A or if <G, A> is a trivial problem.
All simple and trivial problems are solvable. Complex
problems may or may not be solvable. If <G, A> is solvable,
then A is computable from elements in G.
Definition IV.4.7 <G, A> is complete if and only

if <G, A> is solvable.

89

All simple and trivial problems are complete.
Additional analysis is needed to determine if a complex
problem is complete. The knowledge for this analysis is
present in the pedagogic representation. Consider the
problem "Compute the area of a farmer's field knowing that
the field is 149 yards long and that the field has 40 cows
grazing on it." The pedagogic representation would need
to possess the information that the above problem is not
complete.

Extra information may be given in a problem to discover
if a student can distinguish the extraneous information
from the necessary information in solving a problem.

Such problems are called extrinsic problems.

Definition IV.4.8 <G, A> is extrinsic if and only

 

if <G1, A> is complete where Gl C G.

Example IV.4.9 The following problem illustrates an
extrinsic problem. "Compute the area of a farmer's field
knowing that the field is 147 yards long, that the field
has 4 cows grazing under 3 trees, and that the field is
53 yards wide." The answer {area of a field} can be
computed from the givens {147 yards long, 53 yards wide}
which is a proper subset of {147 yards long, 53 yards
wide, 4 cows, 3 trees}.

Extrinsic problems are appropriate problems to give
students. The student must learn to discriminate the
necessary information from the random noise. This
discrimination alters the usual problem solving approach

of most students which is to use all information stated

90

in a problem to solve that problem.

All problems that exist in a pedagogic knowledge
representation can be described as the sentential forms
of a meta-grammar that is derived from the representation.
The meta-grammar describes all possible G's for a given A.

Let the meta-grammar GRPROBA = <Vt, Vn' PGR’ SGR> where

Vt is the set of terminal symbols, Vn is the set of

non-terminal symbols, P is the set of productions, and

GR
SGR is the distinguished symbol. The mapping from a

pedagogic knowledge representation to GRPROB is

A
vt = d
V = D
n
SGR = a1 . . . an where A = {ai for l S 1 e n}
PGR is formed by the mapping
n m ,
For every ( H d., H d.) e T(p),
._ 1 ._ 3
1-1 j-l
I
dj ::= dl . . . dn for 1 S j s an

There are no terminal symbols since the givens are described

by the sentential forms of GRPROB . The m productions that
A

result for every element in T(p) of the form

In I I
d., H dj) indicate that dj is computed from

(
l l j=l

i

":15

d1 X . . . X dn by some procedure.
Let SF(G ) be the set of sentential forms for
RPRoaA

A and let sfi be in SF(GRPROBA). <G, A> 18 complete

if for every element gj in G, gj is also a symbol in Sfi'

GRPROB

and every symbol in sfi is in G. <G, A> is extrinsic if

91

every symbol in sfi is in G but there is at least one
element 93. in G that is not a symbol in Sfi'
Example IV.4.10 Consider the relations
T(Pl) = {(d1, d2)}
T(92’ = {(ds x d6 x d7' d4 x d1)' (d5 x d6 x d10'
d4 X dl)}
T(P3) = {(d8, d6), (all, d6)}

T(P4) = {(dgl dll)’ (d9! d8)}

The productions of GRPROB are:
A
d2 ::= d1 d4 ' = (15 d6 d7 d4 °.= d5 d6 dlo
d6 ::= d8 d1 :.- d5 d6 d7 d1 °.= d5 d6 d10
d6 ::= dll d11 . = (19 d8 ::= d9
The sentential forms for GRPROB{d } are
2
SF(GRPROB{ }’ = {d2' d1' d5 d6 d7' d5 d6 dlords d8 7'
.d
2
d5 d11 d10' d5 d9 d7' d5 d9 d1o}‘

The problem <{d5, d7, dlo}, {d2}> is complete; the problem
<{d8, dlo}, {d2}> is not complete; and the problem

<{d4, d5, d9, d7}, {d2}> is extrinsic.

IV.5 Solutions

The solution process of a pedagogic representation is
viewed as a two step process. The first step is the
construction of a plan to solve the stated problem. The
second step is the execution of that plan. The execution
of a plan is viewed as a successive application of procedures
to single or multiple declarative concepts which results in

declarative concepts that answer the problem.

92

Definition IV.5.1 A solution planning sequence,

 

denoted by 4£ for the problem <G, A> is a sequence of
declarative and procedural concepts that represent a
plan for solving the problem.

J represents all the procedures and data structures
that are necessary to compute the answer for the problem
<G, A>. ,J is composed of sub-solution planning sequences.

Definition IV.5.2 A sub-solution planning sequence

n m

I
IS the sequence (dl . . . dn) pk where (igldi, jgldj) c T(pk).

The parentheses are used to indicate all declarative
concepts upon which pk Operates. If pk only operates on a
single declarative concept, then the sub-sequence d1 pk
is used. The lack of parentheses in the latter case does
not result in any ambiguity within a solution planning
sequence.

Example IV.5.3 Consider the relations

T(pl)
T(PZ)

“as " as x d7' d1 " d4" (d5 " d6 x le'
d1 X d4)}

T(P3) = {(d8, d6), (dll'.d6)}

T(P4) = {(dg, dlll, (dlz, d8)}
A solution planning sequence for the problem <{d9}, {d6}>
is the sequence d9 p4 p3. For the problem <{d5, d9, d101,
(cl, d4}>, J is (d5 d9 p4 p3 c110) p2.

If <G, A> is complete and not extrinsic, every

element in G is also in.gfi and every declarative concept
in J is also an element in G. Thus G and ,4? have identical

declarative concepts. If <G, A> were extrinsic, then G

93

would have some declarative concepts that were not in,J.
If <G, A> is not complete, then.J would not exist by
Definition IV.5.1.

Definition IV.5.4 The execution pf 3 sub-solution

 

 

 

planning sequence (dl . . . dn) pk, denoted as

u n m .
5((d1 . . . dn) pk), 15 dj for some 3 where (igldi, jEldj)
c T(pk).

If 4f= sl . . . (dl . . . dn) pk . . . sn, then

t(dl . . . dn) pk results 1n.{f= sl . . . dj . . . sn

I
where dj is a declarative concept in the range of pk. The
execution of a sub-solution planning sequence is a
non-deterministic process since any declarative concept

in the range of pk can result from the execution of a

sub-solution planning sequence.

 

Definition IV.5.5 The execution ngflfi €(J3, is
the composition of executions of sub-solution planning
sequences.

Example IV.5.6 Using the relations in Example IV.5.3
and the sequence (19 p4 p3, the sub-solution planning
sequence is d9 p4. €(d9 p4) results in all“ The partially
completed solution planning sequence is d11 p3. £(dll p3)

yields d which is the answer to the problem <{d9}, {d6}>.

6

For the problem <{d5, d d {d1, d4}>, the solution

9' 10}’
p1ann1ng sequence 1s ((15 d9 p4 p3 dlo) p2 (d5 d9 p4 p3

The partial progress of a student solving a problem
can be monitored. Suppose a student is solving the

problem <{d5, d d10}' {dl}>. At each step in the

9'

94
solution of the problem, the student's progress can be

monitored by the completion of each sub-problem's solution
which corresponds to the execution of a sub-solution
planning sequence. Various scenarios could be incorporated
in a generative instructional system that uses the execution
of solution planning sequences to monitor or guide a

student through the solution of a problem.

The identification of’gffor a <G, A> is the planning
process of solving a problem. ,J'describes how the computation
of the answer will be accomplished. J is not necessarily
unique. There may exist several solution planning
sequences for a given problem. The execution of a solution
planning sequence is also not necessarily unique. There may
be several sub-solution planning sequences in a solution
planning sequence that could all be executed next. Thus
there may be more than one plan for solving a problem and
more than one manner in carrying out that plan.

Definition IV.5.7 A simple solution planning

 

seguence is a solution planning sequence that contains
one basic procedural concept.

Definition IV.5.8 A complex solution planning

 

seguence is a solution planning sequence that contains
more than one basic procedural concept.

Example IV.5.9 Using the relations in Example IV.5.3,
the problem <{d1}, {d2}> has a simple solution planning

sequence, namely d1 pl. The problem <{d5, d d {d1}>

9' 10}'

has a complex solution planning sequence, namely
(d5 d d

9 P4 p3 10’ p2°

95

A solution planning sequence for the problem <G, A>
can be derived as a sentential form of a meta—grammar

called GRSPSA’ Let GRSPSA = <V

Vn’ PGR' and SGR

as in Section IV.4. V

S > where V

vn' PGR' GR t'

t!
represent the same grammatical entities

t’ Vn’ PGR' and SGR are defined as

E U {(, )}

<
ll

GR 1 . . . an where A = {a1, . . . , a }

PGR is constructed via the mapping

n m ,
For every ( H di' H d.) e T(p)
i=1 j=1 3
'..= 4'
dj .. (dl . . . dn) p for l - j e m.
If n = 1, then the parentheses may be omitted from the
right hand side of the production.
Example IV.5.lO From Example IV.5.3 the following

productions will result from the relations:

d2 ::= d1 pl (11 ::= (d5 d6 d7) p2
d1 ::= (d5 d6 dlo) p2 d4 ::= (d5 d6 67) P2
d4 ::= (d5 d6 le) P2 d6 33? d3 P3

d6 ::= d11 p3 d11 ' = d9 94

d8 “= d12 P4

Each "asked for" has its own meta-grammar that
describes all the solution planning sequences for computing
that declarative concepts. The sentential forms for

GRSPS , SF(GR ), are all the solution planning sequences

A A
for A. For the problem <G, {d2}>

SP8

2
(d5 d8 P3 d7) p2 91' (d5 d11 p3 d7) p2 P1'

96
(d5 d12 P4 p3 d7) 92 91' (d5 d9 94 p3
The only simple solution planning sequence for the problem

<G, {d2}> is (11 pl. The other solution planning sequences

are complex.

CHAPTER V

CONCLUS ION

V.l Summary

The processes of a pedagogic representation are
illustrated by the construction Operations III.2.l
through III.2.8. WLOG the domains and ranges of the
procedural concepts are simplified to single elements.
Operation III.2.l,

d

 

 

1 pl 9. d2 and d2 )- d3

yields dl

 

 

illustrates the combination of two simple problems

to yield the complex problem <{dl}, {d3}> whose solution
planning sequence is d1 p1 p2. The implication of the
above operation is that the procedural concepts p1 and
p2 are meaningful in the subject area as the composition
P2 P1-

Operation III.2.2, III.2.4, and III.2.5 do not
yield additional problems but do provide additional
pedagogic knowledge about the subject area. These
operations help to connect a representation which reflects
the connected nature of the subject area.

Operation III.2.3,

97

98

 

 

d p >5 e and d
l J\
f
yields d >— e ,
J\ pl
f

illustrates the problem <{f}, {e}> in the subject area.
Considering the resulting diagram, one may speculate
that there exists a subset of e such that pl maps f
into this subset. Such speculation is strictly subject
area dependent and is not treated in this development.

In a similar manner, Operation III.2.6,

 

 

(1 p1 > e and g
e
yields 9
d p .>> 4? .
1

illustrates the problem <{d}, {g}> in the subject area.
The last two operations illustrate problems that could
be called "mis-named" problems because the domain or range
of the problem is mis-named, i.e. d is named f, and e
is named g.

Operations III.2.7 and III.2.8,

d )>. e and e
Pi

 

 

 

99

 

 

 

 

 

 

yields d >- e
Pl es». g
f p2
and e and f p2 + g
d :=
P
1 f
yields e
d p :=
l
f i g ,
p2

respectively, illustrate problems where the "givens"

or "asked fors" are not in the same domain or range

of a single procedure. From Operation III.2.7 the
problems <{d, f}, {g}> and <{d, f}, {e, g}> are identified.
From Operation III.2.8 the problem <{d}, {g}> indicates
that the declarative concept e is extraneous to the

solution of the problem.

V.2 Extensions
There are several areas in which the results of this

work is inadequate. Consider the diagram below:

———_>
j:G LD CFL
RG RL
where
D = {context-free grammar(CFG), context-free

language(CFL), regular grammar(RG), regular

language(RL)}

100

and

P = {language determination(LD)}.

The indicated and implied transformations are

LD: CFG«-—v-CFL
and

LD: RG——>—CFL ,_
respectively.

Because of the particular subject area, one would
like to conclude that

LD: RG——>-RL .

In general, the above desired conclusion does not hold
in all subject areas but does appear to hold in specific
instances. The mathematics do not allow the above
conclusion. An alternate formulation with perhaps
additional information would broaden the possible
implications that could be drawn from a given representation.
Such an alternate formulation might involve a different
treatment of the procedural concepts. The information
necessary for the correct implication is imbedded in the
procedural concepts. Thus some alternate formulation

of the information in the procedural concepts might

lead to identifying the appropriate conclusion.

The current work did not consider the components of
the basic procedural concepts. An analysis of the basic
procedural concepts might lead to a fundamental
understanding of their mapping implications, their
components, and the appropriate situations for their

applicability. Two subject areas with a limited number

101

of basic procedural concepts could be examined to determine
the fundamental components of the procedures. The identi-
fication of the fundamental processes might lead to a

basic understanding of the two subject areas and a basic
understanding of whatever commonality might exist between

them.

APPENDIX A

APPENDIX A
Non-repetitive Functional Composition for the

Subject Area "Angles"

r s s S S c c A

x x x x x x x x
D t t s c r A S d r t r t r t r
0 pl 0 0 0 0 0 0 0 0 0 0 O 0 0 0
p7 0 O 0 0 O 0 0 0 O 0 O 0 0 O 0
0 0 0 p2 O 0 0 p5 0 0 0 0 0 0 0 0
0 O 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 p3 O O 0 0 O O 0 0 0 0
0 0 0 0 p10 0 p4 0 p14 0 0 0 0 0 0 0
0 0 0 0 0 p11 0 O 0 0 O 0 0.0 0 0
0 0 0 0 O 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 p6 O 0 0 0 O 0 0 0 0 O
0 p8 0 0 0 0 O O O 0 0 0 0 O 0 0
0 0 0 0 0 p9 0 O 0 0 0 0 0 O 0 O
0 p12 0 0 0 0 0 0 0 0 0 O 0 0 0 0
0 0 0 0 0 p13 0 0 0 0 0 O 0 0 0 O
0 0 0 0 0 O 0 0 0 0 0 0 0 O 0 O
O 0 0 0 O 0 0 O 0 0 0 0 0 0 0 0
0 0 O 0 0 0 0 0 0 0 0 0 O 0 O 0
0 O 0 O 0 0 O O 0 0 0 0 O 0 O 0

102

rrxtu

3‘)
(050

(TXH

H'XU)
HX

O

103

0000

COD-‘0

H'XU)

0

(IX

(TX

3 Mt H:
D t
0 p1
p, o
0 0
0 O
O O
0 O
0 0
O 0
O O
0 p8
0 0
0 p12
0 0
0 p8
0 0
0 p12
0 0

fi'XH

O

00

O

S C
o o
o 0
P2 0
o o
O 0
p10 p10
0 o
o o
o o
o o
o o
o o
o o
o o
o o
o o
o o

104

0 O 0 0
0 0 O O
0 0 p50
0 0 0 0

p11 0 0 0
0 O 0 0
p6 0 0 0
0 0 0 0
p9 0 0 0
0 O 0 0
p13 0 O 0
0 O 0 0
p9 O 0 0
0 0 O 0

H'X

COO
OOOOOOOOOO

COO

CO

00000

HXU)

O

CO

HXO
FIX

OOOOO

000
0000000

0

HX
(IX

(0

137138

p7912

p8+plp798

p12+p1p7p12

(TX

105

p2
o

p1093+p10911p4p3+
piopspl4p3+
plopepl4p1lp4p3+
p10p11p4p6pl4p3
p1o+p1op1lp4+
91096914+
plopsp14pllp4+
p109119496914

p10911+p1opep14p11
o

p1ope+Piop1lp4ps

0

p1op9+910911914p9+
p109691499+
p10969149119499+
p1op1194pep1499

0

p1opl3+piop11p4p13
+p1096914913+
p1opspi4p11p4pl3+
p1op1lp496914p13

0

0

p1093+p1op11p4p3+
p1013691493+
p10p6pl4pllp4p3+
p10p11p4p6p14p3
p10+P1op1lp4+
91096914+
p1096914911134+
p109119496914

p1099+p10911914p9+

p10p6P14p9+
91096914911P4p9+
p10911949691499

0

p10913+Piopllp4p13
+p1096914913+
p109691491194913+
p109119496914913

I?

n

D

c x r p.7p8

c x t 0

A x r

p7912

A x t 0

i .
MT cont1nued
31

t

pa+plp7p8

p12+pip7912

O

106

p10p9+p10p11p4p9
+p109691499+
p10p6914p11p4p9+

p10911949691499

0

p10p13+p1oP11p4p13
+p1opspi4p13+
p1opspl4pllp4p13+
p109119496914913

p10p9+P1op1194p9
+p1opepl4p9+
p10p6pl4pllp4p9+
p10911949691499

0

p10913+p1091194p13
+Plopsp14p13+
p1096914911941’13+
p109119496914913

107

continued

0

p3+p11p4p3+psp14p3+pep14pl1p4p3+p11p4pepl4p3

p3plo+plip4+96914+91194p3plo+pepi4p3P1o+p3p1091194+
p6914pl1p4+p3plopsp14+911P4PSP14+96914P119493910+
p11949691493pio+pep14p391091194”)39109691491194+
p1194p391096914+p3p1op119496?“
pll+p3p10pll+p6pl4pll+p6pl4p3p10pl1+p3p10p6p14p11

o

p6+P3plops+911p4ps+Pllp4P3piope+P3p1op119496

o

p9+p3plop9+p1lp4p9+91194P3p1op9+96P14P3piop9+
p691499”)3910911p4p9+pepl4pllp4p9+p39109691415+
p1194PSP14P9+PSP14P1194P3p1ope+pspl4p3p1op11p4p9+
p1194p3plopep14p9+93910911949691499

o

p13+P1ip4p13+p6914p13+P3plop13+96914p11p4p13+
p119496P14913+P11P4P3plop13+psp14p3910913+
P391096914P13+P3P1op1194913+Psp14pllp4pap1opl3+
p119496?14P3P1o+PSP14p391091194913+P3P1096P14P1194p13
p11P4P3p1opsp14p13+939109119496914913

+

0

108
continued

p9+p3p1op9+p11p4p9+p1194p3p1op9+pspl4p3plop9+
p6914994”?3p1op11p4p9+psp14p1194p9+p3p1op6914p9+
p1194p6914p9+pep14p1lp4p3p1099+96914p3910p119499+
p11P4P3p1opsp14P9+p3plop11p4pspl499

o

913+p1lp4p13+96p14p13+p3p10913+psp14p1lp4913+
p1194p6p14913+911p4p3p1opl3+pep14p3p1opl3+
p391096914913+p3p10911p4p13+96914p11p4p3p1op13+
p11949691493p1o+Pep14p3p1opilp4p13+p39109691491194?13
p119493910969141313+p3p1opilp4pspl4p13

+

(Vka

\.

X

i .
MT cont1nued
n

00>l

0

p4P3+p4pep14p3

p4+p4p3p1o+9496914

+p49691493910+
p49391096914
p4p1l+p4p3p1op11+
P4pepi4pl1+
p4pepl4p3plop11+
p4P3P1op6914p11

o

p4PS+P4P3P1096

0

p4p9+p4p3plop9+
P496914P9+
p4p6pl4p3p10p9+
P4939109691499
o

P4p13+p4pepl4913+

94939103313+
949691493910913+
p49391096914913

109

ps
0

p4p3+p4pep14p3

p4+p4p3pio+P496p14

+P4pepl4p3p1o+
P49391096914
p4911+p4p3910911+
p4p6pl4pll+
p49691493910911+
p49391096914911

o

p4ps+P4paploP6

o
p499+p4p3p1op9+
p496P14P9+
p496914p3p1op9+
p4pap1opspl4p9
o

P4P13+p496914913+
p493910913+
p496p14p3p1op13+
p49391096914913

o
pl4p3+pl4pllp4p3
p14+P14P3910+P14pl1p4
+p149119493910+
P14p3plop1ip4

p14911+P14P3P10911

o
p1496+p14p3plope+
p14P11p4ps+
p14911949391096+
p14939109119496

o

p1499+pl4p3p1op9+
p14911P4P9+
p14911949391099+
p14939109119499

o
p14913+p14p11p4913+
p1493910913+
p“9119493910913+
p1493plop11p4p13

\
V

‘

It

continued

A
o
p4p9+p4p3piop9+
P4pepl4p9+
P496914P3p1op9+
p4939109691499

0

p4913+P496914p13+

p4p3p1opi3+
p49691493910913+
p49391096914913

110

S
o
p499+p4p3plop9+
p49691499+
p4p6914p3plop9+
p4p3plopep14pg

0

p4913+p4p6p14p13+

p4p3p10p13+
p496914p3p1op13+
p4p3p1opep14p13

d

o
p1499+p14p3plop9+
p14911p4p9+
pl4pllp4p3p10p9+
p”9391091119499

O

p14p13+p14pl1p4913+
p1493910913+
914911p4p3910913+
pl4p3p10pllp4pl3

111

7

2'
4t!

/

continued

M;
n

Xt

Xt

XI

Xt

xr

Xt

xr

0

r x t 0

0

s x t 0

0

0 0 0 0 0

S x t 0

0 0 0 0 O 0

X

0 0 0 0 0

c x t 0

AX

O

0 O 0 0 0

A x t O

BIBLIOGRAPHY

BIBLIOGRAPHY

Brown, John Seely, and Burton, Richard R., "SOPIE -
A Pragmatic Use of Artificial Intelligence in
CAI," Proceedings ACM 1974 Annual Conference,
1974, pp 571-579.

Carbonell, Jaime R., "AI in CAI: An Artificial
Intelligence Approach to Computer Assisted
Instruction," IEEE Transactions on Man-Machine
Systems, vol MMS-ll, no 4, December, 1970,
pp 181-189.

Codd, E. F., "A Relational Model of Data for Large
Shared Data Banks," Communications of ACM,
vol 13, no 6, June, 1970, pp 377-387.

Cohen, Ellis 8., "Problems, Mechanisms and Solutions,"
Technical Report, Department of Computer Science,
Carnegie-Mellon University, August, 1976.

deKleer, Johan, "Multiple Representations of Knowledge
in a Mechanics Problem-Solver," Proceedings of
IJCAI-77, August, 1977, pp 299-304.

Erman, Lee D., and Lesser, Victor R., "A Multi-level
Organization for Problem Solving Using Many,
Diverse Cooperating Sources of Knowledge,"
Technical Report, Department of Computer Science,
Carnegie-Mellon University, March, 1975.

Gries, David, Compiler Construction for Digital
Computers, John Wiley & Sons, 1971.

 

 

Izquierdo, F. J., "A Generator/Grader of Problems
about Syntax of Programming Languages to be used
in an Automated Exam System," Department of
Computer Science Report UIUCDCS-R-7S-755,
University of Illinois at Urbana-Champaign,
September, 1975.

Koffman, Elliot 8., "A Generative CAI Tutor for
Computer Science Concepts," Proceedings AFIPS
Spring Joint Computer Conference, 1972,
pp 379-389.

112

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

113

, and Perry, James, "An Intelligent CAI
Monitor and Generative Tutor," Final Report on
Project No. 020193 Grant No. OEG-0-72-0895,
June, 1975.

 

Minsky, Marvin, "A Framework for Representing Knowledge,"
MIT Artificial Intelligence Laboratory Memo No. 306,
June, 1974.

Moore, J., and Newell, A., "How can Merlin Understand?,"
Technical Report, Department of Computer Science,
Carnegie-Mellon University, 1973.

Munem, Mustafa ., and Yizzle, James P., Functional
Approach 59 Precalculus, Worth Publishers, 1970.

 

 

Newell A., and Simon, H. A., Human Problem Solving,
Prentice Hall, 1972.

 

Nilsson, N. J., Problem Solving Methods in Artificial
Intelligence, McGraw-Hill, 1971.

 

 

 

, "Artificial Intelligence," Stanford
Research Institute Technical Note‘89, 1974.

 

Notes from an Interdisciplinary Workshop on Theoretical
Issues in Natural Language Processing, June, 1975.

Novak, Gordon 8., "Computer Understanding of Physics
Problems Stated in Natural Languages," Technical
Report NL-30, Computer Science Department, The
University of Texas at Austin, 1976.

, "Representations of Knowledge in a Program
for Solving Physics Problems," Proceedings of
IJCAI-77, August, 1977, pp 286-291.

 

Page, C. V., Greenberg, L. H., and Gates, G. W.,
"Notes for Introduction to Compiling," 1971.

Proceedings of the Theoretical Issues in Natural
Language _Proce381ng, Association for Computational
Linguistics, June, 1975.

 

 

 

Prosser, Franklin, and Jensen, Donald D., "Computer
Generated Repeatable Tests," Proceedings AFIPS
Spring Joint Computer Conference, 1971,
pp 295-301. ‘

Quillian, M. R., "The Teachable Language Comprehender:
A Simulation Program and Theory of Language,"
Communications of ACM, vol 12, no 8, August,
1969, PP 459-476.

24.

25.

26.

27.

28.

29.

30.

31.

32.

33.

34.

35.

114

Ramani S., and Newell, A., "On the Generation of
Problems," Technical Report, Department of
Computer Science, Carnegie-Mellon University,
November, 1973.

Raphael, B., "SIR: A Computer Program for Semantic
Information Retrieval," Project MAC Report
TR-2, MIT, 1964.

Rychener, Michael D., "The Student Production System:
A Study of Encoding Knowledge in Production
Systems," Technical Report, Department of
Computer Science, Carnegie-Mellon University,
October, 1975.

, "Production Systems as a Programming
Language for Artificial Intelligence Applications
Vol I," Technical Report, Department of Computer
Science, Carnegie-Mellon University, December, 1976.

 

Sacerdoti, Earl D., "Procedural Net for Representing
Hierarchial Plans," Artificial Intelligence -
Research and Applications Progress Report,
Contract DAHCO4-75-C-0005, May, 1975.

Schank, Roger C., Goldman, Niel M., Reiger, Charles J.,
and Riesbeck, Christopher K., "Inference and
Paraphrase by Computer," Journal of ACM, vol 22,
no 3, July, 1975, pp 309-328.

Simon, R., "Some Relations between Predicate Calculus
and Semantic Net Representation of Discourse,"
Technical Report NL-2, Department of Computer
Science, University of Texas at Austin, June, 1971.

, and Slocum, J., "Generating English Discourse
from Semantic Networks," Communications of ACM,
vol 15, no 10, October, 1972, pp 891-905.

 

Sussman, Gerald Jay, "Electrical Design A Problem for
Artificial Intelligence Research," Proceedings of
IJCAI-77, August, 1977, pp 894-900.

Uhr, L., "Teaching Machine Programs that Generate
Problems as a Function of Interaction with
Students," Proceedings of the 24th ACM National
Conference, 1969, pp 125-134.

Vere, Steven A., "Induction of Relational Productions
in the Presence of Background Information,"
Proceedings of IJCAI—77, August, 1977, pp 349-355.

Vickers, F. D., "Cognitive and Creative Test Generators,"
Proceedings AFIPS Fall Joint Computer Conference,
1972, pp 649-659.

 

115

36. Whitlock, L. R., "Interactive Test Construction and
Administration in the Generative Exam System,"
Department of Computer Science Report UIUCDCS-
R-76-821, University of Illinois at Urbana-
Champaign, August, 1976.

37. Winograd, Terry, "Five Lectures on Artificial .
Intelligence," Artificial Intelligence Laboratory
Memo AIM No. 246, Computer Science Department,
Stanford University, September, 1974.

38. Woods, W. A., "Transition Network Grammars for Natural
Language Analysis," Communications of ACM, vol 13,
no 10, October, 1970, pp 591-606.

39. , Kaplan, R. A., and Nash-Webber, B., "The
Lunar Sciences Natural Language Information
System, BBN Report No 2378, June, 1972.

 

40. , "What's in a Link: Foundations for Semantic
Networks," Representation and Understanding:
Studies in Cognitive Science, edited by Bobrow and
Collins, Academic Press, 1975.