A Behavioural Pseudometric based on λ–Bisimilarity

In order to describe approximate equivalence among processes, the notions of λ–bisimilarity and behavioural pseudometric have been introduced by Ying and van Breugel respectively. Van Breugel provides a distance function induced by λ–bisimilarity, and conjectures that his behavioural pseudometric coincides with this function. This paper is inspired by this conjecture. We give a negative answer for van Breugel's conjecture first. Moreover, we show that the distance function induced by λ–bisimilarity is a pseudometric on states, and provide a fixed point characterization of this pseudometric.     

Fast solution of large N×N matrix equations in an MIMD–SIMD Hybrid System

In this paper, we propose a new high-speed computation algorithm for solving a large N×N matrix system using the MIMD–SIMD Hybrid System. The MIMD–SIMD Hybrid System (also denoted as Hybrid System in this paper) is a new parallel architecture consisting of a combination of Cluster of Workstations (COWs) and SIMD systems working concurrently to produce an optimal parallel computation. We first introduce our prototype SIMD system and our Hybrid System setup before presenting how it can be implemented to find the unknowns in a large N×N linear matrix equation system using the Gauss–LU algorithm. This algorithm basically performs the ‘Divide and Conquer’ approach by breaking down the large N×N matrix system into a manageable 32 × 32 matrix for fast computation.     

Bicriteria approximation algorithms for scheduling problems with communications delays

We study the problem of simultaneously minimizing the makespan and the average weighted completion time for the precedence multiprocessor constrained scheduling problem with unit execution times and unit communication delays, known as the UET–UCT problem (Munier and König, Operations Research, 45(1), 145–148 (1997)). We propose a simple (16/9, 16/9)-approximation algorithm for the problem with an unrestricted number of machines. We improve our algorithm by adapting a technique first introduced by Aslam et al. (Proceedings of ACM-SODA, pp. 846–847, 1999) and provide a (1.745, 1.745)-approximate solution. For the considered scheduling problem, we prove the existence of a (1.445, 1.445)-approximate solution, improving the generic existence result of Aslam et al. (Proceedings of ACM-SODA, pp. 846–847, 1999). Also notice that our results for the case of an unrestricted number of processors hold for the more general scheduling problem with small communication delays (SCT problem), and for two other classical optimality criteria: maximum lateness and weighted lateness. Finally, we propose an approximation algorithm for the UET–UCT problem with a restricted number of processors.Research partially supported by the thematic network APPOL II (IST 2001-32007) of the European Union, the ACI-GRID2 project of the French government, and the MULT-APPROX project of the France-Berkeley Fund.     

Set multi-covering via inclusion–exclusion

Set multi-covering is a generalization of the set covering problem where each element may need to be covered more than once and thus some subset in the given family of subsets may be picked several times for minimizing the number of sets to satisfy the coverage requirement. In this paper, we propose a family of exact algorithms for the set multi-covering problem based on the inclusion–exclusion principle. The presented ESMC (Exact Set Multi-Covering) algorithm takes O^*((2t)ⁿ) time and O^*((t+1)ⁿ) space where t is the maximum value in the coverage requirement set (The O^*(f(n)) notation omits a polylog(f(n)) factor). We also propose the other three exact algorithms through different tradeoffs of the time and space complexities. To the best of our knowledge, this present paper is the first one to give exact algorithms for the set multi-covering problem with nontrivial time and space complexities. This paper can also be regarded as a generalization of the exact algorithm for the set covering problem given in [A. Björklund, T. Husfeldt, M. Koivisto, Set partitioning via inclusion–exclusion, SIAM Journal on Computing, in: FOCS 2006 (in press, special issue)].     

Speed–accuracy tradeoff in Fitts’ law tasks—on the equivalency of actual and nominal pointing precision

Pointing tasks in human–computer interaction obey certain speed–accuracy tradeoff rules. In general, the more accurate the task to be accomplished, the longer it takes and vice versa. Fitts’ law models the speed–accuracy tradeoff effect in pointing as imposed by the task parameters, through Fitts’ index of difficulty (I_d) based on the ratio of the nominal movement distance and the size of the target. Operating with different speed or accuracy biases, performers may utilize more or less area than the target specifies, introducing another subjective layer of speed–accuracy tradeoff relative to the task specification. A conventional approach to overcome the impact of the subjective layer of speed–accuracy tradeoff is to use the a posteriori “effective” pointing precision W_e in lieu of the nominal target width W. Such an approach has lacked a theoretical or empirical foundation. This study investigates the nature and the relationship of the two layers of speed–accuracy tradeoff by systematically controlling both I_d and the index of target utilization I_u in a set of four experiments. Their results show that the impacts of the two layers of speed–accuracy tradeoff are not fundamentally equivalent. The use of W_e could indeed compensate for the difference in target utilization, but not completely. More logical Fitts’ law parameter estimates can be obtained by the W_e adjustment, although its use also lowers the correlation between pointing time and the index of difficulty. The study also shows the complex interaction effect between I_d and I_u, suggesting that a simple and complete model accommodating both layers of speed–accuracy tradeoff may not exist.     

