计算机科学 ›› 2017, Vol. 44 ›› Issue (7): 57-60.doi: 10.11896/j.issn.1002-137X.2017.07.010

• 2016 年全国理论计算机科学学术年会 • 上一篇    下一篇

量化上下文无关语言的代数性质

付雯静,韩召伟   

  1. 陕西师范大学数学与信息科学学院 西安710119,陕西师范大学数学与信息科学学院 西安710119
  • 出版日期:2018-11-13 发布日期:2018-11-13
  • 基金资助:
    本文受国家自然科学基金资助

Algebraic Properties of Quantitative Context-free Languages

FU Wen-jing and HAN Zhao-wei   

  • Online:2018-11-13 Published:2018-11-13

摘要: 通过引入量化下推自动机与量化上下文无关文法的定义,研究了以两种不同方式接受语言的量化下推自动机等价性问题,证明了在可交换的双幺赋值幺半群上,量化下推自动机接受的语言与量化上下文无关文法生成的语言相同。

关键词: 双幺赋值幺半群,量化下推自动机,量化上下文无关文法,量化上下文无关语言

Abstract: By introducing the concepts of quantitative pushdown automata and quantitative context-free grammars,this paper investigated the equivalent relation that a quantitative language can be accepted by quantitative pushdown automatain two different ways.It is showed the fact that quantitative pushdown automata can accept the same quantitative context-free languages which are generated by quantitative context-free grammars over commutative double unital valuation monoid in the meanwhile.

Key words: Double unital valuation monoid,Quantitative pushdown automaton,Quantitative context-free grammar,Quantitative context-free language

[1] HOPCROFT J E,MOTWANI R,ULLMAN J D.Introduction to Automata Theory,Languages and Computation (3rd)[M].New Jersey:Pearson Addision Wesley,2007:171-314.
[2] LEE E T,ZADEH L A.Note on fuzzy languages[J].Information Science,1969,1(4):321-434.
[3] 李永明.模糊系统分析[M].北京:科学出版社,2005:218-228.
[4] YING M S.A theory of computation based on quantum logic(I) [J].Theoretical Computer Science,2005,344(2/3):134-207.
[5] LI Y M,PEDRYCZ W.Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids [J].Fuzzy Sets and Systems,2005,156(1):68-92.
[6] QIU D W.Automata theory based on quantum logic:Reversibili-ties and pushdown automata[J].Theoretical Computer Scien-ce,2007,386(1):38-56.
[7] XING H Y,QIU D W,LIU F C.Automata theory based on com-plete residuated lattice-valued logic:Pushdown automata[J].Fuzzy Sets and Systems,2009,160(8):1125-1140.
[8] LI Y M.Finite automata theory with membership value in lattices [J].Information Science,2011,181(5):1003-1017.
[9] DROSTE M,STBER T,VOGLER H.Weighted finite automata over strong bimonoids[J].Information Science,2010,0(1):156-166.
[10] CHATTERJEE K,DOYEN L,HENZINGER T A.Quantitative languages [M]∥Computer Science Logic.Springer,2008:385-400.
[11] DROSTE M,MEINECKE I.Weighted automata and regular expressions over valuation monoid[J].International Journal of Foundations of Computer Science,2011,2(8):1829-1844.
[12] DROSTE M,MEINECKE I.Weighted automata and Weighted MSO logics for average and long-time behaviors[J].Information and Computation,2012,220-221(2):44-59.
[13] HAN Z W,LI Y M.Pushdown automata and context-free grammars based on quantum logic[J].Journal of software,2010,21(9):2107-2117.(in Chinese) 韩召伟,李永明.基于量子逻辑的下推自动机与上下文无关文法 [J].软件学报,2010,1(9):2107-2117.
[14] SONG X Z,HAN Z W,LI Y N.Algebraic properties of context-free grammar based on quantum logic[J].Computer Engineering and Applications,2011,47(4):42-46.(in Chinese) 宋小震,韩召伟,李永明.量子上下文无关文法的代数性质[J].计算机工程与应用,2011,7(4):42-46.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .