Basic research in computer science and software engineering at SKLCS

Abstract

The State Key Laboratory of Computer Science (SKLCS) is committed to basic research in computer science and software engineering. The research topics of the laboratory include: concurrency theory, theory and algorithms for real-time systems, formal specifications based on context-free grammars, semantics of programming languages, model checking, automated reasoning, logic programming, software testing, software process improvement, middleware technology, parallel algorithms and parallel software, computer graphics and human-computer interaction. This paper describes these topics in some detail and summarizes some results obtained in recent years.

References

1. Lin H M Completeinference systems for weak bisimulation equivalences in the π-calculusInformationand Computation 2003 180(1)129
2. Lin H M Wang Y Axiomatising timed automataActa Informatica 2002 38(4)277305
3. Jiao L Huang H J Cheung T Y Property-preserving composition by place mergingJournal of Circuits, Systems and Computers 2005 14(4)793812
4. Huang H J Jiao L Cheung T Y Property-preserving subnet reductions for designing manufacturingsystems with shared resourcesTheoreticalComputer Science 2005 332(1–3)461485
5. Jiao L Cheung T Y Lu W M Handling synchronization problem in Petri-net-based systemdesign by property-preserving transition-reductionThe Computer Journal 2005 48(6)692701
6. Jiao L Cheung T Y Compositional verificationfor workflow netsJournal of Circuits, Systemsand Computers 2006 15(4)551570
7. Zhang W H Combiningstatic analysis and case-based search space partitioning for reducingpeak memory in model checkingJournal ofComputer Science and Technology 2003 18(6)762770
8. Lv Y Lin H M Pan H Computing invariants for parameter abstractionSchneider KHoe JProceedings of MEMOCODENiceIEEE Press 2007 2938
9. Wu P Lin H M Model-based testing of concurrentprograms with predicate sequencing constrainsInternational Journal of Software Engineering and Knowledge Engineering 2006 16(5)727746
10. Lin H M Apredicate mu-calculus for mobile ambientsJournal of Computer Science and Technology 2004 20(1)95104
11. Lin H M Apredicate spatial logic and model checking for mobile processesLiu Z MAraki KProceedings of ICTACBerlinSpringer 2004 36
12. Zhan N J Majster-Cederbaum M Deriving non-determinismfrom conjunction and disjunctionWang FProceedings of FORTEBerlinSpringer 2005 351365
13. Zhan N J Wu J Compositionality of fixpointlogic with chopHung D VWirsing MProceedings of ICTACBerlinSpringer 2005 136150
14. Zhang W H Modelchecking with SAT-based characterization of ACTL formulasProceedings of ICFEMBerlinSpringer 2007 191211
15. Zhou C C Hoare C A R Ravn A A calculus of durationsInformationProcessing Letters 1991 40(5)269276
16. Damm W Hungar H Olderog E - R Verification of cooperating traffic agentsInternational Journal of Control 2006 79(5)395421
17. Zhou C C Hansen M R Duration calculus: a formalapproach to real-time systems. EATCS Series of Monographs in TheoreticalComputer ScienceBerlinSpringer 2004
18. Xu Q W Zhan N J Formalizing scheduling theorieswith duration calculusNordic Journal ofComputing, to appear
19. Liu C L Layland J W Scheduling algorithms for multiprogrammingin a hard real-time environmentJournalof ACM 1973 20(1)4661
20. Li G Y Tang Z S Modeling real-time systemswith continuous-time temporal logicGeorgeCMiao HProceedings of ICFEMBerlinSpringer 2002 231236
21. Tang Z S Aprogram development support environment based on temporal logicProceedings of PLSDNorth Hollland 1983
22. Li G Y Tang Z S Translating a continuous-timetemporal logic into timed automataOhoriA Proceedings of APLASBerlinSpringer 2003 322338
23. Yan R J Li G Y Tang Z S Symbolic model checking of finite precision timed automataHung D VWirsing MProceedings of ICTACBerlinSpringer 2005 272287
24. Fu Y Wang H Distributed utilization controlfor real-time clusters with load balancingProceedings of IEEE RTSS. Rio 2006 137146
25. Zhou H Wang Y J Wang Q Measuring internet bottlenecks: location, capacity, andavailable bandwidthLu X CZhao WProceedingsof CNMCBerlinSpringer 2005 10521062
26. Wang X X Wang Y J Zhou J H et al.Congestion control algorithm based on improved modelin large-delay networksActa ElectronicaSinica 2005 33(5)842846
27. Wang X L Wang Y J Zhou H et al.PSO-PID: a novel controller for AQM routersProceedings of IEEE/IFIP WOCN. Bangalore 2006 15
28. Wang X L Wang Y J Zeng H T et al.Particle swarm optimization with escape velocityProceedings of CISGuangzhouIEEE Press 2006 457460
29. Shen Y D You J H Yuan L Y et al.A dynamic approach to characterizing terminationof general logic programsACM Transactionson Computational Logic 2003 4(4)417430
30. Shen Y D You J H Yuan L Y Enhancing global SLS-resolution with loop cutting and tablingmechanismsTheoretical Computer Science 2004 328(3)271287
31. Dowek G Jiang Y Eigenvariables, bracketingand the decidability of positive minimal predicate logicTheoretical Computer Science 2006 360(1–3)193208
32. Zhang W H Huang Z Zhang J Parallel execution of stochastic search procedures on reducedSAT instancesProceedings of PRICAIBerlinSpringer 2002 108117
33. Jia X X Zhang J Predicate-oriented isomorphismelimination in model findingProceedingsof IJCAISt LouisMorgan Kaufmann Publishers 2005 15251526
34. Jia X X Zhang J A powerful technique to eliminateisomorphism in finite model searchProceedingsof IJCARBerlin. 2006 318331
35. Dong Y M MLIRFmethod for specification acquisition and reuseProceedings of the 9th National Conference of China Computer FederationChongqing 1996 2127 (in Chinese)
36. Dong Y M Recursivefunctions of context free languages (I) --- the definitions of CFPRFand CFRFScience in China Series F 2002 45(1)2539
37. Dong Y M Recursivefunctions of context free languages (II) - validity of CFPRF and CFRFdefinitionsScience in China Series F 2002 45(2)121
38. Dong Y M Aninteractive learning algorithm for acquisition of concepts representedas CFLJournal of Computer Science and Technology 1998 13(1)18
39. Dong Y M Li K Chen H et al.Design and implementation of the formal specificationacquisition system SAQProceedings of ConferenceSoftware: Theory and Practice, IFIP 16th World Computer Congress 2000Beijing 2000 201211
40. Sun J C Multivariatefourier series over a class of non tensor-product partition domainsJournal of Computational Mathematics 2003 21(1)5362
41. Sun J C Yao J F Fast generalized discrete fouriertransforms on hexagon domainsChinese Journalof Numerical Mathematics and Application 2004 26(3)351366
42. Sun J C Li H Y Generalized fourier transformon an arbitrary triangular domainAdvancesin Computational Mathematics 2005 22223248
43. Yao J F Sun J C HFFT on parallel dodecahedrondomains and its parallel implementationNumerical computation and computer applications 2004 4304313 (in Chinese)
44. Sun J C Multivariatefourier transform methods over simplex and super-simplex domainsJournal of Computational Mathematics 2006 24(3)305322
45. Zhang Y Q Performanceoptimizations on parallel numerical software package and study onmemory complexity. Dissertation for the Doctoral Degree.BeijingInstituteof Software, Chinese Academy of Sciences 2000
46. Zhang Y Q DRAM(h): a parallel computation model for highperformance numerical computingChineseJournal of Computers 2003 26(12)16601670
47. Zhang Y Q Chen G L Sun G Z et al.Models of parallel computation: a survey and classificationFrontiers of Computer Science in China 2007 1(2)156165
48. Zhang Y Q Sun J C Tang Z M et al.Memory complexity in high performance computingProceedings of HPC'ASIASingapore1998142151
49. Alpern B Carter L Feig E et al.The Uniform Memory Hierarchy Model of ComputationAlgorithmica 1994 12(2–3)72109
50. Culler D Karpy R Patterson D et al.LogP: towards a realistic model of parallel computationProceedings of PPoPPSan Diego 1993 112
51. Li M S Expandingthe horizons of software development processes: a 3-D integrated methodologyProceedings of SPWBeijing 2005 5467
52. Li M S Assessing3-D integrated software development processes: a new benchmarkProceedings of SPW/ProSimShanghai 2006 1538
53. Wang Q Li M S Software process management:practices in ChinaProceedings of SPWBeijing 2005 317331
54. Li M S TRISO-model:a new approach to integrated software process assessment and improvementSoftware Process: Improvement and Practice 2007 12(5)387398
55. Wang Q Xiao J Li M S et al.A process-agent construction method for softwareprocess modeling in SoftPMProceedings ofSPW/ProSimShanghai 2006 204213
56. Li N Li M S Wang Q et al.A negotiation model for the process agent in anagent-based process-centered software engineering environmentProceedings of SEKESan Francisco 2006 664669
57. Zhao X Chan K Li M S Applying agent technology to software process modelingand process-centered software engineering environmentProceedings of SACSanta Fe 2005 15291533
58. Xiao J Osterweil L J Zhang L et al.Applying little-JIL to describe process-agent knowledgein SoftPMProceedings of SPW/ProSimShanghai 2006 214221
59. Zhang L Wang Q Xiao J et al.A tool to create process-agents for OEC-SPM fromhistorical project dataProceedings of ICSPBeilinSpringer 2007 8495
60. Xiao J Osterweil L J Zhang L et al.Applying little-JIL to describe process-agent knowledgeand support project planningSoftware Process:Improvement and Practice 2007 12(5)437448
61. Li M S Yang Q Zhai J et al.On mobility of software processesProceedings of SPW/ProSimShanghai 2006 105114
62. Yang Q Li M S Wang Q et al.An algebraic approach for managing inconsistenciesin software processesProceedings of ICSPBerlin. 2007 121133
63. Yuan F Li M S Wan Z SPEM2XPDL-towards SPEM model enactmentProceedings of SERPLas vegas 2006 240245
64. Li J Li M S Wu Z et al.A SPEM-based software process metamodel for CMMJournal of Software 2005 16(8)13661377
65. Yang D Wan Y Tang Z et al.COCOMO-U: an extension of COCOMO II for cost estimationwith uncertaintyProceeding of SPW/ProSimShanghai 2006 132141
66. Yang D Boehm B Yang Y et al.Coping with the cone of uncertainty: an empiricalstudy of the SAIV process modelProceedingsof ICSPBerlinSpringer 2007 3748
67. He M Yang Y Wang Q et al.Cost estimation and analysis for government contractpricing in ChinaProceedings of ICSPBerlinSpringer 2007 134146
68. Wang Q Jiang N Gou L et al.BSR: a statistic-based approach for establishingand refining software process performance baselineProceedings of ICSEShanghai 2006 585594
69. Wang Q Li M S Measuring and improving softwareprocess in ChinaProceedings of ISESENoosa Heads 2005 183192
70. Wang Q Li M S Liu X An active measurement model for software process controland improvementJournal of Software 2005 16(3)407418
71. Ruan L Wang Y Wang Q et al.ARIMAmmse: an improved ARIMA-based software productivityprediction methodProceedings of COMPSACChicago 2006 1721
72. Ruan L Wang Y Wang Q et al.Empirical study on benchmarking software developmenttasksthe International Conference on SoftwareProcessMinneapolis 2007 221232
73. Zhang S Wang Y Yuan F et al.Mining software repositories to understand the performanceof individual developersProceedings ofCOMPSAC 2007Beijing 2007 625626
74. Zhang S Wang Y Tong J et al.Evaluation of project quality: a DEA-based approachProceedings of SPW/ProSim. 2005 8896
75. Wang J Li M S A tridimensional requirementsmodel and its support for stakeholder coordinationJournal of Software 2007 18(10)23802392
76. Shu F Zhao Y Wang J et al.User-driven requirements elicitation method withthe support of personalized domain knowledgeComputer Research and Development 2007 44(6)10441052
77. Huang M Shu F Li M S A risk-driven method for prioritizing requirements in iterationdevelopmentJournal of Software 2006 17(12)24502460
78. Li M S Huang M Shu F et al.A risk-driven method for extreme programming releaseplanningProceedings of ICSE 2006Shanghai 2006 423430
79. Huang T Ding X N Wei J An application-semantics-based relaxed transaction modelfor internetwareScience in China SeriesF 2006 49(6)774791
80. Huang T Chen N J Wei J et al.OnceAS/Q: a QoS-enabled web application serverJournal of Software 2004 15(12)17871799
81. Chen H Wu E H An efficient radiosity solutionfor bump texture generationComputer Graphics 1990 24(4)125134
82. Chen H Wu E H Radiosity for furry surfacesPost F HBarth WProceedings of EUROGRAPHICSNorth-HollandElsevier SciencePublishers 1991 447457
83. Wu E H Aradiosity solution for illumination of random fractal surfacesThe Journal of Visualization and Computer Animation 1995 6(4)219229
84. Chen Y Y Sun H Q Wu E H Modeling and rendering snowy natural scenery using multi-mappingtechniquesThe Journal of Visualizationand Computer Animation 2003 14(1)2130
85. Xu Y Q Chen Y Y Lin S et al.Photo-realistic rendering of knitwear using thelumisliceProceedings of ACM SIGGRAPHNew YorkACMPress 2001 391398
86. Liu X H Wu E H Hierarchical structure withfocus criterion for rendering height fieldJournal of Computer Science and Technology 1998 13(12)18
87. Wang W C Wu E H Adaptable splatting for irregularvolume renderingComputer Graphics Forum 1999 18(4)213222
88. Wang W C Wu E H Max N A selective rendering method for data visualizationJournal of Visualization and Computer Animation 1999 10(3)123131
89. Wang W C Zhou D H Wu E H Accelerating techniques in volume rendering of irregulardataComputers and Graphics 1997 21(3)289295
90. Wu E H Liu Y Q Liu X H An improved study of real time fluid simulation on GPU(invited paper)Computer Animation and VirtualWorld 2004 15(3–4)139146
91. Liu Y Q Liu X H Wu E H Real-time 3D fluid simulation on GPU with complex obstaclesProceedings of Pacific GraphicsSeoulIEEE Computer Society 2004 247256
92. Liu Y Q Liu X H Wu E H Fluid simulations on GPU with complex boundary conditionsProceedings of Poster Workshop on GPGPU, at ACM SIGGRAPG 2004
93. Liu Y Q Zhu H B Liu X H et al.Real time simulation of physically based on-surfaceflowThe Visual Computer 2005 21(8–10)727734
94. Zhu H B Liu X H Liu Y Q et al.Simulation of miscible binary mixtures based onlattice boltzmann methodComputer Animationand Virtual Worlds 2006 17(3–4)403411
95. Wu E H Zhu H B Liu X H et al.Physically based fluid dynamics and interactionsProceedings of CyberWorldsLausanneIEEE Computer Society 2006 313
96. Fei G Z Cai K Y Guo B N et al.An adaptive sampling scheme for out-of-core simplificationComputer Graphics Forum 2002 21(2)111119
97. Wang W C Li J Wu E H 2D point-in-polygon test by classifying edges into layersComputers and Graphics 2005 29(3)427439
98. Wang W C Li J Sun H Q et al.A layer-based representation of polyhedrons forpoint containment testsIEEE Transactionson Visualization and Computer Graphics 2007 to appear
99. Ao X Wang X G Tian F et al.Cross-modal error correction of continuous handwritingrecognition by SpeechProceedings of ACMInternational Conference on Intelligent User InterfacesHonolulu 2007 243250
100. Ao X Li J F Wang X G et al.Structuralizing digital ink for efficient selectionProceedings of ACM International Conference on IntelligentUser InterfacesSydney 2006 148153
101. Li J F Zhang X W Ao X et al.Sketch recognition with continuous feedback basedon incremental intention extractionProceedingsof ACM International Conference on Intelligent User InterfacesSan Diego 2005 145150
102. Tian F Ao X Wang H A et al.The tilt cursor: enhancing stimulus-response compatibilityby providing 3D orientation cue of penACMConference on Human Factors in Computing SystemsSan Jose 2007 303306
103. Wang W X Wang H Dai G Z et al.Visualization of large hierarchical data by circlepackingACM Conference on Human Factorsin Computing SystemsNew YorkACM Press 2006 517520
104. Xia M Maximumedge-disjoint paths problem in planar graphsCai J YCooper S BZhu HProceedings of TAMC566572
105. Zhang P Anapproximation algorithm to the k-steiner forest problemCai J YCooper S BZhu HProceedings of TAMC 2007 728737
106. Yan J Zhang J Backtracking algorithms andsearch heuristics to generate test suites for combinatorial testingProceedings of COMPSACChicagoIEEE Computer Society 2006 385394
107. Xu Z X Zhang J A test data generation toolfor unit testing of C programsProceedingsof QSIC 2006 107116
108. Shen Y D Zhang Z Yang Q Objective-oriented utility-based association miningProceedings of ICDM 2002 426433