Verifying Temporal Properties of Reactive Systems: A STeP Tutorial

We review a number of formal verification techniques supported by STeP, the Stanford Temporal Prover, describing how the tool can be used to verify properties of several versions of the Bakery Mutual exclusion algorithm for mutual exclusion. We verify the classic two-process algorithm and simple variants, as well as an atomic parameterized version. The methods used include deductive verification rules, verification diagrams, automatic invariant generation, and finite-state model checking and abstraction.     

An Analysis of Edge Detection by Using the Jensen-Shannon Divergence

This work constitutes a theoretical study of the edge-detection method by means of the Jensen-Shannon divergence, as proposed by the authors. The overall aim is to establish formally the suitability of the procedure of edge detection in digital images, as a step prior to segmentation. In specific, an analysis is made not only of the properties of the divergence used, but also of the method's sensitivity to the spatial variation, as well as the detection-error risk associated with the operating conditions due to the randomness of the spatial configuration of the pixels. Although the paper deals with the procedure based on the Jensen-Shannon divergence, some problems are also related to other methods based on local detection with a sliding window, and part of the study is focused to noisy and textured images.     

Visualization of myocardial perfusion derived from coronary anatomy

Visually assessing the effect of the coronary artery anatomy on the perfusion of the heart muscle in patients with coronary artery disease remains a challenging task. We explore the feasibility of visualizing this effect on perfusion using a numerical approach. We perform a computational simulation of the way blood is perfused throughout the myocardium purely based on information from a three-dimensional anatomical tomographic scan. The results are subsequently visualized using both three-dimensional visualizations and bull's eye plots, partially inspired by approaches currently common in medical practice. Our approach results in a comprehensive visualization of the coronary anatomy that compares well to visualizations commonly used for other scanning technologies. We demonstrate techniques giving detailed insight in blood supply, coronary territories and feeding coronary arteries of a selected region. We demonstrate the advantages of our approach through visualizations that show information which commonly cannot be directly observed in scanning data, such as a separate visualization of the supply from each coronary artery. We thus show that the results of a computational simulation can be effectively visualized and facilitate visually correlating these results to for example perfusion data.     

VisComplete: automating suggestions for visualization pipelines

Building visualization and analysis pipelines is a large hurdle in the adoption of visualization and workflow systems by domain scientists. In this paper, we propose techniques to help users construct pipelines by consensus--automatically suggesting completions based on a database of previously created pipelines. In particular, we compute correspondences between existing pipeline subgraphs from the database, and use these to predict sets of likely pipeline additions to a given partial pipeline. By presenting these predictions in a carefully designed interface, users can create visualizations and other data products more efficiently because they can augment their normal work patterns with the suggested completions. We present an implementation of our technique in a publicly-available, open-source scientific workflow system and demonstrate efficiency gains in real-world situations.     

A heuristic method for the vehicle routing problem with mixed deliveries and pickups

The vehicle routing problem with deliveries and pickups is a challenging extension to the vehicle routing problem that lately attracted growing attention in the literature. This paper investigates the relationship between two versions of this problem, called “mixed” and “simultaneous”. In particular, we wish to know whether a solution algorithm designed for the simultaneous case can solve the mixed case. To this end, we implement a metaheuristic based on reactive tabu search. The results suggest that this approach can yield good results.     

Virtual rights? Property in online game objects and characters

The new industry of Massively Multi-Player Online Role-Playing Games (MMORPGs) brings together two sets of fictions: the interactive stories of shared computer games and the legal devices of intellectual property. In these virtual worlds, scarcity need not exist, but players tend to prefer the competition it creates. This leads to the development of property rights within the game world and players trading real money for virtual objects, ‘land’ and characters. This new phenomenon brings with it familiar legal problems such as theft, fraud and ownership disputes. Game creators also challenge the right of the players to claim ownership outside the game world. The volume and value of the items traded make real money trading an important area of current interest for intellectual property lawyers. Something is being traded, but does it fit neatly into existing conceptions of property rights and who owns it? Analysing the novel problems that result from various theoretical perspectives (utilitarianism, labour-desert theory and personality theory) leads to the conclusion that with time, we will see the development of property rights for players in online games. This connects with a growing understanding that the traditional conception of copyright law dealing with creative work generated by the solitary author is becoming less appropriate in the new creative spaces that information and communications technology brings, where individuals are both consumer and producer. In virtual worlds, new forms of intellectual property, and perhaps even new rights, are taking shape.     

