交换幂等半环上的加权有限自动机的确定式

摘要

每个有限状态自动机都等价于一个确定的有限自动机，但并非每个加权有限自动机都等价于一个子序列加权有限自动机。因此，确定一个加权有限自动机是否等价于一个子序列加权有限自动机是一个有意义的课题。
　　为了研究交换min-半环上的加权有限自动机的子序列等价，文献[1]提出了半环上的有限维极大因式分解的概念，并给出了交换min-半环上的加权有限自动机有子序列等价的一个充分条件。
　　本文证明一交换半环K有一个维数n≥2的极大因式分解当且仅当K是一个满足g.c.d条件的乘法可消半环。利用这个结论，我们还证明了有一个维数n≥2的极大因式分解的交换幂等半环上具有victory性质和twins性质的加权有限自动机T都有子序列等价，从而解决了文献[1]中提出的公开问题。进一步地，利用我们的结论还可以改进文献[1]的主要定理。

目录

声明

摘要

第一章 绪论

第二章 预备知识

2．1 半群和半环

2．2 加权有限自动机

第三章 交换MF-半环的刻画

3．1 基本概念

3．2 交换MF-半环的刻画

第四章 交换幂等MF-半环上的WFA的确定式

4．1 基本概念

4．2 交换幂等MF-半环上的WFA的确定式

第五章 特殊情形

5．1 交换幂等MF-半环上的trim，非模糊WFA

5．2 Trim，非模糊的WFA在某些特殊半环上的结论

第六章 总结与展望

参考文献

攻读硕士学位期间的研究成果

致谢