title: A mathematical framework for automated bug localization

abstract: In this paper, we propose a mathematical framework for automated bug localization. This framework can be briefly summarized as follows. A program execution can be represented as a rooted acyclic directed graph. We define an execution snapshot by a cut-set on the graph. A program state can be regarded as a conjunction of labels on edges in a cut-set. Then we argue that a debugging task is a pruning process of the execution graph by using cut-sets. A pruning algorithm, i.e., a debugging task, is also presented.


title: A Performance Analysis Tool for Nokia Mobile Phone Software

abstract: Performance problems are often observed in embedded software systems. The reasons for poor performance are frequently not obvious. Bottlenecks can occur in any of the software components along the execution path. Therefore it is important to instrument and monitor the different components contributing to the runtime behavior of an embedded software system. Performance analysis tools can help locate performance bottlenecks in embedded software systems by monitoring the software's execution and producing easily understandable performance data. We maintain and further develop a tool for analyzing the performance of Nokia mobile phone software. The user can select among four performance analysis reports to be generated: average processor load, processor utilization, task execution time statistics, and task execution timeline. Each of these reports provides important information about where execution time is being spent. The demo will show how the tool helps to identify performance bottlenecks in Nokia mobile phone software and better understand areas of poor performance.


title: The Graphics Card as a Streaming Computer

abstract: Massive data sets have radically changed our understanding of how to design efficient algorithms; the streaming paradigm, whether it in terms of number of passes of an external memory algorithm, or the single pass and limited memory of a stream algorithm, appears to be the dominant method for coping with large data. A very different kind of massive computation has had the same effect at the level of the CPU. The most prominent example is that of the computations performed by a graphics card. The operations themselves are very simple, and require very little memory, but require the ability to perform many computations extremely fast and in parallel to whatever degree possible. What has resulted is a stream processor that is highly optimized for stream computations. An intriguing side effect of this is the growing use of a graphics card as a general purpose stream processing engine. In an ever-increasing array of applications, researchers are discovering that performing a computation on a graphics card is far faster than performing it on a CPU, and so are using a GPU as a stream co-processor.


title: The Wake Up and Report Problem is Time-Equivalent to the Firing Squad Synchronization Problem

abstract: We consider several problems relating to strongly-connected directed networks of identical finite-state processors that work synchronously in discrete time steps. The conceptually simplest of these is the Wake Up and Report Problem; this is the problem of having a unique "root" processor send a signal to all other processors in the network and then enter a special "done" state only when all other processors have received the signal. The most difficult of the problems we consider is the classic Firing Squad Synchronization Problem; this is the much-studied problem of achieving macro-synchronization in a network given micro-synchronization. We show via a complex algorithmic application of the "snake" data structure first introduced in Even, Litman, and Winkler [ELW], that these two problems are asymptotically time-equivalent up to a constant factor. This result leads immediately to the inclusion of several other related problems into this new asymptotic time-class.


title: Determination of the Topology of a Directed Network

abstract: We consider strongly-connected directed networks of identical synchronous, finite-state processors with in- and out-degree uniformly bounded by a network constant. Via a straightforward extension of Ostrovsky and Wilkerson's Backwards Communication Algorithm in [OW], we exhibit a protocol which solves the Global Topology Determination Problem, the problem of having the root processor map the global topology of a network of unknown size and topology, with running time O(ND) where N represents the number of processors and D represents the diameter of the network. A simple counting argument suffices to show that the Global Topology Determination Problem has time-complexity Omega(N logN) which makes the protocol presented asymptotically time-optimal for many large networks.


title: Using Artificial Intelligence for Model Selection

abstract: We apply the optimization algorithm Adaptive Simulated Annealing (ASA) to the problem of analyzing data on a large population and selecting the best model to predict that an individual with various traits will have a particular disease. We compare ASA with traditional forward and backward regression on computer simulated data. We find that the traditional methods of modeling are better for smaller data sets whereas a numerically stable ASA seems to perform better on larger and more complicated data sets.


title: The Lowell Database Research Self Assessment

abstract: A group of senior database researchers gathers every few years to assess the state of database research and to point out problem areas that deserve additional focus. This report summarizes the discussion and conclusions of the sixth ad-hoc meeting held May 4-6, 2003 in Lowell, Mass. It observes that information management continues to be a critical component of most complex software systems. It recommends that database researchers increase focus on: integration of text, data, code, and streams; fusion of information from heterogeneous data sources; reasoning about uncertain data; unsupervised data mining for interesting correlations; information privacy; and self-adaptation and repair.


title: Event-based Program Analysis with DeWiz

abstract: Due to the increased complexity of parallel and distributed programs, debugging of them is considered to be the most difficult and time consuming part of the software lifecycle. Tool support is hence a crucial necessity to hide complexity from the user. However, most existing tools seem inadequate as soon as the program under consideration exploits more than a few processors over a long execution time. This problem is addressed by the novel debugging tool DeWiz (Debugging Wizard), whose focus lies on scalability. DeWiz has a modular, scalable architecture, and uses the event graph model as a representation of the investigated program. DeWiz provides a set of modules, which can be combined to generate, analyze, and visualize event graph data. Within this processing pipeline the toolset tries to extract useful information, which is presented to the user at an arbitrary level of abstraction. Additionally, DeWiz is a framework, which can be used to easily implement arbitrary user-defined modules.


title: Poster on MPI application in Computational Fluid Dynamics

abstract: Poster-presentation of the paper "Message Passing Fluids: molecules as processes in parallel computational fluids" held at "EURO PVMMPI 2003" Congress; the paper is on the proceedings "Recent Advances in Parallel Virtual Machine and Message Passing Interface", 10th European PVM/MPI User's Group Meeting, LNCS 2840, Springer-Verlag, Dongarra-Laforenza-Orlando editors, pp. 550-554.


title: On Interference of Signals and Generalization in Feedforward Neural Networks

abstract: This paper studies how the generalization ability of neurons can be affected by mutual processing of different signals. This study is done on the basis of a feedforward artificial neural network. The mutual processing of signals can possibly be a good model of patterns in a set generalized by a neural network and in effect may improve generalization. In this paper it is discussed that the interference may also cause a highly random generalization. Adaptive activation functions are discussed as a way of reducing that type of generalization. A test of a feedforward neural network is performed that shows the discussed random generalization.


title: Transient Diversity in Multi-Agent Systems

abstract: Diversity is an important aspect of highly efficient multi-agent teams. We introduce the main factors that drive a multi-agent system in either direction along the diversity scale. A metric for diversity is described, and we speculate on the concept of transient diversity. Finally, an experiment on social entropy using a RoboCup simulated soccer team is presented.


title: Re-Finding Found Things: An Exploratory Study of How Users Re-Find Information

abstract: The problem of how people find information is studied extensively; however, the problem of how people organize, re-use, and re-find information that they have found is not as well understood. Recently, several projects have conducted in-situ studies to explore how people re-find and re-use information. Here, we present results and observations from a controlled, laboratory study of refinding information found on the web. Our study was conducted as a collaborative exercise with pairs of participants. One participant acted as a retriever, helping the other participant re-find information by telephone. This design allowed us to gain insight into the strategies that users employed to re-find information, and into how domain artifacts and contextual information were used to aid the re-finding process. We also introduced the ability for users to add their own explicitly artifacts in the form of making annotations on the web pages they viewed. We observe that re-finding often occurs as a two stage, iterative process in which users first attempt to locate an information source (search), and once found, begin a process to find the specific information being sought (browse). Our findings are consistent with research on waypoints; orienteering approaches to re-finding; and navigation of electronic spaces. Furthermore, we observed that annotations were utilized extensively, indicating that explicitly added context by the user can play an important role in re-finding.


title: A Formal Comparison of Visual Web Wrapper Generators

abstract: We study the core fragment of the Elog wrapping language used in the Lixto system (a visual wrapper generator) and formally compare Elog to other wrapping languages proposed in the literature.


title: WebTeach in practice: the entrance test to the Engineering faculty in Florence

abstract: We present the WebTeach project, formed by a web interface to database for test management, a wiki site for the diffusion of teaching material and student forums, and a suite for the generation of multiple-choice mathematical quiz with automatic elaboration of forms. This system has been massively tested for the entrance test to the Engineering Faculty of the University of Florence, Italy


title: Effective XML Representation for Spoken Language in Organisations

abstract: Spoken Language can be used to provide insights into organisational processes, unfortunately transcription and coding stages are very time consuming and expensive. The concept of partial transcription and coding is proposed in which spoken language is indexed prior to any subsequent processing. The functional linguistic theory of texture is used to describe the effects of partial transcription on observational records. The standard used to encode transcript context and metadata is called CHAT, but a previous XML schema developed to implement it contains design assumptions that make it difficult to support partial transcription for example. This paper describes a more effective XML schema that overcomes many of these problems and is intended for use in applications that support the rapid development of spoken language deliverables.


title: Debugging Tool for Localizing Faulty Processes in Message Passing Programs

abstract: In message passing programs, once a process terminates with an unexpected error, the terminated process can propagate the error to the rest of processes through communication dependencies, resulting in a program failure. Therefore, to locate faults, developers must identify the group of processes involved in the original error and faulty processes that activate faults. This paper presents a novel debugging tool, named MPI-PreDebugger (MPI-PD), for localizing faulty processes in message passing programs. MPI-PD automatically distinguishes the original and the propagated errors by checking communication errors during program execution. If MPI-PD observes any communication errors, it backtraces communication dependencies and points out potential faulty processes in a timeline view. We also introduce three case studies, in which MPI-PD has been shown to play the key role in their debugging. From these studies, we believe that MPI-PD helps developers to locate faults and allows them to concentrate in correcting their programs.


