Multistep-multistage-multiderivative methods for ordinary differential equations

This paper studies a general method for the numerical integration of ordinary differential equations. The method, defined in part 1, contains many known processes as special case, such as multistep methods, Runge-Kutta methods (“multistage”), Taylor, series (“multiderivative”) and their extensions (section 2). After a short section on trees and pairs of trees we derive formulas for the conditions to be satisfied by the free parameters in order to equalize the numerical approximation with the solution up to a certain order. Next we extend the reuslts of Kastlunger [6]. The proof given here is shorter than the original one. Finally we discuss formulas, with the help of which the conditions for the parameters can be reduced considerably and give numerical examples.     

On strictly optimal schedules for the cumulative cost-optimal scheduling problem

Given a set ofn events (or jobs) which are constrained by a precedence relation, we want to order them into a totally ordered sequence (i. e., one machine schedule). Each event has an integer cost (which may be negative) associated with it, and our objective is to minimize the maximum cumulative cost within a schedule, i. e., to obtain a cumulative cost-optimal schedule. We introduce the concept of “strict optimality” and investigate properties of strictly optimal schedules. The usefulness of these schedules is demonstrated in the special case where the precedence relation is “series-parallel”. For this case we describe an algorithm which finds a cumulative cost-optimal schedule inO (n logn) time.     

Predicate control: synchronization in distributed computations with look-ahead

The predicate control problem involves synchronizing a distributed computation to maintain a given global predicate. In contrast with many popular distributed synchronization problems such as mutual exclusion, readers writers, and dining philosophers, predicate control assumes a look-ahead, so that the computation is an off-line rather than an on-line input. Predicate control is targeted towards applications such as rollback recovery, debugging, and optimistic computing, in which such computation look-ahead is natural.We define predicate control formally and show that, in its full generality, the problem is NP-complete. We find efficient solutions for some important classes of predicates including “disjunctive predicates”, “mutual exclusion predicates”, and “readers writers predicates”. For each class of predicates, we determine the necessary and sufficient conditions for solving predicate control and describe an efficient algorithm for determining a synchronization strategy. In the case of “independent mutual exclusion predicates”, we determine that predicate control is NP-complete and describe an efficient algorithm that finds a solution under certain constraints.     

Fujaba case studies for GraBaTs 2008: lessons learned

Both the authors have participated in all three case studies of the GraBaTs 2008 tool contest with the Fujaba tool. This paper reports about our solutions and the improvements we have made to the Fujaba tool suite in order to enhance performance and modeling capabilities and about the lessons we have learned from these case studies.     

Algorithm selection in bilateral negotiation

Despite the abundance of strategies in the multi-agent systems literature on repeated negotiation under incomplete information, there is no single negotiation strategy that is optimal for all possible domains. Thus, agent designers face an “algorithm selection” problem—which negotiation strategy to choose when facing a new domain and unknown opponent. Our approach to this problem is to design a “meta-agent” that predicts the performance of different negotiation strategies at run-time. We study two types of the algorithm selection problem in negotiation: In the off-line variant, an agent needs to select a negotiation strategy for a given domain but cannot switch to a different strategy once the negotiation has begun. For this case, we use supervised learning to select a negotiation strategy for a new domain that is based on predicting its performance using structural features of the domain. In the on-line variant, an agent is allowed to adapt its negotiation strategy over time. For this case, we used multi-armed bandit techniques that balance the exploration–exploitation tradeoff of different negotiation strategies. Our approach was evaluated using the GENIUS negotiation test-bed that is used for the annual international Automated Negotiation Agent Competition which represents the chief venue for evaluating the state-of-the-art multi-agent negotiation strategies. We ran extensive simulations using the test bed with all of the top-contenders from both off-line and on-line negotiation tracks of the competition. The results show that the meta-agent was able to outperform all of the finalists that were submitted to the most recent competition, and to choose the best possible agent (in retrospect) for more settings than any of the other finalists. This result was consistent for both off-line and on-line variants of the algorithm selection problem. This work has important insights for multi-agent systems designers, demonstrating that “a little learning goes a long way”, despite the inherent uncertainty associated with negotiation under incomplete information.     

Coping with uncertainty: police strategies for resilient decision-making and action implementation

