Machine


1   /* $Id: Machine.java,v 1.2 2004/05/20 14:23:53 bures Exp $ */
2   
3   package SOFA.SOFAnode.Util;
4   
5   import java.util.Collection  ;
6   import java.util.Hashtable  ;
7   
8   /**
9    * The interface for creating and transforming the finite-state acceptor.
10   * The state space is represented by an array of states, for each state 
11   * by an array of all action tokens being used. For each pair state,token
12   * there is a reference to the IntVector of states being the targets of
13   * edges from the state by the transition.
14   *
15   * @author  Stanislav Visnovsky
16   * @version     1.5.0
17   * @see     IntVector
18  */
19  interface Machine {
20  
21  /**
22   * Adds new states to the automaton. Each state is represented by the corresponding
23   * representation. Method returns the mapping for transforming indices in 
24   * array of added states, to the new state ids.
25   *
26   * @author  Stanislav Visnovsky
27   * @version     2.0.0
28   * @param n an array of new states to be added
29   * @param size  length of  added array
30  */
31      int[] AddStates( IntVector n[][], int size );
32  
33  /**
34   * Reduces the automaton, that all equivalent states are represented as only one state.
35   *
36   * @author  Stanislav Visnovsky
37   * @version     1.0.0
38  */
39      void Reduce();
40  
41  /**                 
42   * Transforms the automaton to a deterministic one.
43   *
44   * Optimized by Vladimir Mencl
45   *
46   * @author      Vladimir Mencl
47   * @version     2.0.0
48   */                  
49  
50      void Determinize();
51  
52  /**
53   * Eliminates all unreachable states.
54   *
55   * @author  Stanislav Visnovsky
56   * @version     1.0.0
57  */
58      void Reachable();
59  
60  /**
61   * Restrict the automaton by the set passed as the argument.
62   *
63   * @author  Stanislav Visnovsky
64   * @version     2.0.0
65   * @param restrict  the set of action tokens to be eliminated
66  */
67      void Restrict( ActionTokenArray restrict );
68  
69  /**
70   * Restrict the automaton to non-update behavior only.
71   *
72   * @author  Stanislav Visnovsky
73   * @version     1.0.0
74  */
75      void NonUpdateOnly();
76  
77  /**
78   * Restrict the automaton to update behavior only.
79   *
80   * @author  Stanislav Visnovsky
81   * @version     1.0.0
82  */
83      void UpdateOnly();
84  
85  /**
86   * Restrict the automaton to update behavior only and remove [UPDATE] events at the end
87   * of the traces.
88   *
89   * @author  Stanislav Visnovsky
90   * @version     1.0.0
91  */
92      void StrippedUpdateOnly();
93  
94  /**
95   * Query the automaton, whether its language is included in the automaton
96   * given as the argument. It returns the counterexample in case of failure.
97   *
98   * @author  Stanislav Visnovsky
99   * @version     2.0.0
100  * @param m the automaton to be compared
101  * @return  string with counterexample, null for success
102 */
103     String   isIncludedIn( Machine m );
104 
105 /**
106  * Returns the starting state of the automaton.
107  *
108  * @author  Stanislav Visnovsky
109  * @version     1.0.0
110  * @return  the starting state
111 */
112     int Start();
113 
114 /**
115  * Returns the hashtable of accepting states of automaton. The keys and the values
116  * are Integer instances with the indices.
117  *
118  * @author  Stanislav Visnovsky
119  * @version     2.0.0
120  * @return  the hashtable of states
121 */
122     Hashtable   Stop();
123 
124 /**
125  * Returns the hashtable of update states of automaton. The keys and the values
126  * are Integer instances with the indices.
127  *
128  * @author  Stanislav Visnovsky
129  * @version     2.0.0
130  * @return  the hashtable of states
131 */
132     Hashtable   Update();
133 
134 /**
135  * Sets a new starting state of the automaton.
136  *
137  * @author  Stanislav Visnovsky
138  * @version     1.0.0
139  * @param n the new starting state
140 */
141     void SetStart( int n );
142 
143 /**
144  * Adds a new accepting state of the automaton.Returns the target of this edge.
145  *
146  * @author  Stanislav Visnovsky
147  * @version     1.0.0
148  * @param n the new accepting state
149 */
150     void AddStop( int n );
151 
152 /**
153  * Adds a new state to the automaton. Returns the index of the new state.
154  *
155  * @author  Stanislav Visnovsky
156  * @version     2.0.0
157  * @return  the new accepting state
158 */
159     int addState();
160 
161 /**
162  * Adds a collection of new accepting states of the automaton.
163  *
164  * @author  Stanislav Visnovsky
165  * @version     1.0.0
166  * @param n a list of new accepting states
167 */
168     void AddStops( Collection   n );
169 
170 /**
171  * Sets the accepting states to none.
172  *
173  * @author  Stanislav Visnovsky
174  * @version     2.0.0
175 */
176     void ClearStops();
177 
178 /**
179  * Adds a new edge.
180  *
181  * @author  Stanislav Visnovsky
182  * @version     2.0.0
183  * @param from  index of a state which the edge leads from
184  * @param transition    index of an edge identification
185  * @param to    index of a state which the edge leads to
186 */
187     void addEdge( int from, int transition, int to );
188     
189 /**
190  * Adds a new edge from the given state to the update state.
191  *
192  * @author  Stanislav Visnovsky
193  * @version     2.0.0
194  * @param from  index of a state which the edge leads from
195 */
196     void addUpdateEdge( int from );
197 
198 /**
199  * Adds all edges of state from to the state to. Effectively merges all edges.
200  *
201  * @author  Stanislav Visnovsky
202  * @version     2.0.0
203  * @param from  index of state, which should be enhanced by edges
204  * @param to    index of state from which to take the edges
205 */
206     void Merge( int to, int from  );
207 
208 /**
209  * Checks, whether there is enough state space given as a parameter. In case of
210  * failure, it reallocates to the new size. It does not reduce the size.
211  *
212  * @author  Stanislav Visnovsky
213  * @version     2.0.0
214  * @param required  required number of states
215 */
216     void checkSpace( int required );
217 
218 /**
219  * Minimizes the machine to the reduced deterministic form.
220  *
221  * @author  Stanislav Visnovsky
222  * @version     2.0.0
223 */
224     void Minimize();
225 }
226
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags