Formulating the template ILP consistency problem as a constraint satisfaction problem

Inductive Logic Programming (ILP) deals with the problem of finding a hypothesis covering positive examples and excluding negative examples, where both hypotheses and examples are expressed in first-order logic. In this paper we employ constraint satisfaction techniques to model and solve a problem known as template ILP consistency, which assumes that the structure of a hypothesis is known and the task is to find unification of the contained variables. In particular, we present a constraint model with index variables accompanied by a Boolean model to strengthen inference and hence improve efficiency. The efficiency of models is demonstrated experimentally.     

The Price of Anarchy in Network Creation Games Is (Mostly) Constant

We study the price of anarchy and the structure of equilibria in network creation games. A network creation game is played by n players {1,2,…,n}, each identified with a vertex of a graph (network), where the strategy of player i, i=1,…,n, is to build some edges adjacent to i. The cost of building an edge is α>0, a fixed parameter of the game. The goal of every player is to minimize its creation cost plus its usage cost. The creation cost of player i is α times the number of built edges. In the SumGame variant, the usage cost of player i is the sum of distances from i to every node of the resulting graph. In the MaxGame variant, the usage cost is the eccentricity of i in the resulting graph of the game. In this paper we improve previously known bounds on the price of anarchy of the game (of both variants) for various ranges of α, and give new insights into the structure of equilibria for various values of α. The two main results of the paper show that for α>273?n all equilibria in SumGame are trees and thus the price of anarchy is constant, and that for α>129 all equilibria in MaxGame are trees and the price of anarchy is constant. For SumGame this answers (almost completely) one of the fundamental open problems in the field—is price of anarchy of the network creation game constant for all values of α?—in an affirmative way, up to a tiny range of α.     

Braess’s Paradox for Flows over Time

We study the properties of Braess’s paradox in the context of the model of congestion games with flow over time introduced by Koch and Skutella. We compare them to the well known properties of Braess’s paradox for Wardrop’s model of games with static flows. We show that there are networks which do not admit Braess’s paradox in Wardrop’s model, but which admit it in the model with flow over time. Moreover, there is a topology that admits a much more severe Braess’s ratio for this model. Further, despite its symmetry for games with static flow, we show that Braess’s paradox is not symmetric for flows over time. We illustrate that there are network topologies which exhibit Braess’s paradox, but for which the transpose does not. Finally, we conjecture a necessary and sufficient condition of existence of Braess’s paradox in a network, and prove the condition of existence of the paradox either in the network or in its transpose.     

Tensor Clustering for Rendering Many‐Light Animations

Rendering animations of scenes with deformable objects, camera motion, and complex illumination, including indirect lighting and arbitrary shading, is a long‐standing challenge. Prior work has shown that complex lighting can be accurately approximated by a large collection of point lights. In this formulation, rendering of animation sequences becomes the problem of efficiently shading many surface samples from many lights across several frames. This paper presents a tensor formulation of the animated many‐light problem, where each element of the tensor expresses the contribution of one light to one pixel in one frame. We sparsely sample rows and columns of the tensor, and introduce a clustering algorithm to select a small number of representative lights to efficiently approximate the animation. Our algorithm achieves efficiency by reusing representatives across frames, while minimizing temporal flicker. We demonstrate our algorithm in a variety of scenes that include deformable objects, complex illumination and arbitrary shading and show that a surprisingly small number of representative lights is sufficient for high quality rendering. We believe out algorithm will find practical use in applications that require fast previews of complex animation.     

An integral system‐ergonomic approach for IT‐based process management in complex work environments by example of manufacturing and health care

