Data processing: software development – installation – and managem – Software program development tool – Testing or debugging
Reexamination Certificate
1999-12-17
2004-03-16
Nguyen-Ba, Hoang-Vu Antony (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Testing or debugging
C703S017000, C709S241000, C714S038110
Reexamination Certificate
active
06708328
ABSTRACT:
TECHNICAL FIELD
This invention relates generally to analysis of systems and more particularly to analysis of a partial state space that represents information for part of a system.
BACKGROUND OF THE INVENTION
To perform analysis of a system such as a computer system, one typically employs a description of the system. This system description, in one example, comprises a program such as a computer program, or an implementation of a design in a computer language or notation.
A number of techniques exist for employing the system description to obtain a state space that can be used in analyzing the system. This state space includes a description of a particular state of the system. One typically wishes that the state space also include a number of next states for the system. The accuracy of this information regarding a next state for the system, usually. depends on the accuracy of the representation of the present state of the system, as will be understood by those skilled in the art.
In one example, the state space comprises a graph. The graph typically includes an initial state. One commonly builds the graph, with employment of the description of the system, by exploring the next states that are reachable from the initial state. This process usually continues until the graph comprises every next state that one can reach. So, the process assumes that sufficient storage space will be available to hold a description of every state.
However, one can consider a description of a system that would require more space than is available in storage. The description could be larger than the available space in, for example, a data structure that is intended to store the description.
In one example, a given data structure has space sufficient to hold a description of a first system having, for instance, ten million states. One can also consider a description of a second system that has twenty billion states. The challenge remains of how to employ the given data structure to represent the description of the second system in view of the space limitations of the given data structure.
In this regard, one existing design simply cuts off the building of the state space upon reaching the limit of available memory. This cutting off affects at least one node in the graph by incompletely representing all possible transitions from that node. A shortcoming of such a cutoff technique in building the state space, is a possible inaccuracy in analysis of the system.
Should one wish to employ the state space to determine whether a condition such as a loop or deadlock exists in the system, the analysis could output an inaccurate answer. As one example, the analysis may reach a tentative conclusion that no, loop exists. Nevertheless, the analysis cannot definitively state, on the basis of an evaluation of the node affected by the cutoff, that no loop exists in the system, since data related to at least one transition from the node is not represented in the state space.
Thus, a need exists for employment of a value; in a state space that can be used for analysis of a system which is incompletely described in the state space.
SUMMARY OF THE INVENTION
Pursuant to the present invention, shortcomings of the existing art are overcome and additional advantages are provided through the provision of employment of a value of unknown in a portion of a partial state space for analysis of part of a system.
The invention in one embodiment encompasses a method for analyzing a portion of a partial state space, with the portion of the partial state space related to a part of a system. There is received an analysis question that is related to the part of the system. There is employed a value of unknown of the portion of the partial state space to analyze, in response to the analysis question, the portion of the partial state space.
Another embodiment of the invention encompasses a first system for analysis of a portion of a partial state space, with the portion of the partial state space related to a part of a second system. The first system includes a representation component and an analysis component. The representation component employs a value in the portion of the partial state space to represent that information for the part of the second system is unknown. The analysis component employs the value to analyze, in response to an analysis question that is related to the part of the second system, the portion of the partial state space.
A further embodiment of the invention encompasses an article of manufacture. At least one computer usable medium has computer readable program code means embodied therein for causing analysis of a portion of a partial state space, with the portion of the partial state space related to a part of a system. There is provided computer readable program means for causing a computer to receive an analysis question that is related to the part of the system. There is also provided computer readable program code means for causing a computer to employ a value of unknown of the portion of the partial state space to analyze, in response to the analysis question, the portion of the partial state space.
REFERENCES:
patent: 3976864 (1976-08-01), Gordon et al.
patent: 4224534 (1980-09-01), Gordon
patent: 5764883 (1998-06-01), Satterfield et al.
patent: 6141633 (2000-10-01), Iwashita et al.
patent: 6324496 (2001-11-01), Alur et al.
Akama, Many-valued and Annoted Modal Logics, May 1998, Proceedings of the 28thIE International Symposium on Multiple-Vlaued Logic, 114-119.*
De Schutter-De Moor, State Space Transformations and State Space Realization in the Max Algebra, 12V/1995, IEEE, Proceedings of the 34thConference on Decision & Control.*
Verlind et al., A Time Abstraction Method for Efficient Verification of Communicating Systems, Jun. 1994, 31stACM/IEEE Design Automation Conference.*
Bruns, Glenn; Godefroid, Patrice; “Model Checking Partial State Spaces with 3-Valued Temporal Logics,” Computer Aided Verification Undated.
Bruns Glenn R.
Godefroid Patrice Ismael
Lucent Technologies - Inc.
Nguyen-Ba Hoang-Vu Antony
LandOfFree
Employment of value of unknown in portion of partial state... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Employment of value of unknown in portion of partial state..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Employment of value of unknown in portion of partial state... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3210823