计算机工程与应用 ›› 2006, Vol. 42 ›› Issue (10): 25-.

• 博士论坛 • 上一篇    

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

高平安,蔡自兴   

  1. 湘潭大学计算机科学系
  • 收稿日期:2005-12-07 修回日期:1900-01-01 出版日期:2006-04-01 发布日期:2006-04-01
  • 通讯作者: 高平安 gaopa gaopa

Linear Automata over Finite Boolean Algebra

PingAn Gao,ZiXing Cai   

  1. 湘潭大学计算机科学系
  • Received:2005-12-07 Revised:1900-01-01 Online:2006-04-01 Published:2006-04-01
  • Contact: PingAn Gao

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

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. It 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.