UTILIZING SEMANTIC NETWORKS

TO DATABASE AND RETRIEVE

GENERALIZED STOCHASTIC

COLORED PETRI NETS

m

l

3

by

Jeffrey J. Farah and Robert B. Kelley

m

& ,

m

ires

F__

Rensselaer Polytechnic Institute

Electrical, Computer, and Systems Engineering Department

Troy, New York 12180-3590

August 1992

CIRSSE REPORT #123

w
m

m

s

u

m

m

i

u

w

Utilizing Semantic Networks to Database and Retrieve

Generalized Stochastic Colored Petri Nets

Jeffrey J. Farah Robert B. Kelley

Center For Intelligent Systems For Space Exploration

Renssetacr Polyr._hnic Institute

Abstract

Previous work has introduced the Planning Coordinator

(PCOORD) , a coordinator functioning within the hierarchy of the Intelligent Machine Model. Within the structure

of the Planning Coordinator resides the Primitive Structure

Database (PSDB) functioning to provide the primitive

structures utilized by the Planning Coordinator in the

establishing of error recovery or on-line path plans. The

following further explores the Primitive Structure Database

and establishes the potential of utilizing Semantic Networks as a means of efficiently storing and retrieving the

Generalized Stochastic Colored Petri Nets from which the

error recovery plans are derived.

1.0 Introduction

The problemdomain which thispaperaddressesisa

component of thePlanningCoordinatorknown as the

Primitive Swucture Database (PSDB). As the name indicates, the Primitive Structure Database is a database containingprimitivestructuresrepresentingthebasicoperations that can be performed by an Intelligent Machine as

derived from environmental model(s) in which themachine

must operate. Collectively called a Current World Model

(C'%VM),theenvironmentalmodelormodels represent the

mostup-to-dateinformationavailableregardingtheInteUigentMachine'senvironment.

Note that the usage of the term Intelligent Machine is

meant to include any machine that functions to perform

intelligent tasks. For the purposes of this paper and the

continuing research it represents, intelligent tasks can

rangeintypefromprimarilycerebral,asintheidentificationofanobject,toprimarilymechanicalasintheassembly

ofanobject.The common denominatorsinallofthetasks

aretwofold:

1) While task sequences must be performed in a given,

arbitrary amount of time, the components of the sequences

are primarily event driven.

2) Relationships among tasks may be opportunistically

used in later task composition if the relationships axe

known.

