第4卷第3期 智能系统学报 Vol.4 No.3 2009年6月 CAAI Transactions on Intelligent Systems Jn.2009 doi:10.3969/j.issn.16734785.2009.03.009 时态查询语言的并发Lambek演算及范畴语法 刘冬宁12，汤庸，黄昌勤3，汤螂 (1.中山大学计算机科学系，广东广州510275；2.中山大学数学系，广东广州510275；3.华南师范大学教育信息 技术学院，广东广州510631) 摘要：时态逻辑不可递归公理化的性质，造成它的公理化系统和证明论方法不适于时态查询语言的建模这使得 时态逻辑无法利用公理化系统的良好性质及相关证明论方法对时态数据库的推理和查询做更为严谨和细致地刻 画.因此寻找时态逻辑的替代者，以公理化的方式对时态查询语言做句法和语义的分析是必要的.考虑的2个主要 工具是作为句法分析工具的以Lambek演算为核心的范畴语法系统，和作为语义分析工具的类型演算入-演算.这主 要是基于类型论的演算持点、SQL语句与陈述句的相似性、Lambek演算和入-演算的公理化与证明论方法，及它们作 为句法和语义分析工具之间的密切联系与对应性决定的.据此从Lambek演算出发，结合时态的处理，构建了并发的 Lambek演算(Lcm)及相应的范畴语法，对以公理化系统为基础的时态查询语言的句法分析做相关研究，并从证明论 性质上保障了计算性资源，使得系统更为严谨和完善. 关键词：时态查询语言；句法分析；并发的Lambek演算；范畴语法 中图分类号：TP301文献标识码：A文章编号：16734785(2009)030245-06 Concurrence Lambek calculus and its categorical grammar in temporal querying languages LIU Dong-ning'2,TANG Yong',HUANG Chang-qin'3,TANG Na! (1.Department of Computer Science,Sun Yat-sen University,Guangzhou 510275,China;2.Department of Maths,Sun Yat-sen Uni- versity,Guangzhou 510275,China;3.College of Educational Information Technology,South China Normal University,Guangzhou 510631,China) Abstract:Axiomatic systems and proof methods for temporal logic have so far found relatively few applications in querying language modeling of temporal databases because the standard temporal logic is not recursively axiomatiz- able.As a result,temporal logic can not use axiomatic systems and proof methods to religiously depict inference and querying of a temporal database.Thus it is necessary to find a replacement for temporal logic which,by axio- matic methods,can become the implement of a syntactic and semantic analysis of temporal querying languages.The Lambek calculus and its categorical grammar as the former and A-calculus as the latter have become those substi- tutes in this paper,because of the properties of type theory,the comparability between SQL and state sentence,the axiomatic and proof methods of Lambek calculus and A-calculus,and their correspondence by Curry-Howard Isomor- phism.So,according to the operations of temporality,we built a new axiomatic system used in syntactic analysis which is called concurrence Lambek calculus (Lcro),and use its categorial grammar to deal with the temporal que- rying language.Prof theory shows that for protection of computable resources,Lero is more regorous and ideal. Keywords:temporal querying language;syntactic analysis;concurrence Lambek calculus;categorial grammars 关于时间的表达、推理与查询一直是时态数据。 库中最为关键的研究点.目前许多的时态查询语言 已经使用于时态数据库，其理论基础也相对繁杂；但 收稿日期：200807-15. 基金项目：国家自然科学基金资助项目(60673135、60373081)：国家 其中最为直接关联并得到广泛应用的就是基于时态 自然科学基金重点资助项目(60736020)：广东省自然科学 基金资助项目(7003721)，广东省科技攻关资助项目 逻辑的查询语言).这主要是由于时态逻辑能充分 (07B010200052):广州市科技计划资助项目(07Z3- 体现时间的特性， D3191). 通信作者：汤庸.E-mail:igy@ym.eu.cm. 然而在1994年，Gabby等论证了时态逻辑是不