cfl_determin.h
Go to the documentation of this file.
1 /** @file cfl_determin.h powersetset construction */
2 
3 /* FAU Discrete Event Systems Library (libfaudes)
4 
5  Copyright (C) 2006 Bernd Opitz
6  Exclusive copyright is granted to Klaus Schmidt
7 
8  This library is free software; you can redistribute it and/or
9  modify it under the terms of the GNU Lesser General Public
10  License as published by the Free Software Foundation; either
11  version 2.1 of the License, or (at your option) any later version.
12 
13  This library is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16  Lesser General Public License for more details.
17 
18  You should have received a copy of the GNU Lesser General Public
19  License along with this library; if not, write to the Free Software
20  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
21 
22 
23 #ifndef FAUDES_DETERMIN_H
24 #define FAUDES_DETERMIN_H
25 
26 
27 #include "cfl_definitions.h"
28 #include "cfl_agenerator.h"
29 
30 namespace faudes {
31 
32 
33 /**
34  * Make initial states unique.
35  * If the argument generator has precisely one initial state, this function does nothing.
36  * Else, this function introduces a new and unique initial state and relinks transitions
37  * accordinly. If the argument generator used to have more than one initial state, this operation
38  * may render the output nondeterministic. If the argument generator used to have no
39  * initial state, the output generator will generate the empty string language as opposed to
40  * the empty language. Otherwise, generated and marked languages are preserved.
41  *
42  * Note: call this function followed by determine to convert the generator to a
43  * deterministic generator with exactly one initial state.
44  *
45  *
46  * @param rGen
47  * Reference to generator
48  *
49  * @ingroup GeneratorFunctions
50  */
51 extern FAUDES_API void UniqueInit(Generator& rGen);
52 
53 /**
54  * Make initial states unique.
55  *
56  * Convenience wrapper for UniqueInit(Generator&).
57  *
58  *
59  * @param rGen
60  * Reference to generator
61  * @param rResGen
62  * Reference to resulting generator
63  *
64  * @ingroup GeneratorFunctions
65  */
66 extern FAUDES_API void UniqueInit(const Generator& rGen, Generator& rResGen);
67 
68 
69 /**
70  * Make generator deterministic.
71  * Constructs a deterministic generator while preserving the generated and marked languages.
72  * The implementation is based on the so called multiway merge variant of subset construction,
73  * in which the new state set becomes a subset of the power set og the given state set. It is of
74  * exponential complexity. For details on the multiway merge algorithm see
75  * "Ted Leslie, Efficient Approaches to Subset Construction,
76  * Computer Science, University of Waterloo, 1995".
77  *
78  * See also
79  * Deterministic(const Generator&,std::map<Idx,StateSet>&,Generator& rResGen) and
80  * Deterministic(const Generator&,std::vector<StateSet>&,std::vector<Idx>&,Generator& rResGen).
81  *
82  * Technical detail: if the input has no initial state, then so has the output.
83  *
84  * @param rGen
85  * Reference to generator
86  * @param rResGen
87  * Reference to resulting deterministic generator
88  *
89  * <h4>Example:</h4>
90  * <table>
91  * <tr> <td> Generator G </td> <td> Deterministic(G,Result) </td> </tr>
92  * <tr>
93  * <td> @image html tmp_deterministic_nondet.png </td>
94  * <td> @image html tmp_deterministic_det.png </td>
95  * </tr>
96  * </table>
97  *
98  * @ingroup GeneratorFunctions
99  */
100 extern FAUDES_API void Deterministic(const Generator& rGen, Generator& rResGen);
101 
102 /**
103  * Make generator deterministic.
104  *
105  * See also Deterministic(const Generator&, Generator&).
106  * This version maintains event attributes provided they can be castes
107  * to the result type.
108  *
109  * @param rGen
110  * Reference to generator
111  * @param rResGen
112  * Reference to resulting deterministic generator
113  *
114  * @ingroup GeneratorFunctions
115  */
116 extern FAUDES_API void aDeterministic(const Generator& rGen, Generator& rResGen);
117 
118 /**
119  * Make generator deterministic.
120  *
121  * Constructs a deterministic generator while preserving the generated and marked languages.
122  * See Deterministic(const Generator&,Generator& rResGen) for the intended
123  * api. This version provides as a second parameter the resulting map from new states to
124  * their respective original state set. It is used as a so called "entry state map"
125  * for deterministic projected generators.
126  *
127  * @param rGen
128  * Reference to generator
129  * @param rEntryStatesMap
130  * Entry state map
131  * @param rResGen
132  * Reference to resulting deterministic generator
133  */
134 extern FAUDES_API void Deterministic(const Generator& rGen, std::map<Idx,StateSet>& rEntryStatesMap,
135  Generator& rResGen);
136 
137 /**
138  * Make generator deterministic.
139  *
140  * Constructs a deterministic generator while preserving the generated and marked languages.
141  * See Deterministic(const Generator&,Generator& rResGen) for the intended api.
142  * This version provides as second and third parameters the correspondence
143  * between new states and the original state sets.
144  * in vectors
145  *
146  * @param rGen
147  * Reference to generator
148  * @param rPowerStates
149  * Vector that holds the power states
150  * @param rDetStates
151  * Vector that holds the corresponding deterministic states
152  * @param rResGen
153  * Reference to resulting deterministic generator
154  */
155 extern FAUDES_API void Deterministic(const Generator& rGen, std::vector<StateSet>& rPowerStates,
156  std::vector<Idx>& rDetStates, Generator& rResGen);
157 
158 
159 
160 } // namespace faudes
161 
162 #endif
163 
Attributed generator class TaGenerator.
Compiletime options.
#define FAUDES_API
Interface export/import symbols: windows.
Definition: cfl_platform.h:80
vGenerator Generator
Plain generator, api typedef for generator with no attributes.
void UniqueInit(Generator &rGen)
Make initial states unique.
void Deterministic(const Generator &rGen, Generator &rResGen)
Make generator deterministic.
void aDeterministic(const Generator &rGen, Generator &rResGen)
Make generator deterministic.
libFAUDES resides within the namespace faudes.

libFAUDES 2.32f --- 2024.12.22 --- c++ api documentaion by doxygen