Generalized Stochastic Colored Petri Nets (GSC"PN)are

used as tools for effectively and efficiently modeling multiple level discrete event or continuous event dynamic

systems. While the general structure of a GSCPN allows for

the synthesis of more complex GSCPNs from simpler ones,

there is no easily apparent mechanism for databasing the

GSCPNs in such a way as to easily build relations among

them.

Semantic Networks, on the other hand, have been used

as in [1] and [2] as a means of establishing relationships

between differing states within a network. These relationships can be databased and modified without the destruction

of the existing relations or the existing database. It is the

intent in the remainder of this paper, to examine the basic

concepts of Semantic Networks as they pertain to the PSDB,

and to determine if through the utilization of Semantic

Networks, a dynamic means of representing GSCPNs can

be established.

The paper is organized into the following sections:

1.0 Introduction

2.0 Generalized Stochastic Colored Petri Nets

3.0 Semantic Networks

4.0 Derivation of GSCPN's From Semantic Networks

5.0 Conclusions

References

2.0 Generalized Stochastic Colored Petri Nets

Simply put, a Petri Net is a graph theoretic abstract modeling concept used to efficiendy model the states, preconditions and functions of a discrete event, or continuous event,

dynamic system, particularly when concurrency and con-
m

m

u

Z--

m

m

flict arc involved. The discrete or continuous system is

modeled as a continuum of sequences of event driven states

and timed transitions. Note that the us¢ of timed transitions

does not alter the event driven nature of the Pctri Net as it is

the completion of the function that the transition represents

which signals the next action, not the length of time the

function takes to complete.

As defined in [3] and [4], and augmented h_e to include

colors, a Generalized Stochastic Colored Petri Net

(GSCPN) is a sextuplet consisting of places, P, a finite set of

token colors, C, a finite set of transitions, T, a f'mite set of

arcs, A, a f'mite set of firing functions, F, and a set of initial

markings, M0, which indicate the initial configuration of

tokens in each place.

The components are defined below:

Describe the set of states represented in the

system andare divided into input places and output places

which source and sink arcs to/from transitions respectively.

Used to d/fferendate levels of operation or

functions required by the executing Pea'i Net through

tokens.

Tokens: Markers of various colors, shape, used to

denote the location of activity within a Petri Net.

Divided into immediate Transitions,

Ti, and exponential transitions, Te, the transitions dcf'me

events that can change the sys_ states.

Arcs (A); Represent the connections from input places to

F'_'um 1: _ Staze

Raw:_ F_ _I

"::.:"_ ._':.... )=.== ...._,==r_=

f ,.:

[ _" "C".Y'" ga_ _a_at

[ .._...=...._. ta

,,,

...t. h_. "

V_ure 2: Resu_ of f_ra

h--_s;'ficn tl.

mausitionsandtransitions tooutputplaces. Az'csare defined

as a proper subset of."(PxT) U (TxP).

Firine Functions (1;3:Associates with each transition in

the set of transitions a fh'ing time which is a continuous

random variable, independently distributed.

Initial Markings (M0): Is a mapping called the initial

marking, wMch associates zero or more tokens to each

place in the GSCPN. Markings in general define the state

of the GSCPN through the distribution of tokens.

As an example of the operation of a Petri Net, refer to

Figure 1 through Figure 8 . These figures represent an

example of a simple manufacturing system containing two

machines and a single shared robotic resource used for
I

N

====

Z

m

L_

i

I

I

i

F'_ure 4: ResuZt¢:ff'_',g

tr-tr-tr-tr-tr_s_on t3 f_:lhwed _yN.

F'_'ura_: Res_ ¢_£_r',g

lz-at_t_n tl& 15.

Po..;;:;:::.: _ tt / R=_

_e _;'" -_;.--.'-. nm _ l

-

Rgure 6: Result of f_._:j

tr'a_it_n t:;Z& t6.

tz-'_sit_n :3 & t7.
m

u

m

m

m

m

m

N

E:

i

F:

m

FlawSz=cx_" _I

I -_"'_'i::__.I_=_,

Av_ .... t

, n t

_ure S: Resu_ _f r_

tz'-=zls_ont4 & _.

loading and unloading the machines. All wansidons are

considered immediate. It is assumed that the operations of

the two machines never overlap (i.e. machine two is always

ready to accept input from machine one).

Initially, see Figure 1, raw stock is available for use by

machine one, the robot is available for use, machine one is

available and machine two is available. A transition is

considered active, ready to fire, if all of its input places

contain tokens. Initially only transition tl is active. It rrres,

resulting in machine one being loaded. This is rvpresenw.A

in Figure 2. Note that when a transition fires, a token is

removed from each of its input places, and a token is

deposited in each of its output places.

Transition t2 is now active and fires, resulting in Figure 3

where a token has been deposited back to Robot Available

and M1 Machine Raw stock. Figure 4 through Figure 8

show the operation of the system as it continues. Note that

inFigure5,bothtransitiontland transitiont5areactive;

hence both can f'tmresultingin both machineMI and

machineM2 operatingconcurrently.The examplegiven

above isa simpleone used to demonstratesome of the

capabilities ofthePetriNet.

Thisexamplewillbe furtheredinSection4 whereitwill

be shown thata PetriNet canbederivedfrom theSemantic

Networkdescriptionfactivities thatmay berepresentedby

theoperationofthePetriNet. SemanticNetworksarethe

subject of the next Section.

3.0 Semantic Networks

As described in [5], [6], and [7], a Semantic Network

(SNET) is an abstract conceptual strucatre representing

knowledge as a net-like graph. It consists of nodes, representing conceptualunits,anddirectedlinksrepresentingthe

relationshipsbetween units.The essentialideabehind

SemanticNetworksisthatthisgraphtheoreticstructureof

relationsandabstractions canbeusednotonlyforinference,

butalsoforunderstanding.

Unlikespecializednetworksand othergraphtheoretic

structuressuch asPetriNets,SemanticNetworks aim to

representanykindofknowledgewhichcanbe describedin

naturalanguage.Inaddition,theSemanticNetwork providesmethodsforautomaticallydcrivinglargerbodiesof

impliedknowledgewithoutdestroyingtheunderlyingbody

ofknowlcdge explicitlystoredintheSemanticNetwork

structure. This approach remains valid because any event,

idea, object or situation can be shown to have some composite structure which can be decomposed for storage provided

that characteristic relations are maintained.

Semantic Networks possess multiple layers of abstraction.

These multiple layers of abstraction provide the SNET with

the capability of maintaining multiple classes and superclasses for state description. This capability is extremely

important in professional applications, such as hierarchical

object modelling, which have gone past the point where

pure mathematical modeling is effective.

Such activities require in-depth conceDtual analysis as

opposed to repeated processing of modeled elements. This

conceptual analysis is provided through an arranged, ordered structure cailed a knowledge base. However, a

simple knowledge base for storage and retrieval of information is effectively useless for complicated activities such as

those to be performed by an Intelligent Machine, unless the

structured knowledge base can be used to infer other knowledge from what has been stored explicidy. Accomplishing

this task requires the examination and use of the

structttre of the concepts involved.

A SNET provides a map of the semantic meaning of a

natural language sentence in an ordered, arranged, structured knowledgebase. Thispermitsseveralsyntactically

differentsentences,allof whichhavethesame meaning,to

be relatedimmediately.Were theSNET beingused asa

database of information,a savingsof spacewould bc

achieved,sincemultipledistinctrepresentations would not

need tobe maintained.Inaddition,themodelingofdatabasesthroughtheuseof SNETs can be preferabletoroodu

m
m

w

m

_ o

w

. :

w

m

1

r_

m

mm

r _

m

eting databases in some other way, because in the former

one can make use of the relational structures and concepts

in the data model.

The use ofa SNET as a databasing tool is of interest in

the operation of an InteUigent Machine. This is due to the

requirement that in order to be competent in the execution of

fully autonoumous tasks, an Intelligent Machine must necessarily Ix)able to interpret its surroundings and make connections between similar and dissimilar concepts. To accomplish this efficiendy requites a set of Primitive Scucttwes derived from an environmental model which details not

only the environment but also the capabilities of the Intelligent Machine. These Primitive Structu_s form a core of

Level Components Structures

Arb. Concepts, Sentence

L|nguiatl¢ words, express. Descriptions

Semantic or Concept. Concept t)ep.,

Conceptt.tai Relations (cases), Oeep Case

prim. obis. , actions Semantic Nets

C4n¢lpl types, Associative

"pistemologica| Inheritance etc. Rdilationei

Logloa|

Implementation

Propositions

PredlcatSl Boolean Logic)

_0gicat Operators Nodes

Alomt Oats $1ructur|s

Pointers Frames

R_m 9: Brac'-anan's A_ysis

concepts from which remaining concepts can be built. Note

that this does not prohibit the introduction of new concepts

that arc not built from the cote.

The concept of using a core of primitives was first

re,aJized by R. H. Pdchens in his creadon Nude, which was

responsible for language translation [8]. Richens' Nude

sysmm utilJz_ semandc primitives [9], a core of concepts

fl"om which other conceptscould be bull _ pttrpose was

to retain the meaning of the concept. His work on Nude

was organized and improved by M. Mastennan in her Semantic Network T [10] which creamd a thesaurus for organizing langtmge concepts hierarchically. She postulated

that a lattice structure was more effecdve than a _'ee taxonomy. The T lattice was the final product of a network of

sub-lattices in which Masterman used what she mimed

rrdn/nm/a rather thanprimidvea, sincehers we,re not ultimate

primitives. The combined work of Richens and Masterman

was adapted for Preference Semantics (I I] and provides a

ftmcdonal foundation that is usdul for incorporadon into

and adapdon by Primitive Sttuctttre Database of the PlanATTACK

e_sss i TYP_ RESTRICTION

J

ACTOR I animate agent

OBJECT I person 0r thing

INSTRUMENT I movable thing

BENEFICIARY t live being, group, cause

A'T T1ME l time point onlnter*el

)

