● 摘要
作为计算的简单数学模型,自动机在计算机科学中的文本处理、编译程序、硬件设计、人工智能等应用领域中起着重要的作用.同时自动机也可以作为语言识别器, 用来研究各种形式语言.随着Zadeh的模糊集理论的提出,自动机识别语言的能力扩展到了模糊集理论的应用范围,并随之产生了模糊自动机. 通常, 模糊自动机在[0,1]单位区间取值, 为了加强模糊自动机的数据处理能力, 我们把值域扩展到更一般的格值代数结构上, 特别地，李永明把有穷自动机的代数结构取为一般的格，证明了格值有穷自动机与格值确定型有穷自动机以及带$varepsilon$转移格值自动机之间的等价性，给出了基于一般格值逻辑的自动机所对应的Kleene定理表现形式. 关于自动机与单体逻辑之间的研究已经取得非常丰富的理论成果, 并分别在加权逻辑, 量子逻辑, $Lukasieuicz$逻辑和 $Multi-Valued$逻辑上得到相应的推广, 那么本文将就基于格值逻辑下做一些相应的工作.本文的主要研究内容如下:
1. 引入单体二阶格值逻辑, 进而给出基于格值逻辑下的有穷自动机识别语言的逻辑描述, 证明了格值逻辑意义下的B"{u}chi-Elgot定理. 通过引入星-自由语言与非周期格值语言, 完全刻画了可以用一阶格值逻辑定义的格值语言, 得到了格值逻辑意义下的Sch"{u}tzenberger定理.
2. 我们定义了格值逻辑下的一阶有界传递闭包逻辑并且用一阶有界传递闭包逻辑刻画格值有穷自动机;
3. 我们还介绍了两类格值有穷自动机: $nested$ 格值有穷自动机和 $pebble$ 格值有穷自动机, 这两类格值有穷自动机是一个带有单道读写带的机械装置; 而且, 这两类格值自动机都可以由一阶有界传递闭包逻辑来刻画. 从而得到: 这两类有 $nested pebble$ 装置的格值有穷自动机所接受的语言与格值有穷自动机所接受的语言是等价的.