This study uses a hostage negotiation setting to demonstrate how a team of strategic police officers can utilize specific coping strategies to minimize uncertainty at different stages of their decision-making in order to foster resilient decision-making to effectively manage a high-risk critical incident. The presented model extends the existing research on coping with uncertainty by (1) applying the RAWFS heuristic (Lipshitz and Strauss in Organ Behav Human Decis Process 69:149–163, 1997) of individual decision-making under uncertainty to a team critical incident decision-making domain; (2) testing the use of various coping strategies during “in situ” team decision-making by using a live simulated hostage negotiation exercise; and (3) including an additional coping strategy (“reflection-in-action”; Schön in The reflective practitioner: how professionals think in action. Temple Smith, London, 1983) that aids naturalistic team decision-making. The data for this study were derived from a videoed strategic command meeting held within a simulated live hostage training event; these video data were coded along three themes: (1) decision phase; (2) uncertainty management strategy; and (3) decision implemented or omitted. Results illustrate that, when assessing dynamic and high-risk situations, teams of police officers cope with uncertainty by relying on “reduction” strategies to seek additional information and iteratively update these assessments using “reflection-in-action” (Schön 1983) based on previous experience. They subsequently progress to a plan formulation phase and use “assumption-based reasoning” techniques in order to mentally simulate their intended courses of action (Klein et al. 2007), and identify a preferred formulated strategy through “weighing the pros and cons” of each option. In the unlikely event that uncertainty persists to the plan execution phase, it is managed by “reduction” in the form of relying on plans and standard operating procedures or by “forestalling” and intentionally deferring the decision while contingency planning for worst-case scenarios.     

Special issue on formal methods for globally asynchronous and locally synchronous (GALS) systems

This special issue is based on innovative ideas presented and discussed during the first International Workshop on Formal Methods for Globally Asynchronous and Locally Synchronous Systems (FMGALS) held in conjunction with the Formal Methods in Europe (FME) conference in Pisa, Italy, in the fall of 2003. This one-day workshop was initiated to bring together researchers in the area of formal methods, system design languages, asynchronous hardware design, and GALS design. The event was held in co-operation with ACM SIGDA and ACM SIGARCH. Since this first incarnation, another FMGALS workshop was held in Verona, Italy in 2005. A special issue for that event is already planned. One great outcome of the first workshop is that an FMGALS community has been established through a moderated mailing list. Information and research result exchanges are taking place among the various research communities who are engaged in research aimed at providing theoretical foundations of GALS design, industrial GALS design practices, and de-synchronization theory proposed by the Synchronous Programming community. Selected papers from the 2003 workshop were invited for this special issue together with an open call for papers soliciting novel contributions on the topics of this conference. Rigorous reviews of 12 submissions led to the selection of five papers. In this editorial statement, we outline the premise and the context of this special issue, and briefly introduce the papers selected.     

Verified software: theories, tools and experiments

The importance of verification for software products is being increasingly appreciated in industry, although still not to the level to make it a standard approach to high quality software in industry. Since 2005, a global initiative has been underway, started by eminent researchers in both industry and academia, with the aim of establishing and disseminating a culture of software verification from first principles by means of theories, tools and experiments. This special section contains a selection of contributions originally presented at the 2008 Workshop on Tools at VSTTE 2008, the conference on Verified Software: Theories, Tools and Experiments, in Toronto. The VSTTE series of conferences and workshops focuses on the challenge of verifying software systems. Within VSTTE, the scope of the Tools workshop are implementations and enabling techniques for program verifiers, which are important ingredients for the dissemination of principles and techniques among industrial practitioners. This special section complements a sister special section of the Journal on Formal Aspects of computing, Springer. While the FACJ papers address more foundational aspects of tool-based verification and tool construction, the present section presents two toolsets, reflections on usability for verification tools and a novel abstraction technique.     

Context-dependent software solutions to handle video synchronization and delay in collaborative live mobile video production

