首页>
外国专利>
Systems and methods for determining the determinizability of finite-state automata and transducers
Systems and methods for determining the determinizability of finite-state automata and transducers
展开▼
机译:用于确定有限状态自动机和换能器的可确定性的系统和方法
展开▼
页面导航
摘要
著录项
相似文献
摘要
Finite-state transducers and weighted finite-state automata may not be determinizable. The twins property can be used to characterize the determinizability of such devices. For a weighted finite-state automaton or transducer, that weighted finite-state automaton or transducer and its inverse are intersected or composed, respectively. The resulting device is checked to determine if it has the cycle-identity property. If not, the original weighted finite-state automaton or transducer is not determinizable. For a weighted or unweighted finite-state transducer, that device is checked to determine if it is functional. If not, that device is not determinizable. That device is then composed with its inverse. The composed device is checked to determine if every edge in the composed device having a cycle-accessible end state meets at least one of a number of conditions. If so, the original device has the twins property. If the original device has the twins property, then it is determinizable.
展开▼