主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第5期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
邱道文.基于量子逻辑的自动机和文法理论.软件学报,2003,14(1):23-27
基于量子逻辑的自动机和文法理论
Automata and Grammars Theory Based on Quantum Logic
投稿时间:2001-03-29  修订日期:2001-05-18
DOI:
中文关键词:  量子逻辑  自动机  正规文法  形式语言  泵引理
英文关键词:quantum logic  automata  regular grammar  formal language  pumping lemma
基金项目:(Supported by the National Grand Fundamental Research 973 Program of China under Grant No.G1998030509 (国家重点基础研究发展规划(973)); the National Natural Science Foundation of China for Distinguished Young Scholars under Grant No.69725004 (国家杰出青年科学基金); the Natural Science Foundation of Guangdong Province of China under Grant No.020146 (广东省自然科学基金); the Young Foundation of Zhongshan University of China under Grant No.35100-1131127 (中山大学青年基金)
作者单位
邱道文 中山大学,计算机科学系,广东,广州,510275
清华大学,计算机科学与技术系,北京,100084
清华大学,智能技术与系统国家重点实验室,北京,100084 
摘要点击次数: 3315
全文下载次数: 3186
中文摘要:
      初步建立了基于量子逻辑的自动机和文法理论的基本框架.引入了量子文法(称为l值文法),特别是证明了任意l值正规文法生成的语言(称为量子语言)等价于某种基于量子逻辑且含动作(的自动机(称为l值自动机)识别的语言,反之,任意l值自动机识别的语言等价于某l值正规文法生成的语言.建立了l值泵引理,并得到量子语言的判定性刻画.最后简要讨论了正规文法与量子文法(即l值正规文法)的关系.因此,为进一步研究更复杂的量子自动机(如量子下推自动机和Turing机)和量子文法(如量子上下文无关文法和上下文有关文法)奠定了基础.
英文摘要:
      In this paper, a fundamental framework of automata and grammars theory based on quantum logic is preliminarily established. First, the introduce quantum grammar, which is called l valued grammars, is introduced. It is particularly showed that the language (called quantum language) generated by any l valued regular grammar is equivalent to that recognized by some automaton with e moves based on quantum logic (called l valued automata), and conversely, any quantum language recognized by l valued automaton is also equivalent to that generated by some l valued grammar. Afterwards, the l valued pumping lemma is built, and then a decision characterization of quantum languages is presented. Finally, the relationship between regular grammars and quantum grammars (l valued regular grammars) is briefly discussed. Summarily, the introduced work lays a foundation for further studies on more complicated quantum automata and quantum grammars such as quantum pushdown automata and Turing machine as well as quantum context-free grammars and context-sensitive grammars.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利