Toward the three-dimensional structure and lysophosphatidic acid binding characteristics of the LPA4/p2y9/GPR23 receptor: A homology modeling study

Lysophosphatidic acid (LPA) is a naturally occurring phospholipid that initiates a broad array of biological processes, including those involved in cell proliferation, survival and migration via activation of specific G protein-coupled receptors located on the cell surface. To date, at least five receptor subtypes (LPA_1–5) have been identified. The LPA_1–3 receptors are members of the endothelial cell differentiation gene (Edg) family. LPA₄, a member of the purinergic receptor family, and the recently identified LPA₅ are structurally distant from the canonical Edg LPA_1–3 receptors. LPA₄ and LPA₅ are linked to G_q, G_12/13 and G_s but not G_i, while LPA_1–3 all couple to G_i in addition to G_q and G_12/13. There is also evidence that LPA₄ and LPA₅ are functionally different from the Edg LPA receptors. Computational modeling has provided useful information on the structure–activity relationship (SAR) of the Edg LPA receptors. In this work, we focus on the initial analysis of the structural and ligand-binding properties of LPA₄, a prototype non-Edg LPA receptor. Three homology models of the LPA₄ receptor were developed based on the X-ray crystal structures of the ground state and photoactivated bovine rhodopsin and the recently determined human β₂-adrenergic receptor. Docking studies of LPA in the homology models were then conducted, and plausible LPA binding loci were explored. Based on these analyses, LPA is predicted to bind to LPA₄ in an orientation similar to that reported for LPA_1–3, but through a different network of hydrogen bonds. In LPA_1–3, the ligand polar head group is reported to interact with residues at positions 3.28, 3.29 and 7.36, whereas three non-conserved amino acid residues, S114(3.28), T187(EL2) and Y265(6.51), are predicted to interact with the polar head group in the LPA₄ receptor models.     

Expressing Priorities and External Probabilities in Process Algebra via Mixed Open/Closed Systems

Defining operational semantics for a process algebra is often based either on labeled transition systems that account for interaction with a context or on the so-called reduction semantics: we assume to have a representation of the whole system and we compute unlabeled reduction transitions (leading to a distribution over states in the probabilistic case). In this paper we consider mixed models with states where the system is still open (towards interaction with a context) and states where the system is already closed. The idea is that (open) parts of a system “P” can be closed via an operator “P↑G” that turns already synchronized actions whose “handle” is specified inside “G” into prioritized reduction transitions (and, therefore, states performing them into closed states). We show that we can use the operator “P↑G” to express multi-level priorities and external probabilistic choices (by assigning weights to handles inside G), and that, by considering reduction transitions as the only unobservable τ transitions, the proposed technique is compatible, for process algebra with general recursion, with both standard (probabilistic) observational congruence and a notion of equivalence which aggregates reduction transitions in a (much more aggregating) trace based manner. We also observe that the trace-based aggregated transition system can be obtained directly in operational semantics and we present the “aggregating” semantics. Finally, we discuss how the open/closed approach can be used to also express discrete and continuous (exponential probabilistic) time and we show that, in such timed contexts, the trace-based equivalence can aggregate more with respect to traditional lumping based equivalences over Markov Chains.     

Electrical and photoelectrical characterizations of isotype GaAs15P85/GaP heterojunctions prepared by liquid phase epitaxy

The present work deals with the electrical and optoelectronic characterizations of the isotype GaAs₁₅P₈₅/GaP devices prepared by liquid phase epitaxy. The electrical properties of the fabricated junction were studied by analyzing its current–voltage (I–V) characteristics, capacitance–voltage (C–V) characteristics in the dark at different temperatures in the range of 300–450 K. The analysis of dark current–voltage (I–V) characteristics at different temperatures were presented in order to elucidate the conduction mechanism and to evaluate the important device parameters. The predominant charge transport mechanism in these devices was found to be thermionic emission in the depletion layer and over the barrier of GaAs₁₅P₈₅/GaP heterojunction at forward bias voltage. From the capacitance–voltage, measurements at high frequency (1 MHz) information can be obtained about the carrier concentration, the diffusion potential, the barrier height of GaAs₁₅P₈₅/GaP heterojunction. The current–voltage characteristics of the GaAs₁₅P₈₅/GaP heterojunction under different illumination intensities were studied. The power low dependence of the reverse current voltage is characterized by space charge limited conduction, SCLC dominated by exponential trap distribution at the higher reverse voltage region.     