Recent trends in manufacturing and health care move these two work systems closer together from a system ergonomics point of view. Individual treatment of products, especially patients, by specialists in a distributed environment demand information technology (IT)‐based support suitable for complex systems. IT‐based support of processes in complex systems is difficult due to the lack of standard processes. IT support also means to rethink processes to use efficiency potentials. Close cooperation of users and software developers is needed to increase the ergonomic quality of the system. Therefore, suitable tools are needed: UML is available as the standard industry modeling language, Zope/Plone as the quasi‐standard for content management systems, SimPy as an object‐oriented simulation tool for event‐triggered processes, and ACT‐R as a powerful cognitive architecture for simulation of human information processes. The integration of these tools enables system‐ergonomic support of processes in the complex work system as well as of the development and deployment process. It is the base of an integral system‐ergonomic approach for IT‐based process management. Knowledge gained during process analysis either enters models or leads to the extension and adaptation of the tool chain. The models serve as basis for discussion among system ergonomists, programmers, and specialists from the work system. Further, they are understood by simulation and process support tools. Transcoding efforts between humans with different professional backgrounds and machines are reduced, and the flexibility demanded by complex systems is met. © 2008 Wiley Periodicals, Inc.     

Study on the electrical conductivity and morphology of porous polypyrrole layers prepared electrochemically in the presence of pyridinium chlorochromate

The electrical conductivity and morphology of thick (up to 3 mm) porous polypyrrole (PPy) layers produced electrochemically from pyrrole in acetonitrile (ACN) solutions have been studied. The electrical conductivity of pressed porous layers ranges from 1 to 10 Scm^–1, which is about one order of magnitude less than that in films which were prepared under similar conditions but without PnClCr. Analysis of the temperature dependence of conductivity has confirmed the major role of hopping in relation to tunnelling in charge transport inside the PPy layers even at lower temperatures. Scanning electron microscopy (SEM) showed a globular structure, which is different from the usual cauliflower-like structure of PPy films prepared without any oxidizing agent. Globular particles of about 1–3 m diameter have been found under a thin smooth crust on the electrode side of the sample. Globular particles form linked chain-like or larger round formations poorly filling the space. Closely packed fibrils of about 20 nm diameter and over 100 nm in length were found inside the aggregates.     

A variable-precision square root implementation for field programmable gate arrays

Applications requiring variable-precision arithmetic often rely on software implementations because custom hardware is either unavailable or too costly to build. By using the flexibility of the Xilinx XC4010 field programmable gate arrays, we present a hardware implementation of square root that is easily tailored to any desired precision. Our design consists of three types of modules: a control logic module, a data path module to extend the precision in 4-bit increments, and an interface module to span multiple chips. Our data path design avoids the common problem of large fan-out delay in the critical path. Cycle time is independent of precision, and operation latency can be independent of interchip communication delays.Notation S_j square root digit of weight 2^–j - S _j {–1, 0, 1} - S[j] computed square root value as of stepj - S _j ^s sign bit in the representation ofS _j in sign and magnitude form - S _j ^m magnitude bit in the representation ofS _j in sign and magnitude form - w[j] residual at stepj in two's complement carry-save representation - a sum vector in the carry-save representation of 2w[j] - b carry vector in the carry-save representation of 2w[j] - a _i bit of weight 2^–i in the sum vector,a - b_i bit of weight 2^–i in the carry vector,b - T[j]=–S[j – 1]s_j – s _j ² 2^–(j+1) T _i bit of weight 2^–i inT     

State of the Art of Molecular Visualization in Immersive Virtual Environments

Visualization plays a crucial role in molecular and structural biology. It has been successfully applied to a variety of tasks, including structural analysis and interactive drug design. While some of the challenges in this area can be overcome with more advanced visualization and interaction techniques, others are challenging primarily due to the limitations of the hardware devices used to interact with the visualized content. Consequently, visualization researchers are increasingly trying to take advantage of new technologies to facilitate the work of domain scientists. Some typical problems associated with classic 2D interfaces, such as regular desktop computers, are a lack of natural spatial understanding and interaction, and a limited field of view. These problems could be solved by immersive virtual environments and corresponding hardware, such as virtual reality head-mounted displays. Thus, researchers are investigating the potential of immersive virtual environments in the field of molecular visualization. There is already a body of work ranging from educational approaches to protein visualization to applications for collaborative drug design. This review focuses on molecular visualization in immersive virtual environments as a whole, aiming to cover this area comprehensively. We divide the existing papers into different groups based on their application areas, and types of tasks performed. Furthermore, we also include a list of available software tools. We conclude the report with a discussion of potential future research on molecular visualization in immersive environments.