1 // properties.h 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // \file 16 // FST property bits. 17 18 #ifndef FST_LIB_PROPERTIES_H__ 19 #define FST_LIB_PROPERTIES_H__ 20 21 #include "fst/lib/compat.h" 22 23 namespace fst { 24 25 // The property bits here assert facts about an FST. If individual 26 // bits are added, then the composite properties below, the property 27 // functions and property names in properties.cc, and 28 // TestProperties() in test-properties.h should be updated. 29 30 // 31 // BINARY PROPERTIES 32 // 33 // For each property below, there is a single bit. If it is set, 34 // the property is true. If it is not set, the property is false. 35 // 36 37 // The Fst is an ExpandedFst 38 const uint64 kExpanded = 0x0000000000000001ULL; 39 40 // The Fst is a MutableFst 41 const uint64 kMutable = 0x0000000000000002ULL; 42 43 // 44 // TRINARY PROPERTIES 45 // 46 // For each of these properties below there is a pair of property bits 47 // - one positive and one negative. If the positive bit is set, the 48 // property is true. If the negative bit is set, the property is 49 // false. If neither is set, the property has unknown value. Both 50 // should never be simultaneously set. The individual positive and 51 // negative bit pairs should be adjacent with the positive bit 52 // at an odd and lower position. 53 54 // ilabel == olabel for each arc 55 const uint64 kAcceptor = 0x0000000000010000ULL; 56 // ilabel != olabel for some arc 57 const uint64 kNotAcceptor = 0x0000000000020000ULL; 58 59 // ilabels unique leaving each state 60 const uint64 kIDeterministic = 0x0000000000040000ULL; 61 // ilabels not unique leaving some state 62 const uint64 kNonIDeterministic = 0x0000000000080000ULL; 63 64 // olabels unique leaving each state 65 const uint64 kODeterministic = 0x0000000000100000ULL; 66 // olabels not unique leaving some state 67 const uint64 kNonODeterministic = 0x0000000000200000ULL; 68 69 // FST has input/output epsilons 70 const uint64 kEpsilons = 0x0000000000400000ULL; 71 // FST has no input/output epsilons 72 const uint64 kNoEpsilons = 0x0000000000800000ULL; 73 74 // FST has input epsilons 75 const uint64 kIEpsilons = 0x0000000001000000ULL; 76 // FST has no input epsilons 77 const uint64 kNoIEpsilons = 0x0000000002000000ULL; 78 79 // FST has output epsilons 80 const uint64 kOEpsilons = 0x0000000004000000ULL; 81 // FST has no output epsilons 82 const uint64 kNoOEpsilons = 0x0000000008000000ULL; 83 84 // ilabels sorted wrt < for each state 85 const uint64 kILabelSorted = 0x0000000010000000ULL; 86 // ilabels not sorted wrt < for some state 87 const uint64 kNotILabelSorted = 0x0000000020000000ULL; 88 89 // olabels sorted wrt < for each state 90 const uint64 kOLabelSorted = 0x0000000040000000ULL; 91 // olabels not sorted wrt < for some state 92 const uint64 kNotOLabelSorted = 0x0000000080000000ULL; 93 94 // Non-trivial arc or final weights 95 const uint64 kWeighted = 0x0000000100000000ULL; 96 // Only trivial arc and final weights 97 const uint64 kUnweighted = 0x0000000200000000ULL; 98 99 // FST has cycles 100 const uint64 kCyclic = 0x0000000400000000ULL; 101 // FST has no cycles 102 const uint64 kAcyclic = 0x0000000800000000ULL; 103 104 // FST has cycles containing the initial state 105 const uint64 kInitialCyclic = 0x0000001000000000ULL; 106 // FST has no cycles containing the initial state 107 const uint64 kInitialAcyclic = 0x0000002000000000ULL; 108 109 // FST is topologically sorted 110 const uint64 kTopSorted = 0x0000004000000000ULL; 111 // FST is not topologically sorted 112 const uint64 kNotTopSorted = 0x0000008000000000ULL; 113 114 // All states reachable from the initial state 115 const uint64 kAccessible = 0x0000010000000000ULL; 116 // Not all states reachable from the initial state 117 const uint64 kNotAccessible = 0x0000020000000000ULL; 118 119 // All states can reach a final state 120 const uint64 kCoAccessible = 0x0000040000000000ULL; 121 // Not all states can reach a final state 122 const uint64 kNotCoAccessible = 0x0000080000000000ULL; 123 124 // If NumStates() > 0, then state 0 is initial, state NumStates()-1 is 125 // final, there is a transition from each non-final state i to 126 // state i+1, and there are no other transitions. 127 const uint64 kString = 0x0000100000000000ULL; 128 129 // Not a string FST 130 const uint64 kNotString = 0x0000200000000000ULL; 131 132 // 133 // COMPOSITE PROPERTIES 134 // 135 136 // Properties of an empty machine 137 138 const uint64 kNullProperties 139 = kAcceptor | kIDeterministic | kODeterministic | kNoEpsilons | 140 kNoIEpsilons | kNoOEpsilons | kILabelSorted | kOLabelSorted | 141 kUnweighted | kAcyclic | kInitialAcyclic | kTopSorted | 142 kAccessible | kCoAccessible | kString; 143 144 // Properties that are preserved when an FST is copied 145 const uint64 kCopyProperties 146 = kAcceptor | kNotAcceptor | kIDeterministic | kNonIDeterministic | 147 kODeterministic | kNonODeterministic | kEpsilons | kNoEpsilons | 148 kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons | 149 kILabelSorted | kNotILabelSorted | kOLabelSorted | 150 kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic | 151 kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted | 152 kAccessible | kNotAccessible | kCoAccessible | kNotCoAccessible | 153 kString | kNotString; 154 155 // Properties that are preserved when an FST start state is set 156 const uint64 kSetStartProperties 157 = kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic | 158 kNonIDeterministic | kODeterministic | kNonODeterministic | 159 kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | 160 kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted | 161 kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic | 162 kTopSorted | kNotTopSorted | kCoAccessible | kNotCoAccessible; 163 164 // Properties that are preserved when an FST final weight is set 165 const uint64 kSetFinalProperties 166 = kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic | 167 kNonIDeterministic | kODeterministic | kNonODeterministic | 168 kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | 169 kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted | 170 kNotOLabelSorted | kCyclic | kAcyclic | kInitialCyclic | 171 kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible | 172 kNotAccessible; 173 174 // Properties that are preserved when an FST state is added 175 const uint64 kAddStateProperties 176 = kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic | 177 kNonIDeterministic | kODeterministic | kNonODeterministic | 178 kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | 179 kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted | 180 kNotOLabelSorted | kWeighted | kUnweighted | kCyclic | kAcyclic | 181 kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted | 182 kNotAccessible | kNotCoAccessible | kNotString; 183 184 // Properties that are preserved when an FST arc is added 185 const uint64 kAddArcProperties = kExpanded | kMutable | kNotAcceptor | 186 kNonIDeterministic | kNonODeterministic | kEpsilons | kIEpsilons | 187 kOEpsilons | kNotILabelSorted | kNotOLabelSorted | kWeighted | 188 kCyclic | kInitialCyclic | kNotTopSorted | kAccessible | kCoAccessible; 189 190 // Properties that are preserved when an FST arc is set 191 const uint64 kSetArcProperties = kExpanded | kMutable; 192 193 // Properties that are preserved when FST states are deleted 194 const uint64 kDeleteStatesProperties 195 = kExpanded | kMutable | kAcceptor | kIDeterministic | 196 kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons | 197 kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic | 198 kInitialAcyclic | kTopSorted; 199 200 // Properties that are preserved when FST arcs are deleted 201 const uint64 kDeleteArcsProperties 202 = kExpanded | kMutable | kAcceptor | kIDeterministic | 203 kODeterministic | kNoEpsilons | kNoIEpsilons | kNoOEpsilons | 204 kILabelSorted | kOLabelSorted | kUnweighted | kAcyclic | 205 kInitialAcyclic | kTopSorted | kNotAccessible | kNotCoAccessible; 206 207 // Properties that are preserved when an FST's states are reordered 208 const uint64 kStateSortProperties = kExpanded | kMutable | kAcceptor | 209 kNotAcceptor | kIDeterministic | kNonIDeterministic | 210 kODeterministic | kNonODeterministic | kEpsilons | kNoEpsilons | 211 kIEpsilons | kNoIEpsilons | kOEpsilons | kNoOEpsilons | 212 kILabelSorted | kNotILabelSorted | kOLabelSorted | kNotOLabelSorted 213 | kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic | 214 kInitialAcyclic | kAccessible | kNotAccessible | kCoAccessible | 215 kNotCoAccessible; 216 217 // Properties that are preserved when an FST's arcs are reordered 218 const uint64 kArcSortProperties = 219 kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic | 220 kNonIDeterministic | kODeterministic | kNonODeterministic | 221 kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | 222 kNoOEpsilons | kWeighted | kUnweighted | kCyclic | kAcyclic | 223 kInitialCyclic | kInitialAcyclic | kTopSorted | kNotTopSorted | 224 kAccessible | kNotAccessible | kCoAccessible | kNotCoAccessible | 225 kString | kNotString; 226 227 // Properties that are preserved when an FST's input labels are changed. 228 const uint64 kILabelInvariantProperties = 229 kExpanded | kMutable | kODeterministic | kNonODeterministic | 230 kOEpsilons | kNoOEpsilons | kOLabelSorted | kNotOLabelSorted | 231 kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic | 232 kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible | 233 kNotAccessible | kCoAccessible | kNotCoAccessible | kString | kNotString; 234 235 // Properties that are preserved when an FST's output labels are changed. 236 const uint64 kOLabelInvariantProperties = 237 kExpanded | kMutable | kIDeterministic | kNonIDeterministic | 238 kIEpsilons | kNoIEpsilons | kILabelSorted | kNotILabelSorted | 239 kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic | 240 kInitialAcyclic | kTopSorted | kNotTopSorted | kAccessible | 241 kNotAccessible | kCoAccessible | kNotCoAccessible | kString | kNotString; 242 243 // Properties that are preserved when an FST's weights are changed. 244 // This assumes that the set of states that are non-final is not changed. 245 const uint64 kWeightInvariantProperties = 246 kExpanded | kMutable | kAcceptor | kNotAcceptor | kIDeterministic | 247 kNonIDeterministic | kODeterministic | kNonODeterministic | 248 kEpsilons | kNoEpsilons | kIEpsilons | kNoIEpsilons | kOEpsilons | 249 kNoOEpsilons | kILabelSorted | kNotILabelSorted | kOLabelSorted | 250 kNotOLabelSorted | kCyclic | kAcyclic | kInitialCyclic | kInitialAcyclic | 251 kTopSorted | kNotTopSorted | kAccessible | kNotAccessible | kCoAccessible | 252 kNotCoAccessible | kString | kNotString; 253 254 // Properties that are preserved when a superfinal state is added 255 // and an FSTs final weights are directed to it via new transitions. 256 const uint64 kAddSuperFinalProperties = kExpanded | kMutable | kAcceptor | 257 kNotAcceptor | kNonIDeterministic | kNonODeterministic | kEpsilons | 258 kIEpsilons | kOEpsilons | kNotILabelSorted | kNotOLabelSorted | 259 kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic | 260 kInitialAcyclic | kNotTopSorted | kNotAccessible | kCoAccessible | 261 kNotCoAccessible | kNotString; 262 263 // Properties that are preserved when a superfinal state is removed 264 // and the epsilon transitions directed to it are made final weights. 265 const uint64 kRmSuperFinalProperties = kExpanded | kMutable | kAcceptor | 266 kNotAcceptor | kIDeterministic | kODeterministic | kNoEpsilons | 267 kNoIEpsilons | kNoOEpsilons | kILabelSorted | kOLabelSorted | 268 kWeighted | kUnweighted | kCyclic | kAcyclic | kInitialCyclic | 269 kInitialAcyclic | kTopSorted | kAccessible | kCoAccessible | 270 kNotCoAccessible | kString; 271 272 // All binary properties 273 const uint64 kBinaryProperties = 0x0000000000000003ULL; 274 275 // All trinary properties 276 const uint64 kTrinaryProperties = 0x00003fffffff0000ULL; 277 278 // 279 // COMPUTED PROPERTIES 280 // 281 282 // 1st bit of trinary properties 283 const uint64 kPosTrinaryProperties = 284 kTrinaryProperties & 0x5555555555555555ULL; 285 286 // 2nd bit of trinary properties 287 const uint64 kNegTrinaryProperties = 288 kTrinaryProperties & 0xaaaaaaaaaaaaaaaaULL; 289 290 // All properties 291 const uint64 kFstProperties = kBinaryProperties | kTrinaryProperties; 292 293 // 294 // PROPERTY FUNCTIONS and STRING NAMES (defined in properties.cc) 295 // 296 297 uint64 ClosureProperties(uint64 inprops, bool star, bool delayed = false); 298 uint64 ComplementProperties(uint64 inprops); 299 uint64 ComposeProperties(uint64 inprops1, uint64 inprops2); 300 uint64 ConcatProperties(uint64 inprops1, uint64 inprops2, 301 bool delayed = false); 302 uint64 DeterminizeProperties(uint64 inprops); 303 uint64 DifferenceProperties(uint64 inprops1, uint64 inprops2); 304 uint64 FactorWeightProperties(uint64 inprops); 305 uint64 IntersectProperties(uint64 inprops1, uint64 inprops2); 306 uint64 InvertProperties(uint64 inprops); 307 uint64 ProjectProperties(uint64 inprops, bool project_input); 308 uint64 RelabelProperties(uint64 inprops); 309 uint64 ReplaceProperties(const vector<uint64>& inprops); 310 uint64 ReverseProperties(uint64 inprops); 311 uint64 ReweightProperties(uint64 inprops); 312 uint64 RmEpsilonProperties(uint64 inprops, bool delayed = false); 313 uint64 SynchronizeProperties(uint64 inprops); 314 uint64 UnionProperties(uint64 inprops1, uint64 inprops2, bool delayed = false); 315 316 extern const char *PropertyNames[]; 317 318 } // namespace fst 319 320 #endif // FST_LIB_PROPERTIES_H__ 321