Conditional transition networks and computational processes for use interactive computer-based systems

• US 5,809,212 A
• Filed: 12/18/1996
• Issued: 09/15/1998
• Est. Priority Date: 07/12/1993
• Status: Expired due to Term

• Current Assignee: New York University
• Original Assignee: New York University
• Inventors: Shasha, Dennis
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Shah, Sanjiv
• Application Number:
  US08/768,727
• Time in Patent Office: 636 Days
• Field of Search: 395/10, 395/55, 395/600, 395/162, 364/200, 376/259
• US Class Current: 706/46
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

A conditional transition network for representing a domain of knowledge in a computer based system and computational procedures for use with the same is here presented. Each node of the network comprises a number of data fields, namely: a Precondition Field which contains an expression that evaluates to either TRUE, POSSIBLE or FALSE; a Question Field consisting of a linguistic string; an Answer Field whose expression can evaluate to any numerical or string domain, a Contents Field from a textual, visual, audio, or multimedia domain; and several other fields including a Delay Field. The edges of the network are induced by the precondition and answer formula and by edges embedded in the contents. If the precondition of node A refers to node B, then there is a precondition edge from B to A. Similarly, if the answer formula of node A refers to node B, then there is an answer edge from node B to node A. Edges from the Contents Field of one node to the Contents Field of another node are called hypermedia edges or links. They also may have predicates attached to them. When the querier of the network answers questions, various nodes change their precondition values among the values TRUE, POSSIBLE and FALSE. TRUE nodes correspond to those the querier should examine further. FALSE ones correspond to those of no further interest. POSSIBLE ones correspond to those that may or may not be of further interest.

Claims

1. A computer-based system for providing a user flexible access to information items stored in an information storage medium associated with said computer-based system, said computer-based system comprising:

(a) programmed means for producing a data structure for use in representing a knowledge network including a set of questions answerable so as to provide a set of answers associated with said information items, said data structure including a plurality of nodes, each said node having a plurality of data fields including;

a question field for storing data representative of a question in said knowledge network,

an answer field for storing data representative of an answer formula evaluatable to produce a value for said answer formula, the value of said answer formula, or an answer to the question in said question field of said node,

a qualified answer field for storing data representative of a qualified answer evaluatable to produce a value for said qualified answer,

a precondition expression field for storing data representative of a precondition expression evaluatable to produce a value for said precondition expression which expresses a truth condition upon said answer formula, the value of said answer formula, or the answer to said question, stored in the answer field of said node,

a contents field for storing data representative of one or more information items associated with said node, and

a display field for storing a display label having a display value dependent on the values of one or more of said plurality of data fields at said node, said display label being visually displayable to said user,

wherein the value of the precondition expression in the precondition expression field of at least one said node depends on the value of one or more of said plurality of data fields associated with at least one other said node,

wherein the value of the qualified answer in the qualified answer field of each said node depends upon the value of the answer in the answer field of said node and the value of the precondition expression in the precondition expression field of said node, and

wherein the display label in the display field of each said node depends at least on the value of the precondition expression field of said node;

(b) data storage means operably connected to said programmed means, for storing the data associated with said data structure produced by said programmed means;

(c) visual display means, operably connected to said data storage means, having a display surface for visually displaying data representative of at least a portion of said data structure including said display labels associated with at least one or more nodes in said data structure; and

(d) data entry means operably connected to said data storage means, for entering data into said data structure or modifying data stored in said data structure.

2. The computer-based system of claim 1, wherein the precondition expression in the precondition expression field of each said node is formulated using propositional logic, predicate calculus, arithmetic expressions, mathematical functions, or information from an external database, or any combination thereof.

3. The computer-based system of claim 1, wherein the value of each said precondition expression is a value selected from the group consisting of TRUE, FALSE and POSSIBLE.

4. The computed-based system of claim 1, wherein the answer in the answer field of at least one node is an answer-formula.

5. The computer-based system of claim 1, wherein each said node further comprises a title field for storing a title assigned to said node.

6. The computer-based system of claim 1, wherein said set of questions are answerable so as to lead to one or more conclusions, and wherein each said question in said knowledge network is represented by one said node having a non-null question value in the question field of said node, and wherein each said conclusion in said knowledge network is represented by one said node.

7. The computer-based system of claim of 1, wherein the display label in the display field of at least one of said plurality of nodes depends at least on the value of the precondition expression field of said at least one of said plurality of nodes and on the value of the answer field of said at least one of said plurality of nodes.

