有限布尔代数上的线性自动机

摘要：

自动机理论是计算机科学理论的重要组成部分.论文研究了布尔代数上的线性自动机,证明了任意一个线性有限自动机是函数布尔代数上的一个内动机.定出了有限布尔代数上的一类可逆线性内动机,给出并证明了有限布尔代数上内动机图型为下向森林的充分必要条件,给出了树型内动机中每一层节点数的计算公式,进而证明了有限布尔代数上的非可逆内动机图型为恰等叉支下向树的充分必要条件.

关键词：布尔函数矩阵、线性有限内动机、森林、恰等叉支树

所属期刊栏目：42

分类号：TP301(计算技术、计算机技术)

资助基金：中国科学院资助项目60234030;湖南省教育厅科研项目02C589

在线出版日期：2006-05-11（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：25-27,125