摘要
本文利用模型论博奕理论的方法证明了（Ｐ１，１）能够刻画正则语言．由此我们得到结论：在有限的离散线性序上（Ｐ１，１）和Ｍｏｎａｄｉｃ二阶逻辑的刻画能力是一致的．
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.
出处
《计算机学报》
EI
CSCD
北大核心
1996年第11期848-853,共6页
Chinese Journal of Computers
基金
国家自然科学基金
关键词
正则语言
模型论博奕
形式语言
计算机
Partition logic, regular language, model-theoretical game
