基于量子逻辑的下推自动机的代数刻画  

Algebraic Characterization of Pushdown Automata Based on Quantum Logic

作　　者：韩召伟[1,2] 李永明[2] 

机构地区：[1]陕西师范大学数学与信息科学学院,陕西西安710062 [2]陕西师范大学计算机科学学院,陕西西安710062

出　　处：《计算机工程与科学》2008年第11期72-74,共3页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(10571112);陕西师范大学青年科技项目(200701008)

摘　　要：首先,本文提出量子下推自动机(简记为L-VPDA)的概念,从代数角度出发详细研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用量子状态构造证明了任意L-VPDA与状态转移为经典函数且具有量子终状态的L-VPDA间的相互等价性;其次详细研究了量子上下文无关语言的代数刻画以及对于正则运算的封闭性。Firstly, the notion of orthomodular lattice-valued pushdown automaton（abbr. L-VPDA） is introduced, we traverse some algebraic properties of these automata in detail and also establish the algebraic features of these automata, i. e, by using the means of quantum state construction. We prove the fact that an arbitrary L-VPDA can accept the same L-valued language by the final states and by one L-VPDA with the crisp transition relation and fuzzy final states. Secondly, we discuss the algebraic characterization of orthomodular lattice-valued context-free languages, and also deal with the closed properties of these L-valued languages under some regular operations in particular at the same time.

关 键 词：量子逻辑 正交模格 量子下推自动机 量子上下文无关语言 代数刻画 

分 类 号：TP301.1[自动化与计算机技术—计算机系统结构] O153.1[自动化与计算机技术—计算机科学与技术]