题目：格值树自动机的最小化

?????? 有穷自动机最小化问题的研究在程序测试、模糊系统、概率自动机等方面具有重要意义.因为在等价的前提下,有穷自动机的状态越少,越节省软件和硬件资源.树自动机是自动机的一种推广形式，而加权树自动机是树自动机的一种推广,它们在模型检测和自然语言处理等方面都有非常重要的应用,对于上述应用,因为自动机的规模大小是一个非常关键的问题,所以自动机的最小化就显得极其重要.因此,自动机的最小化问题引起了许多研究者的兴趣.
??????? Huffman于1954年提出了经典确定型自动机的最小化算法,随后,Moore和Hopcroft给出了更有效的最小化算法.Hogberg和Maletti等讨论了树自动机和加权树自动机的最小化,并分别给出了相应的最小化算法.近来,李永明和雷红轩分别研究了确定型格值自动机和完备格值自动机的最小化,并给出了相应的最小化算法.
??????? 受上述文献研究思想和方法的启发,本文主要研究基于格半群上的树自动机理论,即格值树自动机的最小化.格值树自动机是树自动机和模糊有穷自动机的一种推广,同时,它也是加权树自动机的一种特例.关于树自动机，模糊自动机和加权树自动机的研究已经取得非常丰富的理论成果.自动机的最小化是其中一个非常活跃的课题.本文从同余关系和互模拟两个角度讨论了格值树自动机的最小化问题,主要研究内容如下:
??????? 1 首先讨论了无零因子格半群上的确定型可识别树级数的同余关系;其次,通过研究满足左右消去律的格半群上的确定型全接受树自动机,得到了最小化确定型全接受格值树自动机的一个定理,并给出了满足左右消去律的格半群上的全接受型树自动机的Myhill-Nerode定理;最后,给出了确定型可识别树级数的一个特征.
????????2 定义了格值有穷树自动机(L-fta)的前向和后向互模拟关系,进而给出了前向和后向互模拟关系决定的商格值树自动机,并证明了格值树自动机与其相应的商自动机是等价的.通过对前向和后向互模拟关系的研究,证明了最小前向L-fta和最小后向L-fta的存在性.另外,还给出了在有限步内求解极大前向互模拟关系的一种算法.