On the security of public key cryptosystems with a double decryption mechanism

In public key encryption schemes with a double decryption mechanism (DD-PKE), decryption can be done in either of two ways: by the user owning the secret/public key pair corresponding to the ciphertext, or by a trusted party holding a sort of master secret-key. In this note we argue that the classical security notion for standard public key encryption schemes does not suffice for DD-PKE schemes, and propose a new natural definition. Additionally, we illustrate the usefulness of the new security definition by showing that a DD-PKE scheme presented in the workshop Selected Areas in Cryptography 2005 is insecure under this augmented security notion.     

A density‐based greedy algorithm for higher strength covering arrays

Algorithmic construction of software interaction test suites has focussed on pairwise coverage; less is known about the efficient construction of test suites for t‐way interactions with t≥3. This study extends an efficient density‐based algorithm for pairwise coverage to generate t‐way interaction test suites and shows that it guarantees a logarithmic upper bound on the size of the test suites as a function of the number of factors. To complement this theoretical guarantee, an implementation is outlined and some practical improvements are made. Computational comparisons with other published methods are reported. Many of the results improve upon those in the literature. However, limitations on the ability of one‐test‐at‐a‐time algorithms are also identified. Copyright © 2008 John Wiley & Sons, Ltd.     

Axioms for generalized graphs, illustrated by a Cantor–Bernstein proposition

The notion of a graph type is introduced by a collection of axioms. A graph of type (or -graph) is defined as a set of edges, of which the structure is specified by . From this, general notions of subgraph and isomorphism of -graphs are derived. A Cantor-Bernstein (CB) result for -graphs is presented as an illustration of a general proof for different types of graphs. By definition, a relation on -graphs satisfies the CB property if and imply that A and B are isomorphic. In general, the relation ‘isomorphic to a subgraph’ does not satisfy the CB property. However, requiring the subgraph to be disconnected from the remainder of the graph, a relation that satisfies the CB property is obtained. A similar result is shown for -graphs with multiple edges. Received: 25 October 1996 / 5 February 1998     

A review of: “CONNECTIVITY,COMPLEXITY, AND CATASTROPHE IN LARGE-SCALE SYSTEMS”, by John Casti. John Wiley,New York, 1979, XIII+203 pp. (Volume 7 in Wiley/IIASA International Series on Applied Systems Analysis. )

A complex large-scale system is a central subject of systems engineering. However, there is no integrated theory for it partially because it has been treated on a specialized model built for a specific purpose. This paper, in order to lay a foundation for a theory of a complex large-scale system, introduces a general definition of a complex system in the framework of the general systems theory and characterizes an interaction which is one of the most basic concepts of a complex system.

This paper shows that every interaction consists of two primitive interactions, process and system interactions and that they have some unique representations. Models of complex systems are classified according to their types of interactions and it is shown as an application of the above analysis that this classification is relative to realization of a system, that is, a model can be transformed from one type into another by restructuring its input-output pair.     

Exploiting purity for atomicity

Multithreaded programs often exhibit erroneous behavior because of unintended interactions between concurrent threads. This paper focuses on the noninterference property of atomicity. A procedure is atomic if, for every execution, there is an equivalent serial execution in which the actions of the atomic procedure are not interleaved with actions of other threads. This key property makes atomic procedures amenable to sequential reasoning techniques, which significantly facilitates subsequent validation activities such as code inspection and testing. Several existing tools verify atomicity by using commutativity of actions to show that every execution reduces to a corresponding serial execution. However, experiments with these tools have highlighted a number of interesting procedures that, while intuitively atomic, are not reducible. In this paper, we exploit the notion of pure code blocks to verify the atomicity of such irreducible procedures. If a pure block terminates normally, then its evaluation does not change the program state and, hence, these evaluation steps can be removed from the program trace before reduction. We develop a static typed-based analysis for atomicity based on this insight, and we illustrate this analysis on a number of interesting examples that could not be verified using earlier tools based purely on reduction.     

