On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata

The study of the computational power of randomized computations is one of the central tasks of complexity theory. The main goal of this paper is the comparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. We investigate the power of Las Vegas computation for the complexity measures of one-way communication, ordered binary decision diagrams, and finite automata.(i) For the one-way communication complexity of two-party protocols we show that Las Vegas communication can save at most one half of the deterministic one-way communication complexity. We also present a language for which this gap is tight.(ii) The result (i) is applied to show an at most polynomial gap between determinism and Las Vegas for ordered binary decision diagrams.(iii) For the size (i.e., the number of states) of finite automata we show that the size of Las Vegas finite automata recognizing a language L is at least the square root of the size of the minimal deterministic finite automaton recognizing L. Using a specific language we verify the optimality of this lower bound.     

Ontological query answering under expressive Entity-Relationship schemata

The Entity-Relationship (ER) model is a fundamental tool for database design, recently extended and employed in knowledge representation and reasoning due to its expressiveness and comprehensibility. We address the problem of answering conjunctive queries under constraints representing schemata expressed in an extended version of the Entity-Relationship model. This extended model, called ER⁺, comprises is-a constraints among entities and relationships, plus functional and mandatory participation constraints. In particular, it allows for arbitrary permutations of the roles in is-a among relationships. A key notion that ensures high tractability in ER⁺ schemata is separability, i.e., the absence of interaction between the functional participation constraints and the other constructs of ER⁺. We provide a precise syntactic characterization of separable ER⁺ schemata by means of a necessary and sufficient condition. We present a complete complexity analysis of the conjunctive query answering problem under separable ER⁺ schemata, and also under several sublanguages of ER⁺. We show that the addition of so-called negative constraints does not increase the complexity of query answering. With such constraints, our model properly generalizes the most widely adopted tractable ontology languages, including those in the DL-Lite family.     

Analysing quadratic effects of formative constructs by means of variance-based structural equation modelling

Together with the development of information systems research, there has also been increased interest in non-linear relationships between focal constructs. This article presents six Partial Least Squares-based approaches for estimating formative constructs’ quadratic effects. In addition, these approaches’ performance is tested by means of a complex Monte Carlo experiment. The experiment reveals significant and substantial differences between the approaches. In general, the performance of the hybrid approach as suggested by Wold (1982) is most convincing in terms of point estimate accuracy, statistical power, and prediction accuracy. The two-stage approach suggested by Chin et al (1996) showed almost the same performance; differences between it and the hybrid approach – although statistically significant – were unsubstantial. Based on these results, the article provides guidelines for the analysis of non-linear effects by means of variance-based structural equation modelling.     

Mobile robot localization using a self-organized visual environment representation

Owing to the upcoming applications in the field of service robotics mobile robots are currently receiving increasing attention in industry and the scientific community. Applications in the area of service robotics demand a high degree of system autonomy, which robots without learning capabilities will not be able to meet. Learning is required in the context of action models and appropriate perception procedures. In both areas flexible adaptivity is difficult to achieve especially when high bandwidth sensors (e.g. video cameras) - which are needed in the envisioned unstructured worlds - are used. This paper proposes a new methodology for image-based navigation using a self-organized visual representation of the environment. Self-organization leads to internal representations, which can be used by the robot, but are not transparent to the user. It is shown how this conceptual gap can be bridged.     

Integrating a flexible anthropomorphic, robot hand into the control, system of a humanoid robot

This article presents the approaches taken to integrate a novel anthropomorphic robot hand into a humanoid robot. The requisites enabling such a robot hand to use everyday objects in an environment built for humans are presented. Starting from a design that resembles the human hand regarding size and movability of the mechatronical system, a low-level control system is shown providing reliable and stable controllers for single joint angles and torques, entire fingers and several coordinated fingers. Further on, the high-level control system connecting the low-level control system with the rest of the humanoid robot is presented. It provides grasp skills to the superior robot control system, coordinates movements of hand and arm and determines grasp patterns, depending on the object to grasp and the task to execute. Finally some preliminary results of the system, which is currently tested in simulations, will be presented.     

RTS-MAC: A Relative Time Synchronization MAC Protocol for Low Duty Cycle Body Sensor Networks

Emerging applications in the medical field require body sensor networks to communicate in real-time in a very energy-efficient way. An example is the Artificial Accommodation System??a set of two small active medical implants aiming at restoring accommodation of the human eye??in which sensor data have to be exchanged continuously between both eyes. To achieve energy efficiency, it is essential to operate the radios with a very low duty cycle. Therefore, idle listening and general protocol overhead must be reduced as much as possible. In this paper, we present a relative time synchronization medium access control protocol (RTS-MAC), which keeps relative time synchronization between two or more sensor nodes in a very energy-efficient manner: RTS-MAC makes use of the periodic broadcast of regular data messages and exploits the inter-arrival times to predict future arrivals within tight boundaries. Thereby, no overhead is generated for synchronization purposes, and still, idle listening is reduced to a minimum, which solely depends on the short-term accuracy of the underlying clock systems. We implemented the proposed protocol using off-the-shelf components and employed the internal low-accuracy oscillators of the microcontrollers as clock sources. Thereby, we achieved very low duty cycles close to an ideal minimum. Further, our results indicate that through omitting external crystals in favor of a minimally larger battery, the battery life of a sensor node can be prolonged.     

Regulations and research on RC&S for hydrogen storage relevant to transport and vehicle issues with special focus on composite containments

Developers interested in high pressure storage of hydrogen for mobile use increasingly rely on composite cylinders for onboard storage or transport of dangerous goods. Thus, composite materials and systems deserve special consideration. History gives interesting background information important to the understanding of the current situation as to regulations, codes and standards.