Automatically generating a program
First Claim
1. A method for automatically generating a state-based program for a component of a system consisting of a plurality of components communicating with each other, wherein said program is generated from a specification of said system, said specification comprising interaction-based sequence descriptions of said system, said method comprising the steps of:
- a) determining all sequence descriptions of said component defined by said specification of said system, b) normalizing said sequence descriptions of said component such that a normalized sequence description comprises exactly one initial condition and exactly one final condition and, between said initial condition and said final condition, communication actions only, c) determining a state-based specification of said component by identifying all equal initial and final conditions of said normalized sequence descriptions of said component with a single state, and d) determining said state-based program for said component, wherein each sequence description contained in said state-based specification of said component is replaced by a sequence of said communication actions of this sequence description, separated by additionally inserted states.
0 Assignments
0 Petitions
Accused Products
Abstract
A method, an apparatus and a computer program product are described for automatically generating a state-based program for a component of a system consisting of a plurality of components communicating with each other, wherein the program is generated from a specification of the system, the specification comprising interaction-based sequence descriptions of the system. According to the present invention, all sequence descriptions of said component are determined, the sequence descriptions are normalized, a state-based specification of said component is determined from the normalized sequence descriptions, and the state-based program for the component is determined from the state-based specification. The present invention facilitates the process of program development since the costly, manual development of a state-based program from the specification of a system is automated at least to a substantial degree.
129 Citations
20 Claims
-
1. A method for automatically generating a state-based program for a component of a system consisting of a plurality of components communicating with each other, wherein said program is generated from a specification of said system, said specification comprising interaction-based sequence descriptions of said system, said method comprising the steps of:
-
a) determining all sequence descriptions of said component defined by said specification of said system, b) normalizing said sequence descriptions of said component such that a normalized sequence description comprises exactly one initial condition and exactly one final condition and, between said initial condition and said final condition, communication actions only, c) determining a state-based specification of said component by identifying all equal initial and final conditions of said normalized sequence descriptions of said component with a single state, and d) determining said state-based program for said component, wherein each sequence description contained in said state-based specification of said component is replaced by a sequence of said communication actions of this sequence description, separated by additionally inserted states. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
b1) inserting a condition prescribed in said specification of said system as an initial condition into each of those sequence descriptions of said component that begin with a communication action, b2) inserting a condition prescribed in said specification of said system as a final condition into each of those sequence descriptions of said component that end with a communication action, and b3) splitting all sequence descriptions of said component having more than two conditions into a plurality of sequence descriptions of said component, each of the split sequence descriptions having exactly two conditions.
-
-
4. The method of claim 3, wherein at least one of sub-steps b1) and b2) is/are repeated for each of a plurality of conditions to be inserted in order to obtain a corresponding number of sequence descriptions of said component.
-
5. The method of claim 1, wherein said interaction-based sequence descriptions of said system are represented by at least one of Message Sequence Charts and UML sequence diagrams.
-
6. The method of claim 1, wherein said state-based program for said component is represented by an automaton.
-
7. The method of claim 6, wherein said automaton is one of an SDL automaton and a Statechart automaton and a ROOM automaton.
-
8. The method of claim 1, wherein said state-based program is based on an extended state automaton whose state space comprises a control state and a data state, and wherein state transitions are performed depending on the current data state and are adapted to change this data state.
-
9. The method of claim 1, wherein step d) comprises the step of removing ε
- -transitions from said state-based program.
-
10. The method of claim 1, wherein a deterministic state-based program is generated in step d).
-
11. The method of claim 1, further including a step of optimizing said state-based program generated in step d).
-
12. The method of claim 11, wherein the optimization is performed with respect to the number of states.
-
13. The method of claim 1, wherein non-local conditions in said sequence descriptions of said system are replaced in step a) by local conditions in accordance with a predetermined surjective mapping.
-
14. The method of claim 1, wherein the method is used for at least one of generating a state-based program for a telecommunication application and generating a state-based program for providing an error tolerant communication of data and generating a state-based program for providing an error tolerant communication of messages and generating a state-based program for a reactive system and generating a state-based program for a control system and generating a user interface program and generating a data base query schema program.
-
15. An apparatus for automatically generating a state-based program for a component of a system consisting of a plurality of components communicating with each other, wherein said program is generated from a specification of said system, said specification comprising interaction-based sequence descriptions of said system, said apparatus comprising a general purpose computer programmed for executing the steps of:
-
a) determining all sequence descriptions of said component defined by said specification of said system, b) normalizing said sequence descriptions of said component such that a normalized sequence description comprises exactly one initial condition and exactly one final condition and, between said initial condition and said final condition, communication actions only, c) determining a state-based specification of said component by identifying all equal initial and final conditions of said normalized sequence descriptions of said component with a single state, and d) determining said state-based program for said component, wherein each sequence description contained in said state-based specification of said component is replaced by a sequence of said communication actions of this sequence description, separated by additionally inserted states. - View Dependent Claims (16, 17)
b1) inserting a condition prescribed in said specification of said system as an initial condition into each of those sequence descriptions of said component that begin with a communication action, b2) inserting a condition prescribed in said specification of said system as a final condition into each of those sequence descriptions of said component that end with a communication action, and b3) splitting all sequence descriptions of said component having more than two conditions into a plurality of sequence descriptions of said component, each of the split sequence descriptions having exactly two conditions.
-
-
17. The apparatus of claim 15, wherein said apparatus is used for at least one of generating a state-based program for a telecommunication application and generating a state-based program for providing an error tolerant communication of data and generating a state-based program for providing an error tolerant communication of messages and generating a state-based program for a reactive system and generating a state-based program for a control system and generating a user interface program and generating a data base query schema program.
-
18. A computer program product for execution by a general purpose computer for automatically generating a state-based program for a component of a system consisting of a plurality of components communicating with each other, wherein said program is generated from a specification of said system, said specification comprising interaction-based sequence descriptions of said system, said computer program product including instructions for making said general purpose computer perform the steps of:
-
a) determining all sequence descriptions of said component defined by said specification of said system, b) normalizing said sequence descriptions of said component such that a normalized sequence description comprises exactly one initial condition and exactly one final condition and, between said initial condition and said final condition, communication actions only, c) determining a state-based specification of said component by identifying all equal initial and final conditions of said normalized sequence descriptions of said component with a single state, and d) determining said state-based program for said component, wherein each sequence description contained in said state-based specification of said component is replaced by a sequence of said communication actions of this sequence description, separated by additionally inserted states. - View Dependent Claims (19, 20)
b1) inserting a condition prescribed in said specification of said system as an initial condition into each of those sequence descriptions of said component that begin with a communication action, b2) inserting a condition prescribed in said specification of said system as a final condition into each of those sequence descriptions of said component that end with a communication action, and b3) splitting all sequence descriptions of said component having more than two conditions into a plurality of sequence descriptions of said component, each of the split sequence descriptions having exactly two conditions.
-
-
20. The computer program product of claim 18, said computer program product being used for at least one of generating a state-based program for a telecommunication application and generating a state-based program for providing an error tolerant communication of data and generating a state-based program for providing an error tolerant communication of messages and generating a state-based program for a reactive system and generating a state-based program for a control system and generating a user interface program and generating a data base query schema program.
Specification