Move to get moved: a search for methods,tools and knowledge to design for expressive and rich movement-based interaction

The world is inherently meaningful for us, i.e. we perceive the world in terms of what we can do with it, and by physically interacting with it we access this meaning and express the meaning. We believe that this is the core reason and foundation for turning to movement-based interaction. ‘Interaction creates meaning’ does not only hold for users during interaction but also for designers when generating ideas and developing concepts. Therefore, we postulate that if one truly likes to design for movement-based interaction, one has to be or become an expert in movement, not just theoretically, by imagination or on paper, but by doing and experiencing while designing. In order to do so, we believe that designers need design tools, techniques, knowledge, awareness and skills that support their search for expressive, rich behaviour. Our search for this support resulted in several methods, tools and knowledge that help designers exploring, visualising and reflecting on interactions. Our developed methods and tools such as the Design Movement approach with its choreography of interaction, gestural design tools, interactive installations and interactive tangible sketching, have not only supported and inspired designers to design for movement-based interaction, but also resulted in surprising, fresh designs in comparison with the limited scope of rather uniform and traditional electronic consumer products. This paper discusses the possibilities and limitations of our approach.     

Weakly Monotonic Averaging Functions

Monotonicity with respect to all arguments is fundamental to the definition of aggregation functions. It is also a limiting property that results in many important nonmonotonic averaging functions being excluded from the theoretical framework. This work proposes a definition for weakly monotonic averaging functions, studies some properties of this class of functions, and proves that several families of important nonmonotonic means are actually weakly monotonic averaging functions. Specifically, we provide sufficient conditions for weak monotonicity of the Lehmer mean and generalized mixture operators. We establish weak monotonicity of several robust estimators of location and conditions for weak monotonicity of a large class of penalty‐based aggregation functions. These results permit a proof of the weak monotonicity of the class of spatial‐tonal filters that include important members such as the bilateral filter and anisotropic diffusion. Our concept of weak monotonicity provides a sound theoretical and practical basis by which (monotonic) aggregation functions and nonmonotonic averaging functions can be related within the same framework, allowing us to bridge the gap between these previously disparate areas of research.     

A Quasi-Metric Topology Compatible with Inclusion Monotonicity on Interval Space

It is well known that the metric topology [8] on interval space is not compatible with the interval inclusion monotonicity property in the sense that there may exist monotonic functions which are not continuous and conversely. This paper provides a quasi-metric topology for the interval space consistent with the real line topology and whose continuous functions are exactly the monotonic ones. The provided quasi-metric is not a metric only because it fails to satisfy the symmetrical property. The quoted title is due to the fact that except to the Hausdorff property of the metric-which does not fit for our point of view-the other good metric properties remain.     

A framework for the control of stable aperiodic walking in underactuated planar bipeds

This paper presents a new definition of stable walking for point-footed planar bipedal robots that is not necessarily periodic. The inspiration for the definition is the commonly-held notion of stable walking: the biped does not fall. Somewhat more formally, biped walking is shown to be stable if the trajectory of each step places the robot in a state at the end of the step for which a controller is known to exist that generates a trajectory for the next step with this same property. To make the definition useful, an algorithm is given to verify if a given controller induces stable walking in the given sense. Also given is a framework to synthesize controllers that induce stable walking. The results are illustrated on a 5-link biped ERNIE in simulation and experiment.     

Interaction interfaces in proteins via the Voronoi diagram of atoms

