基于量子逻辑的自动机理论的拓扑性质

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software, Vol.18, No.6, June 2007, pp.1282−1286 http://www.jos.org.cn DOI: 10.1360/jos181282 Tel/Fax: +86-10-62562563 © 2007 by Journal of Software. All rights reserved. 基于量子逻辑的自动机理论的拓扑性质∗ 郭秀红 (四川师范大学 数学与软件科学学院,四川 成都 610066) Topological Characterizations of Automata Theory Based on Quantum Logic GUO Xiu-Hong (College of Mathematics and Software Science, Sichuan Normal University, Chengdu 610066, China) + Corresponding author: Phn: +86-28-84761502, Fax: +86-28-84762620, E-mail: hmxiuxiu@tom.com, http://www.sicnu.edu.cn Guo XH. Topological characterizations of automata theory based on quantum logic. Journal of Software, 2007,18(6):1282−1286. http://www.jos.org.cn/1000-9825/18/1282.htm Abstract: In this paper, some topological characterizations of automata theory based on quantum logic (abbr. l-valued automata theory) are discussed. First, l-valued successor and source operators are redefined and the equivalences of l-valued successor operators, source operators and l-valued subautomata are demonstrated. Afterwards, some topological characterizations in terms of the l-valued successor. source operators and l-valued subautomata are described, and then some fundamental properties of l-valued successor operators, source operators and l-valued subautomata are characterized. Particularly, when the multiplication (&) is distributive over the union in the truth-value lattices, some of the special properties of l-valued successor operators, source operators and l-valued subautomata are verified. So a weaker limitation to form a topology is obtained. Finally, it is shown that the l-valued topologies in terms of the l-valued successor, source operators and l-valued subautomata are equivalent. Key words: quantum logic; automata; successor operator; source operator; subautomata; topology 摘 要: 研究了基于量子逻辑的自动机理论(简称 l-值自动机理论)的拓扑性质.给出了 successor算子和 source算 子的另一种定义,讨论了 successor算子、source算子和 l-值子自动机之间的关系,得到了 successor算子、source算 子和 l-值子自动机的某种等价性.进一步描述了由 successor 算子、source 算子和 l-值子自动机来构造拓扑.得出了 successor算子、source算子和 l-值子自动机的一些基本性质, 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 了在&关于∨分配时,successor算子、source算子 以及 l-值子自动机的某些特殊性质.因而得到了由它们构造拓扑的一个较弱的条件,并且澄清了三者构造拓扑时的 等价性. 关键词: 量子逻辑;自动机;successor算子;source算子;子自动机;拓扑 中图法分类号: TP301 文献标识码: A 20世纪 80年代初,Benioff[1]和 Feyman[2,3]首先提出了量子计算机的思想.Deutsch[4]指出,利用量子态的相干 叠加性可以实现并行的量子计算,并且引入了量子 Turing 机的概念.1994 年,Shor[5]发现了量子计算机上计算离 散对数和大数因子分解的多项式时间算法.Grover[6]于 1996 年为模式识别和数据挖掘提出了一种快速的量子 ∗ Received 2005-06-24; Accepted 2006-06-29 郭秀红:基于量子逻辑的自动机理论的拓扑性质 1283 算法 .此后 ,量子计算的研究日益活跃 .在经典计算机理论中 ,自动机是计算机的简单数学模型 .Moore, Crutchfield[7]和 Gudder[8]从不同的角度引入了作为量子计算机的数学模型的量子自动机,推广了经典自动机理 论.1936 年,Birkhoff 和 von Neumann[9]提出了量子逻辑.文献[10,11]将量子逻辑定义为完备的正交模格值逻辑, 提出了基于量子逻辑的自动机理论,即 l-值自动机,并且研究了 l-值自动机的一些性质.文献[12]建立了基于量子 逻辑的文法理论的基本框架.证明了任意 l-值量子正规文法生成的语言等价于某种 l-值量子自动机识别的语 言,反之,任意 l-值量子自动机识别的语言等价于某 l-值量子正规文法生成的语言.文献[13]给出了基于量子逻辑 且含动作ε的自动机的定义,推广了文献[10]中 l-值自动机的定义,并且建立了基于量子逻辑的自动机和文法理 论的基本框架,讨论了 l-值自动机识别的语言与 l-值正规文法生成的语言的等价性.文献[14]定义和研究了几种 不同类型的格值量子自动机,得出了不确定的格值量子自动机不一定有确定的格值量子自动机与之等价,并且 由格值量子自动机构造了半格和格,进一步讨论了初始格 l与由格值量子自动机构造的格之间的紧密关系. 在经典自动机理论中,可以用 successor 算子、source 算子和子自动机来讨论自动机的拓扑性质.文献[15] 给出了在 l-值自动机理论中的 successor算子、source算子和 l-值子自动机的定义,讨论了 successor算子、source 算子和 l-值子自动机的性质.得到了在∧关于∨分配时 successor算子、source算子和 l-值子自动机的某种等价性, 以及 successor 算子和 source 算子的某些特殊性质,研究了在&关于∨分配时任意两个 l-值子自动机的∩仍是 l- 值子自动机,证明了 successor 算子、source 算子和 l-值子自动机的一些基本性质.因此得到了在∧关于∨分配时 successor 算子和 source 算子可以构造 l-值自动机的拓扑 .在完备的正交模格中 ,正交模律 (即∀a,b∈L, a∧(a⊥∨(a∧b))≤b)可以看成分配律较弱的形式.由此,本文给出了 successor算子和 source算子的另一种定义,得到 了 successor 算子、source 算子和 l-值子自动机之间的某种等价关系(定理 1).研究了由它们构造拓扑,证明了 successor 算子和 source 算子的一些基本性质(定理 2),得到了在&关于∨分配时 successor 算子和 source 算子的 某些特殊性质(定理 3).因而得出在&关于∨分配时,successor算子、source算子和 l-值子自动机可以构造 l-值自 动机的拓扑(定理 5),显然,&关于∨分配较∧关于∨分配是一个较弱的条件.最后证明了三者构造拓扑之间的等价 关系(定理 4). 1 预备知识 定义 1[15]. 设 l=(L,≤,∧,∨,⊥,0,1)是一个完备的正交模格,→是 l 上的蕴涵算子,Σ是有限的输入字母 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf ,称 R=(Q,I,T,δ)是Σ上的 l-值自动机,其中 Q表示有限状态集合,I⊆Q表示初始状态集合,T⊆Q表示终结状态集合,δ是 Q×Σ×Q的 l-值子集,即从 Q×Σ×Q到 L的映射称为 R的 l-值转移关系,即∀p,q∈Q,σ∈Σ,δ(p,σ,q)代表当输入为σ状 态 p 转移到 q 时的真值.δ描述的是输入单个字符时的转移关系.当描述输入字符串时的转移关系时,δ扩展为 δ*:Q×Σ*×Q→L如下:∀p,q∈Q,当 q=p时,δ*(p,ε,q)=1,否则δ*(p,ε,q)=0,并且 δ*(p,xa,q)=∨{δ*(p,x,r)∧δ*(r,a,q):r∈Q},∀x∈Σ*,a∈Σ. 定义 2[15]. 令 M=(Q,Σ,δ)是一个 l-值自动机,∀A∈LQ,称 A是 M的一个 l-值子自动机,如果 ))),,)(()(()((| ** AppxqxQpAqQq l ∈→∈Σ∈∀∈∀→∈∈∀= δ . 等价地,∀q∈Q,A(q)≤∧{δ*(q,x,p)→A(p):x∈Σ*,p∈Q}. 定义 3[15]. 令 X是一个非空集,T⊆LX,称 T是 X上的 l-值拓扑,如果 (i) φ,X∈T. (ii) A,B∈T,A∩B∈T. (iii) 设 I是一个指标集,如果∀i∈I,Ai∈T,则∪i∈IAi∈T. 2 l-值 successor算子和 source算子 定义 4. 设M=(Q,Σ,δ)是一个 l-值自动机,对于任意的 A∈LQ,q∈Q,我们定义 successor算子和 source算子 S,R 如下: S(A)(q)=∨{A(p)&δ*(p,x,q):p∈Q,x∈Σ*}=∨{(A(p)∨δ*(p,x,q)⊥)∧δ*(p,x,q):p∈Q,x∈Σ*}, 1284 Journal of Software 软件学报 Vol.18, No.6, June 2007 R(A)(q)=∨{A(p)&δ*(q,y,q):p∈Q,y∈Σ*}=∨{(A(p)∨δ*(q,y,q)⊥)∧δ*(q,y,q):p∈Q,y∈Σ*}. 定理 1. 设 M=(Q,Σ,δ)是一个 l-值自动机,∀A∈LQ, (i) AAS l ≡= )(| 当且仅当 ⊥⊥ ≡= AARl )(| . (ii) AAS l ≡= )(| 当且仅当 A是 M的一个 l-值子自动机. 证明:(i) ∀q∈Q,因为 A(q)≤S(A)(q),A(q)≤R(A)(q)成立,则只需证明 S(A)⊆A当且仅当 R(A⊥)⊆A⊥.设 S(A)⊆A,则 )()},,()),,()({( *** qAqxpqxppAxQp ≤∧∨∨∨ ⊥∈∈ δδΣ (1) ∀p∈Q,欲证 R(A⊥)(p)≤A⊥(p),即 )()},,()),,()({( *** pArypryprAyQr ⊥⊥⊥ ∈∈ ≤∧∨∨∨ δδΣ (2) 由式(1),(A(p)∨δ*(p,y,r)⊥)∧δ*(p,y,r)≤A(r),于是 A(r)∧δ*(p,y,r)≥(A(p)∨δ*(p,y,r)⊥)∧δ*(p,y,r), A⊥(r)∨δ*(p,y,r)⊥≤(A⊥(p)∧δ*(p,y,r))∨δ*(p,y,r)⊥. 因此, (A⊥(r)∨δ*(p,y,r)⊥)∧δ*(p,y,r)≤((A⊥(p)∧δ*(p,y,r))∨δ*(p,y,r)⊥)∧δ*(p,y,r)≤A⊥(p), 则式(2)成立. 同理可证,如果 R(A⊥)⊆A⊥,则 S(A)⊆A,故结论成立. (ii) 设 S(A)=A,∀q∈Q,欲证 A(q)≤∧{δ*(q,x,p)→A(p):x∈Σ*,p∈Q},即 ∀p∈Q,x∈Σ*,A(q)≤δ*(q,x,p)⊥∨(δ*(q,x,p)∧A(p)). 因为 S(A)(p)≤A(p),则(A(q)∨δ*(q,x,p)⊥)∧δ*(q,x,p)≤A(p),于是 δ*(q,x,p)⊥∨(δ*(q,x,p)∧A(p))≥δ*(q,x,p)⊥∨(δ*(q,x,p)∧(A(q)∨δ*(q,x,p)⊥))≥A(q). 因此,A是 M的一个 l-值子自动机. 同理可证,如果 A是 M的一个 l-值子自动机,则 S(A)=A,故结论成立. □ 3 l-值拓扑 定理 2. 设 M=(Q,Σ,δ)是一个 l-值自动机,A,B∈LQ,则 (i) QQRRQQSS l ≡∧≡∧≡∧≡= )()()()(| φφφφ ,并且φ,Q是 M的 l-值子自动机. (ii) )(|),(| ARAASA ll ⊆=⊆= . (iii) 如果 BBSAAS ll ≡=≡= )(|,)(| ,则 BABASl ∩≡∩= )(| . (iv) 如果 BBRAAR ll ≡=≡= )(|,)(| ,则 BABARl ∩≡∩= )(| . (v) ∪ ∪ Ji Ji ii l ASAS ∈ ∈ ⎟ ⎟ ⎠ ⎞ ⎜⎜⎝ ⎛⊆= )(| , ∪ ∪ Ji Ji ii l ARAR ∈ ∈ ⎟ ⎟ ⎠ ⎞ ⎜⎜⎝ ⎛⊆= )(| ,其中 J是一个指标集,∀i∈J,Ai∈LQ. (vi) 如果 A,B是 M的 l-值子自动机,则 A∪B也是 M的一个 l-值子自动机. 证明:(i) 由 S,R以及 l-值子自动机的定义可知结论成立. (ii) ∀p∈Q, )),,()),,()((())(( *** pxqpxqqApAS xQq δδΣ ∧∨∨∨= ⊥∈∈ ≥((A(p)∨δ⊥(p,ε,p))∧δ(p,ε,p)=A(p)), )),,()),,()((())(( *** qxpqxpqApAR xQq δδΣ ∧∨∨∨= ⊥∈∈ ≥((A(p)∨δ⊥(p,ε,p))∧δ(p,ε,p)=A(p)). 故(ii)成立. (iii) ∀q∈Q,因为 S(A)=A,S(B)=B,则∀p∈Q,x∈Σ*, (A(p)∨δ*(p,x,q)⊥)∧δ*(p,x,q)≤A(q), (B(p)∨δ*(p,x,q)⊥)∧δ*(p,x,q)≤B(q). 郭秀红:基于量子逻辑的自动机理论的拓扑性质 1285 于是, ((A(p)∧B(p))∨δ*(p,x,q)⊥)∧δ*(p,x,q)≤A(q)∧B(q)=(A∩B)(q), 因此, ))(()()()),,()),,())()(((( *** qBAqBqAqxpqxppBpAxQp ∩=∧≤∧∨∧∨∨ ⊥∈∈ δδΣ , 则 S(A∩B)(q)≤(A∩B)(q),故结论成立. (iv)与(iii)类似,可知结论成立. (v) ∀p∈Q, )),,()),,())(((()( *** pxqpxqqApAS iJixQq Ji i δδΣ ∧∨∨∨∨=⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ⊥ ∈∈∈∈ ∪ )),,()),,()((( *** pxqpxqqAixQqJi δδΣ ∧∨∨∨∨≥ ⊥∈∈∈ ∪ Ji i pAS ∈ = ))(( . 故 ∪ ∪ Ji Ji ii l ASAS ∈ ∈ ⎟ ⎟ ⎠ ⎞ ⎜⎜⎝ ⎛⊆= )(| ,同理可证 ∪ ∪ Ji Ji ii l ARAR ∈ ∈ ⎟ ⎟ ⎠ ⎞ ⎜⎜⎝ ⎛⊆= )(| . (vi) 由文献[15]可知结论成立. □ 定理 3. 设 M=(Q,Σ,δ)是一个 l-值自动机,下列条件是等价的: (i) ∀a,b,c∈L,(b&a)∨(c&a)=(b∨c)&a. (ii) ∀a,b,c∈L,(a∨(a⊥∧b))∧(a∨(a⊥∧c))=a∨(a⊥∧b∧c). (iii) ∀A,B∈LQ,如果 BBSAAS ll ≡=≡= )(|,)(| ,则 BABASl ∪≡∪= )(| . (iv) ∀A,B∈LQ,如果 BBRAAR ll ≡=≡= )(|,)(| ,则 BABARl ∪≡∪= )(| . (v) 如果 A,B是 M的 l-值子自动机,则 A∩B也是 M的一个 l-值子自动机. 证明: (i)⇔(ii)显然成立. (i)⇒(iii) ∀p∈Q,x∈Σ*,因为 S(A)(q)≤A(q),S(B)(q)≤B(q),则 (A(p)∨δ*(p,x,q)⊥)∧δ*(p,x,q)≤A(q), (B(p)∨δ*(p,x,q)⊥)∧δ*(p,x,q)≤B(q). 于是,((A(p)∨B(p))∨δ*(p,x,q)⊥)∧δ*(p,x,q) =((A(p)∨δ*(p,x,q)⊥)∧δ*(p,x,q))∨((B(p)∨δ*(p,x,q)⊥)∧δ*(p,x,q)) ≤A(q)∨B(q). 因此,∀q∈Q,S(A∪B)(q)≤(A∪B)(q),故 S(A∪B)=A∪B. (iii)⇒(i) ∀a,b,c∈L,令 Q={p,q},Σ={σ},δ(q,σ,p)=a,A,B∈LQ. A(p)=c&a,A(q)=c,B(p)=b&a,B(q)=b,易知 S(A)=A,S(B)=B,于是, S(A∪B)(p)≤(A∪B)(p)=A(p)∨B(p),则 (c&a)∨(b&a)≥S(A∪B)(p)≥(A(q)∨B(q))&δ(q,σ,p),即 ((c∨a⊥)∧a)∨((b∨a⊥)∧a)≥(c∨b∨a⊥)∧a,而 ((c∨a⊥)∧a)∨((b∨a⊥)∧a)≤(c∨b∨a⊥)∧a成立,故(b&a)∨(c&a)=(b∨c)&a. (i)⇔(iv)类似于(i)⇔(iii)的证明,可知结论成立. (ii)⇔(v)由文献[15]可知结论成立. □ 定义 5. 设 M=(Q,Σ,δ)是一个 l-值自动机,令 })(||{ AASLAJ l Q S ≡=∈= , })(||{ ⊥⊥ ≡=∈= AARLAJ lQR , Jl={A∈LQ|A是 M的一个 l-值子自动机}. 定理 4. 设 M=(Q,Σ,δ)是一个 l-值自动机,则 JS=JR,JS=Jl,Jl=JR. 1286 Journal of Software 软件学报 Vol.18, No.6, June 2007 证明:由定理 1可知结论成立. □ 定理 5. 设 M=(Q,Σ,δ)是一个 l-值自动机,则下列条件是等价的: (i) ∀a,b,c∈L,(b&a)∨(c&a)=(b∨c)&a. (ii) ∀a,b,c∈L,(a∨(a⊥∧b))∧(a∨(a⊥∧c))=a∨(a⊥∧b∧c). (iii) JS是 Q上的一个 l-值拓扑. (iv) JR是 Q上的一个 l-值拓扑. (v) Jl是 Q上的一个 l-值拓扑. 证明:由定理 2、定理 3可知结论成立. □ 注:文献[15]中,由 l-值 successor 算子和 source 算子构造拓扑时需满足∧关于∨分配,定理 4、定理 5 说明重 新定义后的 l-值 successor 算子和 source 算子构造拓扑时只需满足&关于∨分配.显然,&关于∨分配与∧关于∨分 配相比是一个较弱的条件. 致谢 谨向对本文的工作给予支持和帮助的亲人表示衷心的感谢! References: [1] Benioff P. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computer as represented by Turing machines. Journal of Statistical Physics, 1980,22(5):563−591. [2] Feynman RP. Simulating physics with computers. Int’l Journal of Theoretical Physics, 1982,21(6-7):467−488. [3] Feynman RP. Quantum mechanical computers. Foundation of Physics, 1986,16(6):507−531. [4] Deutsh D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc. of the Royal Society of London A, 1985,400(1818):97−117. [5] Shor PW. Polynomial-Time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 1997,26(5):1484−1509. [6] Grover L. A fast quantum mechanical algorithm for database search. In: Proc. of the 28th Annual ACM Symp. on the Theory of Computing. 1996. 212−219. [7] Moore C, Crutchfield JP. Quantum automata and quantum grammars. Theoretical Computer Science, 2000,237(1−2):275−306. [8] Gudder S. Basic properties of quantum automata. Foundations of Physics, 2000,30(2):301−319. [9] Birkhoff G, von Neumann J. The logic of quantum mechanics. Annals of Mathematics, 1936,37(4):823−843. [10] Ying MS. Automata theory based on quantum logic (I). Int’l Journal of Theoretical Physics, 2000,39(4):985−996. [11] Ying MS. Automata theory based on quantum logic (II). Int’l Journal of Theoretical Physics, 2000,39(11):2545−2557. [12] Cheng W, Wang J. Grammar theory based on quantum logic. Int’l Journal of Theoretical Physics, 2003,42(8):1677−1691. [13] Qiu DW. Automata and grammars theory based on quantum logic. Journal of Software, 2003,14(1):23−27 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/14/23.htm [14] Lu RQ, Zheng H. Lattices of quantum automata. Int’l Journal of Theoretical Physics, 2003,42(7):1425−1449. [15] Qiu DW. Automata theory based on quantum logic: Some characterizations. Information and Computation, 2004,190(2):179−195. 附中文参考文献: [13] 邱道文.基于量子逻辑的自动机和文法理论.软件学报,2003,14(1):23−27. http://www.jos.org.cn/1000-9825/14/23.htm 郭秀红(1981－),女,四川绵阳人,硕士,主要研究领域为人工智能.