Catálogo de publicaciones - libros

Server logs of search engines store traces of queries submitted by users, which include queries themselves along with Web pages selected in their answers. Here we describe several graph-based relations among queries and many applications where these graphs could be used.

With the increase in the complexity of computer systems, it becomes even more important to develop formal methods for ensuring their quality. Early detection of errors requires application of advanced analysis, verification and validation techniques for modelling resources, temporal properties, datatype invariants, and security properties. Various techniques for automated and semi-automated analysis and verification of computer systems have been proposed.

We deal with the issue of realizability and computability of interactive interface behaviors as described in [1]. We treat the following aspects of interactive behaviors that are represented by relations between communication streams:

– Causality between input and output streams

– Realizability of single output histories for given input histories

– The role of non-realizable output in specific system contexts and for composition

– Relating non-realizable behaviors to state machines

– The concept of interactive computation and computability

Finally, we relate our results to classical notions of computability. The main goal of this paper is the characterization of a general concept of interactive interface behavior as basis for the extension and generalization of the notion of computability to interactive behaviors.

Computational social choice is an interdisciplinary field of study at the interface of social choice theory and computer science, promoting an exchange of ideas in both directions. On the one hand, it is concerned with the application of techniques developed in computer science, such as complexity analysis or algorithm design, to the study of social choice mechanisms, such as voting procedures or fair division algorithms. On the other hand, computational social choice is concerned with importing concepts from social choice theory into computing. For instance, the study of preference aggregation mechanisms is also very relevant to multiagent systems. In this short paper we give a general introduction to computational social choice, by proposing a taxonomy of the issues addressed by this discipline, together with some illustrative examples and an (incomplete) bibliography.

Systems consisting of a collection of independently operating mobile robots (a.k.a. ) have recently been studied from a distributed computing point of view. The paper reviews the basic model developed for such systems and some recent algorithmic results on a number of coordination and control tasks for robot swarms. The paper then discusses various possibilities for modifications in the basic model, and examines their effects via the example of the partitioning problem.

This is a survey of some recent results on point-to-point shortest path algorithms. This classical optimization problem received a lot of attention lately and significant progress has been made. After an overview of classical results, we study recent heuristics that solve the problem while examining only a small portion of the input graph; the graph can be very big. Note that the algorithms we discuss find exact shortest paths. These algorithms are heuristic because they perform well only on some graph classes. While their performance has been good in experimental studies, no theoretical bounds are known to support the experimental observations. Most of these algorithms have been motivated by finding paths in large road networks.

We start by reviewing the classical Dijkstra’s algorithm and its bidirectional variant, developed in 1950’s and 1960’s. Then we review A* search, an AI technique developed in 1970’s. Next we turn our attention to modern results which are based on preprocessing the graph. To be practical, preprocessing needs to be reasonably fast and not use too much space. We discuss landmark- and reach-based algorithms as well as their combination.

Digital technology is increasingly deployed in safety-critical situations. This calls for systematic design and verification methodologies that can cope with three major sources of system complexity: concurrency, real time, and uncertainty. We advocate a two-step process: formal modeling followed by algorithmic analysis (or, “model building” followed by “model checking”). We model the concurrent components of a reactive system as potential collaborators or adversaries in a multi-player game with temporal objectives, such as system safety. The real-time aspect of embedded systems requires models that combine discrete state transitions and continuous state evolutions. Uncertainty in the environment is naturally modeled by probabilistic state changes. As a result, we obtain three orthogonal extensions of the basic state-transition graph model for reactive systems —game graphs, timed graphs, and stochastic graphs— as well as combinations thereof. In this short text, we provide a uniform exposition of the underlying definitions. For verification algorithms, we refer the reader to the literature.

This paper will outline a number of recent advances in developing technologies that autonomous software agents can use in order to reach mutually acceptable agreements. In particular, we will look at the area of computational mechanism design and its application in a variety of real world contexts.

Effective testing involves preparing test oracles and test cases, two activities which are too tedious to be effectively performed by humans, yet for the most part remain manual. The AutoTest unit testing framework automates both, by using Eiffel contracts — already present in the software — as test oracles, and generating objects and routine arguments to exercise all given classes; manual tests can also be added, and all failed test cases are automatically retained for regression testing, in a “minimized” form retaining only the relevant instructions. AutoTest has already detected numerous hitherto unknown bugs in production software.

Scalable models of extra-functional properties such as reliability, availability and timeliness are still presenting great challenges to researchers and practitioners in component-based software architecture.

In our research centre at Monash in collaboration with industrial partners and other universities, we have been developing compositional dynamic models for such extra-functional properties. Architecture definitions supported by our tool cater for components that are parameterised by environment characteristics, such as configuration choices, deployment context or run-time usage profiles.

The behaviour of such components is characterised by annotated automata and Petri nets. Annotations capture synchronisation and resource constraints, such as timing, as well as execution probabilities for run types.

This paper provides a short survey of work around over the past years and sheds light on some key aspects which have led to using in industrial applications for the analysis of large-scale real-world component-based systems.