A protein consists of one or more chains where each chain is a linear sequence of amino acids bonded by peptide bonds. Chains in a protein interact with each other and the interaction is known to be one of the most fundamental factors which determine important physiological phenomena in the body. Hence, biologists have been investigating protein interactions since the early days of life science.While the studies on the interactions by biologists have emphasized the biological, chemical and/or physical aspects of the interactions, we approach the interactions from a geometric point of view.In this paper, we define an interaction interface using the Voronoi diagram of atoms in proteins. Based on a mathematical definition of the interaction interface, we provide a set of measures to characterize the inter- and intra-protein interactions.Given a Voronoi diagram of atoms in a protein consisting of a number of chains, we compute a geometric mid-surface, called an interaction interface, between each pair of chains in the protein. The interface consists of a set of faces where each face in the interface is a Voronoi face defined by two atoms belonging to different chains. Hence, the interface can be found in time in the worst case for m Voronoi faces in the Voronoi diagram. Then, a number of geometric and topological measures are derived from the interface to characterize the interaction.     

“She is just stupid”—Analyzing user–agent interactions in emotional game situations

A multiplayer dice game was realized which is played by two users and one embodied conversational agent. During the game, the players have to lie to each other to win the game and the longer the game commences the more probable it is that someone is lying, which creates highly emotional situations. We ran a number of evaluation studies with the system. The specific setting allows us to compare user–user interactions directly with user–agent interactions in the same game. So far, the users’ gaze behavior and the users’ verbal behavior towards one another and towards the agent have been analyzed. Gaze and verbal behavior towards the agent partly resembles patterns found in the literature for human–human interactions, partly the behavior deviates from these observations and could be interpreted as rude or impolite like continuous staring, insulting, or talking about the agent. For most of these seemingly abusive behaviors, a more thorough analysis reveals that they are either acceptable or present some interesting insights for improving the interaction design between users and embodied conversational agents.     

A first-order coalition logic for BDI-agents

Coalition logic (CL) enables us to model the strategic abilities and specify what a group of agents can achieve whatever the other agents do. However, some rational mental attitudes of the agents are beyond the scope of CL such as the prestigious beliefs, desires and intentions (BDI) which is an interesting and useful epistemic notion and has spawned substantial amount of studies in multi-agent systems. In this paper, we introduce a first-order coalition BDI (FCBDI) logic for multi-agent systems, which provides a semantic glue that allows the formal embedding and interaction of BDI, coalition and temporal operators in a first-order language. We further introduce a semantic model based on the interpreted system model and present an axiomatic system that is proved sound and complete with respect to the semantics. Finally, it is shown that the computational complexity of its model checking in finite structures is PSPACE-complete.     

An Integrated Approach for the Specification and Analysis of Stochastic Real-Time Systems

The usage of process algebras for the performance modeling and evaluation of concurrent systems turned out to be convenient due to their feature of compositionality. A particularly simple and elegant solution in this field is the calculus of Interactive Markov Chains (IMCs), where the behavior of processes is just represented by Continuous Time Markov Chains extended with action transitions representing process interaction. The main advantage of IMCs with respect to other existing approaches is that a notion of bisimulation which abstracts from τ-transitions (“complete” interactions) can be defined which is a congruence. However in the original definition of the calculus of IMCs the high potentiality of compositionally minimizing the system state space given by the usage of a “weak” notion of equivalence and the elegance of the approach is somehow limited by the fact that the equivalence adopted over action transitions is a finer variant of Milner's observational congruence that distinguishes τ-divergent “Zeno” processes from non-divergent ones. In this paper we show that it is possible to reformulate the calculus of IMCs in such a way that we can just rely on simple standard observational congruence. Moreover we show that the new calculus is the first Markovian process algebra allowing for a new notion of Markovian bisimulation equivalence which is coarser than the standard one.     

Probabilistic bipartition interaction index of multiple decision criteria associated with the nonadditivity of fuzzy measures

