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

Previous Articles     Next Articles

Applications of Fibrations Theory to Uncertainty Semantic Computation for Indexed Inductive Data Types

MIAO De-cheng, XI Jian-qing, LIU Xin-sheng and SU Jin-dian   

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

Abstract: This paper discussed the uncertainty semantic computation of indexed inductive data types using Fibrations theory.Firstly,we demonstrated the construction of indexed category,presented the concept of indexed Fibration and its truth and comprehension functors.And then,we proposed a truth-preserving lifting on endo-functor in indexed category.We also presented the definition of partial F-algebra,abstractly described the uncertainty semantic computation of indexed inductive data types using some tools including fold function,and briefly introduced the application by example.At last,we stated the advantages of Fibrations theory by comprising with some related works.

Key words: Semantic computation,Uncertainty,Indexed inductive data types,Fibrations theory,Lifting

[1] 陈意云,张昱.程序设计语言理论(第二版)[M].北京:高等教育出版社,2010:135-219.
[2] WINSKEL G.程序设计语言的形式语义[M].宋国新,等译.北京:机械工业出版社,2005:143-259.
[3] BARR M,WELLS C.Category theory for computing science[M].NewYork:Prentice-Hall,1990:252-270.
[4] 贺伟.范畴论[M].北京:科学出版社,2006:23-44.
[5] 王兵山,毛晓光,刘万伟.高级范畴论[M].北京:清华大学出版社,2012:1-114.
[6] RUTTEN J.Universal coalgebra:a theory of systems[J].Theoretical Computer Science,2000,249(1):3-80.
[7] HUTTON G.Fold and unfold for program semantics[C]∥Proc.of the 3rd ACM SIGPLAN Int.Conf.on Functional Programming,1998.NewYork:ACM,1998:280-288.
[8] BIRD R S,MOOR O D.Algebra of Programming[M].UK:Prentice-Hall,1997:107-156.
[9] SU J D,YU S S.Bialgebraic Structures for Abstract Data Types and Their Computations[J].Journal of Computer Research and Development,2012,9(8):1787-1803.(in Chinese) 苏锦钿,余珊珊.抽象数据类型的双代数结构及其计算[J].计算机研究与发展,2012,9(8):1787-1803.
[10] JOHNSON M,ROSEBRUGH R,WOOD R J.Lenses,fibrations and universal translations[J].Mathematics Structure in Computer Science,2012,22(1):25-42.
[11] GHANI N,JOHANN P,FUMEX C.Generic fibrationalinduction[J].Logical Methods in Computer Science,2012,8(2):1-27.
[12] MIAO D C,XI J Q,DAI J G,et al.Fibrations method of co-inductive data types in programming[J].Computer Science,2016,43(3):188-192,212.(in Chinese) 苗德成,奚建清,戴经国,等.程序语言中共归纳数据类型的一种fibrations方法[J].计算机科学,2016,43(3):188-192,212.
[13] MIAO D C,XI J Q,SU J D.A category theoretical method of inductive data types[J].Computer Science,2015,42(6):8-11.(in Chinese) 苗德成,奚建清,苏锦钿.归纳数据类型的范畴论方法[J].计算机科学,2015,42(6):8-11.
[14] HERMIDA C,JACOBS B.Structural induction and coinduction in a fibrational setting [J].Information and Computation,1998,145(2):107-152.
[15] GHANI N,JOHANN P,FUMEX C.Indexed induction and coinduction,fibrationally[J].Logical Methods in Computer Science,2013,9(3-6):1-31.
[16] MIAO D C,XI J Q,GUO Y B,et al.Inductive data types based on Fibrations theory in programming[J].Journal of Computing and Information Technology,2016,24(1):1-16.
[17] 屈延文.形式语义学基础与形式说明[M].北京:科学出版社,2010:194-207.
[18] SRINIVASAN R,MITHUN H,MARWAN K.Linear time distributed construction of colored trees for disjoint multiple routing[J].Computer Networks,2007,51(10):2854-2866.
[19] WEISS M A.数据结构与算法分析C++描述(第3版)[M].张怀勇,译.北京:人民邮电出版社,2007:379-387.
[20] Bengt N,Kent P,Jan M S.Martin-Lf类型论程序设计导引[M].宋方敏,译.南京:南京大学出版社,2002:1-15.
[21] COQUAND T,PAULIN M C.Inductively Defined Types[J].International Conference on Colog,1990(417):50-66.
[22] DYBIER P.Inductive sets and families in Martin-Lof type theory and their set theoretical semantics[M].Cambridge University Press,1991:3-27.
[23] FU Y.Recursive Models of General Inductive Types[J].IOS Press,1996,26(2):115-131.
[24] FU Y X.Constructive Semantics of Inductive Types[J].Journal of Software,1998,9(3):236-240.
[25] PAWLAK Z.Rough sets,decision algorithms and Bayes’ theorem[J].European Journal of Operational Research,2002,136(1):181-189.
[26] ZIARKO W P,RIJSBERGEN C J V.Rough Sets,Fuzzy Setsand Knowledge Discovery[M].New York:Springer-Verlag,1994:366-376.
[27] LI D Y,LIU C Y,DU Y,et al.Artificial Intelligence with Uncertainty[J].Journal of Software,2004,15(11):1583-1594.(in Chinese) 李德毅,刘常昱,杜鹢,等.不确定性人工智能[J].软件学报,2004,15(11):1583-1594.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!