微信服务号

微信订阅号

2025-4-24- 19
Home > Archive>Volume 21, Issue 7, 2010 >1481-1490
PDF HTML XML Export Cite reminder
Subtyping Algorithm with Pruning Optimization
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [21]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    Statically typed XML processing languages show new ways of processing XML data. However, current languages are not efficient enough. This paper studies the decision problem of subtyping relation which is an important issue of the languages, and optimizes XDuce’s subtyping algorithm with a pruning strategy. Experimental data show the efficiency of the algorithm increased 20% averagely. This optimization strategy can be applied to other languages which use similar subtyping algorithm.

    Reference
    [1] Chen HM, Dong YM. A formal specification language supporting specification acquisition. Chinese Journal of Computers, 2002, 25(5):459?466 (in Chinese with English abstract).
    [2] Hosoya H. Regular expression types for XML [Ph.D. Thesis]. Tokyo: The University of Tokyo, 2000.
    [3] Hosoya H, Pierce BC. Regular expression pattern matching for XML. Journal of Functional Programming, 2002,13(6):961?1004. [doi: 10.1017/S0956796802004410]
    [4] Hosoya H, Pierce BC. XDuce: A statically typed XML processing language. ACM Trans. on Internet Technology, 2003,3(2): 117?148. [doi: 10.1145/767193.767195]
    [5] Hosoya H, Vouillon J, Pierce BC. Regular expression types for XML. ACM Trans. on Programming Languages and Systems, 2005, 27(1):46?90. [doi: 10.1145/1053468.1053470]
    [6] Castagna G, Frisch A. A gentle introduction to semantic subtyping. In: Proc. of the 7th ACM SIGPLAN Int’l Conf. on Principles and Practice of Declarative Programming. New York: ACM Press, 2005. 198?199. http://centria.di.fct.unl.pt/conferences/ppdp05/
    [7] Benzaken V, Castagna G, Frisch A. CDuce: An XML-centric general-purpose language. In: Proc. of the 8th ACM SIGPLAN Int’l Conf. on Functional Programming. New York: ACM Press, 2003. 51?63. http://www.cc.gatech.edu/icfp03/
    [8] Frisch A, Castagna G, Benzaken V. Semantic subtyping. In: Proc. of the 17th Annual IEEE Symp. on Logic in Computer Science. Washington: IEEE Computer Society, 2002. 137?146. http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=8005
    [9] Gapeyev V, Garillot F, Pierce BC. Statically typed document transformation: An Xtatic experience. In: Castagna G, Raghavachari M, eds. Proc. of the Workshop on Programming Language Technologies for XML (PLAN-X). Aarhus: BRICS, 2006. 2?13.
    [10] Gapeyev V, Levin M, Pierce BC, Schmitt A. XML goes native: Run-Time representations for Xtatic. In: Bodik R, ed. Proc. of the 14th Int’l Conf. on Compiler Construction. Berlin: Springer-Verlag, 2005. 43?58.
    [11] Gapeyev V, Levin M, Pierce BC, Schmitt A. The Xtatic experience. In: Proc. of the Workshop on Programming Language Technologies for XML (PLAN-X). 2005. 16?31. http://www.research.att.com/conf/planx2005/
    [12] Gapeyev V, Pierce BC. Regular object types. In: Cardelli L, ed. Proc. of the European Conf. on Object-Oriented Programming (ECOOP). Berlin: Springer-Verlag, 2003. 151?175.
    [13] Comon H, Dauchet M, Gilleron R, Jacquemard F, Lugiez D, Tison S, Tommasi M. Tree automata techniques and applications. 2002. http://www.grappa.univ-lille3.fr/tata
    [14] Seid H. Deciding equivalence of finite tree automata. SIAM Journal, 1990,19(3):424?437. [doi: 10.1137/0219027]
    [15] Aiken A, Murphy BR. Implementing regular tree expressions. In: Hughes J, ed. Proc. of the 5th ACM Conf. on Functional Programming Languages and Computer Architecture. London: Springer-Verlag, 1991. 427?447.
    [16] XDuce: A typed XML processing language. 2003. http://xduce.sourceforge.net/
    [17] Lu K, Sulzmann M. An implementation of subtyping among regular expression types. In: Chin WN, ed. Proc. of the APLAS 2004. Berlin: Springer-Verlag, 2004. 57?73.
    [18] Haskell. http://www.haskell.org/
    [19] Antimirov V. Rewriting regular inequalities (extended abstract). In: Reichel H, ed. Proc. of the 10th Int’l Symp. on Fundamentals of Computation Theory. London: Springer-Verlag, 1995. 116?125.
    [20] CDuce. http://www.cduce.org/
    附中文参考文献: [1] 陈海明,董韫美.一个支持规约获取的形式规约语言.计算机学报,2002,25(5):459?466.M
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

戴晓君,陈海明.采用了剪枝优化的子类型关系判定算法.软件学报,2010,21(7):1481-1490

Copy
Share
Article Metrics
  • Abstract:4424
  • PDF: 5972
  • HTML: 0
  • Cited by: 0
History
  • Received:December 24,2008
  • Revised:November 26,2009
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2038233Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063