The advent of modern mobile phones, 3G networks, and live video streaming has made it possible to broadcast live video from mobile devices. This is now giving rise to a new class of applications which enable mobile collaborative live video production, in which groups of amateurs work together to provide a rich broadcast of events. We focus on new and expected synchronization problems that arise in these more complex systems when broadcasting live events because of the delays that often occur in streaming over internet and mobile networks. The problem has been investigated by acquiring initial user feedback, as well as conducting technical delay measurements of two examples of such systems and relating them to existing literature. We identified two types of technical problems which affect the mixing of the streams, namely the difference in delay in multiple streams, a.k.a. asynchrony among streams, and the delay between the event itself and its presentation in the mixer. These problems affect the mixing in various ways depending on whether or not the director has visual access to the unmediated event. This knowledge has then been used to inform the conceptualization of identifiable ways of handling delays and synchronization. We suggest the introduction of a software feature providing context-dependent delay, in which these requirements can be balanced differently to fit specific contexts of use. We specifically address the different types of mixing which occurs when the director, or mixer, only has access to the topic through the mobile media (“out of view”), as well as mixing in a context in which the topic also is physically present (“in-view”) in front of the mixer.     

Software diversity: state of the art and perspectives

Diversity is prevalent in modern software systems to facilitate adapting the software to customer requirements or the execution environment. Diversity has an impact on all phases of the software development process. Appropriate means and organizational structures are required to deal with the additional complexity introduced by software variability. This introductory article to the special section “Software Diversity—Modeling, Analysis and Evolution” provides an overview of the current state of the art in diverse systems development and discusses challenges and potential solutions. The article covers requirements analysis, design, implementation, verification and validation, maintenance and evolution as well as organizational aspects. It also provides an overview of the articles which are part of this special section and addresses particular issues of diverse systems development.     

Uniform random generation of expressions respecting algebraic identities

Algorithms for the uniform random generation of a particular class of formal expressions (containing arithmetical expressions, propositional calculus formulas, tree representations, special algebraic expressions and program structures) are described. “Uniform” means that all non-equivalent expressions of the same size are equiprobable, where equivalence is induced by commutative or associative properties of certain symbols (e.g.“a+b”≡“b+a”). In the special case where no commutative symbols occur, it is shown that the problem can be treated by a modification of Hickey's and Cohen's well known generation algorithm for context-free languages. In order to obtain a speed up in the generation time, a new, parallelizable algorithm is developed, which turns out to be applicable also to the general case (occurrence of commutative symbols).     

A study of the fixed points and spurious solutions of the deflation-based FastICA algorithm

The FastICA algorithm is one of the most popular algorithms in the domain of independent component analysis (ICA). Despite its success, it is observed that FastICA occasionally yields outcomes that do not correspond to any true solutions (known as demixing vectors) of the ICA problem. These outcomes are commonly referred to as spurious solutions. Although FastICA is a well-studied ICA algorithm, the occurrence of spurious solutions is not yet completely understood by the ICA community. In this contribution, we aim at addressing this issue. In the first part of this work, we are interested in characterizing the relationship between demixing vectors, local optimizers of the contrast function and (attractive or unattractive) fixed points of FastICA algorithm. We will show that there exists an inclusion relationship between these sets. In the second part, we investigate the possible scenarios where spurious solutions occur. It will be shown that when certain bimodal Gaussian mixture distributions are involved, there may exist spurious solutions that are attractive fixed points of FastICA. In this case, popular nonlinearities such as “Gauss” or “tanh” tend to yield spurious solutions, whereas “kurtosis” gives much more reliable results.

     

Case systems for natural language

In many languages (e.g. Latin, Greek, Russian, Turkish, German) the relationship of a noun phrase to the rest of a sentence is indicated by altered forms of the noun. The possible relationships are called (surface) “cases”. Because (1) it is difficult to specify semantic-free selection rules for the cases, and (2) related phenomena based on prepositions or word order appear in apparently case-less languages, many have argued that studies of cases should focus on meaning, i.e. on “deep cases”.Deep cases bear a close relationship to the modifiers of a concept. In fact, one could consider a deep case to be a special, or distinguishing, modifier. Several criteria for recognizing deep cases are considered here in the context of the problem of describing an event. Unfortunately, none of the criteria serves as a completely adequate decision procedure. A notion based on the context-dependent “importance” of a relation appears as useful as any rule for selecting deep cases.A representative sample of proposed case systems is examined. Issues such as surface versus deep versus conceptual levels of cases, and the efficiency of the representations implicit in a case system are also discussed.     

Relation-algebraic specification and solution of special university timetabling problems

