A Compact Linear Translation for Bounded Model Checking

We present a syntactic scheme for translating future-time LTL bounded model checking problems into propositional satisfiability problems. The scheme is similar in principle to the Separated Normal Form encoding proposed in [Frisch, A., D. Sheridan and T. Walsh, A fixpoint based encoding for bounded model checking, in: M.D. Aagaard and J.W. O'Leary, editors, Formal Methods in Computer-Aided Design; 4th International Conference, FMCAD 2002, Lecture Notes in Computer Science 2517 (2002), pp. 238–254] and extended to past time in [Cimatti, A., M. Roveri and D. Sheridan, Bounded verification of past LTL, in: A.J. Hu and A.K. Martin, editors, Proceedings of the 5th International Conference on Formal Methods in Computer Aided Design (FMCAD 2004), Lecture Notes in Computer Science (2004)]: an initial phase involves putting LTL formulae into a normal form based on linear-time fixpoint characterisations of temporal operators.As with [Cimatti, A., M. Roveri and D. Sheridan, Bounded verification of past LTL, in: A.J. Hu and A.K. Martin, editors, Proceedings of the 5th International Conference on Formal Methods in Computer Aided Design (FMCAD 2004), Lecture Notes in Computer Science (2004)] and [Latvala, T., A. Biere, K. Heljanko and T. Junttila, Simple bounded LTL model checking, in: Formal Methods in Computer-Aided Design; 5th International Conference, FMCAD 2004, Lecture Notes in Computer Science 3312 (2004), pp. 186–200], the size of propositional formulae produced is linear in the model checking bound, but the constant of proportionality appears to be lower.A denotational approach is taken in the presentation which is significantly more rigorous than that in [Frisch, A., D. Sheridan and T. Walsh, A fixpoint based encoding for bounded model checking, in: M.D. Aagaard and J.W. O'Leary, editors, Formal Methods in Computer-Aided Design; 4th International Conference, FMCAD 2002, Lecture Notes in Computer Science 2517 (2002), pp. 238–254] and [Cimatti, A., M. Roveri and D. Sheridan, Bounded verification of past LTL, in: A.J. Hu and A.K. Martin, editors, Proceedings of the 5th International Conference on Formal Methods in Computer Aided Design (FMCAD 2004), Lecture Notes in Computer Science (2004)], and which provides an elegant alternative way of viewing fixpoint based translations in [Latvala, T., A. Biere, K. Heljanko and T. Junttila, Simple bounded LTL model checking, in: Formal Methods in Computer-Aided Design; 5th International Conference, FMCAD 2004, Lecture Notes in Computer Science 3312 (2004), pp. 186–200] and [Biere, A., A. Cimatti, E. M. Clarke, O. Strichman and Y. Zhu, Bounded model checking, Advances in Computers 58 (2003)].     

Book Reviews

Strasser, W., Klein, R. and Rau, R. (editors). Geometric Modelling: Theory and Practice
Schonhut, Jurgen. Document Imaging: Computer Meets Press
Stocker, Gerfried and Schopf, Christine (editors). Fleshfactor: Informationsmaschine Mensch
McCullough, Malcolm. Abstracting Craft: The Practiced Digital Hand
O'Quinn, Donnie and Leclair, Matt. Photoshop in a Nutshell
Merz, Thomas. PostScript and Acrobat/PDF
Strothotte, Thomas and Strothotte, Christine. Seeing between the Pixels: Pictures in Interactive Systems     

Book Reviews

Books reviewed:
Maeda, John. Design by Numbers
Knuth, Donald E. Digital Typography
Farin, G., Bieri, H., Brunnet, G. and Derose, T. (Editors). Geometric Modelling
Knudson, Jonathan. Java 2D Graphics
Hege, H.-C. and Polthier, K. (Editors). Mathematical Visualization
Pickover, Clifford (Editor). Chaos and Fractals: A Computer Graphical Journey
Flake, Gary William. The Computational Beauty of Nature: Computer Explorations of Fractals, Chaos, Complex Systems and Adaptation
Strothotte, Thomas. Computational Visualization, Graphics, Abstraction and Interactivity
Russ, John C. The Image Processing Handbook (3rd edition)     

The Study on the Competence of Digital Publishing Editors under the Tools of Change： From the Functional Analysis Viewpoint

