Patent US5136698A successfully refreshed from Google Patents.
US5136698A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for selective back-tracking in a hierarchical system containing a flag which indicates the validity of a choice-point
Assignee: Toshiba Corp
•
Filing: 1989-09-13
•
Granted: 1992-08-04
•
Expires: 2009-09-13
Abstract
Abstract A method of back-tracking in a computer processing operation in which the programmer can be provided with a number of different types of the back-track controlling, from which a suitable one can freely be selected in accordance with the need of the programmer. In this method, a flag is provided in each choice point, for indicating a type of back-track controlling, and a stack which contains an address of a choice point specified as a present choice point by a present choice point register and an address of a preceding choice point which is immediately preceding the present choice point is utilized in changing indication of the flag.
Inventors
- 👤 Toshio Okamoto
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 23:42
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/30; G06F8/31; G06F8/313; G06F8/3135
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
256 words
A computer implemented method of back-tracking in a computer processing operation, comprising the steps of: (a) for a predicate that is to be executed, creating a choice point containing: values of arguments of this predicate at a beginning of execution of this predicate; register values of registers necessary for carrying out back-tracking; and a flag indicating this choice point as either valid or invalid; (b) with respect to a certain choice point, creating a stack containing; an address of said certain choice point specified as a present choice point by a present choice point register; and an address of a preceding choice point which is immediately preceding the present choice point; (c) resetting the flag of a certain choice point from valid to invalid, or from invalid to valid, by using the address of the present choice point in the stack; (d) in back-tracking for a certain predicate, determining whether said certain predicate contains a flag which indicates that said certain predicate is valid or invalid; (e) for a certain predicate whose flag indicates that it is valid, back-tracking according to the register values of the registers in the present choice point; (f) for a certain predicate whose flag indicates that it is invalid, resetting a register value of the present choice point register from a location of the present choice point to a location of a nearest valid choice point superior to the choice point corresponding to that predicate; and back-tracking according to the register values of the registers in the nearest valid choice point.
Claim 2
Dependent Claim
256 words
A computer implemented method of back-tracking in a computer processing operation, comprising the steps of: (a) for a predicate that is to be executed, creating a choice point containing: values of arguments of this predicate at a beginning of execution of this predicate; register values of registers necessary for carrying out back-tracking; and a flag indicating this choice point as either valid or invalid; (b) with respect to a certain choice point, creating a stack containing; an address of said certain choice point specified as a present choice point by a present choice point register; and an address of a preceding choice point which is immediately preceding the present choice point; (c) resetting the flag of a certain choice point from valid to invalid, or from invalid to valid, by using the address of the present choice point in the stack; (d) in back-tracking for a certain predicate, determining whether said certain predicate contains a flag which indicates that said certain predicate is valid or invalid; (e) for a certain predicate whose flag indicates that it is valid, back-tracking according to the register values of the registers in the present choice point; (f) for a certain predicate whose flag indicates that it is invalid, resetting a register value of the present choice point register from a location of the present choice point to a location of a nearest valid choice point superior to the choice point corresponding to that predicate; and back-tracking according to the register values of the registers in the nearest valid choice point.
Claim 3
Dependent Claim
68 words
The method of claim 1, wherein the computer processing operation is performed under a program written in a logic type language, and wherein the step (b) is performed in response to a presence of a particular operator in the program, the particular operator having two distinctive and interchangeable types, while the step (c) is performed in response to a type of the particular operator present in the program.
Claim 4
Dependent Claim
50 words
The method of claim 1, wherein register values of registers contained in each choice point include a register value of a register indicating a location of an alternative predicate to be attempted in a back-tracking, and a register value of a register indicating a location of the preceding choice point.
Claim 5
Dependent Claim
44 words
The method of claim 1, wherein the computer processing operation further utilizes an environment containing permanent variables for each clause to be executed, and wherein the stack is created such that when the back-tracking starts, the stack is located adjacent to a newest environment.
Claim 6
Dependent Claim
220 words
A computer implemented method of back-tracking in a computer processing operation, comprising the steps of: (a) for a predicate that is to be executed, creating a choice point containing: values of arguments of this predicate at a beginning of execution of this predicate; register values of registers necessary for carrying out back-tracking; and a flag indicating some integer value; (b) with respect to a certain choice point, creating a stack containing; an address of said certain choice point specified as a present choice point by a present choice point register; and an address of a preceding choice point which is immediately preceding the present choice point; (c) changing the flag of a certain choice point from one integer value to another integer value, by using the address of the present choice point in the stack; (d) in back-tracking for a certain predicate, determining whether said certain predicate contains a flag which indicates an integer n; (e) for a certain predicate whose flag indicates an integer n, resetting a register value of the present choice point register from a location of the present choice point to a location of an n-th nearest valid choice point superior to the choice point corresponding to that predicate; and back-tracking according to the register values of the registers in the n-th nearest valid choice point.
Claim 7
Dependent Claim
220 words
A computer implemented method of back-tracking in a computer processing operation, comprising the steps of: (a) for a predicate that is to be executed, creating a choice point containing: values of arguments of this predicate at a beginning of execution of this predicate; register values of registers necessary for carrying out back-tracking; and a flag indicating some integer value; (b) with respect to a certain choice point, creating a stack containing; an address of said certain choice point specified as a present choice point by a present choice point register; and an address of a preceding choice point which is immediately preceding the present choice point; (c) changing the flag of a certain choice point from one integer value to another integer value, by using the address of the present choice point in the stack; (d) in back-tracking for a certain predicate, determining whether said certain predicate contains a flag which indicates an integer n; (e) for a certain predicate whose flag indicates an integer n, resetting a register value of the present choice point register from a location of the present choice point to a location of an n-th nearest valid choice point superior to the choice point corresponding to that predicate; and back-tracking according to the register values of the registers in the n-th nearest valid choice point.
Claim 8
Dependent Claim
73 words
The method of claim 5, wherein the computer processing operation is performed under a program written in a logic type language, and wherein the step (b) is performed in response to a presence of a particular operator in the program, the particular operator having n distinctive and interchangeable types where n is an integer, while the step (c) is performed in response to a type of the particular operator present in the program.
Claim 9
Dependent Claim
50 words
The method of claim 5, wherein register values of registers contained in each choice point include a register value of a register indicating a location of an alternative predicate to be attempted in a back-tracking, and a register value of a register indicating a location of the preceding choice point.
Claim 10
Dependent Claim
44 words
The method of claim 5, wherein the computer processing operation further utilizes an environment containing permanent variables for each clause to be executed, and wherein the stack is created such that when the back-tracking starts, the stack is located adjacent to a newest environment.
References Cited (Backward Citations)
US5016164A
Cited
US4931931A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-08-04 | 1996-02-03 | 1996-08-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-08-04 | 2000-02-03 | 2000-08-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-08-04 | 2004-02-03 | 2004-08-04 | $7700.00 | Window Closed / Lapsed |