Computer Science ›› 2017, Vol. 44 ›› Issue (7): 57-60.doi: 10.11896/j.issn.1002-137X.2017.07.010

Previous Articles     Next Articles

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   
No Suggested Reading articles found!