The aims of the study were to understand the required skills for the digital publishing editors in a technology-driven publishing industry. The study used document analysis, literature analysis and expert interviews combined with the Delphi Technique to explore the required competences for digital publishing editors. The study adopted the functional analysis to establish the Competence Framework for digital publishing editors. The result of Delphi Technique questionnaire from a panel of selected experts in the five modalities ranged from 1 （not important at all） to 5 （very important） for the competences; For those with the mean value （,u） greater than 3.35, the competences were categorized into ＂must-have＂ （μ≥4.19） and ＂should-have＂ （3.35 ≤μ〈 4.19） groups. Fundamental Technology, Developing Digital Contents, Fundamental Knowledge, Commissioning-and-Acquisitions and Feedbacks were ＂must-have＂ competences; Design Digital Contents, Proofreading, Devices, Copy Editing, Substantive Editing, Project Management, Data Management, Promotions and Readers were ＂should-have＂ competences. This study results could provide some valuable references for the educators and learners of digital publishing related fields, help to assist with curriculum design and assessment, select and train students. It also can be used by the Digital Publishing Industry as standards in recruitment, training and evaluations of editors.     

Commerce by Any Other Name

D.F. Aldrich, Mastering the Digital Marketplace: Practical Strategies for Competitiveness in the New Economy, New York, NY: Wiley (2000) 309 pp.

R. Kalakota and M. Robinson, e-Business: Roadmap for Success, Reading, MA: Addison-Wesley (1999) 378 pp.

R. Murch and T. Johnson, Intelligent Software Agents, Upper Saddle River, NJ: Prentice Hall PTR, (1999) 210 pp.

R. T. Watson, P. Berthon, L.F. Pitt, and G.M. Zinkhan, Electronic Commerce: the Strategic Perspective, Ft. Worth, TX: the Dryden Press (2000) 162 pp.

J. Christopher Westland and T.K.H. Clark, Global Electronic Commerce: Theory and Cases, Cambridge, MA: MIT Press (2000) 585 pp.     

Conservation properties of a new unstructured staggered scheme

