作　　者： ; ;

机构地区： 北京师范大学数学科学学院

出　　处： 《计算机学报》 1996年第11期848-853,共6页

摘　　要： 本文利用模型论博奕理论的方法证明了（Ｐ１，１）能够刻画正则语言．由此我们得到结论：在有限的离散线性序上（Ｐ１，１）和Ｍｏｎａｄｉｃ二阶逻辑的刻画能力是一致的． Based on the theory of model-theoretical game, it is proved that the partition logic (p1,1 ) can characterize the regular language. Then it is concluded that the partition logic has the same expressive power as Monadic second-order logicdoes in the class of finite discrete linear order structure.

关 键 词： 正则语言 模型论博奕 形式语言 计算机

领　　域： [自动化与计算机技术] [自动化与计算机技术]