Fx;ure 10 C_e_Ft_rr, e f(:r ATTACK

ning Coordinator.

The ability to compose additional concepts from a core of

original concepts is extremely important. However, in addition to the general concepts there must be some specification

as to the content of the concepts. This specific information

is necessary to ensure distinction of objects within the same

conceptual class as well as formulauon of new concepts and

conceptual classes. R.J'. Brachman [12] realized this and

suggested five link]node levels as shown in Figure 9 below.

A descripuon using a Semantic Network can exist on all of

the levels simultaneously, with objects and reladons at one

level being realized using the structures of a lower level.

The question becomes, how are the structures represented for

implementation in computer environs.

The standard representation of Semandc Networks in

conventional computer environs is achieved through the

use of frames. However, it has been shown by F'dlmore and

Simmons [13], [14] that simple frame relauons are insufficient. They postulated that the semandc case represents the

real- world role played by an ACTOR in an EVE, VT. Hence

they applied restrictions to the frames developed by

Minsky. This new frame type, characterized by an event,

its cases and the type restrictions placed on related objects

is called a case frame or schema. An example of such a

case_frame is given in Figure 10, for the case frame .A.T.z

TACK.

With respect to the Primitive Structure Database and its

operation, the use of case_frames is highly appropriate.

This is due to the fact that in a limited environment such

