| 有限布尔代数上的线性自动机 |
| |
| 引用本文： | 高平安,蔡自兴. 有限布尔代数上的线性自动机[J]. 计算机工程与应用, 2006, 42(10): 25-27,125 |
| |
| 作者姓名： | 高平安 蔡自兴 |
| |
| 作者单位： | 1. 中南大学信息科学与工程学院,长沙,410083;湘潭大学计算机科学系,湘潭,411105
2. 中南大学信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 中国科学院资助项目;湖南省教育厅科研项目 |
| |
| 摘 要： | 自动机理论是计算机科学理论的重要组成部分。论文研究了布尔代数上的线性自动机,证明了任意一个线性有限自动机是函数布尔代数上的一个内动机。定出了有限布尔代数上的一类可逆线性内动机,给出并证明了有限布尔代数上内动机图型为下向森林的充分必要条件,给出了树型内动机中每一层节点数的计算公式,进而证明了有限布尔代数上的非可逆内动机图型为恰等叉支下向树的充分必要条件。
|
| 关 键 词： | 布尔函数矩阵 线性有限内动机 森林 恰等叉支树 |
| 文章编号： | 1002-8331-（2006）10-0025-03 |
| 收稿时间： | 2006-01-01 |
| 修稿时间： | 2006-01-01 |
Linear Automata over Finite Boolean Algebra |
| |
| Gao Ping'an,Cai Zixing. Linear Automata over Finite Boolean Algebra[J]. Computer Engineering and Applications, 2006, 42(10): 25-27,125 |
| |
| Authors: | Gao Ping'an Cai Zixing |
| |
| Affiliation: | 1College of Information Science and Engineering, Central South University, Changsha 410083 ; 2Department of Computer Science,Xiangtan University,Xiangtan 411105 |
| |
| Abstract: | Automata theory is an important component of computer science.This paper considers the linear autonomous automata over finite Boolean algebra.In fact,any finite automaton over finite field can be regarded as a Boolean function-matrix automaton.h presents a reversible linear autonomous automaton over finite Boolean algebra.A necessary and sufficient condition is given and proved for an automaton to be a forest.Thirdly,a formula counting the nodes of tree is put forward.Finally, A necessary and sufficient condition is given and proved for an autonomous automaton to be a equal-branch-tree. |
| |
| Keywords: | Boolean function-matrix linear finite autonomous automaton forest equal-branch-tree |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