title: Debugging Backwards in Time

abstract: By recording every state change in the run of a program, it is possible to present the programmer every bit of information that might be desired. Essentially, it becomes possible to debug the program by going ``backwards in time,'' vastly simplifying the process of debugging. An implementation of this idea, the ``Omniscient Debugger,'' is used to demonstrate its viability and has been used successfully on a number of large programs. Integration with an event analysis engine for searching and control is presented. Several small-scale user studies provide encouraging results. Finally performance issues and implementation are discussed along with possible optimizations. This paper makes three contributions of interest: the concept and technique of ``going backwards in time,'' the GUI which presents a global view of the program state and has a formal notion of ``navigation through time,'' and the integration with an event analyzer.


title: Circle and sphere blending with conformal geometric algebra

abstract: Blending schemes based on circles provide smooth `fair' interpolations between series of points. Here we demonstrate a simple, robust set of algorithms for performing circle blends for a range of cases. An arbitrary level of G-continuity can be achieved by simple alterations to the underlying parameterisation. Our method exploits the computational framework provided by conformal geometric algebra. This employs a five-dimensional representation of points in space, in contrast to the four-dimensional representation typically used in projective geometry. The advantage of the conformal scheme is that straight lines and circles are treated in a single, unified framework. As a further illustration of the power of the conformal framework, the basic idea is extended to the case of sphere blending to interpolate over a surface.


title: The Study of the Application of a Keywords-based Chatbot System on the Teaching of Foreign Languages

abstract: This paper reports the findings of a study conducted on the application of an on-line human-computer dialog system with natural language (chatbot) on the teaching of foreign languages. A keywords-based human-computer dialog system makes it possible that the user could chat with the computer using a natural language, i.e. in English or in German to some extent. So an experiment has been made using this system online to work as a chat partner with the users learning the foreign languages. Dialogs between the users and the chatbot are collected. Findings indicate that the dialogs between the human and the computer are mostly very short because the user finds the responses from the computer are mostly repeated and irrelevant with the topics and context and the program does not understand the language at all. With analysis of the keywords or pattern-matching mechanism used in this chatbot it can be concluded that this kind of system can not work as a teaching assistant program in foreign language learning.


title: A hierarchical Algorithm to Solve the Shortest Path Problem in Valued Graphs

abstract: This paper details a new algorithm to solve the shortest path problem in valued graphs. Its complexity is $O(D \log v)$ where $D$ is the graph diameter and $v$ its number of vertices. This complexity has to be compared to the one of the Dijkstra's algorithm, which is $O(e\log v)$ where $e$ is the number of edges of the graph. This new algorithm lies on a hierarchical representation of the graph, using radix trees. The performances of this algorithm show a major improvement over the ones of the algorithms known up to now.


title: Pure Prolog Execution in 21 Rules

abstract: A simple mathematical definition of the 4-port model for pure Prolog is given. The model combines the intuition of ports with a compact representation of execution state. Forward and backward derivation steps are possible. The model satisfies a modularity claim, making it suitable for formal reasoning.


title: Fuzzy Relational Modeling of Cost and Affordability for Advanced Technology Manufacturing Environment

abstract: Relational representation of knowledge makes it possible to perform all the computations and decision making in a uniform relational way by means of special relational compositions called triangle and square products. In this paper some applications in manufacturing related to cost analysis are described. Testing fuzzy relational structures for various relational properties allows us to discover dependencies, hierarchies, similarities, and equivalences of the attributes characterizing technological processes and manufactured artifacts in their relationship to costs and performance. A brief overview of mathematical aspects of BK-relational products is given in Appendix 1 together with further references in the literature.


title: Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices

abstract: Let $\orig{A}$ be any matrix and let $A$ be a slight random perturbation of $\orig{A}$. We prove that it is unlikely that $A$ has large condition number. Using this result, we prove it is unlikely that $A$ has large growth factor under Gaussian elimination without pivoting. By combining these results, we bound the smoothed precision needed by Gaussian elimination without pivoting. Our results improve the average-case analysis of Gaussian elimination without pivoting performed by Yeung and Chan (SIAM J. Matrix Anal. Appl., 1997).


title: Application of Kullback-Leibler Metric to Speech Recognition

abstract: Article discusses the application of Kullback-Leibler divergence to the recognition of speech signals and suggests three algorithms implementing this divergence criterion: correlation algorithm, spectral algorithm and filter algorithm. Discussion covers an approach to the problem of speech variability and is illustrated with the results of experimental modeling of speech signals. The article gives a number of recommendations on the choice of appropriate model parameters and provides a comparison to some other methods of speech recognition.


title: Availability Guarantee for Deterministic Replay Starting Points in Real-Time Systems

abstract: Cyclic debugging requires repeatable executions. As non-deterministic or real-time systems typically do not have the potential to provide this, special methods are required. One such method is replay, a process that requires monitoring of a running system and logging of the data produced by that monitoring. We shall discuss the process of preparing the replay, a part of the process that has not been very well described before.


title: A Monitoring Language for Run Time and Post-Mortem Behavior Analysis and Visualization

abstract: UFO is a new implementation of FORMAN, a declarative monitoring language, in which rules are compiled into execution monitors that run on a virtual machine supported by the Alamo monitor architecture.


title: Generalized Systematic Debugging for Attribute Grammars

abstract: Attribute grammars (AGs) are known to be a useful formalism for semantic analysis and translation. However, debugging AGs is complex owing to inherent difficulties of AGs, such as recursive grammar structure and attribute dependency. In this paper, a new systematic method of debugging AGs is proposed. Our approach is, in principle, based on previously proposed algorithmic debugging of AGs, but is more general. This easily enables integration of various query-based systematic debugging methods, including the slice-based method. The proposed method has been implemented in Aki, a debugger for AG description. We evaluated our new approach experimentally using Aki, which demonstrates the usability of our debugging method.


title: On the continuous Fermat-Weber problem

abstract: We give the first exact algorithmic study of facility location problems that deal with finding a median for a continuum of demand points. In particular, we consider versions of the ``continuous k-median (Fermat-Weber) problem'' where the goal is to select one or more center points that minimize the average distance to a set of points in a demand region. In such problems, the average is computed as an integral over the relevant region, versus the usual discrete sum of distances. The resulting facility location problems are inherently geometric, requiring analysis techniques of computational geometry. We provide polynomial-time algorithms for various versions of the L1 1-median (Fermat-Weber) problem. We also consider the multiple-center version of the L1 k-median problem, which we prove is NP-hard for large k.


title: Providing Diversity in K-Nearest Neighbor Query Results

abstract: Given a point query Q in multi-dimensional space, K-Nearest Neighbor (KNN) queries return the K closest answers according to given distance metric in the database with respect to Q. In this scenario, it is possible that a majority of the answers may be very similar to some other, especially when the data has clusters. For a variety of applications, such homogeneous result sets may not add value to the user. In this paper, we consider the problem of providing diversity in the results of KNN queries, that is, to produce the closest result set such that each answer is sufficiently different from the rest. We first propose a user-tunable definition of diversity, and then present an algorithm, called MOTLEY, for producing a diverse result set as per this definition. Through a detailed experimental evaluation on real and synthetic data, we show that MOTLEY can produce diverse result sets by reading only a small fraction of the tuples in the database. Further, it imposes no additional overhead on the evaluation of traditional KNN queries, thereby providing a seamless interface between diversity and distance.


title: Optimizing Noncontiguous Accesses in MPI-IO

abstract: The I/O access patterns of many parallel applications consist of accesses to a large number of small, noncontiguous pieces of data. If an application's I/O needs are met by making many small, distinct I/O requests, however, the I/O performance degrades drastically. To avoid this problem, MPI-IO allows users to access noncontiguous data with a single I/O function call, unlike in Unix I/O. In this paper, we explain how critical this feature of MPI-IO is for high performance and how it enables implementations to perform optimizations. We first provide a classification of the different ways of expressing an application's I/O needs in MPI-IO--we classify them into four levels, called level~0 through level~3. We demonstrate that, for applications with noncontiguous access patterns, the I/O performance improves dramatically if users write their applications to make level-3 requests (noncontiguous, collective) rather than level-0 requests (Unix style). We then describe how our MPI-IO implementation, ROMIO, delivers high performance for noncontiguous requests. We explain in detail the two key optimizations ROMIO performs: data sieving for noncontiguous requests from one process and collective I/O for noncontiguous requests from multiple processes. We describe how we have implemented these optimizations portably on multiple machines and file systems, controlled their memory requirements, and also achieved high performance. We demonstrate the performance and portability with performance results for three applications--an astrophysics-application template (DIST3D), the NAS BTIO benchmark, and an unstructured code (UNSTRUC)--on five different parallel machines: HP Exemplar, IBM SP, Intel Paragon, NEC SX-4, and SGI Origin2000.


title: A Particular Bug Trap: Execution Replay Using Virtual Machines

abstract: Execution-replay (ER) is well known in the literature but has been restricted to special system architectures for many years. Improved hardware resources and the maturity of virtual machine technology promise to make ER useful for a broader range of development projects. This paper describes an approach to create a practical, generic ER infrastructure for desktop PC systems using virtual machine technology. In the created VM environment arbitrary application programs will run and be replayed unmodified, neither instrumentation nor recompilation are required.


title: A weak definition of Delaunay triangulation

abstract: We show that the traditional criterion for a simplex to belong to the Delaunay triangulation of a point set is equivalent to a criterion which is a priori weaker. The argument is quite general; as well as the classical Euclidean case, it applies to hyperbolic and hemispherical geometries and to Edelsbrunner's weighted Delaunay triangulation. In spherical geometry, we establish a similar theorem under a genericity condition. The weak definition finds natural application in the problem of approximating a point-cloud data set with a simplical complex.


title: A combinatorial characterization of higher-dimensional orthogonal packing

abstract: Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Previous efforts for exact algorithms have been unable to avoid structural problems that appear for instances in two- or higher-dimensional space. We present a new approach for modeling packings, using a graph-theoretical characterization of feasible packings. Our characterization allows it to deal with classes of packings that share a certain combinatorial structure, instead of having to consider one packing at a time. In addition, we can make use of elegant algorithmic properties of certain classes of graphs. This allows our characterization to be the basis for a successful branch-and-bound framework. This is the first in a series of papers describing new approaches to higher-dimensional packing.


title: A Hash of Hash Functions

abstract: In this paper, we present a general review of hash functions in a cryptographic sense. We give special emphasis on some particular topics such as cipher block chaining message authentication code (CBC MAC) and its variants. This paper also broadens the information given in some well known surveys, by including more details on block-cipher based hash functions and security of different hash schemes.


title: Minimizing the stabbing number of matchings, trees, and triangulations

abstract: The (axis-parallel) stabbing number of a given set of line segments is the maximum number of segments that can be intersected by any one (axis-parallel) line. This paper deals with finding perfect matchings, spanning trees, or triangulations of minimum stabbing number for a given set of points. The complexity of these problems has been a long-standing open question; in fact, it is one of the original 30 outstanding open problems in computational geometry on the list by Demaine, Mitchell, and O'Rourke. The answer we provide is negative for a number of minimum stabbing problems by showing them NP-hard by means of a general proof technique. It implies non-trivial lower bounds on the approximability. On the positive side we propose a cut-based integer programming formulation for minimizing the stabbing number of matchings and spanning trees. We obtain lower bounds (in polynomial time) from the corresponding linear programming relaxations, and show that an optimal fractional solution always contains an edge of at least constant weight. This result constitutes a crucial step towards a constant-factor approximation via an iterated rounding scheme. In computational experiments we demonstrate that our approach allows for actually solving problems with up to several hundred points optimally or near-optimally.


title: Supporting Exploratory Queries in Database Centric Web Applications

abstract: Users of database-centric Web applications, especially in the e-commerce domain, often resort to exploratory ``trial-and-error'' queries since the underlying data space is huge and unfamiliar, and there are several alternatives for search attributes in this space. For example, scouting for cheap airfares typically involves posing multiple queries, varying flight times, dates, and airport locations. Exploratory queries are problematic from the perspective of both the user and the server. For the database server, it results in a drastic reduction in effective throughput since much of the processing is duplicated in each successive query. For the client, it results in a marked increase in response times, especially when accessing the service through wireless channels. In this paper, we investigate the design of automated techniques to minimize the need for repetitive exploratory queries. Specifically, we present SAUNA, a server-side query relaxation algorithm that, given the user's initial range query and a desired cardinality for the answer set, produces a relaxed query that is expected to contain the required number of answers. The algorithm incorporates a range-query-specific distance metric that is weighted to produce relaxed queries of a desired shape (e.g. aspect ratio preserving), and utilizes multi-dimensional histograms for query size estimation. A detailed performance evaluation of SAUNA over a variety of multi-dimensional data sets indicates that its relaxed queries can significantly reduce the costs associated with exploratory query processing.


title: Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$

abstract: We present a linear-system solver that, given an $n$-by-$n$ symmetric positive semi-definite, diagonally dominant matrix $A$ with $m$ non-zero entries and an $n$-vector $\bb $, produces a vector $\xxt$ within relative distance $\epsilon$ of the solution to $A \xx = \bb$ in time $O (m^{1.31} \log (n \kappa_{f} (A)/\epsilon)^{O (1)})$, where $\kappa_{f} (A)$ is the log of the ratio of the largest to smallest non-zero eigenvalue of $A$. In particular, $\log (\kappa_{f} (A)) = O (b \log n)$, where $b$ is the logarithm of the ratio of the largest to smallest non-zero entry of $A$. If the graph of $A$ has genus $m^{2\theta}$ or does not have a $K_{m^{\theta}} $ minor, then the exponent of $m$ can be improved to the minimum of $1 + 5 \theta $ and $(9/8) (1+\theta)$. The key contribution of our work is an extension of Vaidya's techniques for constructing and analyzing combinatorial preconditioners.


title: Maximum dispersion and geometric maximum weight cliques

abstract: We consider a facility location problem, where the objective is to ``disperse'' a number of facilities, i.e., select a given number k of locations from a discrete set of n candidates, such that the average distance between selected locations is maximized. In particular, we present algorithmic results for the case where vertices are represented by points in d-dimensional space, and edge weights correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where k is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where k is part of the input, we present a polynomial-time approximation scheme.


title: On Addressing Efficiency Concerns in Privacy Preserving Data Mining

abstract: Data mining services require accurate input data for their results to be meaningful, but privacy concerns may influence users to provide spurious information. To encourage users to provide correct inputs, we recently proposed a data distortion scheme for association rule mining that simultaneously provides both privacy to the user and accuracy in the mining results. However, mining the distorted database can be orders of magnitude more time-consuming as compared to mining the original database. In this paper, we address this issue and demonstrate that by (a) generalizing the distortion process to perform symbol-specific distortion, (b) appropriately choosing the distortion parameters, and (c) applying a variety of optimizations in the reconstruction process, runtime efficiencies that are well within an order of magnitude of undistorted mining can be achieved.


title: A Game Theoretic Framework for Incentives in P2P Systems

abstract: Peer-To-Peer (P2P) networks are self-organizing, distributed systems, with no centralized authority or infrastructure. Because of the voluntary participation, the availability of resources in a P2P system can be highly variable and unpredictable. In this paper, we use ideas from Game Theory to study the interaction of strategic and rational peers, and propose a differential service-based incentive scheme to improve the system's performance.


title: Automated Fault Localization Using Potential Invariants

abstract: We present a general method for fault localization based on abstracting over program traces, and a tool that implements the method using Ernst's notion of potential invariants. Our experiments so far have been unsatisfactory, suggesting that further research is needed before invariants can be used to locate faults.


title: A Dynamic Programming Algorithm for the Segmentation of Greek Texts

abstract: In this paper we introduce a dynamic programming algorithm to perform linear text segmentation by global minimization of a segmentation cost function which consists of: (a) within-segment word similarity and (b) prior information about segment length. The evaluation of the segmentation accuracy of the algorithm on a text collection consisting of Greek texts showed that the algorithm achieves high segmentation accuracy and appears to be very innovating and promissing.


title: Rigorous design of tracers: an experiment for constraint logic programming

abstract: In order to design and implement tracers, one must decide what exactly to trace and how to produce this trace. On the one hand, trace designs are too often guided by implementation concerns and are not as useful as they should be. On the other hand, an interesting trace which cannot be produced efficiently, is not very useful either. In this article we propose a methodology which helps to efficiently produce accurate traces. Firstly, design a formal specification of the trace model. Secondly, derive a prototype tracer from this specification. Thirdly, analyze the produced traces. Fourthly, implement an efficient tracer. Lastly, compare the traces of the two tracers. At each step, problems can be found. In that case one has to iterate the process. We have successfully applied the proposed methodology to the design and implementation of a real tracer for constraint logic programming which is able to efficiently generate information required to build interesting graphical views of executions.


title: Value-at-Risk and Expected Shortfall for Quadratic portfolio of securities with mixture of elliptic Distributed Risk Factors

abstract: Generally, in the financial literature, the notion of quadratic VaR is implicitly confused with the Delta-Gamma VaR, because more authors dealt with portfolios that contains derivatives instruments. In this paper, we postpone to estimate the Value-at-Risk of a quadratic portfolio of securities (i.e equities) without the Delta and Gamma greeks, when the joint log-returns changes with multivariate elliptic distribution. We have reduced the estimation of the quadratic VaR of such portfolio to a resolution of one dimensional integral equation. To illustrate our method, we give special attention to the mixture of normal and mixture of t-student distribution. For given VaR, when joint Risk Factors changes with elliptic distribution, we show how to estimate an Expected Shortfall .


title: The Algebra of Utility Inference

abstract: Richard Cox [1] set the axiomatic foundations of probable inference and the algebra of propositions. He showed that consistency within these axioms requires certain rules for updating belief. In this paper we use the analogy between probability and utility introduced in [2] to propose an axiomatic foundation for utility inference and the algebra of preferences. We show that consistency within these axioms requires certain rules for updating preference. We discuss a class of utility functions that stems from the axioms of utility inference and show that this class is the basic building block for any general multiattribute utility function. We use this class of utility functions together with the algebra of preferences to construct utility functions represented by logical operations on the attributes.


title: An information theory for preferences

abstract: Recent literature in the last Maximum Entropy workshop introduced an analogy between cumulative probability distributions and normalized utility functions. Based on this analogy, a utility density function can de defined as the derivative of a normalized utility function. A utility density function is non-negative and integrates to unity. These two properties form the basis of a correspondence between utility and probability. A natural application of this analogy is a maximum entropy principle to assign maximum entropy utility values. Maximum entropy utility interprets many of the common utility functions based on the preference information needed for their assignment, and helps assign utility values based on partial preference information. This paper reviews maximum entropy utility and introduces further results that stem from the duality between probability and utility.


title: Theory of One Tape Linear Time Turing Machines

abstract: A theory of one-tape (one-head) linear-time Turing machines is essentially different from its polynomial-time counterpart since these machines are closely related to finite state automata. This paper discusses structural-complexity issues of one-tape Turing machines of various types (deterministic, nondeterministic, reversible, alternating, probabilistic, counting, and quantum Turing machines) that halt in linear time, where the running time of a machine is defined as the length of any longest computation path. We explore structural properties of one-tape linear-time Turing machines and clarify how the machines' resources affect their computational patterns and power.


title: Abductive Logic Programs with Penalization: Semantics, Complexity and Implementation

abstract: Abduction, first proposed in the setting of classical logics, has been studied with growing interest in the logic programming area during the last years. In this paper we study abduction with penalization in the logic programming framework. This form of abductive reasoning, which has not been previously analyzed in logic programming, turns out to represent several relevant problems, including optimization problems, very naturally. We define a formal model for abduction with penalization over logic programs, which extends the abductive framework proposed by Kakas and Mancarella. We address knowledge representation issues, encoding a number of problems in our abductive framework. In particular, we consider some relevant problems, taken from different domains, ranging from optimization theory to diagnosis and planning; their encodings turn out to be simple and elegant in our formalism. We thoroughly analyze the computational complexity of the main problems arising in the context of abduction with penalization from logic programs. Finally, we implement a system supporting the proposed abductive framework on top of the DLV engine. To this end, we design a translation from abduction problems with penalties into logic programs with weak constraints. We prove that this approach is sound and complete.


title: Managing Evolving Business Workflows through the Capture of Descriptive Information

abstract: Business systems these days need to be agile to address the needs of a changing world. In particular the discipline of Enterprise Application Integration requires business process management to be highly reconfigurable with the ability to support dynamic workflows, inter-application integration and process reconfiguration. Basing EAI systems on model-resident or on a so-called description-driven approach enables aspects of flexibility, distribution, system evolution and integration to be addressed in a domain-independent manner. Such a system called CRISTAL is described in this paper with particular emphasis on its application to EAI problem domains. A practical example of the CRISTAL technology in the domain of manufacturing systems, called Agilium, is described to demonstrate the principles of model-driven system evolution and integration. The approach is compared to other model-driven development approaches such as the Model-Driven Architecture of the OMG and so-called Adaptive Object Models.


title: An O(m) Algorithm for Cores Decomposition of Networks

abstract: The structure of large networks can be revealed by partitioning them to smaller parts, which are easier to handle. One of such decompositions is based on $k$--cores, proposed in 1983 by Seidman. In the paper an efficient, $O(m)$, $m$ is the number of lines, algorithm for determining the cores decomposition of a given network is presented.


title: Feedforward Neural Networks with Diffused Nonlinear Weight Functions

abstract: In this paper, feedforward neural networks are presented that have nonlinear weight functions based on look--up tables, that are specially smoothed in a regularization called the diffusion. The idea of such a type of networks is based on the hypothesis that the greater number of adaptive parameters per a weight function might reduce the total number of the weight functions needed to solve a given problem. Then, if the computational complexity of a propagation through a single such a weight function would be kept low, then the introduced neural networks might possibly be relatively fast. A number of tests is performed, showing that the presented neural networks may indeed perform better in some cases than the classic neural networks and a number of other learning machines.


title: Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems

abstract: This paper has been divided into three papers. arXiv:0809.3232, arXiv:0808.4134, arXiv:cs/0607105


title: On secret sharing for graphs

abstract: In the paper we discuss how to share the secrets, that are graphs. So, far secret sharing schemes were designed to work with numbers. As the first step, we propose conditions for "graph to number" conversion methods. Hence, the existing schemes can be used, without weakening their properties. Next, we show how graph properties can be used to extend capabilities of secret sharing schemes. This leads to proposal of using such properties for number based secret sharing.


title: Secret Sharing for n-Colorable Graphs with Application to Public Key Cryptography

abstract: At the beginning some results from the field of graph theory are presented. Next we show how to share a secret that is proper n-coloring of the graph, with the known structure. The graph is described and converted to the form, where colors assigned to vertices form the number with entries from Zn. A secret sharing scheme (SSS) for the graph coloring is proposed. The proposed method is applied to the public-key cryptosystem called "Polly Cracker". In this case the graph structure is a public key, while proper 3-colouring of the graph is a private key. We show how to share the private key. Sharing particular n-coloring (color-to-vertex assignment) for the known-structure graph is presented next.


title: Kleene algebra with domain

abstract: We propose Kleene algebra with domain (KAD), an extension of Kleene algebra with two equational axioms for a domain and a codomain operation, respectively. KAD considerably augments the expressiveness of Kleene algebra, in particular for the specification and analysis of state transition systems. We develop the basic calculus, discuss some related theories and present the most important models of KAD. We demonstrate applicability by two examples: First, an algebraic reconstruction of Noethericity and well-foundedness; second, an algebraic reconstruction of propositional Hoare logic.


title: Mace4 Reference Manual and Guide

abstract: Mace4 is a program that searches for finite models of first-order formulas. For a given domain size, all instances of the formulas over the domain are constructed. The result is a set of ground clauses with equality. Then, a decision procedure based on ground equational rewriting is applied. If satisfiability is detected, one or more models are printed. Mace4 is a useful complement to first-order theorem provers, with the prover searching for proofs and Mace4 looking for countermodels, and it is useful for work on finite algebras. Mace4 performs better on equational problems than did our previous model-searching program Mace2.


title: OTTER 3.3 Reference Manual

abstract: OTTER is a resolution-style theorem-proving program for first-order logic with equality. OTTER includes the inference rules binary resolution, hyperresolution, UR-resolution, and binary paramodulation. Some of its other abilities and features are conversion from first-order formulas to clauses, forward and back subsumption, factoring, weighting, answer literals, term ordering, forward and back demodulation, evaluable functions and predicates, Knuth-Bendix completion, and the hints strategy. OTTER is coded in ANSI C, is free, and is portable to many different kinds of computer.


title: An Introduction to Using Software Tools for Automatic Differentiation

abstract: We give a gentle introduction to using various software tools for automatic differentiation (AD). Ready-to-use examples are discussed, and links to further information are presented. Our target audience includes all those who are looking for a straightforward way to get started using the available AD technology. The document is dynamic in the sense that its content will be updated as the AD software evolves.


title: Application Architecture for Spoken Language Resources in Organisational Settings

abstract: Special technologies need to be used to take advantage of, and overcome, the challenges associated with acquiring, transforming, storing, processing, and distributing spoken language resources in organisations. This paper introduces an application architecture consisting of tools and supporting utilities for indexing and transcription, and describes how these tools, together with downstream processing and distribution systems, can be integrated into a workflow. Two sample applications for this architecture are outlined- the analysis of decision-making processes in organisations and the deployment of systems development methods by designers in the field.


title: Design and Implementation of MPICH2 over InfiniBand with RDMA Support

abstract: For several years, MPI has been the de facto standard for writing parallel applications. One of the most popular MPI implementations is MPICH. Its successor, MPICH2, features a completely new design that provides more performance and flexibility. To ensure portability, it has a hierarchical structure based on which porting can be done at different levels. In this paper, we present our experiences designing and implementing MPICH2 over InfiniBand. Because of its high performance and open standard, InfiniBand is gaining popularity in the area of high-performance computing. Our study focuses on optimizing the performance of MPI-1 functions in MPICH2. One of our objectives is to exploit Remote Direct Memory Access (RDMA) in Infiniband to achieve high performance. We have based our design on the RDMA Channel interface provided by MPICH2, which encapsulates architecture-dependent communication functionalities into a very small set of functions. Starting with a basic design, we apply different optimizations and also propose a zero-copy-based design. We characterize the impact of our optimizations and designs using microbenchmarks. We have also performed an application-level evaluation using the NAS Parallel Benchmarks. Our optimized MPICH2 implementation achieves 7.6 $\mu$s latency and 857 MB/s bandwidth, which are close to the raw performance of the underlying InfiniBand layer. Our study shows that the RDMA Channel interface in MPICH2 provides a simple, yet powerful, abstraction that enables implementations with high performance by exploiting RDMA operations in InfiniBand. To the best of our knowledge, this is the first high-performance design and implementation of MPICH2 on InfiniBand using RDMA support.


title: Puzzle: Zermelo-Fraenkel set theory is inconsistent

abstract: In this note, we present a puzzle. We prove that Zermelo-Fraenkel set theory is inconsistent by proving, using Zermelo-Fraenkel set theory, the false statement that any algorithm that determines whether any $n \times n$ matrix over $\mathbb F_2$, the finite field of order 2, is nonsingular must run in exponential time in the worst-case scenario. The object of the puzzle is to find the error in the proof.


title: Local-search techniques for propositional logic extended with cardinality constraints

abstract: We study local-search satisfiability solvers for propositional logic extended with cardinality atoms, that is, expressions that provide explicit ways to model constraints on cardinalities of sets. Adding cardinality atoms to the language of propositional logic facilitates modeling search problems and often results in concise encodings. We propose two ``native'' local-search solvers for theories in the extended language. We also describe techniques to reduce the problem to standard propositional satisfiability and allow us to use off-the-shelf SAT solvers. We study these methods experimentally. Our general finding is that native solvers designed specifically for the extended language perform better than indirect methods relying on SAT solvers.


title: WSAT(cc) - a fast local-search ASP solver

abstract: We describe WSAT(cc), a local-search solver for computing models of theories in the language of propositional logic extended by cardinality atoms. WSAT(cc) is a processing back-end for the logic PS+, a recently proposed formalism for answer-set programming.


title: Logic programs with monotone cardinality atoms

abstract: We investigate mca-programs, that is, logic programs with clauses built of monotone cardinality atoms of the form kX, where k is a non-negative integer and X is a finite set of propositional atoms. We develop a theory of mca-programs. We demonstrate that the operational concept of the one-step provability operator generalizes to mca-programs, but the generalization involves nondeterminism. Our main results show that the formalism of mca-programs is a common generalization of (1) normal logic programming with its semantics of models, supported models and stable models, (2) logic programming with cardinality atoms and with the semantics of stable models, as defined by Niemela, Simons and Soininen, and (3) of disjunctive logic programming with the possible-model semantics of Sakama and Inoue.


title: Satisfiability and computing van der Waerden numbers

abstract: In this paper we bring together the areas of combinatorics and propositional satisfiability. Many combinatorial theorems establish, often constructively, the existence of positive integer functions, without actually providing their closed algebraic form or tight lower and upper bounds. The area of Ramsey theory is especially rich in such results. Using the problem of computing van der Waerden numbers as an example, we show that these problems can be represented by parameterized propositional theories in such a way that decisions concerning their satisfiability determine the numbers (function) in question. We show that by using general-purpose complete and local-search techniques for testing propositional satisfiability, this approach becomes effective -- competitive with specialized approaches. By following it, we were able to obtain several new results pertaining to the problem of computing van der Waerden numbers. We also note that due to their properties, especially their structural simplicity and computational hardness, propositional theories that arise in this research can be of use in development, testing and benchmarking of SAT solvers.


title: Maintaining Information in Fully-Dynamic Trees with Top Trees

abstract: We introduce top trees as a design of a new simpler interface for data structures maintaining information in a fully-dynamic forest. We demonstrate how easy and versatile they are to use on a host of different applications. For example, we show how to maintain the diameter, center, and median of each tree in the forest. The forest can be updated by insertion and deletion of edges and by changes to vertex and edge weights. Each update is supported in O(log n) time, where n is the size of the tree(s) involved in the update. Also, we show how to support nearest common ancestor queries and level ancestor queries with respect to arbitrary roots in O(log n) time. Finally, with marked and unmarked vertices, we show how to compute distances to a nearest marked vertex. The later has applications to approximate nearest marked vertex in general graphs, and thereby to static optimization problems over shortest path metrics. Technically speaking, top trees are easily implemented either with Frederickson's topology trees [Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees, SIAM J. Comput. 26 (2) pp. 484-538, 1997] or with Sleator and Tarjan's dynamic trees [A Data Structure for Dynamic Trees. J. Comput. Syst. Sc. 26 (3) pp. 362-391, 1983]. However, we claim that the interface is simpler for many applications, and indeed our new bounds are quadratic improvements over previous bounds where they exist.


title: Modeling State in Software Debugging of VHDL-RTL Designs -- A Model-Based Diagnosis Approach

abstract: In this paper we outline an approach of applying model-based diagnosis to the field of automatic software debugging of hardware designs. We present our value-level model for debugging VHDL-RTL designs and show how to localize the erroneous component responsible for an observed misbehavior. Furthermore, we discuss an extension of our model that supports the debugging of sequential circuits, not only at a given point in time, but also allows for considering the temporal behavior of VHDL-RTL designs. The introduced model is capable of handling state inherently present in every sequential circuit. The principal applicability of the new model is outlined briefly and we use industrial-sized real world examples from the ISCAS'85 benchmark suite to discuss the scalability of our approach.


title: Computing Convex Hulls with a Linear Solver

abstract: A programming tactic involving polyhedra is reported that has been widely applied in the polyhedral analysis of (constraint) logic programs. The method enables the computations of convex hulls that are required for polyhedral analysis to be coded with linear constraint solving machinery that is available in many Prolog systems. To appear in Theory and Practice of Logic Programming (TPLP)


title: Enhancing a Search Algorithm to Perform Intelligent Backtracking

abstract: This paper illustrates how a Prolog program, using chronological backtracking to find a solution in some search space, can be enhanced to perform intelligent backtracking. The enhancement crucially relies on the impurity of Prolog that allows a program to store information when a dead end is reached. To illustrate the technique, a simple search program is enhanced. To appear in Theory and Practice of Logic Programming. Keywords: intelligent backtracking, dependency-directed backtracking, backjumping, conflict-directed backjumping, nogood sets, look-back.


title: Utility-Probability Duality

abstract: This paper presents duality between probability distributions and utility functions.


title: On The Cost Distribution of a Memory Bound Function

abstract: Memory Bound Functions have been proposed for fighting spam, resisting Sybil attacks and other purposes. A particular implementation of such functions has been proposed in which the average effort required to generate a proof of effort is set by parameters E and l to E * l. The distribution of effort required to generate an individual proof about this average is fairly broad. When particular uses of these functions are envisaged, the choice of E and l, and the system design surrounding the generation and verification of proofs of effort, need to take the breadth of the distribution into account. We show the distribution for this implementation, discuss the system design issues in the context of two proposed applications, and suggest an improved implementation.


title: How Push-To-Talk Makes Talk Less Pushy

abstract: This paper presents an exploratory study of college-age students using two-way, push-to-talk cellular radios. We describe the observed and reported use of cellular radio by the participants. We discuss how the half-duplex, lightweight cellular radio communication was associated with reduced interactional commitment, which meant the cellular radios could be used for a wide range of conversation styles. One such style, intermittent conversation, is characterized by response delays. Intermittent conversation is surprising in an audio medium, since it is typically associated with textual media such as instant messaging. We present design implications of our findings.


title: Parametric Connectives in Disjunctive Logic Programming

abstract: Disjunctive Logic Programming (\DLP) is an advanced formalism for Knowledge Representation and Reasoning (KRR). \DLP is very expressive in a precise mathematical sense: it allows to express every property of finite structures that is decidable in the complexity class $\SigmaP{2}$ ($\NP^{\NP}$). Importantly, the \DLP encodings are often simple and natural. In this paper, we single out some limitations of \DLP for KRR, which cannot naturally express problems where the size of the disjunction is not known ``a priori'' (like N-Coloring), but it is part of the input. To overcome these limitations, we further enhance the knowledge modelling abilities of \DLP, by extending this language by {\em Parametric Connectives (OR and AND)}. These connectives allow us to represent compactly the disjunction/conjunction of a set of atoms having a given property. We formally define the semantics of the new language, named $DLP^{\bigvee,\bigwedge}$ and we show the usefulness of the new constructs on relevant knowledge-based problems. We address implementation issues and discuss related works.


title: A Parameterised Hierarchy of Argumentation Semantics for Extended Logic Programming and its Application to the Well-founded Semantics

abstract: Argumentation has proved a useful tool in defining formal semantics for assumption-based reasoning by viewing a proof as a process in which proponents and opponents attack each others arguments by undercuts (attack to an argument's premise) and rebuts (attack to an argument's conclusion). In this paper, we formulate a variety of notions of attack for extended logic programs from combinations of undercuts and rebuts and define a general hierarchy of argumentation semantics parameterised by the notions of attack chosen by proponent and opponent. We prove the equivalence and subset relationships between the semantics and examine some essential properties concerning consistency and the coherence principle, which relates default negation and explicit negation. Most significantly, we place existing semantics put forward in the literature in our hierarchy and identify a particular argumentation semantics for which we prove equivalence to the paraconsistent well-founded semantics with explicit negation, WFSX$_p$. Finally, we present a general proof theory, based on dialogue trees, and show that it is sound and complete with respect to the argumentation semantics.


title: OGSA/Globus Evaluation for Data Intensive Applications

abstract: We present an architecture of Globus Toolkit 3 based testbed intended for evaluation of applicability of the Open Grid Service Architecture (OGSA) for Data Intensive Applications.


title: Problem of Application Job Monitoring in GRID Systems

abstract: We present a new approach to monitoring of the execution process of an application job in the GRID environment. The main point of the approach is use of GRID ervices to access monitoring information with the security level available in GRID.


title: On an explicit finite difference method for fractional diffusion equations

abstract: A numerical method to solve the fractional diffusion equation, which could also be easily extended to many other fractional dynamics equations, is considered. These fractional equations have been proposed in order to describe anomalous transport characterized by non-Markovian kinetics and the breakdown of Fick's law. In this paper we combine the forward time centered space (FTCS) method, well known for the numerical integration of ordinary diffusion equations, with the Grunwald-Letnikov definition of the fractional derivative operator to obtain an explicit fractional FTCS scheme for solving the fractional diffusion equation. The resulting method is amenable to a stability analysis a la von Neumann. We show that the analytical stability bounds are in excellent agreement with numerical tests. Comparison between exact analytical solutions and numerical predictions are made.

categories: cs.NA cond-mat.stat-mech cs.CE physics.comp-ph


title: A rigorous definition of axial lines: ridges on isovist fields

abstract: We suggest that 'axial lines' defined by (Hillier and Hanson, 1984) as lines of uninterrupted movement within urban streetscapes or buildings, appear as ridges in isovist fields (Benedikt, 1979). These are formed from the maximum diametric lengths of the individual isovists, sometimes called viewsheds, that make up these fields (Batty and Rana, 2004). We present an image processing technique for the identification of lines from ridges, discuss current strengths and weaknesses of the method, and show how it can be implemented easily and effectively.


title: Optimized Flooding Protocol for Ad hoc Networks

abstract: Flooding provides important control and route establishment functionality for a number of unicast and multicast protocols in Mobile Ad Hoc Networks. Considering its wide use as a building block for other network layer protocols, the flooding methodology should deliver a packet from one node to all other network nodes using as few messages as possible. In this paper, we propose the Optimized Flooding Protocol (OFP), based on a variation of The Covering Problem that is encountered in geometry, to minimize the unnecessary transmissions drastically and still be able to cover the whole region. OFP does not need hello messages and hence OFP saves a significant amount of wireless bandwidth and incurs lesser overhead. We present simulation results to show the efficiency of OFP in both ideal cases and randomly distributed networks. Moreover, OFP is scalable with respect to density; in fact OFP requires lesser number of transmissions at higher densities. OFP is also resilient to transmission errors.


title: Optimality of Universal Bayesian Sequence Prediction for General Loss and Alphabet

abstract: Various optimality properties of universal sequence predictors based on Bayes-mixtures in general, and Solomonoff's prediction scheme in particular, will be studied. The probability of observing $x_t$ at time $t$, given past observations $x_1...x_{t-1}$ can be computed with the chain rule if the true generating distribution $\mu$ of the sequences $x_1x_2x_3...$ is known. If $\mu$ is unknown, but known to belong to a countable or continuous class $\M$ one can base ones prediction on the Bayes-mixture $\xi$ defined as a $w_\nu$-weighted sum or integral of distributions $\nu\in\M$. The cumulative expected loss of the Bayes-optimal universal prediction scheme based on $\xi$ is shown to be close to the loss of the Bayes-optimal, but infeasible prediction scheme based on $\mu$. We show that the bounds are tight and that no other predictor can lead to significantly smaller bounds. Furthermore, for various performance measures, we show Pareto-optimality of $\xi$ and give an Occam's razor argument that the choice $w_\nu\sim 2^{-K(\nu)}$ for the weights is optimal, where $K(\nu)$ is the length of the shortest program describing $\nu$. The results are applied to games of chance, defined as a sequence of bets, observations, and rewards. The prediction schemes (and bounds) are compared to the popular predictors based on expert advice. Extensions to infinite alphabets, partial, delayed and probabilistic prediction, classification, and more active systems are briefly discussed.


title: Make search become the internal function of Internet

abstract: Domain Resource Integrated System (DRIS) is introduced in this paper. DRIS is a distributed information retrieval system, which will solve problems like poor coverage, long update interval in current web search system. The most distinct character of DRIS is that it's a public opening system, and acts as an internal component of Internet, but not the production of a company. The implementation of DRIS is also represented.


title: Generic and Efficient Program Monitoring by trace analysis

abstract: Program execution monitoring consists of checking whole executions for given properties in order to collect global run-time information. Monitoring is very useful to maintain programs. However, application developers face the following dilemma: either they use existing tools which never exactly fit their needs, or they invest a lot of effort to implement monitoring code. In this article we argue that, when an event-oriented tracer exists, the compiler developers can enable the application developers to easily code their own, relevant, monitors which will run efficiently. We propose a high-level operator, called foldt, which operates on execution traces. One of the key advantages of our approach is that it allows a clean separation of concerns; the definition of monitors is neither intertwined in the user source code nor in the language compiler. We give a number of applications of the foldt operator to compute monitors for Mercury program executions: execution profiles, graphical abstract views, and two test coverage measurements. Each example is implemented by a few simple lines of Mercury. Detailed measurements show acceptable performance of the basic mechanism of foldt for executions of several millions of execution events.


title: 2 P2P or Not 2 P2P?

abstract: In the hope of stimulating discussion, we present a heuristic decision tree that designers can use to judge the likely suitability of a P2P architecture for their applications. It is based on the characteristics of a wide range of P2P systems from the literature, both proposed and deployed.


title: Ackermann Encoding, Bisimulations, and OBDDs

abstract: We propose an alternative way to represent graphs via OBDDs based on the observation that a partition of the graph nodes allows sharing among the employed OBDDs. In the second part of the paper we present a method to compute at the same time the quotient w.r.t. the maximum bisimulation and the OBDD representation of a given graph. The proposed computation is based on an OBDD-rewriting of the notion of Ackermann encoding of hereditarily finite sets into natural numbers.


title: Replay Debugging of Complex Real-Time Systems: Experiences from Two Industrial Case Studies

abstract: Deterministic replay is a method for allowing complex multitasking real-time systems to be debugged using standard interactive debuggers. Even though several replay techniques have been proposed for parallel, multi-tasking and real-time systems, the solutions have so far lingered on a prototype academic level, with very little results to show from actual state-of-the-practice commercial applications. This paper describes a major deterministic replay debugging case study performed on a full-scale industrial robot control system, as well as a minor replay instrumentation case study performed on a military aircraft radar system. In this article, we will show that replay debugging is feasible in complex multi-million lines of code software projects running on top of off-the-shelf real-time operating systems. Furthermore, we will discuss how replay debugging can be introduced in existing systems without impracticable analysis efforts. In addition, we will present benchmarking results from both studies, indicating that the instrumentation overhead is acceptable and affordable.


title: An Optimal Algorithm for the Maximum-Density Segment Problem

abstract: We address a fundamental problem arising from analysis of biomolecular sequences. The input consists of two numbers $w_{\min}$ and $w_{\max}$ and a sequence $S$ of $n$ number pairs $(a_i,w_i)$ with $w_i>0$. Let {\em segment} $S(i,j)$ of $S$ be the consecutive subsequence of $S$ between indices $i$ and $j$. The {\em density} of $S(i,j)$ is $d(i,j)=(a_i+a_{i+1}+...+a_j)/(w_i+w_{i+1}+...+w_j)$. The {\em maximum-density segment problem} is to find a maximum-density segment over all segments $S(i,j)$ with $w_{\min}\leq w_i+w_{i+1}+...+w_j \leq w_{\max}$. The best previously known algorithm for the problem, due to Goldwasser, Kao, and Lu, runs in $O(n\log(w_{\max}-w_{\min}+1))$ time. In the present paper, we solve the problem in O(n) time. Our approach bypasses the complicated {\em right-skew decomposition}, introduced by Lin, Jiang, and Chao. As a result, our algorithm has the capability to process the input sequence in an online manner, which is an important feature for dealing with genome-scale sequences. Moreover, for a type of input sequences $S$ representable in $O(m)$ space, we show how to exploit the sparsity of $S$ and solve the maximum-density segment problem for $S$ in $O(m)$ time.


title: LCG-1 Deployment and usage experience

abstract: LCG-1 is the second release of the software framework for the LHC Computing Grid project. In our work we describe the installation process, arising problems and their solutions, and configuration tuning details of the complete LCG-1 site, including all LCG elements required for the self-sufficient site.


title: Temporalized logics and automata for time granularity

abstract: Suitable extensions of the monadic second-order theory of k successors have been proposed in the literature to capture the notion of time granularity. In this paper, we provide the monadic second-order theories of downward unbounded layered structures, which are infinitely refinable structures consisting of a coarsest domain and an infinite number of finer and finer domains, and of upward unbounded layered structures, which consist of a finest domain and an infinite number of coarser and coarser domains, with expressively complete and elementarily decidable temporal logic counterparts. We obtain such a result in two steps. First, we define a new class of combined automata, called temporalized automata, which can be proved to be the automata-theoretic counterpart of temporalized logics, and show that relevant properties, such as closure under Boolean operations, decidability, and expressive equivalence with respect to temporal logics, transfer from component automata to temporalized ones. Then, we exploit the correspondence between temporalized logics and automata to reduce the task of finding the temporal logic counterparts of the given theories of time granularity to the easier one of finding temporalized automata counterparts of them.


title: The Chameleon Type Debugger (Tool Demonstration)

abstract: In this tool demonstration, we give an overview of the Chameleon type debugger. The type debugger's primary use is to identify locations within a source program which are involved in a type error. By further examining these (potentially) problematic program locations, users gain a better understanding of their program and are able to work towards the actual mistake which was the cause of the type error. The debugger is interactive, allowing the user to provide additional information to narrow down the search space. One of the novel aspects of the debugger is the ability to explain erroneous-looking types. In the event that an unexpected type is inferred, the debugger can highlight program locations which contributed to that result. Furthermore, due to the flexible constraint-based foundation that the debugger is built upon, it can naturally handle advanced type system features such as Haskell's type classes and functional dependencies.


title: Logic-Based Specification Languages for Intelligent Software Agents

abstract: The research field of Agent-Oriented Software Engineering (AOSE) aims to find abstractions, languages, methodologies and toolkits for modeling, verifying, validating and prototyping complex applications conceptualized as Multiagent Systems (MASs). A very lively research sub-field studies how formal methods can be used for AOSE. This paper presents a detailed survey of six logic-based executable agent specification languages that have been chosen for their potential to be integrated in our ARPEGGIO project, an open framework for specifying and prototyping a MAS. The six languages are ConGoLog, Agent-0, the IMPACT agent programming language, DyLog, Concurrent METATEM and Ehhf. For each executable language, the logic foundations are described and an example of use is shown. A comparison of the six languages and a survey of similar approaches complete the paper, together with considerations of the advantages of using logic-based languages in MAS modeling and prototyping.


title: Fine-Grained Authorization for Job Execution in the Grid: Design and Implementation

abstract: In this paper we describe our work on enabling fine-grained authorization for resource usage and management. We address the need of virtual organizations to enforce their own polices in addition to those of the resource owners, in regard to both resource consumption and job management. To implement this design, we propose changes and extensions to the Globus Toolkit's version 2 resource management mechanism. We describe the prototype and the policy language that we designed to express fine-grained policies, and we present an analysis of our solution.


title: Great Expectations. Part I: On the Customizability of Generalized Expected Utility

abstract: We propose a generalization of expected utility that we call generalized EU (GEU), where a decision maker's beliefs are represented by plausibility measures, and the decision maker's tastes are represented by general (i.e.,not necessarily real-valued) utility functions. We show that every agent, ``rational'' or not, can be modeled as a GEU maximizer. We then show that we can customize GEU by selectively imposing just the constraints we want. In particular, we show how each of Savage's postulates corresponds to constraints on GEU.


title: Great Expectations. Part II: Generalized Expected Utility as a Universal Decision Rule

abstract: Many different rules for decision making have been introduced in the literature. We show that a notion of generalized expected utility proposed in Part I of this paper is a universal decision rule, in the sense that it can represent essentially all other decision rules.


title: Using Counterfactuals in Knowledge-Based Programming

abstract: This paper adds counterfactuals to the framework of knowledge-based programs of Fagin, Halpern, Moses, and Vardi. The use of counterfactuals is illustrated by designing a protocol in which an agent stops sending messages once it knows that it is safe to do so. Such behavior is difficult to capture in the original framework because it involves reasoning about counterfactual executions, including ones that are not consistent with the protocol. Attempts to formalize these notions without counterfactuals are shown to lead to rather counterintuitive behavior.


title: Staging Transformations for Multimodal Web Interaction Management

abstract: Multimodal interfaces are becoming increasingly ubiquitous with the advent of mobile devices, accessibility considerations, and novel software technologies that combine diverse interaction media. In addition to improving access and delivery capabilities, such interfaces enable flexible and personalized dialogs with websites, much like a conversation between humans. In this paper, we present a software framework for multimodal web interaction management that supports mixed-initiative dialogs between users and websites. A mixed-initiative dialog is one where the user and the website take turns changing the flow of interaction. The framework supports the functional specification and realization of such dialogs using staging transformations -- a theory for representing and reasoning about dialogs based on partial input. It supports multiple interaction interfaces, and offers sessioning, caching, and co-ordination functions through the use of an interaction manager. Two case studies are presented to illustrate the promise of this approach.


title: Set K-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks

abstract: Wireless sensor networks (WSNs) are emerging as an effective means for environment monitoring. This paper investigates a strategy for energy efficient monitoring in WSNs that partitions the sensors into covers, and then activates the covers iteratively in a round-robin fashion. This approach takes advantage of the overlap created when many sensors monitor a single area. Our work builds upon previous work in "Power Efficient Organization of Wireless Sensor Networks" by Slijepcevic and Potkonjak, where the model is first formulated. We have designed three approximation algorithms for a variation of the SET K-COVER problem, where the objective is to partition the sensors into covers such that the number of covers that include an area, summed over all areas, is maximized. The first algorithm is randomized and partitions the sensors, in expectation, within a fraction 1 - 1/e (~.63) of the optimum. We present two other deterministic approximation algorithms. One is a distributed greedy algorithm with a 1/2 approximation ratio and the other is a centralized greedy algorithm with a 1 - 1/e approximation ratio. We show that it is NP-Complete to guarantee better than 15/16 of the optimal coverage, indicating that all three algorithms perform well with respect to the best approximation algorithm possible. Simulations indicate that in practice, the deterministic algorithms perform far above their worst case bounds, consistently covering more than 72% of what is covered by an optimum solution. Simulations also indicate that the increase in longevity is proportional to the amount of overlap amongst the sensors. The algorithms are fast, easy to use, and according to simulations, significantly increase the longevity of sensor networks. The randomized algorithm in particular seems quite practical.


title: Towards an Intelligent Database System Founded on the SP Theory of Computing and Cognition

abstract: The SP theory of computing and cognition, described in previous publications, is an attractive model for intelligent databases because it provides a simple but versatile format for different kinds of knowledge, it has capabilities in artificial intelligence, and it can also function like established database models when that is required. This paper describes how the SP model can emulate other models used in database applications and compares the SP model with those other models. The artificial intelligence capabilities of the SP model are reviewed and its relationship with other artificial intelligence systems is described. Also considered are ways in which current prototypes may be translated into an 'industrial strength' working system.


title: A Very Short Self-Interpreter

abstract: In this paper we would like to present a very short (possibly the shortest) self-interpreter, based on a simplistic Turing-complete imperative language. This interpreter explicitly processes the statements of the language, which means the interpreter constitutes a description of the language inside that same language. The paper does not require any specific knowledge; however, experience in programming and a vivid imagination are beneficial.


title: The Rank-Frequency Analysis for the Functional Style Corpora in the Ukrainian Language

abstract: We use the rank-frequency analysis for the estimation of Kernel Vocabulary size within specific corpora of Ukrainian. The extrapolation of high-rank behaviour is utilized for estimation of the total vocabulary size.


title: Visualization of variations in human brain morphology using differentiating reflection functions

abstract: Conventional visualization media such as MRI prints and computer screens are inherently two dimensional, making them incapable of displaying true 3D volume data sets. By applying only transparency or intensity projection, and ignoring light-matter interaction, results will likely fail to give optimal results. Little research has been done on using reflectance functions to visually separate the various segments of a MRI volume. We will explore if applying specific reflectance functions to individual anatomical structures can help in building an intuitive 2D image from a 3D dataset. We will test our hypothesis by visualizing a statistical analysis of the genetic influences on variations in human brain morphology because it inherently contains complex and many different types of data making it a good candidate for our approach


title: Improving TCP/IP Performance over Wireless IEEE 802.11 Link

abstract: Cellular phones, wireless laptops, personal portable devices that supports both voice and data access are all examples of communicating devices that uses wireless communication. Sine TCP/IP (and UDP) is the dominant technology in use in the internet, it is expected that they will be used (and they are currently) over wireless connections. In this paper, we investigate the performance of the TCP (and UDP) over IEEE802.11 wireless MAC protocol. We investigate the performance of the TCP and UDP assuming three different traffic patterns. First bulk transmission where the main concern is the throughput. Second real-time audio (using UDP) in the existence of bulk TCP transmission where the main concern is the packet loss for audio traffic. Finally web traffic where the main concern is the response time. We also investigate the effect of using forward Error Correction (FEC) technique and the MAC sublayer parameters on the throughput and response time.


title: Measuring the Functional Load of Phonological Contrasts

abstract: Frequency counts are a measure of how much use a language makes of a linguistic unit, such as a phoneme or word. However, what is often important is not the units themselves, but the contrasts between them. A measure is therefore needed for how much use a language makes of a contrast, i.e. the functional load (FL) of the contrast. We generalize previous work in linguistics and speech recognition and propose a family of measures for the FL of several phonological contrasts, including phonemic oppositions, distinctive features, suprasegmentals, and phonological rules. We then test it for robustness to changes of corpora. Finally, we provide examples in Cantonese, Dutch, English, German and Mandarin, in the context of historical linguistics, language acquisition and speech recognition. More information can be found at http://dinoj.info/research/fload


title: DUCT: An Interactive Define-Use Chain Navigation Tool for Relative Debugging

abstract: This paper describes an interactive tool that facilitates following define-use chains in large codes. The motivation for the work is to support relative debugging, where it is necessary to iteratively refine a set of asser-tions between different versions of a program. DUCT is novel because it exploits the Microsoft Intermediate Language (MSIL) that underpins the .NET Framework. Accordingly, it works on a wide range of programming languages without any modification. The paper describes the design and implementation of DUCT, and then illustrates its use with a small case study.


title: XPath-Logic and XPathLog: A Logic-Programming Style XML Data Manipulation Language

abstract: We define XPathLog as a Datalog-style extension of XPath. XPathLog provides a clear, declarative language for querying and manipulating XML whose perspectives are especially in XML data integration. In our characterization, the formal semantics is defined wrt. an edge-labeled graph-based model which covers the XML data model. We give a complete, logic-based characterization of XML data and the main language concept for XML, XPath. XPath-Logic extends the XPath language with variable bindings and embeds it into first-order logic. XPathLog is then the Horn fragment of XPath-Logic, providing a Datalog-style, rule-based language for querying and manipulating XML data. The model-theoretic semantics of XPath-Logic serves as the base of XPathLog as a logic-programming language, whereas also an equivalent answer-set semantics for evaluating XPathLog queries is given. In contrast to other approaches, the XPath syntax and semantics is also used for a declarative specification how the database should be updated: when used in rule heads, XPath filters are interpreted as specifications of elements and properties which should be added to the database.


title: Quantum m-out-of-n Oblivious Transfer

abstract: In the m-out-of-n oblivious transfer (OT) model, one party Alice sends n bits to another party Bob, Bob can get only m bits from the n bits. However, Alice cannot know which m bits Bob received. Y.Mu[MJV02]} and Naor[Naor01] presented classical m-out-of-n oblivious transfer based on discrete logarithm. As the work of Shor [Shor94], the discrete logarithm can be solved in polynomial time by quantum computers, so such OTs are unsafe to the quantum computer. In this paper, we construct a quantum m-out-of-n OT (QOT) scheme based on the transmission of polarized light and show that the scheme is robust to general attacks, i.e. the QOT scheme satisfies statistical correctness and statistical privacy.


title: Idempotent I/O for safe time travel

abstract: Debuggers for logic programming languages have traditionally had a capability most other debuggers did not: the ability to jump back to a previous state of the program, effectively travelling back in time in the history of the computation. This ``retry'' capability is very useful, allowing programmers to examine in detail a part of the computation that they previously stepped over. Unfortunately, it also creates a problem: while the debugger may be able to restore the previous values of variables, it cannot restore the part of the program's state that is affected by I/O operations. If the part of the computation being jumped back over performs I/O, then the program will perform these I/O operations twice, which will result in unwanted effects ranging from the benign (e.g. output appearing twice) to the fatal (e.g. trying to close an already closed file). We present a simple mechanism for ensuring that every I/O action called for by the program is executed at most once, even if the programmer asks the debugger to travel back in time from after the action to before the action. The overhead of this mechanism is low enough and can be controlled well enough to make it practical to use it to debug computations that do significant amounts of I/O.


title: S-ToPSS: Semantic Toronto Publish/Subscribe System

abstract: The increase in the amount of data on the Internet has led to the development of a new generation of applications based on selective information dissemination where, data is distributed only to interested clients. Such applications require a new middleware architecture that can efficiently match user interests with available information. Middleware that can satisfy this requirement include event-based architectures such as publish-subscribe systems. In this demonstration paper we address the problem of semantic matching. We investigate how current publish/subscribe systems can be extended with semantic capabilities. Our main contribution is the development and validation (through demonstration) of a semantic pub/sub system prototype S-ToPSS (Semantic Toronto Publish/Subscribe System).


title: Toward Attribute Efficient Learning Algorithms

abstract: We make progress on two important problems regarding attribute efficient learnability. First, we give an algorithm for learning decision lists of length $k$ over $n$ variables using $2^{\tilde{O}(k^{1/3})} \log n$ examples and time $n^{\tilde{O}(k^{1/3})}$. This is the first algorithm for learning decision lists that has both subexponential sample complexity and subexponential running time in the relevant parameters. Our approach establishes a relationship between attribute efficient learning and polynomial threshold functions and is based on a new construction of low degree, low weight polynomial threshold functions for decision lists. For a wide range of parameters our construction matches a 1994 lower bound due to Beigel for the ODDMAXBIT predicate and gives an essentially optimal tradeoff between polynomial threshold function degree and weight. Second, we give an algorithm for learning an unknown parity function on $k$ out of $n$ variables using $O(n^{1-1/k})$ examples in time polynomial in $n$. For $k=o(\log n)$ this yields a polynomial time algorithm with sample complexity $o(n)$. This is the first polynomial time algorithm for learning parity on a superconstant number of variables with sublinear sample complexity.


title: Combining Logic Programs and Monadic Second Order Logics by Program Transformation

abstract: We present a program synthesis method based on unfold/fold transformation rules which can be used for deriving terminating definite logic programs from formulas of the Weak Monadic Second Order theory of one successor (WS1S). This synthesis method can also be used as a proof method which is a decision procedure for closed formulas of WS1S. We apply our synthesis method for translating CLP(WS1S) programs into logic programs and we use it also as a proof method for verifying safety properties of infinite state systems.


title: Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism

abstract: Program specialization is a program transformation methodology which improves program efficiency by exploiting the information about the input data which are available at compile time. We show that current techniques for program specialization based on partial evaluation do not perform well on nondeterministic logic programs. We then consider a set of transformation rules which extend the ones used for partial evaluation, and we propose a strategy for guiding the application of these extended rules so to derive very efficient specialized programs. The efficiency improvements which sometimes are exponential, are due to the reduction of nondeterminism and to the fact that the computations which are performed by the initial programs in different branches of the computation trees, are performed by the specialized programs within single branches. In order to reduce nondeterminism we also make use of mode information for guiding the unfolding process. To exemplify our technique, we show that we can automatically derive very efficient matching programs and parsers for regular languages. The derivations we have performed could not have been done by previously known partial evaluation techniques.


title: Unsupervised Grammar Induction in a Framework of Information Compression by Multiple Alignment, Unification and Search

abstract: This paper describes a novel approach to grammar induction that has been developed within a framework designed to integrate learning with other aspects of computing, AI, mathematics and logic. This framework, called "information compression by multiple alignment, unification and search" (ICMAUS), is founded on principles of Minimum Length Encoding pioneered by Solomonoff and others. Most of the paper describes SP70, a computer model of the ICMAUS framework that incorporates processes for unsupervised learning of grammars. An example is presented to show how the model can infer a plausible grammar from appropriate input. Limitations of the current model and how they may be overcome are briefly discussed.


title: Algebras for Agent Norm-Regulation

abstract: An abstract architecture for idealized multi-agent systems whose behaviour is regulated by normative systems is developed and discussed. Agent choices are determined partially by the preference ordering of possible states and partially by normative considerations: The agent chooses that act which leads to the best outcome of all permissible actions. If an action is non-permissible depends on if the result of performing that action leads to a state satisfying a condition which is forbidden, according to the norms regulating the multi-agent system. This idea is formalized by defining set-theoretic predicates characterizing multi-agent systems. The definition of the predicate uses decision theory, the Kanger-Lindahl theory of normative positions, and an algebraic representation of normative systems.


title: I know what you mean: semantic issues in Internet-scale publish/subscribe systems

abstract: In recent years, the amount of information on the Internet has increased exponentially developing great interest in selective information dissemination systems. The publish/subscribe paradigm is particularly suited for designing systems for routing information and requests according to their content throughout wide-area network of brokers. Current publish/subscribe systems use limited syntax-based content routing but since publishers and subscribers are anonymous and decoupled in time, space and location, often over wide-area network boundary, they do not necessarily speak the same language. Consequently, adding semantics to current publish/subscribe systems is important. In this paper we identify and examine the issues in developing semantic-based content routing for publish/subscribe broker networks.


title: Turning CARTwheels: An Alternating Algorithm for Mining Redescriptions

abstract: We present an unusual algorithm involving classification trees where two trees are grown in opposite directions so that they are matched at their leaves. This approach finds application in a new data mining task we formulate, called "redescription mining". A redescription is a shift-of-vocabulary, or a different way of communicating information about a given subset of data; the goal of redescription mining is to find subsets of data that afford multiple descriptions. We highlight the importance of this problem in domains such as bioinformatics, which exhibit an underlying richness and diversity of data descriptors (e.g., genes can be studied in a variety of ways). Our approach helps integrate multiple forms of characterizing datasets, situates the knowledge gained from one dataset in the context of others, and harnesses high-level abstractions for uncovering cryptic and subtle features of data. Algorithm design decisions, implementation details, and experimental results are presented.


title: Performance of TCP/UDP under Ad Hoc IEEE802.11

abstract: TCP is the De facto standard for connection oriented transport layer protocol, while UDP is the De facto standard for transport layer protocol, which is used with real time traffic for audio and video. Although there have been many attempts to measure and analyze the performance of the TCP protocol in wireless networks, very few research was done on the UDP or the interaction between TCP and UDP traffic over the wireless link. In this paper, we tudy the performance of TCP and UDP over IEEE802.11 ad hoc network. We used two topologies, a string and a mesh topology. Our work indicates that IEEE802.11 as a ad-hoc network is not very suitable for bulk transfer using TCP. It also indicates that it is much better for real-time audio. Although one has to be careful here since real-time audio does require much less bandwidth than the wireless link bandwidth. Careful and detailed studies are needed to further clarify that issue.


title: Data mining and Privacy in Public Sector using Intelligent Agents (discussion paper)

abstract: The public sector comprises government agencies, ministries, education institutions, health providers and other types of government, commercial and not-for-profit organisations. Unlike commercial enterprises, this environment is highly heterogeneous in all aspects. This forms a complex network which is not always optimised. A lack of optimisation and communication hinders information sharing between the network nodes limiting the flow of information. Another limiting aspect is privacy of personal information and security of operations of some nodes or segments of the network. Attempts to reorganise the network or improve communications to make more information available for sharing and analysis may be hindered or completely halted by public concerns over privacy, political agendas, social and technological barriers. This paper discusses a technical solution for information sharing while addressing the privacy concerns with no need for reorganisation of the existing public sector infrastructure . The solution is based on imposing an additional layer of Intelligent Software Agents and Knowledge Bases for data mining and analysis.