as that represented by a specific robodc testbed, only

specific actions may be appropriate. For example, ira robot

has a particular type of gripper it may not be able to pick up

certain types of objects. Application of the limiting restrictions of a schema permits those limitations to be easily
i

W

i

=

U

m

u

identified within the type restrictions of the schema. This, in

turn, provides a speed up in overall operation as less

searching need be performed to determine what applications are possible given the available information.

It had been mentioned earlier that Semantic Networks

permit classes and superclasses to be established. This is in

keeping with the idea of multiple levels of abstraction

provided by Semantic Networks. Conceptual graphs have

been examined extensively by Sowa [15] and use nested

contexts derived odginaUy from the nested negations of

Pierce's Existential Graphs. The idea of conceptual graphs

can be utilized in the PSDB, allowing primitive structures,

which represent primitive actions , some of which are

themselves non-trivial, to themselves be represented by

complex nested structures.

It has been discussed previously that Semantic Networks provide the capability of building concepts from a

core of concepts, limiting relations between objects existing at multiple levels of absgaction, and providing a structured arranged net composed of nodes and links which

represent concepts and the relations between concepts respectively. Previously, Generalized Stochastic ColoredPetri

Nets were inlroduced and theft structure defined. What

remains is to determine whether or not GSCPNs can be

derived from SNETs. This is the subject of the next

section.

4.0 Derivation of Petri Nets From

Semantic Networks

As defined in Section 2 a Generalized Stochastic

Colored Petri Net is a sextuplet of places, colors, transitions, arcs, f'n'ing function(s), and initial markings. As described in Section 3 a Semantic Network is a doublet of

arbitrarily complex nodes and arcs. If it is to be anticipated

that a GSCPN can be derived from a SNET, some relationship between the varying components which form a GSCPN

and those that form a SNET must be identified.

The nodes of a SNET have been described as being

arbitrarily complex, consisting of possible nested structures.

This description is akin to the use of colors in the GSCPN,

which arc used to distinguish different levels of activity.

Hence it is possible to chromatically identify the differing

levels of a complex node in a manner similar to the identification of differing functional levels in a GSCPN. Since, as

stated, the complex hierarchy of the nodes can be represented by unfolding them, the structure of their functional

representation can easily be revealed.

Semantic Network arcs ate also complex, representing

non-arbitrary relations between the nodes that connect to

the head and tail of the arc. In effect, the arcs can be

viewed as functions relating the two nodes, taking one node

(state) to the other node (state). This is the exact function

of the arc-transition (Firing Function)-arc structure of the

GSCPN.

One complex difference between GSCPNs and SNETs

is that the GSCPN utilizes tokens as markers to visually indicate the flow of the system operation over a marked path.