In Wenneker et al. [Computation of compressible flows on unstructured staggered grids. In: Oñate E, Bugeda G, Suárez B, editors. Proceedings European Congress on Computational Methods in Applied Sciences and Engineering, ECCOMAS 2000, Barcelona, 11-14 September 2000, Barcelona, 2000. CIMNE. http://ta.twi.tudelft.nl/users/wesseling/pub.html] an unstructured staggered scheme for the two-dimensional (2D) Euler equations is discussed. Such a scheme cannot be in classic conservation form for momentum. The aim of the present paper is to formulate a generalized conservation form for momentum on unstructured staggered grids, and to demonstrate by numerical experiments that the scheme satisfies the Rankine-Hugoniot conditions. Numerical results for 1D Riemann problems on 2D unstructured grids confirm that the scheme converges to the entropy solution. In addition, transonic flow around an airfoil is computed.     

Book reviews

Monk, A., Diaper, D., and Harrison, M. D. (1992). People and Computers VII. 534 pages, US$69.96: Cambridge, England: Cambridge University Press. (ISBN 0–521–44591–4)

Duffy, T. M., Palmer, J. E., and Mehlenbacher, B. (1992). Online Help: Design and Evaluation. 260 pages, US$55.00 (cloth) US$26.50 (paper): Norwood, NJ: Ablex Publishing Corp. (ISBN 0–89391–848–2)     

Book Reviews

Book reviewed in this article:
Advances in Computer Graphics V Purgathofer, W., and Schiinhut, J. (editors)
An Introduction to Ray Tracing, Glassner, AS. (editor)     

Four that Belong on Your Bookshelf

T. DeMarco and T. Lister, Waltzing with Bears: Managing Risk on Software Projects, New York: Dorset House Publishing (2003), 196 pp.

M.W. Doll, S. Rai, and J. Granado, Defending the Digital Frontier: A Security Agenda, Hoboken, NJ: John Wiley & Sons (2003), 238 pp.

.J.D. McKeen and H.A. Smith, Making IT Happen: Critical Issues in IT Management, Chichester, UK: Wiley (2003), 366 pp.

D.J. Power, Decision Support Systems: Concepts and Resources for Managers, Westport, CT: Quorum (2002), 251 pp.     

The two faces of high-level synthesis

Reviewed in this issue High-Level Synthesis: From Algorithm to Digital Circuit, edited by Philippe Coussy and Adam Morawiec (Springer, 2008, ISBN: 978-1-4020-8587-1, 300 pp., $129).     

Evolution of supra-glacial lakes across the Greenland Ice Sheet

We used 268 cloud-free Moderate-resolution Imaging Spectroradiometer (MODIS) images from 2003 and 2005-2007 to study the seasonal evolution of supra-glacial lakes in three different regions of the Greenland Ice Sheet. Lake area estimates were obtained by developing an automated classification method for their identification based on 250 m resolution MODIS surface reflectance observations. Widespread supra-glacial lake formation and drainage is observed across the ice sheet, with a 2-3 week delay in the evolution of total supra-glacial lake area in the northern areas compared to the south-west. The onset of lake growth varies by up to one month inter-annually, and lakes form and drain at progressively higher altitudes during the melt season. A positive correlation was found between the annual peak in total lake area and modelled annual runoff. High runoff and lake extent years are generally characterised by low accumulation and high melt season temperatures, and vice versa. Our results indicate that, in a future warmer climate [Meehl, G. A., Stocker, T. F., Collins W. D., Friedlingstein, P., Gaye, A. T., Gregory, J. M., Kitoh, A., Knutti, R., Murphy, J. M., Noda, A., Raper, S. C. B., Watterson, I. G., Weaver, A. J. & Zhao, Z. C. (2007). Global Climate Projections. In: Climate Change 2007: The Physical Science Basis. Contribution of Working Group I to the Fourth Assessment Report of the Intergovernmental Panel on Climate Change Solomon, S., D. Qin, M. Manning, Z. Chen, M. Marquis, K. B. Averyt, M. Tignor & H. L. Miller (eds.), Cambridge University Press, Cambridge, United Kingdom and New York, NY, USA.], Greenland supra-glacial lakes can be expected to form at higher altitudes and over a longer time period than is presently the case, expanding the area and time period over which connections between the ice sheet surface and base may be established [Das, S., Joughin, M., Behn, M., Howat, I., King, M., Lizarralde, D., & Bhatia, M. (2008). Fracture propagation to the base of the Greenland Ice Sheet during supra-glacial lake drainage. Science, 5877, 778-781] with potential consequences for ice sheet discharge [Zwally, H.J., Abdalati, W., Herring, T., Larson, K., Saba, J. & Steffen, K. (2002). Surface melt-induced acceleration of Greenland Ice Sheet flow. Science, 297, 218-221.].     

Semantics and Verification of Data Flow in UML 2.0 Activities

One of the major changes in going from UML 1.5 to UML 2.0 is the reengineering of activity diagrams. This paper examines activity diagramies as described in the current version of the UML 2.0 standard by defining a denotational semantics. It covers basic control flow and data flow, but excludes hierarchy, expansion nodes, and exception handling (see [Störrle, H., Semantics of Control-Flow in UML 2.0 Activities, in: P. Bottoni, C. Hundhausen, S. Levialdi and G. Tortora, editors, Proc. IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC) (2004), pp. 235–242, Störrle, H., Semantics of Exceptions in UML 2.0 Activities (2004), submitted to Journal of Software and Systems Modeling, May, 9^th, available at www.pst.informatik.uni-muenchen.de/~stoerrle, Störrle, H., Semantics of Expansion Nodes in UML 2.0 Activities, in: I. Porres, editor, Proc. 2^nd Nordic Ws. on UML, Modeling, Methods and Tools (NWUML'04), 2004] for these issues). The paper shows, where the constructs proposed in the standard are not so easily formalized, and how the formalisation may be used for formal analysis.     

A practical look at ATPG

Book Reviewed: Digital Logic Testing and Simulation, 2nd edition, by Alexander Miczo (Wiley-Interscience, 2003, ISBN 0-471-43995-9, 696 pp., $115).     

DOI在数据引用中的应用:问题与建议

数字对象唯一标识符(DOI)是为解决互联网环境下数字资源的多重链接和版权转移问题而提出的唯一标识符系统,已在图书馆和出版领域得到广泛应用。数字对象唯一标识符也可用于科学数据共享,具有跟踪价值、引用价值、集成价值和互联价值。基于DOI的数据引用是推动数据出版的重要环节,由于数据知识产权信息不清晰、数据引用标准不规范,基于DOI的数据引用在国内并没有得到有效推广。建议数据中心、DOI注册代理中心和期刊编辑部加强合作,DOI注册中心明确数据DOI注册与数据出版的区别,建立类似DataCite的数据出版机构,允许所有类型数据注册DOI,将符合数据出版和数据引用的科学数据引文信息另行集中管理。数据中心要理清数据版权信息,为符合条件的数据补充数据引用信息。期刊编辑部要引导作者在论文中规范化引用数据和标注数据。     

基于DEM的水利三维可视化系统的研究

分析了DEM（数字高程模型）技术、格网模型算法和分层设计思想,研究了水利可视化系统创作过程中数据整理、格网划分及三维要素的叠加的方法,采用分层设计的思想解决了不同比例尺下显示详细程度不同问题,从而为水利工程管理提供更形象、直观的信息     

Real-time 3D shape reconstruction, dynamic 3D mesh deformation, and high fidelity visualization for 3D video

3D video [IEEE Multimedia (1997) 18] is the ultimate image media recording dynamic visual events in the real world as is; it records time varying 3D object shape with high fidelity surface properties (i.e., color and texture). Its applications cover wide varieties of personal and social human activities: entertainment (e.g., 3D game and 3D TV), education (e.g., 3D animal picture books), sports (e.g., sport performance analysis), medicine (e.g., 3D surgery monitoring), culture (e.g., 3D archive of traditional dances), and so on. In this paper, we propose: (1) a PC cluster system for real-time reconstruction of dynamic 3D object action from multi-view video images, (2) a deformable 3D mesh model for reconstructing the accurate dynamic 3D object shape, and (3) an algorithm of rendering natural-looking texture on the 3D object surface from the multi-view video images. Experimental results with quantitative performance evaluations demonstrate the effectiveness of these methods in generating high fidelity 3D video from multi-view video images.     

LSC Verification for UML Models with Unbounded Creation and Destruction

The approaches to automatic formal verification of UML models known up to now require a finite bound on the number of objects existing at each point in time. In [W. Damm, B. Westphal, Live and let die: LSC-based verification of UML-models, Science of of Computer Programming 55 (2005) 117–159] we have observed that the class of hardware systems with replicated components studied by McMillan [K.L. McMillan, A methodology for hardware verification using compositional model checking, Science of Computer Programming 37 (2000) 279–309] is equivalent to the class of systems where the only source of infiniteness is unbounded creation and destruction of objects, i.e. where all data-types except for object identities are finite. Exploiting the symmetry of UML models induced by objects being instances of classes, the restriction to finite bounds can be overcome applying [K.L. McMillan, A methodology for hardware verification using compositional model checking, Science of Computer Programming 37 (2000) 279–309].In this paper we report on experiences from an evaluation of this approach within the UML Verifi- cation Environment (UVE) [I. Schinz, T. Toben, C. Mrugalla and B. Westphal, The Rhapsody UML Verification Environment, in: J.R. Cuellar and Z. Liu, editors, Proceedings SEFM 2004 (2004), pp. 174–183], a state-of-the-art tool for formal verification of UML models using Live Sequence Charts (LSC) [W. Damm, D. Harel, LSCs: Breathing Life into Message Sequence Charts, Formal Methods in System Design 19 (2001) 45–80] for requirements specification.     

Spatial structuring,cinematic mediation,and evocative narrative elements in the design of an RT 3D VE: The Common Tales Project

The practice-based research project Common Tales investigates and formulates methods of spatial structuring, cinematic mediation, and evocative narrative elements in the design of a meaningful Real Time 3-Dimensional Virtual Environment (RT 3D VE). It is a collaboration between the Digital Studios (University of Cambridge), the National Film and Television School (NFTS), and Sony Computer Entertainment Europe (SCEE), and combines the know-how of the industry partner (SCEE) with academic expertise (Digital Studios) and practical knowledge of film-making (NFTS). The unique inputs into the project of the three partners combine to provide and shape insights and outcomes impossible for any of the three individually to have produced, and provide a sound template for collaborative research.     

Interactive 3D content modeling for Digital Earth

Digital Earth is a global reference model for integrating, processing and visualizing geospatial datasets. In this reference model, various data-types, including Digital Elevation Models (DEM) and imagery (orthophotos), are universally and openly available for the entire globe. However, 3D content such as detailed terrains with features, man-made structures, 3D water bodies and 3D vegetation are not commonly available in Digital Earth. In this paper, we present an interactive system for the rapid creation and integration of these types of 3D content to augment Digital Earth. The inputs to our system include available data sources, such as DEM and imagery information depicting landscapes and urban environments. The proposed system employs sketch-based and image-assisted tools to support interactive creation of textured 3D content. For adding terrain features visible in orthophotos, and also the basin of water bodies, we use a multiscale least square surface fitting to generate an adaptive triangular subdivision. For modeling forests and vegetation, we use image-based techniques and take advantage of visible regions and colors of forests in orthophotos. For 3D man-made structures, starting from a single photograph, we provide a simple image-assisted sketching tool to extract these objects, correct for perspective distortion and place them into desired locations.     

The connotation of digital twin,and the construction and application method of shop-floor digital twin

Digital twin (DT) technology provides a novel, feasible, and clear implementation path for the realization of smart manufacturing and cyber-physical systems (CPS). Currently, DT is applied to all stages of the product lifecycle, including design, production, and service, although its application in the production stage is not yet extensive. Shop-floor digital twin (SDT) is a digital mapping model of the corresponding physical shop-floor. How to build and apply SDT has always been challenging when applying DT technology in the production phase. To address the existing problems, this paper first reviews the origin and evolution of DT, including its application status in the production stage. Then, an implementation framework for the construction and application of SDT is proposed. Three key implementation techniques are explained in detail: the five-dimensional modeling of SDT; DT-based 3D visual and real-time monitoring of shop-floor operating status; and prediction of shop-floor operating status based on SDT using Markov chain. A DT-based visual monitoring and prediction system (DT-VMPS) for shop-floor operating status is developed, and the feasibility and effectiveness of the proposed method are demonstrated through the use of an engineering case study. Finally, a summary of the contributions of the paper is given, and future research issues are discussed.