The probabilistic simultaneous interaction index has been widely adopted to measure the interaction among the decision criteria. However, this type of indices sometimes fails to reflect the kind of interaction associated with the nonadditivity of a fuzzy measure (capacity). For example, any simultaneous interaction index of the universal set of criteria w.r.t. a strictly superadditive capacity is not always positive. The main reason is that the simultaneous interaction index generalizes the notion of value by replacing the marginal contribution of a single criterion with the marginal simultaneous interaction of criteria subset. In this paper, we reform the generalization process and replace the marginal contribution with the marginal bipartition interaction, which can better reflect the kind of interaction associated with the nonadditivity, for example, superadditivity, subadditivity, strict-superadditivity, or strict-subadditivity. We construct a family of probabilistic bipartition interaction indices of subsets of criteria and study its properties. We discuss the issue of capacity identification based on the bipartition interaction index and demonstrate that the new type of interaction index can be adopted as a feasible alternative to describing the interaction phenomenon among the decision criteria.     

Set invariance under output feedback: a set-dynamics approach

The article offers a framework to define and analyse the notion of invariance with respect to output feedback under non-parametric disturbances. The motivation is that the straightforward generalisation of the definition of invariance under state feedback to the output feedback framework, namely relying only on feedback from the output, does not yield a useful notion. Our model follows standard feedback invariance considerations with, however, a crucial modification that is needed when only an observation of the state, rather than the state itself, is available. The model incorporates information gathered by the controller during the process; this is in similarity with the observer-based dynamics model; however our framework represents the information within a set dynamics. The evolution of the resulting information sets determines invariant sets and attractors of the state dynamics. The framework in this article is discrete-time control systems. We offer an analysis of the notion with results on existence of, and convergence to, output feedback invariant sets; illustrative examples related to potentially practical feedback rules are exhibited.     

CPL: Detecting Protein Complexes by Propagating Labels on Protein-Protein Interaction Network

Proteins usually bind together to form complexes, which play an important role in cellular activities. Many graph clustering methods have been proposed to identify protein complexes by finding dense regions in protein-protein interaction networks. We present a novel framework （CPL） that detects protein complexes by propagating labels through interactions in a network, in which labels denote complex identifiers. With proper propagation in CPL, proteins in the same complex will be assigned with the same labels. CPL does not make any strong assumptions about the topological structures of the complexes, as in previous methods. Tile CPL algorithm is tested on several publicly available yeast protein-protein interaction networks and compared with several state-of-the-art methods. The results suggest that CPL performs better than the existing methods. An analysis of the functional homogeneity based on a gene ontology analysis shows that the detected complexes of CPL are highly biologically relevant.     

Logical Input Devices and Interaction

The logical input device model, as is adopted in the standardized graphics package GKS, has been an accepted basis for producing device-independent graphics systems. However, when used in highly interactive graphical applications, the logical input device model does not provide sufficient support for a number of fundamental issues inherent to interaction. This paper reopens a discussion which questions the functionality provided by the logical input device model when brought in conjunction with interaction. In particular, the logical input device model does not support the notion of input/output symmetry. CR Categories: 1.3.4 [Computer graphics]: Graphics utilities- graphics packages; 1.3.6 [Computer graphics]: Methodology and techniques- device independence, interaction techniques     

On the meta‐knowledge choquet integral and related models

Choquet integral and multistep Choquet integrals have been used in recent years as models for decision making and information aggregation. Such models can be used to fuse information when information sources are not independent. A basic property of such models is that their output is monotonically increasing with respect to inputs. In this article we study two alternative models built on the basis of such Choquet integrals. The motivation is, on the one hand, to study the modeling capabilities of such operators and, on the other, to build models that are capable of approximating any arbitrary functions (not only monotonic ones). In this article we describe and study two models that are universal approximators. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 1017–1036, 2005.     

Greatest Bisimulations for Binary Methods

In previous work [14] I introduced a generalised notion of coalgebra that is capable of modelling binary methods as they occur in object-oriented programming. An important problem with this generalisation is that bisimulations are not closed under union and that a greatest bisimulation does not exists in general. There are two possible approaches to improve this situation: First, to strengthen the definition of bisimulation, and second, to place constraints on the coalgebras (i.e., on the behaviour of the binary methods). In this paper I combine both approaches to show that (under reasonable assumptions) the greatest bisimulation does exist for all coalgebras of extended polynomial functors.