It is in this that a problem may arise. The problem is that

while both the SNET and the GSCPN have mechanisms

for identifying a flow pattern, how is it possible to create

one flow pattern from the other. Specifically, how is it

possible to create a GSCPN from a SNET.

By definition, Petri Nets are useful for the modeling of

concurrent systems. As shown in the example of Sectionl

this concurrency can be easily achieved. Effectively, the

Petri Net passes a marker or markers, called tokens, from

one finite state to another through functions represented by

transitions.

J. A. Hendier [16] and M.R. Quillian [17] performed extensive work on massively parallel marker passing in Semantic Networks. Effectively, symbolic marker passing is a

technique developed for finding connections between objects in a Semantic Network, while avoiding many irrelevant

facts. Essentially, two nodes representing the objects to be

connected, are marked, meaning that they are identified as

being of interest. The algorithm then marks appropriate

neighbor nodes and continues in that fashion until a node (or

nodes) is marked from two differing origins. The algorithm

then uses the back pointers it established during marking to

compute a path comprised of the set of nodes and links that

were marked during the marking expansion phase of the

algorithm. The established path connects the two original

nodes that a connection was initially desired for.

It is possible that during the marking procedure,

exponential explosion of the number of marked nodes can

take place due to the large number of nodes that would exist

in even a simple SNET. This difficulty and that of algorithmic improvements for avoiding false paths were examined in [18], [19], and [20], with the result being that through

restrictions on type and limitations on acceptable link traversals, false paths and exponential explosion could be

virtually eliminated.

In all, this indicates that a path can and was derived from

the node and link relationships of the Semantic Network. If

those node and link relationships were to represent Intelligent Machine activities, it is feasible that the derived paths

would represent an ordered sequence of Intelligent Machine activities. Like a GSCPN, the nodes of the path could

represent system states of arbitrary complexity. Unlike a

GSCPN however, the links of the SNET represent relationships between the nodes. This structure is unlike the

input arc, transition, output arc structure of the GSCPN,

where the transition represents the relation or rather action
m

i

m

w

- =

F

F'_-ure 11

that takes one system s_ tOanother. It is apparent that the

transition can be made to represent the relation of the S/VET

while the input and output arc, can be formed by following

the directional pointer retnesented by the arc of the SNET.

Once all SNET node, and links have been transformed

to their equivalent GSCPN nodes, wansifions and arcs, one

of the nodes must be designated as the initial node in the

GSCPN. This node is necessarily one of the two from

which the marking algorithm began. What remains at this

point is the establishment of the initial markings of the newly

derived GSCPN. Logically, it can be assumed that the

wansifion to which the lead place is connected should be

active. Hence whatever lXecondidons it needs must be met.

This will effectively identify the initial markings.

The result of all of the above is a G$CPN which is

ready to be used by the Planning Coordinator after having

•".'Mr:'"

_-_'_k _ ;-'._2".'.

"...-....-._ -.:_.:." _....... need_foe ma_.

F'cjure 12 ""'_"_

,,.=.. ==, _

_.i..u.. .*:.._ .__,_ jo=a.

...... .

...

.... oo.°

°

"-Mr;.:" _,.-_.t::"_.._eeo _¢ !¢aa.

'i".Y::

"" _._¢ m_'_

Fcjure 13" ,-.)a',._.,_ •
nLUMm

n

UInu

m

r...,

UI_

m

1

1