A dynamic bibliometric model for identifying online communities

Predictive modelling of online dynamic user-interaction recordings and community identification from such data becomes more and more important with the widespread use of online communication technologies. Despite of the time-dependent nature of the problem, existing approaches of community identification are based on static or fully observed network connections. Here we present a new, dynamic generative model for the inference of communities from a sequence of temporal events produced through online computer- mediated interactions. The distinctive feature of our approach is that it tries to model the process in a more realistic manner, including an account for possible random temporal delays between the intended connections. The inference of these delays from the data then forms an integral part of our state-clustering methodology, so that the most likely communities are found on the basis of the likely intended connections rather than just the observed ones. We derive a maximum likelihood estimation algorithm for the identification of our model, which turns out to be computationally efficient for the analysis of historical data and it scales linearly with the number of non-zero observed (L + 1)-grams, where L is the Markov memory length. In addition, we also derive an incremental version of the algorithm, which could be used for real-time analysis. Results obtained on both synthetic and real-world data sets demonstrate the approach is flexible and able to reveal novel and insightful structural aspects of online interactions. In particular, the analysis of a full day worth synchronous Internet relay chat participation sequence, reveals the formation of an extremely clear community structure.     

Incremental Branching Programs

We propose a new model of restricted branching programs specific to solving GEN problems, which we call incremental branching programs. We show that syntactic incremental branching programs capture previously studied models of computation for the problem GEN, namely marking machines (Cook, S.A. in J. Comput. Syst. Sci. 9(3):308–316, 1974) and Poon’s extension (Proc. of the 34th IEEE Symp. on the Foundations of Computer Science, pp. 218–227, 1993) of jumping automata on graphs (Cook, S.A., Rackoff, C.W. in SIAM J. Comput. 9:636–652, 1980). We then prove exponential size lower bounds for our syntactic incremental model, and for some other variants of branching program computation for GEN. We further show that nondeterministic syntactic incremental branching programs are provably stronger than their deterministic counterpart when solving a natural NL-complete GEN sub-problem. It remains open if syntactic incremental branching programs are as powerful as unrestricted branching programs for GEN problems. A preliminary version of this paper appears as (Gál, A., Koucky, M., McKenzie, P., Incremental branching programs, in Proc. of the 2006 Computer Science in Russia Conference CSR06. Lecture Notes in Computer Science, vol. 3967, pp. 178–190, 2006). A. Gal supported in part by NSF Grant CCF-0430695 and an Alfred P. Sloan Research Fellowship. M. Koucky did part of this work while being a postdoctoral fellow at McGill University, Canada and at CWI, Amsterdam, Netherlands. Supported in part by NWO vici project 2004–2009, project No. 1M0021620808 of MŠMT ČR, grants 201/07/P276, 201/05/0124 of GA ČR, and Institutional Research Plan No. AV0Z10190503. P. McKenzie supported by the NSERC of Canada and the (Québec) FQRNT.     

Convergence with a fixed regulator in lattice ordered groups and applications to MV-algebras

A convergence with a fixed regulator v in lattice ordered groups is applied to MV-algebras. For each Archimedean MV-algebra A there exists a v-Cauchy completion A ^* and it is uniquely determined up to isomorphisms over A. The relation between the Dedekind completion A ^∧ of A and A ^* is established. There is solved a question of the existence of the greatest v-Cauchy complete ideal of A.     

Staged self-assembly: nanomanufacture of arbitrary shapes with <Emphasis Type="Italic">O</Emphasis>(1) glues

We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various constraints and performance measures are motivated by a practical nanofabrication scenario through protein-based bioengineering. Staging allows us to break through the traditional lower bounds in tile self-assembly by encoding the shape in the staging algorithm instead of the tiles. All of our results are based on the practical assumption that only a constant number of glues, and thus only a constant number of tiles, can be engineered. Under this assumption, traditional tile self-assembly cannot even manufacture an n × n square; in contrast, we show how staged assembly in theory enables manufacture of arbitrary shapes in a variety of precise formulations of the model.