In this paper, we are concerned with a special timetabling problem. It was posed to us by the administration of our university and stems from the adoption of the British-American system of university education in Germany. This change led to the concrete task of constructing a timetable that enables the undergraduate education of secondary school teachers within three years in the “normal case” and within four years in the case of exceptional combinations of subjects. We develop two relation-algebraic models of the timetabling problem and in each case algorithms for computing solutions. The latter easily can be implemented in the Kiel RelView tool showing that RelView can be used for timetabling.     

Report on the 7th International Conference on Autonomous Infrastructure,Management, and Security (AIMS 2013): Emerging Management Mechanisms for the Future Internet

This article contains the report on AIMS 2013, which was held on June 25–28, 2013 at the Universitat Politècnica de Catalunya (UPC), Spain and was driven by the theme “Emerging Management Mechanisms for the Future Internet”. It covers the three main parts that formed the event program: the keynote and technical sessions of the main track, the PhD workshop and the hands-on tutorials. Finally, the report highlights the evolutions that would shape the future version of AIMS.     

The effects of trust and constructive controversy on student achievement and attitude in online cooperative learning environments

This study investigated the effects of trust and constructive controversy on student achievement and attitude in online cooperative learning environments. Students in one university course were randomly assigned to one of the two treatment groups after they took part in a common initial workshop on general cooperative learning skills. The “trust” and the “constructive controversy” groups received subsequent associated skills training. The overall results indicated that after each group received the treatment during online cooperative group activities, the “trust” groups had significantly higher achievement than the “constructive controversy” groups. In addition, the “trust” groups had significantly more positive attitudes toward online cooperative learning than the “constructive controversy” groups. Specifically, using “trust” building strategies was significantly more effective than using “constructive controversy” strategies for improving the ‘openness and sharing’ and ‘acceptance and support’ components of student attitudes in online cooperative learning environments.     

Sensor-driven agenda for intelligent home care of the elderly

The exponential increase of home-bound persons who live alone and are in need of continuous monitoring requires new solutions to current problems. Most of these cases present illnesses such as motor or psychological disabilities that deprive of a normal living. Common events such as forgetfulness or falls are quite common and have to be prevented or dealt with. This paper introduces a platform to guide and assist these persons (mostly elderly people) by providing multisensory monitoring and intelligent assistance. The platform operates at three levels. The lower level, denominated “Data acquisition and processing” performs the usual tasks of a monitoring system, collecting and processing data from the sensors for the purpose of detecting and tracking humans. The aim is to identify their activities in an intermediate level called “activity detection”. The upper level, “Scheduling and decision-making”, consists of a scheduler which provides warnings, schedules events in an intelligent manner and serves as an interface to the rest of the platform. The idea is to use mobile and static sensors performing constant monitoring of the user and his/her environment, providing a safe environment and an immediate response to severe problems. A case study on elderly fall detection in a nursery home bedroom demonstrates the usefulness of the proposal.     

Scheduling on parallel identical machines with job-rejection and position-dependent processing times

We solve scheduling problems which combine the option of job-rejection and general position-dependent processing times. The option of rejection reflects a very common scenario, where the scheduler may decide not to process a job if it is not profitable. The assumption of position-dependent processing time is a common generalization of classical settings, and contains the well-known and extensively studied special cases of “learning” and “aging”. The machine setting is parallel identical machines, and two scheduling measures are considered: total flow-time and total load. When the number of jobs is given, both problems are shown to be solved in polynomial time in the number of jobs. The special case of non-decreasing job-position processing times (“aging”) is shown to be solved much faster.     

Supervisor direct synthesis method for a structured discrete dynamical system

We present an implementation method for a supervisor of a discrete event system (DES) structured in a special way. Such a DES has the following characteristic features: the language generator is represented by a set of finite automata, the language model is extended with a new type of events called “expected,” and the specification is defined as a sequence of control commands. The primary advantage of our method is that it uses structural knowledge of the event stream in order to construct a supervisor. Thus, we achieve linear dependence of the supervisor’s size in the input data.     

Linking Multidimensional Feature Space Cluster Visualization to Multifield Surface Extraction

The IEEE Visualization Design Contests aim to foster the development of new visualization tools, techniques and solutions to existing real-world problems. This article describes the scientific questions posed for the contest for a turbulence data set, contest evaluation procedure, and the 2008 contest results. The winning entry presents a system for linking multi-dimensional feature-space cluster visualization to surface extraction from multi-field volume data designed to answer the contest questions. This article also includes a sidebar by Amit Chourasia and Russell M. Taylor II.