Calculating the Galois Group of Y′ = = = AY + + + B,Y′ = = = AY Completely Reducible

We consider a special case of the problem of computing the Galois group of a system of linear ordinary differential equations Y′ = MY, M C (x)^{n × n}. We assume that C is a computable, characteristic-zero, algebraically closed constant field with a factorization algorithm. There exists a decision procedure, due to Compoint and Singer, to compute the group in case the system is completely reducible. Berman and Singer (1999, J. Pure Appl. Algebr., 139, 3–23) address the case in which M = [yjsco5390x.gif M 1 * 0 M 2 ], Y′ = M_iY completely reducible for i = 1, 2. Their article shows how to reduce that case to the case of an inhomogeneous system Y′ = AY + B, A C (x)^{n × n}, B C (x)ⁿ, Y′ = AY completely reducible. Their article further presents a decision procedure to reduce this inhomogeneous case to the case of the associated homogeneous system Y′ = AY. The latter reduction involves using a cyclic-vector algorithm to find an equivalent inhomogeneous scalar equation L(y) = b,L C(x)[ D ], b C (x), then computing a certain set of factorizations of L in C(x)[D ]; this set is very large and difficult to compute in general. In this article, we give a new and more efficient algorithm to reduce the case of a system Y′ = AY + B,Y′ = AY completely reducible, to that of the associated homogeneous systemY′ = AY. The new method’s improved efficiency comes from replacing the large set of factorizations required by the Berman–Singer method with a single block-diagonal decomposition of the coefficient matrix satisfying certain properties.     

Fidelity of Gaussian Channels

A noisy Gaussian channel is defined as a channel in which an input field mode is subjected to random Gaussian displacements in phase space. We introduce the quantum fidelity of a Gaussian channel for pure and mixed input states, and we derive a universal scaling law of the fidelity for pure initial states. We also find the maximum fidelity of a Gaussian channel over all input states. Quantum cloning and continuous-variable teleportation are presented as physical examples of Gaussian channels to which the fidelity results can be applied.Presented at the 36th Symposium on Mathematical Physics, “Open Systems & Quantum Information”, Toruń, Poland, June 9–12, 2004.Supported in part by US O.ce of Naval Research Grant No. N00014–03–1–0426.Supported in part by KBN Grant No. PBZ–Min–008/P03/03     

A critical thermodynamic assessment of the Mg–Ni, Ni–Y binary and Mg–Ni–Y ternary systems

A thorough review and critical evaluation of phase equilibria and thermodynamic data for the phases in the Mg–Ni–Y ternary system have been carried out over the entire composition range from room temperature to above the liquidus. This system is being modeled for the first time using the modified quasichemical model which considers the presence of short range ordering in the liquid. The Gibbs energies of the different phases have been modeled, and optimized model parameters that reproduce all the experimental data simultaneously within experimental error limits have been obtained. For the liquid phases, the modified quasichemical model is applied. A sublattice model within the compound-energy formalism is used to take proper account of the structures of the binary intermediate solid solutions. The Mg–Ni and Ni–Y binary systems have been re-optimized based on the experimental phase equilibrium and thermodynamic data available in the literature. The optimized thermodynamic parameters for the Mg–Y system are taken from the previous thermodynamic assessment of the Mg–Cu–Y system by the same authors. The constructed database has been used to calculate liquidus projection, isothermal and vertical sections which are compared with the available experimental information on this system. The current calculations are in a good agreement with the experimental data reported in the literature.     

Behind Fitts’ law: kinematic patterns in goal-directed movements

Half a century ago, Paul Fitts first discovered that the time necessary to complete a pointing movement (MT) linearly increases with the amount of information (ID) necessary to specify the target width (W) relative to the distance (D). The so-called Fitts’ law states that , with ID being a logarithmic function of the D/W ratio. With the rising importance of pointing in human–computer interaction, Fitts’ law is nowadays an important tool for the quantitative evaluation of user interface design. We show that changes in ID give rise to systematic changes in the kinematics patterns that determine MT, and provide evidence that the observed patterns result from the interplay between basic oscillatory motion and visual control processes. We also emphasize the generality and abstract nature of Fitts’ robust model of human psychomotor behavior, and suggest that some adaptations in the design of the (computer-mediated) coupling of perception and production of movement might improve the efficiency of the interaction.     