8. The computer-based system of claim of 1 comprising a global clock for incrementally producing global clock ticks, wherein each said node comprises:

a precondition parents field for storing data representative of the identities of other said nodes having qualified answers upon which the value of the precondition expression of said node depends;

a delay field for storing a data representative of a first number of global clock ticks; and

wherein the display label in the display field of at least one of said plurality of nodes also depends on whether the precondition parents field of said at least one of said plurality of nodes stores data representative of the identities of other nodes having qualified answers upon which the value of the precondition expression of said node depends, or whether the delay field of said at least one of said plurality of nodes stores data representative of a positive number of global clock ticks.

9. The computer-based system of claim 1, wherein data stored in the contents field of each said node identifies a data storage location in an external memory storage device.

10. The computer-based system of claim 1, wherein at least one said node comprises:

a precondition children field for storing data representative of other said nodes each having a precondition expression whose value depends on the qualified answer of said node; and

an answer children field for storing data representative of other said nodes, each having an answer-formula whose value depends on the qualified answer of said node.

11. The computer-based system of claim 1, wherein at least one said node comprises:

a precondition parents field for storing data representative of other said nodes having qualified answers upon which the value of the precondition expression of said node depends; and

an answer parents field for storing data representative of other said nodes having qualified answers upon which the value of the answer-formula in said node depends.

12. The computer-based system of claim 1, wherein said programmed means comprises:

means for automatically updating the value of the qualified answer in the qualified answer field of said node when the value of the answer in the answer field or the value of the precondition expression of said node has been changed.

13. The computer-based system of claim 1, wherein said programmed means comprises:

means for automatically updating the value of the qualified answer in the qualified answer field of other said nodes when the value of the qualified answer in the qualified answer field of said node has been changed.

14. The computer-based system of claim 1, wherein said programmed means comprises:

means for automatically updating the value of the precondition expression in the precondition expression field of other said nodes when the value of the qualified answer in the qualified answer field of said node has been changed.

15. The computer-based system of claim 1 comprising a selectable writer mode of operation and a selectable reader mode of operation, wherein during said writer mode of operation a user can write said precondition expressions in the precondition expression field of said plurality of nodes, and write said questions in the question field of said plurality of nodes, and wherein during said reader mode of operation the user can read one or more of said questions from the question field of said nodes and write answers in the answer fields of said nodes.

16. The computer-based system of claim 1, wherein said programmed means comprises:

means for determining the answer values in the answer fields of some of said plurality of nodes, which cause at least a selected one of said nodes to have a predetermined value in the answer field, the qualified answer field, or the precondition expression field of said selected node.

17. The computer-based system of claim 16, wherein said predetermined value is TRUE.

18. The computer-based system of claim 16, wherein said predetermined value is FALSE.

19. The computer-based system of claim 1, wherein said plurality of nodes includes one or more nodes which are influential to other said nodes;

and

wherein said programmed means comprises means for analyzing the data fields of said plurality of nodes, and for identifying a set of influential nodes among said plurality of nodes.

20. The computer-based system of claim of 19, wherein the display label in the display field of at least one of said plurality of nodes depends at least on the value of the precondition expression field of said at least one of said plurality of nodes and also on whether said at least one of said plurality of nodes is identified as being an influential node among said plurality of nodes.

21. The computer-based system of claim 1, wherein each said node comprises a precondition flag field for storing data representative of a precondition flag at said node.

22. The computer-based system of claim 21, wherein said programmed means comprises:

means for automatically updating the value of the qualified answer in the qualified answer field of said node when the value of the answer in said answer field or the value of the precondition expression of said node has been changed.

23. The computer-based system of claim 21, wherein said programmed means comprises:

means for automatically updating the value of the qualified answer in the qualified answer field of other said nodes when the value of the qualified answer in the qualified answer field of said node has been changed.

24. The computer-based system of claim 21, wherein said programmed means comprises:

means for automatically updating the value of the precondition expression in the precondition expression field of other said nodes when the value of the qualified answer in the qualified answer field of said node has been changed.

25. The computer-based system of claim 21 comprising a global clock for incrementally producing global clock ticks, and wherein each said node comprises:

a delay field for storing a data representative of a first number of global clock ticks; and

a delay remaining field for storing data representative of a second number of global clock ticks.

26. The computer-based system of claim 25, wherein the value of the precondition flag in the precondition flag field of at least one said node depends on the value of the precondition expression in the precondition expression field of said node and the value of the delay remaining field of said node.