"""_". .,_'_t_

--_._:..,:.

... r___.__._ ...,_,. _,,,od_.__.

.i_'_"; -

F_l'e 14

"!_-_ :_$._...,__,__.,.._.

"_., ,,,-'-_-_,_.'

"_,_,:..,,,--'"_,.,__ ..,=_.

F_um 16

.-_. _ _'_.

"-.: ._=..'." .,/.:-.,y,.._::--'_ _._d__:_,.

-;. o:.

_. _- ;.._..:,,,..,,.._,,,..:.-.=

_.-_._:!I'- ,w .'=-_. 1 I

F',_'ut_'t7
i

w

i

m

= = .

m

T_

m

=

a

_=

m

,3":_:]

::s_ _,,,,___. -;

:., ,... _.oad'.

•-.._:.

.._:;,<..,,__r__oad.:.:_:;..._.,_n__,_rJc_d.

_-'._;': _ :C_-_"

"','_"_'_'_ "':,.;:." _ _.

"°"_

F'_jum 18

been derived from the Semantic Network on which the

Primitive Su'uctu_ Database was creauxi. The following

example shows the tzansformadon of a Scmand¢ Net'work

representing the manufacturing system of Section 1 into a

GSCPbl utilizing the above proc_urc. Following it arc

some conclusions as to further research and development.

Given that the following Semantic Network existz, the problem ix to derive the Petri Net of Fieure 1.

utilizing the marker pa_ing techniques outlined earlier in

this section. It ixa_xumed that pruaing tecimiques have been

and are applied to the overall SNE'I'srructare such that

unneeded branches are el'u'nin_ed.

The SNET _ven in Figure 11 , representsthe Semantic

F_jure 19

-::M1':."

"::MI.::"
m

W

7. 7

" " ":" .

FGu_ 2_

F_um 2_.
uw

=w

:'- b¢_..-

,¢

-;kr_iI _.'_i

_c2ure 26

Network description of the manufacturing system of Figure

I. The two nodes labeled 'Load MI' and 'Unload M2'

represent the nodes from which the marking algorithm is

called. Later, one of these nodes must be designated as the

GSCPN Start Node.

The marking algorithm begins by marking all neighbors

connected to the outgoing links of the two initial nodes. The

progression of this marking is shown in Figures 12 through

17 by thicker darkened lines.

As can be seen, at the completion of the marking phase,

the final figure appears as in Figure 18 which in this

example is the same structurally as Figure 11. Note however, that the marking algorithm has provided two alternate

paths from the ini_al nodes. They are designated by the solid

and dashed lines. This is acceptable for an overall primary

solution, because both the f'trst and second paths are immediately connected to both of the initial nodes. Thus both will

be needed for the final GSCPN cons[auction.

Once the necessary paths have been generated, as above,

one of the two nodes initially calling the marking algorithm

must be designated as the start node of the GSCPN. In this

example that node is the one marked_

Upon designation of the GSCPN start node, it is

necessary to transform all nodes to GSCPN nodes and all

arcs to GSCPN arc- transition (Firing Function)-arc constructions. This is accomplished as follows. Starting from

the GSCPN start node, all outgoing ares are transformed

into input transitions and input ares, i.e. their direction is

¢tmn_ed anda transition re t)resenting their relation (funcli_/a).Jf_gaL_. The nodes at the head of the SNET arc

become source nodes for this transition and an outgoing are

iscreated from the transition to the tail of theSNET arc. This

is shown in Figure 19 for the GSCPN start node.

Figures 20 through 26 show the progression of this

operation for each of the remaining nodes. Note that some

of this can be done in parallel. However, for clarity at this

point it is done serially. The resulting figure is the GSCPN

of Figure 1.

What remains is the initial marking of the net. From the

algorithm, it is obvious that the nodes connected to the

transition that is connected to the node designated as the

starting node of the GSCPN should each contain tokens.

Depending on the type of node, more than one token may be

necessary. Similarly, the nodes connected to the outgoing

side of the transition connected to the end node of the GSCPN

could contain tokens since the end node must necessarily

provide for the potentiality of these nodes acting concurre.nay in the operation of the GSCPN. In the previous

example the nodes did require tokens.

w
K

m

_4

w

The example provided above is a necessarily simple,

limited expression of what the overall capabilities of the

techniques proposed will eventually be able to do. The

following section provides some conclusions on the research

done and recommendations for future work on the subject.

5.0 Conclusions

This paper has introduced the use of Generalized

Stochastic Colored Petri Nets, and examined Semantic Networks with respect to their use as a means of realizing the

Primitive Structure Database of the Planning Coordinator.

In addition, a potential method for designing the Primitive

Structure Database of the Planning Coordinator such that

useful Generalized Stochastic Colored Petri Nets can be

derived from it was introduced. While the method

presented provides for a database structure that is both

refinable given new data and usefully structured as a knowledge base, and uses an algorithm that has been tested and

accepted, the method itself has yet to be proven. Further

research, development and undoubtedly refinement particularly in the initial marking of the derived GSCPNs is

ongoing.

Acknowledgements

Jeffrey J. Farah was supported by AT&T through the

AT&T Bell Laboratories Doctoral Support Program. Dr.

Robert B. Kelley was supported in part through grant NAGW1333 from NASA, to the Center For Intelligent Robotic

Systems For Space Exploration, Rensselaer Polytechnic

Institute.

References

[1] Lehman, F.,"Semantic Networks", Computers MathematicsApplications, Vol. 23, No. 2-5, pp. 1-50, 1992.

[2] Vogler, W., "Failure Semantics Based On IntervalSemiwords Is A Congruence For Refinement", DistributedComputing, Vol. 4, pp. 139-162, 1991.

[3] Narahari, Y. and Viswanadham, N., "A Petri Net ApproachTo The Modeling And Analysis Of Flexible ManufacturingS ystems,'" Ann. Oper. Res., Vol. 3, pp. 449-472, 1985.

[4] Murata, T.,"Modeling And Analysis Of Concurrent

S ystems",Handbook of Systems Engineering, C.R. Vick and

C.V.RamamoorthyEds.,NewYork:Van Nostrand Reinhold

,1984, ch. 3.

[5] Nilsson, N.J., Principles of Artificial Intelligence.

Morgan Kaufman, California, 1980, ch. 9.

[6] MacRandal, D., "Semantic Networks", Approaches

toKnowledge Representation: An Introduction, Research

StudiesPress/John Wiley & Sons, Letchworth, Hertfordshire/New York,1988. [

7] Shastri, L., Semantic Networks: An Evidential Form_llization and its Connectionist Realization, Morgan

Kaufman, California, 1988.

[8] Richens, R.H., "Preprogramming for MechanicalTranslation", Mechanical Translation, 3 (1), 1956.

[9] Richens, R.H., "Report on research of the CambridgeLanguage Unit", Mechanical Translation, 3 (2), 1956.

[10] Masterman, M.,"Semantic Message detection for

machinetranslation, using an interlingua", 1961 InternationalConference on Machine Translation of Languages and AppliedLanguage Analysis - Proceedings, Her Majesty's StationaryOffice, London (1962).

[11] Evens, M.W., Relational models of the lexicon:

Re oresenting Knowledge in semantic networks, Cambridge

University Press, New York, 1988.

[12] Brachman, R.J.,"On the epistomological status ofsemantic networks", Associative Networks, (N.V. Findler,Ed.),

Academic Press, Florida (1975). Reprinted (1985), Readings in Knowledge Representations, Morgan Kaufman,

California.

[ 13] Fillmore, C.J.,"The case for Case", Universals inLinguistic Theory, (E. Bach and R.T. Harms, Eds.), Holt,Reinhart

& Winston, New York, 1986.

[14] Simmons, R.F.,"Semantic Networks: Their computation anduse for understanding English sentences", Computer

Models of Thought and Language, (R.. Schank and K.M.

Colby, Eds.), W.H.Freeman, Chicago, 1973.

[15] Sowa, J.F., Ed., Princioles of Semantic Networks:

Explorations in the Representation of Knowledge, MorganKaufman, California, 1992.

[16] Hendler, J.A., "Massively-Parallel Marker-Passing

InSemantic Networks", Computers Mathematics &

Applications,Vol. 23, No. 2-5, pp. 277-291, 1992.

[ 17] Quillian, M.R.,"The teachable language corn prehender:. ASimulation program and theory of language", Communications ofthe ACM, 12, 459-476, 1969.

[18] Norvig, P.," Marker passing as a weak method for

textinferencing", Cognitive Science, 13 (4), 1989.

[19] Yu, Y. and Simmons, R.,"I'ruly parallel understanding oftext", Proceedings of AAAI-90, Iuly 1990.

[20] Riesbeck, C. and Martin, C.,"Direct memory accessingparsing", Experience, Memory & Reasoning (J.

Koiodner andC.K. Reisbeck, Eds.), Lawrence Erlbaum, 1986.1=

= =