Pebble格值有穷自动机和有界传递闭包逻辑

发布时间：2023-03-24 22:45

　　作为计算的简单数学模型,自动机在计算机科学中的文本处理、编译程序、硬件设计、人工智能等应用领域中起着重要的作用.同时自动机也可以作为语言识别器,用来研究各种形式语言.随着Zadeh的模糊集理论的提出,自动机识别语言的能力扩展到了模糊集理论的应用范围,并随之产生了模糊自动机.通常,模糊自动机在[0,1]单位区间取值,为了加强模糊自动机的数据处理能力,我们把值域扩展到更一般的格值代数结构上,特别地,李永明把有穷自动机的代数结构取为一般的格,证明了格值有穷自动机与格值确定型有穷自动机以及带ε转移格值自动机之间的等价性,给出了基于一般格值逻辑的自动机所对应的Kleene定理表现形式.关于自动机与单体逻辑之间的研究己经取得非常丰富的理论成果,并分别在加权逻辑,量子逻辑,Lukasieuicz逻辑和Multi-Valued逻辑上得到相应的推广,那么本文将就基于格值逻辑下做一些相应的工作.本文的主要研究内容如下： 1.引入单体二阶格值逻辑,进而给出基于格值逻辑下的有穷自动机识别语言的逻辑描述,证明了格值逻辑意义下的Biichi-Elgot定理.通过引入星-自由语言与非周期格值语言,完全刻画了可以用一...

【文章页数】：39 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
目录
前言
第1章 预备知识
    1.1 格的概念和基本性质
    1.2 Buchi-Elgot定理
第2章 格值有穷自动机和单体二阶逻辑
    2.1 格值自动机识别语言的有关逻辑性质
    2.2 基于格值逻辑下的Buchi-Elgot定理
    2.3 格值逻辑意义下的Schutzenberger定理
第3章 Pebble格值有穷自动机和闭包逻辑
    3.1 闭包逻辑和格值有穷自动机
    3.2 格值nested自动机
    3.3 pebble格值自动机
结论
参考文献
致谢
攻读硕士学位期间的研究成果



本文编号：3769997