A VLSI system architecture for high-speed radiative transfer 3D image synthesis

In this paper we describe a VLSI system architecture for high-speed synthesis of 3D images composed of diffusely reflective surfaces. The system consists of two loosely coupled sub-systems. The first sub-system computes the form-factor matrixF. The form-factors are computed by an efficient ray-tracing algorithm. The second sub-system, a multiprocessor Gauss-Seidel iterative system solver, solves the sparse system of radiosity equations(I–F)b=e.This work has been supported by the Dutch National Applied Science Foundation under grant STW DEL 47.0643This article is the second part of the Special Feature onGraphics Hardware, guest-edited by T. Nakamura. (For the first part, see The Visual Computer 4:175–221)     

ZENTURIO: A Grid Service-Based Tool for Optimising Parallel and Grid Applications

ZENTURIO [R. Prodan and T. Fahringer, ZENTURIO: A Grid Middleware-based Tool for Experiment Management of Parallel and Distributed Applications, Journal of Parallel and Distributed Computing, 2003. http://authors.elsevier.com/sd/article/S0743731503001977 (to appear)] is a semi-automatic experiment management tool for performance and parameter studies of parallel and distributed applications on cluster and Grid architectures. ZENTURIO has been designed as an Open Grid Services Architecture (OGSA) – compliant Grid application built on top of standard Web and Grid services technologies. In this paper we first comparatively present various issues from our transition to an Open Grid Services Infrastructure (OGSI) – compliant prototype. Then we introduce a generic framework for solving NP-complete optimisation problems for parallel and Grid applications. We present a case study on high throughput scheduling for large sets of computational tasks on the Grid using genetic algorithms. Our algorithm has a complexity of and delivers a fivefold improvement in solution over 500 generations in a Grid with uniformly distributed computational resources. This research is supported by the Austrian Science Fund as part of the Aurora project under contract SFBF1104.     

“ExTherm 2 ”: An interactive support package of experimental and computational thermodynamics

“ExTherm 2” shows clear advances over ExTHERM as presented in [J. Tomiska, CALPHAD 26 (2002) 143–154]: All three parts have been improved in powerfulness, comfort, and interactive work. Especially the module cM3_ is now designed for interactive evaluation by means of an overall best fit technique applicable on experimental data from calorimetric and vapor pressure measurements as well as from measurements on the electromotive force (emf) on all types of metal alloy. The new data bank module cM1_(ETD/ ExP/ PhD) is an easy-to-handle tool for interactive work in many applications in physical chemistry. The data bank ETD has been enlarged by a series of new molar mixing properties of all types of metal alloy systems, and two sub-modules are added: The first tool, ExP, makes extrapolating binary data to a high number of ternary systems of all types of metal alloy possible. And the second tool, PhD, is designed for simple interactive computations on binary phase diagrams, especially for education items.     

Analysis of interface states of metal–insulator–semiconductor photodiode with n-type silicon by conductance technique

A metal–insulator–semiconductor photodiode (MIS-PD) as active layer with n-type silicon as interdigitated Schottky electrodes has been fabricated. The current–voltage characteristics, density of interface states and photovoltaic properties of the MIS-PD diode have been investigated. The diode has a metal–insulator–semiconductor configuration with ideality factor higher than unity. The electronic parameters (ideality factor, series resistance and barrier height) of the diode were found to be 1.94, 2.23 × 10⁴ Ω and 0.74, respectively. At voltages between 0.13 and 0.50 V, the charge transport mechanism of the diode is controlled by space charge-limited current mechanism. The interface state density of the diode was found to vary from 5.54 × 10¹² to 5.67 × 10¹² eV⁻¹ cm⁻² with bias voltage. The Au/SiO₂/n-Si/Al device shows a photovoltaic behavior with a maximum open circuit voltage V_oc of 97.7 mV and short-circuit current I_sc of 17.4 μA under lower illumination intensities. The obtained electronic parameters confirm that the Au/SiO₂/n-Si/Al diode is a MIS type photodiode.     

Robust Control of Discrete‐time Singular Systems via Integral Sliding Surface

In this paper, the sliding mode control for a class of uncertain discrete‐time singular system with performance constraint is studied. By taking the singular matrix E into consideration, a new type of integral sliding mode surface is firstly introduced, based on which a sufficient condition is derived to guarantee the sliding mode dynamics admissible with a given γ‐level disturbance attenuation of the unmatched disturbance. A controller law is also given to keep the system trajectory staying in a neighborhood of the ideal sliding surface. Finally, a numerical example is given to show the effectiveness of the proposed approach.