title: Quasi-Optimal Arithmetic for Quaternion Polynomials

abstract: Fast algorithms for arithmetic on real or complex polynomials are well-known and have proven to be not only asymptotically efficient but also very practical. Based on Fast Fourier Transform (FFT), they for instance multiply two polynomials of degree up to N or multi-evaluate one at N points simultaneously within quasi-linear time O(N.polylog N). An extension to (and in fact the mere definition of) polynomials over the skew-field H of quaternions is promising but still missing. The present work proposes three such definitions which in the commutative case coincide but for H turn out to differ, each one satisfying some desirable properties while lacking others. For each notion we devise algorithms for according arithmetic; these are quasi-optimal in that their running times match lower complexity bounds up to polylogarithmic factors.


title: Quantum Computation and Lattice Problems

abstract: We present the first explicit connection between quantum computation and lattice problems. Namely, we show a solution to the Unique Shortest Vector Problem (SVP) under the assumption that there exists an algorithm that solves the hidden subgroup problem on the dihedral group by coset sampling. Moreover, we solve the hidden subgroup problem on the dihedral group by using an average case subset sum routine. By combining the two results, we get a quantum reduction from $\Theta(n^{2.5})$-unique-SVP to the average case subset sum problem.


title: Learning to Paraphrase: An Unsupervised Approach Using Multiple-Sequence Alignment

abstract: We address the text-to-text generation problem of sentence-level paraphrasing -- a phenomenon distinct from and more difficult than word- or phrase-level paraphrasing. Our approach applies multiple-sequence alignment to sentences gathered from unannotated comparable corpora: it learns a set of paraphrasing patterns represented by word lattice pairs and automatically determines how to apply these patterns to rewrite new sentences. The results of our evaluation experiments show that the system derives accurate paraphrases, outperforming baseline systems.


title: A Method for Clustering Web Attacks Using Edit Distance

abstract: Cluster analysis often serves as the initial step in the process of data classification. In this paper, the problem of clustering different length input data is considered. The edit distance as the minimum number of elementary edit operations needed to transform one vector into another is used. A heuristic for clustering unequal length vectors, analogue to the well known k-means algorithm is described and analyzed. This heuristic determines cluster centroids expanding shorter vectors to the lengths of the longest ones in each cluster in a specific way. It is shown that the time and space complexities of the heuristic are linear in the number of input vectors. Experimental results on real data originating from a system for classification of Web attacks are given.


title: A Physics-Free Introduction to the Quantum Computation Model

abstract: This article defines and proves basic properties of the standard quantum circuit model of computation. The model is developed abstractly in close analogy with (classical) deterministic and probabilistic circuits, without recourse to any physical concepts or principles. It is intended as a primer for theoretical computer scientists who do not know--and perhaps do not care to know--any physics.


title: Stochastic Volatility in a Quantitative Model of Stock Market Returns

abstract: Standard quantitative models of the stock market predict a log-normal distribution for stock returns (Bachelier 1900, Osborne 1959), but it is recognised (Fama 1965) that empirical data, in comparison with a Gaussian, exhibit leptokurtosis (it has more probability mass in its tails and centre) and fat tails (probabilities of extreme events are underestimated). Different attempts to explain this departure from normality have coexisted. In particular, since one of the strong assumptions of the Gaussian model concerns the volatility, considered finite and constant, the new models were built on a non finite (Mandelbrot 1963) or non constant (Cox, Ingersoll and Ross 1985) volatility. We investigate in this thesis a very recent model (Dragulescu et al. 2002) based on a Brownian motion process for the returns, and a stochastic mean-reverting process for the volatility. In this model, the forward Kolmogorov equation that governs the time evolution of returns is solved analytically. We test this new theory against different stock indexes (Dow Jones Industrial Average, Standard and Poor s and Footsie), over different periods (from 20 to 105 years). Our aim is to compare this model with the classical Gaussian and with a simple Neural Network, used as a benchmark. We perform the usual statistical tests on the kurtosis and tails of the expected distributions, paying particular attention to the outliers. As claimed by the authors, the new model outperforms the Gaussian for any time lag, but is artificially too complex for medium and low frequencies, where the Gaussian is preferable. Moreover this model is still rejected for high frequencies, at a 0.05 level of significance, due to the kurtosis, incorrectly handled.


title: Efficient linear feedback shift registers with maximal period

abstract: We introduce and analyze an efficient family of linear feedback shift registers (LFSR's) with maximal period. This family is word-oriented and is suitable for implementation in software, thus provides a solution to a recent challenge posed in FSE '94. The classical theory of LFSR's is extended to provide efficient algorithms for generation of irreducible and primitive LFSR's of this new type.


title: Embedded Reflection Mapping

abstract: Environment maps are used to simulate reflections off curved objects. We present a technique to reflect a user, or a group of users, in a real environment, onto a virtual object, in a virtual reality application, using the live video feeds from a set of cameras, in real-time. Our setup can be used in a variety of environments ranging from outdoor or indoor scenes.


title: Individual Communication Complexity

abstract: We initiate the theory of communication complexity of individual inputs held by the agents, rather than worst-case or average-case. We consider total, partial, and partially correct protocols, one-way versus two-way, with and without help bits. The results are expressed in trems of Kolmogorov complexity.


title: Hidden Polynomial(s) Cryptosystems

abstract: We propose public-key cryptosystems with public key a system of polynomial equations, algebraic or differential, and private key a single polynomial or a small-size ideal. We set up probabilistic encryption, signature, and signcryption protocols.


title: Commitment Capacity of Discrete Memoryless Channels

abstract: In extension of the bit commitment task and following work initiated by Crepeau and Kilian, we introduce and solve the problem of characterising the optimal rate at which a discrete memoryless channel can be used for bit commitment. It turns out that the answer is very intuitive: it is the maximum equivocation of the channel (after removing trivial redundancy), even when unlimited noiseless bidirectional side communication is allowed. By a well-known reduction, this result provides a lower bound on the channel's capacity for implementing coin tossing, which we conjecture to be an equality. The method of proving this relates the problem to Wyner's wire--tap channel in an amusing way. We also discuss extensions to quantum channels.


title: A Performance Study of Monitoring and Information Services for Distributed Systems

abstract: Monitoring and information services form a key component of a distributed system, or Grid. A quantitative study of such services can aid in understanding the performance limitations, advise in the deployment of the systems, and help evaluate future development work. To this end, we study the performance of three monitoring and information services for distributed systems: the Globus Toolkit's Monitoring and Discovery Service (MDS), the European Data Grid Relational Grid Monitoring Architecture (R-GMA), and Hawkeye, part of the Condor project. We perform experiments to test their scalability with respect to number of users, number of resources, and amount of data collected. Our study shows that each approach has different behaviors, often due to their different design goals. In the four sets of experiments we conducted to evaluate the performance of the service components under different circumstances, we found a strong advantage to caching or prefetching the data, as well as the need to have primary components at well connected sites due to high load seen by all systems.


title: Symmetric and anti-symmetric quantum functions

abstract: This paper introduces and analyzes symmetric and anti-symmetric quantum binary functions. Generally, such functions uniquely convert a given computational basis state into a different basis state, but with either a plus or a minus sign. Such functions may serve along with a constant function (in a Deutsch-Jozsa type of algorithm) to provide 2**n deterministic qubit combinations (for n qubits) instead of just one.


title: Ground Canonicity

abstract: We explore how different proof orderings induce different notions of saturation. We relate completion, paramodulation, saturation, redundancy elimination, and rewrite system reduction to proof orderings.


title: Quasiconvex Analysis of Backtracking Algorithms

abstract: We consider a class of multivariate recurrences frequently arising in the worst case analysis of Davis-Putnam-style exponential time backtracking algorithms for NP-hard problems. We describe a technique for proving asymptotic upper bounds on these recurrences, by using a suitable weight function to reduce the problem to that of solving univariate linear recurrences; show how to use quasiconvex programming to determine the weight function yielding the smallest upper bound; and prove that the resulting upper bounds are within a polynomial factor of the true asymptotics of the recurrence. We develop and implement a multiple-gradient descent algorithm for the resulting quasiconvex programs, using a real-number arithmetic package for guaranteed accuracy of the computed worst case time bounds.


title: Blind Normalization of Speech From Different Channels

abstract: We show how to construct a channel-independent representation of speech that has propagated through a noisy reverberant channel. This is done by blindly rescaling the cepstral time series by a non-linear function, with the form of this scale function being determined by previously encountered cepstra from that channel. The rescaled form of the time series is an invariant property of it in the following sense: it is unaffected if the time series is transformed by any time-independent invertible distortion. Because a linear channel with stationary noise and impulse response transforms cepstra in this way, the new technique can be used to remove the channel dependence of a cepstral time series. In experiments, the method achieved greater channel-independence than cepstral mean normalization, and it was comparable to the combination of cepstral mean normalization and spectral subtraction, despite the fact that no measurements of channel noise or reverberations were required (unlike spectral subtraction).


title: A direct sum theorem in communication complexity via message compression

abstract: We prove lower bounds for the direct sum problem for two-party bounded error randomised multiple-round communication protocols. Our proofs use the notion of information cost of a protocol, as defined by Chakrabarti, Shi, Wirth and Yao and refined further by Bar-Yossef, Jayram, Kumar and Sivakumar. Our main technical result is a `compression' theorem saying that, for any probability distribution $\mu$ over the inputs, a $k$-round private coin bounded error protocol for a function $f$ with information cost $c$ can be converted into a $k$-round deterministic protocol for $f$ with bounded distributional error and communication cost $O(kc)$. We prove this result using a substate theorem about relative entropy and a rejection sampling argument. Our direct sum result follows from this `compression' result via elementary information theoretic arguments. We also consider the direct sum problem in quantum communication. Using a probabilistic argument, we show that messages cannot be compressed in this manner even if they carry small information. Hence, new techniques may be necessary to tackle the direct sum problem in quantum communication.


title: Model Checking for a Class of Weighted Automata

abstract: A large number of different model checking approaches has been proposed during the last decade. The different approaches are applicable to different model types including untimed, timed, probabilistic and stochastic models. This paper presents a new framework for model checking techniques which includes some of the known approaches, but enlarges the class of models for which model checking can be applied to the general class of weighted automata. The approach allows an easy adaption of model checking to models which have not been considered yet for this purpose. Examples for those new model types for which model checking can be applied are max/plus or min/plus automata which are well established models to describe different forms of dynamic systems and optimization problems. In this context, model checking can be used to verify temporal or quantitative properties of a system. The paper first presents briefly our class of weighted automata, as a very general model type. Then Valued Computational Tree Logic (CTL$) is introduced as a natural extension of the well known branching time logic CTL. Afterwards, algorithms to check a weighted automaton according to a CTL$ formula are presented. As a last result, a bisimulation is presented for weighted automata and for CTL$.


title: Self-Replicating Machines in Continuous Space with Virtual Physics

abstract: JohnnyVon is an implementation of self-replicating machines in continuous two-dimensional space. Two types of particles drift about in a virtual liquid. The particles are automata with discrete internal states but continuous external relationships. Their internal states are governed by finite state machines but their external relationships are governed by a simulated physics that includes Brownian motion, viscosity, and spring-like attractive and repulsive forces. The particles can be assembled into patterns that can encode arbitrary strings of bits. We demonstrate that, if an arbitrary "seed" pattern is put in a "soup" of separate individual particles, the pattern will replicate by assembling the individual particles into copies of itself. We also show that, given sufficient time, a soup of separate individual particles will eventually spontaneously form self-replicating patterns. We discuss the implications of JohnnyVon for research in nanotechnology, theoretical biology, and artificial life.


title: Partitioning Regular Polygons into Circular Pieces I: Convex Partitions

abstract: We explore an instance of the question of partitioning a polygon into pieces, each of which is as ``circular'' as possible, in the sense of having an aspect ratio close to 1. The aspect ratio of a polygon is the ratio of the diameters of the smallest circumscribing circle to the largest inscribed disk. The problem is rich even for partitioning regular polygons into convex pieces, the focus of this paper. We show that the optimal (most circular) partition for an equilateral triangle has an infinite number of pieces, with the lower bound approachable to any accuracy desired by a particular finite partition. For pentagons and all regular k-gons, k > 5, the unpartitioned polygon is already optimal. The square presents an interesting intermediate case. Here the one-piece partition is not optimal, but nor is the trivial lower bound approachable. We narrow the optimal ratio to an aspect-ratio gap of 0.01082 with several somewhat intricate partitions.


title: Glottochronologic Retrognostic of Language System

abstract: A glottochronologic retrognostic of language system is proposed


title: Computational Geometry Column 44

abstract: The open problem of whether or not every pair of equal-area polygons has a hinged dissection is discussed.


title: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

abstract: Given a $k$-uniform hyper-graph, the E$k$-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyper-edge. We present a new multilayered PCP construction that extends the Raz verifier. This enables us to prove that E$k$-Vertex-Cover is NP-hard to approximate within factor $(k-1-\epsilon)$ for any $k \geq 3$ and any $\epsilon>0$. The result is essentially tight as this problem can be easily approximated within factor $k$. Our construction makes use of the biased Long-Code and is analyzed using combinatorial properties of $s$-wise $t$-intersecting families of subsets.


title: "I'm sorry Dave, I'm afraid I can't do that": Linguistics, Statistics, and Natural Language Processing circa 2001

abstract: A brief, general-audience overview of the history of natural language processing, focusing on data-driven approaches.Topics include "Ambiguity and language analysis", "Firth things first", "A 'C' change", and "The empiricists strike back".


title: Grid-Enabling Natural Language Engineering By Stealth

abstract: We describe a proposal for an extensible, component-based software architecture for natural language engineering applications. Our model leverages existing linguistic resource description and discovery mechanisms based on extended Dublin Core metadata. In addition, the application design is flexible, allowing disparate components to be combined to suit the overall application functionality. An application specification language provides abstraction from the programming environment and allows ease of interface with computational grids via a broker.


title: An XML based Document Suite

abstract: We report about the current state of development of a document suite and its applications. This collection of tools for the flexible and robust processing of documents in German is based on the use of XML as unifying formalism for encoding input and output data as well as process information. It is organized in modules with limited responsibilities that can easily be combined into pipelines to solve complex tasks. Strong emphasis is laid on a number of techniques to deal with lexical and conceptual gaps that are typical when starting a new application.


title: Small Spans in Scaled Dimension

abstract: Juedes and Lutz (1995) proved a small span theorem for polynomial-time many-one reductions in exponential time. This result says that for language A decidable in exponential time, either the class of languages reducible to A (the lower span) or the class of problems to which A can be reduced (the upper span) is small in the sense of resource-bounded measure and, in particular, that the degree of A is small. Small span theorems have been proven for increasingly stronger polynomial-time reductions, and a small span theorem for polynomial-time Turing reductions would imply BPP != EXP. In contrast to the progress in resource-bounded measure, Ambos-Spies, Merkle, Reimann, and Stephan (2001) showed that there is no small span theorem for the resource-bounded dimension of Lutz (2000), even for polynomial-time many-one reductions. Resource-bounded scaled dimension, recently introduced by Hitchcock, Lutz, and Mayordomo (2003), provides rescalings of resource-bounded dimension. We use scaled dimension to further understand the contrast between measure and dimension regarding polynomial-time spans and degrees. We strengthen prior results by showing that the small span theorem holds for polynomial-time many-one reductions in the -3rd-order scaled dimension, but fails to hold in the -2nd-order scaled dimension. Our results also hold in exponential space. As an application, we show that determining the -2nd- or -1st-order scaled dimension in ESPACE of the many-one complete languages for E would yield a proof of P = BPP or P != PSPACE. On the other hand, it is shown unconditionally that the complete languages for E have -3rd-order scaled dimension 0 in ESPACE and -2nd- and -1st-order scaled dimension 1 in E.


title: Transforming the Structure of Network Interconnection and Transport

abstract: Vibrant development of a network-based economy requires separating investment in highly location specific local access technology from the development of standardized, geography-independent, wide-area network services. Thus far interconnection arrangements and associated regulations have been too closely tied to the idiosyncratic geographic structure of individual operators' networks. A key industry challenge is to foster the development of a wide area lattice of common geographic points of interconnection. Sound regulatory and anti-trust policy can help address this industry need.


title: Growth in the "New Economy": U.S. Bandwidth Use and Pricing Across the 1990s

abstract: An acceleration in the growth of communications bandwidth in use and a rapid reduction in bandwidth prices have not accompanied the U.S. economy's strong performance in the second half of the 1990s. Overall U.S. bandwidth in use has grown robustly throughout the 1990s, but growth has not significantly accelerated in the second half of 1990s. Average prices for U.S. bandwidth in use have fallen little in nominal terms in the second half of the 1990s. Policy makers and policy analysts should recognize that institutional change, rather than more competitors of established types, appears to be key to dramatic improvements in bandwidth growth and prices. Such a development could provide a significant additional impetus to aggregate growth and productivity.


title: A New Account of Personalization and Effective Communication

abstract: To contribute to understanding of information economies of daily life, this paper explores over the past millennium given names of a large number of persons. Analysts have long both condemned and praised mass media as a source of common culture, national unity, or shared symbolic experiences. Names, however, indicate a large decline in shared symbolic experience over the past two centuries, a decline that the growth of mass media does not appear to have affected significantly. Study of names also shows that action and personal relationships, along with time horizon, are central aspects of effective communication across a large population. The observed preference for personalization over the past two centuries and the importance of action and personal relationships to effective communication are aspects of information economies that are likely to have continuing significance for industry developments, economic statistics, and public policy.


title: Revolutionary Ideas for Radio Regulation

abstract: Radio technology seems destined to become part of the standard micro-processor input/output system. But unlike for memory or display systems, for radio systems government regulation matters a lot. Much discussion of radio regulation has focused on narrow spectrum management and interference issues. Reflecting on historical experience and centuries of conversation about fundamental political choices, persons working with radio technology should also ponder three questions. First, what is a good separation and balance of powers in radio regulation? Second, how should radio regulation be geographically configured? Third, how should radio regulation understand and respect personal freedom and equality? Working out answering to these questions involves a general process of shaping good government. This process will be hugely important for radio regulation, technology, and applications.


title: Exploiting Sublanguage and Domain Characteristics in a Bootstrapping Approach to Lexicon and Ontology Creation

abstract: It is very costly to build up lexical resources and domain ontologies. Especially when confronted with a new application domain lexical gaps and a poor coverage of domain concepts are a problem for the successful exploitation of natural language document analysis systems that need and exploit such knowledge sources. In this paper we report about ongoing experiments with `bootstrapping techniques' for lexicon and ontology creation.


title: An Approach for Resource Sharing in Multilingual NLP

abstract: In this paper we describe an approach for the analysis of documents in German and English with a shared pool of resources. For the analysis of German documents we use a document suite, which supports the user in tasks like information retrieval and information extraction. The core of the document suite is based on our tool XDOC. Now we want to exploit these methods for the analysis of English documents as well. For this aim we need a multilingual presentation format of the resources. These resources must be transformed into an unified format, in which we can set additional information about linguistic characteristics of the language depending on the analyzed documents. In this paper we describe our approach for such an exchange model for multilingual resources based on XML.


title: Using Regression Techniques to Predict Large Data Transfers

abstract: The recent proliferation of Data Grids and the increasingly common practice of using resources as distributed data stores provide a convenient environment for communities of researchers to share, replicate, and manage access to copies of large datasets. This has led to the question of which replica can be accessed most efficiently. In such environments, fetching data from one of the several replica locations requires accurate predictions of end-to-end transfer times. The answer to this question can depend on many factors, including physical characteristics of the resources and the load behavior on the CPUs, networks, and storage devices that are part of the end-to-end data path linking possible sources and sinks. Our approach combines end-to-end application throughput observations with network and disk load variations and captures whole-system performance and variations in load patterns. Our predictions characterize the effect of load variations of several shared devices (network and disk) on file transfer times. We develop a suite of univariate and multivariate predictors that can use multiple data sources to improve the accuracy of the predictions as well as address Data Grid variations (availability of data and sporadic nature of transfers). We ran a large set of data transfer experiments using GridFTP and observed performance predictions within 15% error for our testbed sites, which is quite promising for a pragmatic system.


title: How NP got a new definition: a survey of probabilistically checkable proofs

abstract: We survey a collective achievement of a group of researchers: the PCP Theorems. They give new definitions of the class \np, and imply that computing approximate solutions to many \np-hard problems is itself \np-hard. Techniques developed to prove them have had many other consequences.


title: Approximation thresholds for combinatorial optimization problems

abstract: An NP-hard combinatorial optimization problem $\Pi$ is said to have an {\em approximation threshold} if there is some $t$ such that the optimal value of $\Pi$ can be approximated in polynomial time within a ratio of $t$, and it is NP-hard to approximate it within a ratio better than $t$. We survey some of the known approximation threshold results, and discuss the pattern that emerges from the known results.


title: Hardness as randomness: a survey of universal derandomization

abstract: We survey recent developments in the study of probabilistic complexity classes. While the evidence seems to support the conjecture that probabilism can be deterministically simulated with relatively low overhead, i.e., that $P=BPP$, it also indicates that this may be a difficult question to resolve. In fact, proving that probabilistic algorithms have non-trivial deterministic simulations is basically equivalent to proving circuit lower bounds, either in the algebraic or Boolean models.


title: $P \ne NP$, propositional proof complexity, and resolution lower bounds for the weak pigeonhole principle

abstract: Recent results established exponential lower bounds for the length of any Resolution proof for the weak pigeonhole principle. More formally, it was proved that any Resolution proof for the weak pigeonhole principle, with $n$ holes and any number of pigeons, is of length $\Omega(2^{n^{\epsilon}})$, (for a constant $\epsilon = 1/3$). One corollary is that certain propositional formulations of the statement $P \ne NP$ do not have short Resolution proofs. After a short introduction to the problem of $P \ne NP$ and to the research area of propositional proof complexity, I will discuss the above mentioned lower bounds for the weak pigeonhole principle and the connections to the hardness of proving $P \ne NP$.


title: On probabilistic analog automata

abstract: We consider probabilistic automata on a general state space and study their computational power. The model is based on the concept of language recognition by probabilistic automata due to Rabin and models of analog computation in a noisy environment suggested by Maass and Orponen, and Maass and Sontag. Our main result is a generalization of Rabin's reduction theorem that implies that under very mild conditions, the computational power of the automaton is limited to regular languages.


title: gTybalt - a free computer algebra system

abstract: This article documents the free computer algebra system "gTybalt". The program is build on top of other packages, among others GiNaC, TeXmacs and Root. It offers the possibility of interactive symbolic calculations within the C++ programming language. Mathematical formulae are visualized using TeX fonts.


title: Hardness of approximating the weight enumerator of a binary linear code

abstract: We consider the problem of evaluation of the weight enumerator of a binary linear code. We show that the exact evaluation is hard for polynomial hierarchy. More exactly, if WE is an oracle answering the solution of the evaluation problem then P^WE=P^GapP. Also we consider the approximative evaluation of the weight enumerator. In the case of approximation with additive accuracy $2^{\alpha n}$, $\alpha$ is constant the problem is hard in the above sense. We also prove that approximate evaluation at a single point $e^{\pi i/4}$ is hard for $0<\al<\al_0\approx0.88$.


title: On a composition of digraphs

abstract: Many "good" topologies for interconnection networks are based on line digraphs of regular digraphs. These digraphs support unitary matrices. We propose the property "being the digraph of a unitary matrix" as additional criterion for the design of new interconnection networks. We define a composition of digraphs, which we call diagonal union. Diagonal union can be used to construct digraphs of unitary matrices. We remark that digraphs obtained via diagonal union are state split graphs, as defined in symbolic dynamics. Finally, we list some potential directions for future research.


title: Distributed States Temporal Logic

abstract: We introduce a temporal logic to reason on global applications in an asynchronous setting. First, we define the Distributed States Logic (DSL), a modal logic for localities that embeds the local theories of each component into a theory of the distributed states of the system. We provide the logic with a sound and complete axiomatization. The contribution is that it is possible to reason about properties that involve several components, even in the absence of a global clock. Then, we define the Distributed States Temporal Logic (DSTL) by introducing temporal operators a' la Unity. We support our proposal by working out a pair of examples: a simple secure communication system, and an algorithm for distributed leader election. The motivation for this work is that the existing logics for distributed systems do not have the right expressive power to reason on the systems behaviour, when the communication is based on asynchronous message passing. On the other side, asynchronous communication is the most used abstraction when modelling global applications.


title: A Framework for Searching AND/OR Graphs with Cycles

abstract: Search in cyclic AND/OR graphs was traditionally known to be an unsolved problem. In the recent past several important studies have been reported in this domain. In this paper, we have taken a fresh look at the problem. First, a new and comprehensive theoretical framework for cyclic AND/OR graphs has been presented, which was found missing in the recent literature. Based on this framework, two best-first search algorithms, S1 and S2, have been developed. S1 does uninformed search and is a simple modification of the Bottom-up algorithm by Martelli and Montanari. S2 performs a heuristically guided search and replicates the modification in Bottom-up's successors, namely HS and AO*. Both S1 and S2 solve the problem of searching AND/OR graphs in presence of cycles. We then present a detailed analysis for the correctness and complexity results of S1 and S2, using the proposed framework. We have observed through experiments that S1 and S2 output correct results in all cases.


title: Hybrid Rounding Techniques for Knapsack Problems

abstract: We address the classical knapsack problem and a variant in which an upper bound is imposed on the number of items that can be selected. We show that appropriate combinations of rounding techniques yield novel and powerful ways of rounding. As an application of these techniques, we present a linear-storage Polynomial Time Approximation Scheme (PTAS) and a Fully Polynomial Time Approximation Scheme (FPTAS) that compute an approximate solution, of any fixed accuracy, in linear time. This linear complexity bound gives a substantial improvement of the best previously known polynomial bounds.


title: The Ubiquitous Interactor - Device Independent Access to Mobile Services

abstract: The Ubiquitous Interactor (UBI) addresses the problems of design and development that arise around services that need to be accessed from many different devices. In UBI, the same service can present itself with different user interfaces on different devices. This is done by separating interaction between users and services from presentation. The interaction is kept the same for all devices, and different presentation information is provided for different devices. This way, tailored user interfaces for many different devices can be created without multiplying development and maintenance work. In this paper we describe the system design of UBI, the system implementation, and two services implemented for the system: a calendar service and a stockbroker service.


title: Approximate Grammar for Information Extraction

abstract: In this paper, we present the concept of Approximate grammar and how it can be used to extract information from a documemt. As the structure of informational strings cannot be defined well in a document, we cannot use the conventional grammar rules to represent the information. Hence, the need arises to design an approximate grammar that can be used effectively to accomplish the task of Information extraction. Approximate grammars are a novel step in this direction. The rules of an approximate grammar can be given by a user or the machine can learn the rules from an annotated document. We have performed our experiments in both the above areas and the results have been impressive.


title: An In-Place Sorting with O(n log n) Comparisons and O(n) Moves

abstract: We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports. This solves a long-standing open problem, stated explicitly, e.g., in [J.I. Munro and V. Raman, Sorting with minimum data movement, J. Algorithms, 13, 374-93, 1992], of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously.


title: On the Ramsey Numbers for Bipartite Multigraphs

abstract: A coloring of a complete bipartite graph is shuffle-preserved if it is the case that assigning a color $c$ to edges $(u, v)$ and $(u', v')$ enforces the same color assignment for edges $(u, v')$ and $(u',v)$. (In words, the induced subgraph with respect to color $c$ is complete.) In this paper, we investigate a variant of the Ramsey problem for the class of complete bipartite multigraphs. (By a multigraph we mean a graph in which multiple edges, but no loops, are allowed.) Unlike the conventional m-coloring scheme in Ramsey theory which imposes a constraint (i.e., $m$) on the total number of colors allowed in a graph, we introduce a relaxed version called m-local coloring which only requires that, for every vertex $v$, the number of colors associated with $v$'s incident edges is bounded by $m$. Note that the number of colors found in a graph under $m$-local coloring may exceed m. We prove that given any $n \times n$ complete bipartite multigraph $G$, every shuffle-preserved $m$-local coloring displays a monochromatic copy of $K_{p,p}$ provided that $2(p-1)(m-1) < n$. Moreover, the above bound is tight when (i) $m=2$, or (ii) $n=2^k$ and $m=3\cdot 2^{k-2}$ for every integer $k\geq 2$. As for the lower bound of $p$, we show that the existence of a monochromatic $K_{p,p}$ is not guaranteed if $p> \lceil \frac{n}{m} \rceil$. Finally, we give a generalization for $k$-partite graphs and a method applicable to general graphs. Many conclusions found in $m$-local coloring can be inferred to similar results of $m$-coloring.


title: Computing only minimal answers in disjunctive deductive databases

abstract: A method is presented for computing minimal answers in disjunctive deductive databases under the disjunctive stable model semantics. Such answers are constructed by repeatedly extending partial answers. Our method is complete (in that every minimal answer can be computed) and does not admit redundancy (in the sense that every partial answer generated can be extended to a minimal answer), whence no non-minimal answer is generated. For stratified databases, the method does not (necessarily) require the computation of models of the database in their entirety. Compilation is proposed as a tool by which problems relating to computational efficiency and the non-existence of disjunctive stable models can be overcome. The extension of our method to other semantics is also considered.


title: A Representation of Changes of Images and its Application for Developmental Biolology

abstract: In this paper, we consider a series of events observed at spaced time intervals and present a method of representation of the series. To explain an idea, by dealing with a set of gene expression data, which could be obtained from developmental biology, the procedures are sketched with comments in some details. We mean representation by choosing a proper function, which fits well with observed data of a series, and turning its characteristics into numbers, which extract the intrinsic properties of fluctuating data. With help of a machine learning techniques, this method will give a classification of developmental biological data as well as any varying data during a certain period and the classification can be applied for diagnosis of a disease.


title: The Threshold for Random k-SAT is 2^k ln2 - O(k)

abstract: Let F be a random k-SAT formula on n variables, formed by selecting uniformly and independently m = rn out of all possible k-clauses. It is well-known that if r>2^k ln 2, then the formula F is unsatisfiable with probability that tends to 1 as n tends to infinity. We prove that there exists a sequence t_k = O(k) such that if r < 2^k ln 2 - t_k, then the formula F is satisfiable with probability that tends to 1 as n tends to infinity. Our technique yields an explicit lower bound for the random k-SAT threshold for every k. For k>3 this improves upon all previously known lower bounds. For example, when k=10 our lower bound is 704.94 while the upper bound is 708.94.


title: The NPC Framework for Building Information Dissemination Networks

abstract: Numerous systems for dissemination, retrieval, and archiving of documents have been developed in the past. Those systems often focus on one of these aspects and are hard to extend and combine. Typically, the transmission protocols, query and filtering languages are fixed as well as the interfaces to other systems. We rather envisage the seamless establishment of networks among the providers, repositories and consumers of information, supporting information retrieval and dissemination while being highly interoperable and extensible. We propose a framework with a single event-based mechanism that unifies document storage, retrieval, and dissemination. This framework offers complete openness with respect to document and metadata formats, transmission protocols, and filtering mechanisms. It specifies a high-level building kit, by which arbitrary processors for document streams can be incorporated to support the retrieval, transformation, aggregation and disaggregation of documents. Using the same kit, interfaces for different transmission protocols can be added easily to enable the communication with various information sources and information consumers.


title: Optimizing Optimal Reduction: A Type Inference Algorithm for Elementary Affine Logic

abstract: We present a type inference algorithm for lambda-terms in Elementary Affine Logic using linear constraints. We prove that the algorithm is correct and complete.


title: Time-scales, Meaning, and Availability of Information in a Global Brain

abstract: We note the importance of time-scales, meaning, and availability of information for the emergence of novel information meta-structures at a global scale. We discuss previous work in this area and develop future perspectives. We focus on the transmission of scientific articles and the integration of traditional conferences with their virtual extensions on the Internet, their time-scales, and availability. We mention the Semantic Web as an effort for integrating meaningful information.


title: On Nonspecific Evidence

abstract: When simultaneously reasoning with evidences about several different events it is necessary to separate the evidence according to event. These events should then be handled independently. However, when propositions of evidences are weakly specified in the sense that it may not be certain to which event they are referring, this may not be directly possible. In this paper a criterion for partitioning evidences into subsets representing events is established. This criterion, derived from the conflict within each subset, involves minimising a criterion function for the overall conflict of the partition. An algorithm based on characteristics of the criterion function and an iterative optimisation among partitionings of evidences is proposed.


title: Dempster's Rule for Evidence Ordered in a Complete Directed Acyclic Graph

abstract: For the case of evidence ordered in a complete directed acyclic graph this paper presents a new algorithm with lower computational complexity for Dempster's rule than that of step-by-step application of Dempster's rule. In this problem, every original pair of evidences, has a corresponding evidence against the simultaneous belief in both propositions. In this case, it is uncertain whether the propositions of any two evidences are in logical conflict. The original evidences are associated with the vertices and the additional evidences are associated with the edges. The original evidences are ordered, i.e., for every pair of evidences it is determinable which of the two evidences is the earlier one. We are interested in finding the most probable completely specified path through the graph, where transitions are possible only from lower- to higher-ranked vertices. The path is here a representation for a sequence of states, for instance a sequence of snapshots of a physical object's track. A completely specified path means that the path includes no other vertices than those stated in the path representation, as opposed to an incompletely specified path that may also include other vertices than those stated. In a hierarchical network of all subsets of the frame, i.e., of all incompletely specified paths, the original and additional evidences support subsets that are not disjoint, thus it is not possible to prune the network to a tree. Instead of propagating belief, the new algorithm reasons about the logical conditions of a completely specified path through the graph. The new algorithm is O(|THETA| log |THETA|), compared to O(|THETA| ** log |THETA|) of the classic brute force algorithm.


title: Finding a Posterior Domain Probability Distribution by Specifying Nonspecific Evidence

abstract: This article is an extension of the results of two earlier articles. In [J. Schubert, On nonspecific evidence, Int. J. Intell. Syst. 8 (1993) 711-725] we established within Dempster-Shafer theory a criterion function called the metaconflict function. With this criterion we can partition into subsets a set of several pieces of evidence with propositions that are weakly specified in the sense that it may be uncertain to which event a proposition is referring. In a second article [J. Schubert, Specifying nonspecific evidence, in Cluster-based specification techniques in Dempster-Shafer theory for an evidential intelligence analysis of multiple target tracks, Ph.D. Thesis, TRITA-NA-9410, Royal Institute of Technology, Stockholm, 1994, ISBN 91-7170-801-4] we not only found the most plausible subset for each piece of evidence, we also found the plausibility for every subset that this piece of evidence belongs to the subset. In this article we aim to find a posterior probability distribution regarding the number of subsets. We use the idea that each piece of evidence in a subset supports the existence of that subset to the degree that this piece of evidence supports anything at all. From this we can derive a bpa that is concerned with the question of how many subsets we have. That bpa can then be combined with a given prior domain probability distribution in order to obtain the sought-after posterior domain distribution.


title: The one-round Voronoi game replayed

abstract: We consider the one-round Voronoi game, where player one (``White'', called ``Wilma'') places a set of n points in a rectangular area of aspect ratio r <=1, followed by the second player (``Black'', called ``Barney''), who places the same number of points. Each player wins the fraction of the board closest to one of his points, and the goal is to win more than half of the total area. This problem has been studied by Cheong et al., who showed that for large enough $n$ and r=1, Barney has a strategy that guarantees a fraction of 1/2+a, for some small fixed a. We resolve a number of open problems raised by that paper. In particular, we give a precise characterization of the outcome of the game for optimal play: We show that Barney has a winning strategy for n>2 and r>sqrt{2}/n, and for n=2 and r>sqrt{3}/2. Wilma wins in all remaining cases, i.e., for n>=3 and r<=sqrt{2}/n, for n=2 and r<=sqrt{3}/2, and for n=1. We also discuss complexity aspects of the game on more general boards, by proving that for a polygon with holes, it is NP-hard to maximize the area Barney can win against a given set of points by Wilma.


title: Cluster-based Specification Techniques in Dempster-Shafer Theory

abstract: When reasoning with uncertainty there are many situations where evidences are not only uncertain but their propositions may also be weakly specified in the sense that it may not be certain to which event a proposition is referring. It is then crucial not to combine such evidences in the mistaken belief that they are referring to the same event. This situation would become manageable if the evidences could be clustered into subsets representing events that should be handled separately. In an earlier article we established within Dempster-Shafer theory a criterion function called the metaconflict function. With this criterion we can partition a set of evidences into subsets. Each subset representing a separate event. In this article we will not only find the most plausible subset for each piece of evidence, we will also find the plausibility for every subset that the evidence belongs to the subset. Also, when the number of subsets are uncertain we aim to find a posterior probability distribution regarding the number of subsets.


title: Cluster-based Specification Techniques in Dempster-Shafer Theory for an Evidential Intelligence Analysis of MultipleTarget Tracks (Thesis Abstract)

abstract: In Intelligence Analysis it is of vital importance to manage uncertainty. Intelligence data is almost always uncertain and incomplete, making it necessary to reason and taking decisions under uncertainty. One way to manage the uncertainty in Intelligence Analysis is Dempster-Shafer Theory. This thesis contains five results regarding multiple target tracks and intelligence specification.


title: On rho in a Decision-Theoretic Apparatus of Dempster-Shafer Theory

abstract: Thomas M. Strat has developed a decision-theoretic apparatus for Dempster-Shafer theory (Decision analysis using belief functions, Intern. J. Approx. Reason. 4(5/6), 391-417, 1990). In this apparatus, expected utility intervals are constructed for different choices. The choice with the highest expected utility is preferable to others. However, to find the preferred choice when the expected utility interval of one choice is included in that of another, it is necessary to interpolate a discerning point in the intervals. This is done by the parameter rho, defined as the probability that the ambiguity about the utility of every nonsingleton focal element will turn out as favorable as possible. If there are several different decision makers, we might sometimes be more interested in having the highest expected utility among the decision makers rather than only trying to maximize our own expected utility regardless of choices made by other decision makers. The preference of each choice is then determined by the probability of yielding the highest expected utility. This probability is equal to the maximal interval length of rho under which an alternative is preferred. We must here take into account not only the choices already made by other decision makers but also the rational choices we can assume to be made by later decision makers. In Strats apparatus, an assumption, unwarranted by the evidence at hand, has to be made about the value of rho. We demonstrate that no such assumption is necessary. It is sufficient to assume a uniform probability distribution for rho to be able to discern the most preferable choice. We discuss when this approach is justifiable.


title: Specifying nonspecific evidence

abstract: In an earlier article [J. Schubert, On nonspecific evidence, Int. J. Intell. Syst. 8(6), 711-725 (1993)] we established within Dempster-Shafer theory a criterion function called the metaconflict function. With this criterion we can partition into subsets a set of several pieces of evidence with propositions that are weakly specified in the sense that it may be uncertain to which event a proposition is referring. Each subset in the partitioning is representing a separate event. The metaconflict function was derived as the plausibility that the partitioning is correct when viewing the conflict in Dempster's rule within each subset as a newly constructed piece of metalevel evidence with a proposition giving support against the entire partitioning. In this article we extend the results of the previous article. We will not only find the most plausible subset for each piece of evidence as was done in the earlier article. In addition we will specify each piece of nonspecific evidence, in the sense that we find to which events the proposition might be referring, by finding the plausibility for every subset that this piece of evidence belong to the subset. In doing this we will automatically receive indication that some evidence might be false. We will then develop a new methodology to exploit these newly specified pieces of evidence in a subsequent reasoning process. This will include methods to discount evidence based on their degree of falsity and on their degree of credibility due to a partial specification of affiliation, as well as a refined method to infer the event of each subset.


title: Creating Prototypes for Fast Classification in Dempster-Shafer Clustering

abstract: We develop a classification method for incoming pieces of evidence in Dempster-Shafer theory. This methodology is based on previous work with clustering and specification of originally nonspecific evidence. This methodology is here put in order for fast classification of future incoming pieces of evidence by comparing them with prototypes representing the clusters, instead of making a full clustering of all evidence. This method has a computational complexity of O(M * N) for each new piece of evidence, where M is the maximum number of subsets and N is the number of prototypes chosen for each subset. That is, a computational complexity independent of the total number of previously arrived pieces of evidence. The parameters M and N are typically fixed and domain dependent in any application.


title: Applying Data Mining and Machine Learning Techniques to Submarine Intelligence Analysis

abstract: We describe how specialized database technology and data analysis methods were applied by the Swedish defense to help deal with the violation of Swedish marine territory by foreign submarine intruders during the Eighties and early Nineties. Among several approaches tried some yielded interesting information, although most of the key questions remain unanswered. We conclude with a survey of belief-function- and genetic-algorithm-based methods which were proposed to support interpretation of intelligence reports and prediction of future submarine positions, respectively.


title: Fast Dempster-Shafer clustering using a neural network structure

abstract: In this paper we study a problem within Dempster-Shafer theory where 2**n - 1 pieces of evidence are clustered by a neural structure into n clusters. The clustering is done by minimizing a metaconflict function. Previously we developed a method based on iterative optimization. However, for large scale problems we need a method with lower computational complexity. The neural structure was found to be effective and much faster than iterative optimization for larger problems. While the growth in metaconflict was faster for the neural structure compared with iterative optimization in medium sized problems, the metaconflict per cluster and evidence was moderate. The neural structure was able to find a global minimum over ten runs for problem sizes up to six clusters.


title: A neural network and iterative optimization hybrid for Dempster-Shafer clustering

abstract: In this paper we extend an earlier result within Dempster-Shafer theory ["Fast Dempster-Shafer Clustering Using a Neural Network Structure," in Proc. Seventh Int. Conf. Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU 98)] where a large number of pieces of evidence are clustered into subsets by a neural network structure. The clustering is done by minimizing a metaconflict function. Previously we developed a method based on iterative optimization. While the neural method had a much lower computation time than iterative optimization its average clustering performance was not as good. Here, we develop a hybrid of the two methods. We let the neural structure do the initial clustering in order to achieve a high computational performance. Its solution is fed as the initial state to the iterative optimization in order to improve the clustering performance.


title: Simultaneous Dempster-Shafer clustering and gradual determination of number of clusters using a neural network structure

abstract: In this paper we extend an earlier result within Dempster-Shafer theory ["Fast Dempster-Shafer Clustering Using a Neural Network Structure," in Proc. Seventh Int. Conf. Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU'98)] where several pieces of evidence were clustered into a fixed number of clusters using a neural structure. This was done by minimizing a metaconflict function. We now develop a method for simultaneous clustering and determination of number of clusters during iteration in the neural structure. We let the output signals of neurons represent the degree to which a pieces of evidence belong to a corresponding cluster. From these we derive a probability distribution regarding the number of clusters, which gradually during the iteration is transformed into a determination of number of clusters. This gradual determination is fed back into the neural structure at each iteration to influence the clustering process.


abstract: In this article we study a problem within Dempster-Shafer theory where 2**n - 1 pieces of evidence are clustered by a neural structure into n clusters. The clustering is done by minimizing a metaconflict function. Previously we developed a method based on iterative optimization. However, for large scale problems we need a method with lower computational complexity. The neural structure was found to be effective and much faster than iterative optimization for larger problems. While the growth in metaconflict was faster for the neural structure compared with iterative optimization in medium sized problems, the metaconflict per cluster and evidence was moderate. The neural structure was able to find a global minimum over ten runs for problem sizes up to six clusters.


title: Managing Inconsistent Intelligence

abstract: In this paper we demonstrate that it is possible to manage intelligence in constant time as a pre-process to information fusion through a series of processes dealing with issues such as clustering reports, ranking reports with respect to importance, extraction of prototypes from clusters and immediate classification of newly arriving intelligence reports. These methods are used when intelligence reports arrive which concerns different events which should be handled independently, when it is not known a priori to which event each intelligence report is related. We use clustering that runs as a back-end process to partition the intelligence into subsets representing the events, and in parallel, a fast classification that runs as a front-end process in order to put the newly arriving intelligence into its correct information fusion process.


title: Dempster-Shafer clustering using Potts spin mean field theory

abstract: In this article we investigate a problem within Dempster-Shafer theory where 2**q - 1 pieces of evidence are clustered into q clusters by minimizing a metaconflict function, or equivalently, by minimizing the sum of weight of conflict over all clusters. Previously one of us developed a method based on a Hopfield and Tank model. However, for very large problems we need a method with lower computational complexity. We demonstrate that the weight of conflict of evidence can, as an approximation, be linearized and mapped to an antiferromagnetic Potts Spin model. This facilitates efficient numerical solution, even for large problem sizes. Optimal or nearly optimal solutions are found for Dempster-Shafer clustering benchmark tests with a time complexity of approximately O(N**2 log**2 N). Furthermore, an isomorphism between the antiferromagnetic Potts spin model and a graph optimization problem is shown. The graph model has dynamic variables living on the links, which have a priori probabilities that are directly related to the pairwise conflict between pieces of evidence. Hence, the relations between three different models are shown.


title: Conflict-based Force Aggregation

abstract: In this paper we present an application where we put together two methods for clustering and classification into a force aggregation method. Both methods are based on conflicts between elements. These methods work with different type of elements (intelligence reports, vehicles, military units) on different hierarchical levels using specific conflict assessment methods on each level. We use Dempster-Shafer theory for conflict calculation between elements, Dempster-Shafer clustering for clustering these elements, and templates for classification. The result of these processes is a complete force aggregation on all levels handled.


title: Reliable Force Aggregation Using a Refined Evidence Specification from Dempster-Shafer Clustering

abstract: In this paper we develop methods for selection of templates and use these templates to recluster an already performed Dempster-Shafer clustering taking into account intelligence to template fit during the reclustering phase. By this process the risk of erroneous force aggregation based on some misplace pieces of evidence from the first clustering process is greatly reduced. Finally, a more reliable force aggregation is performed using the result of the second clustering. These steps are taken in order to maintain most of the excellent computational performance of Dempster-Shafer clustering, while at the same time improve on the clustering result by including some higher relations among intelligence reports described by the templates. The new improved algorithm has a computational complexity of O(n**3 log**2 n) compared to O(n**2 log**2 n) of standard Dempster-Shafer clustering using Potts spin mean field theory.


title: Clustering belief functions based on attracting and conflicting metalevel evidence

abstract: In this paper we develop a method for clustering belief functions based on attracting and conflicting metalevel evidence. Such clustering is done when the belief functions concern multiple events, and all belief functions are mixed up. The clustering process is used as the means for separating the belief functions into subsets that should be handled independently. While the conflicting metalevel evidence is generated internally from pairwise conflicts of all belief functions, the attracting metalevel evidence is assumed given by some external source.


title: Robust Report Level Cluster-to-Track Fusion

abstract: In this paper we develop a method for report level tracking based on Dempster-Shafer clustering using Potts spin neural networks where clusters of incoming reports are gradually fused into existing tracks, one cluster for each track. Incoming reports are put into a cluster and continuous reclustering of older reports is made in order to obtain maximum association fit within the cluster and towards the track. Over time, the oldest reports of the cluster leave the cluster for the fixed track at the same rate as new incoming reports are put into it. Fusing reports to existing tracks in this fashion allows us to take account of both existing tracks and the probable future of each track, as represented by younger reports within the corresponding cluster. This gives us a robust report-to-track association. Compared to clustering of all available reports this approach is computationally faster and has a better report-to-track association than simple step-by-step association.


title: Beslutst\"odssystemet Dezzy - en \"oversikt

abstract: Within the scope of the three-year ANTI-SUBMARINE WARFARE project of the National Defence Research Establishment, the INFORMATION SYSTEMS subproject has developed the demonstration prototype Dezzy for handling and analysis of intelligence reports concerning foreign underwater activities. ----- Inom ramen f\"or FOA:s tre{\aa}riga huvudprojekt UB{\AA}TSSKYDD har delprojekt INFORMATIONSSYSTEM utvecklat demonstrationsprototypen Dezzy till ett beslutsst\"odsystem f\"or hantering och analys av underr\"attelser om fr\"ammande undervattensverksamhet.


title: Cryptanalysis of HFE

abstract: I transform the trapdoor problem of HFE into a linear algebra problem.


title: A mathematical definition of "simplify"

abstract: Even though every mathematician knows intuitively what it means to "simplify" a mathematical expression, there is still no universally accepted rigorous mathematical definition of "simplify". In this paper, we shall give a simple and plausible definition of "simplify" in terms of the computational complexity of integer functions. We shall also use this definition to show that there is no deterministic and exact algorithm which can compute the permanent of an $n \times n$ matrix in $o(2^n)$ time.


title: Using Dynamic Simulation in the Development of Construction Machinery

abstract: As in the car industry for quite some time, dynamic simulation of complete vehicles is being practiced more and more in the development of off-road machinery. However, specific questions arise due not only to company structure and size, but especially to the type of product. Tightly coupled, non-linear subsystems of different domains make prediction and optimisation of the complete system's dynamic behaviour a challenge. Furthermore, the demand for versatile machines leads to sometimes contradictory target requirements and can turn the design process into a hunt for the least painful compromise. This can be avoided by profound system knowledge, assisted by simulation-driven product development. This paper gives an overview of joint research into this issue by Volvo Wheel Loaders and Linkoping University on that matter, lists the results of a related literature review and introduces the term "operateability". Rather than giving detailed answers, the problem space for ongoing and future research is examined and possible solutions are sketched.


title: Power Law Distributions in Class Relationships

abstract: Power law distributions have been found in many natural and social phenomena, and more recently in the source code and run-time characteristics of Object-Oriented (OO) systems. A power law implies that small values are extremely common, whereas large values are extremely rare. In this paper, we identify twelve new power laws relating to the static graph structures of Java programs. The graph structures analyzed represented different forms of OO coupling, namely, inheritance, aggregation, interface, parameter type and return type. Identification of these new laws provide the basis for predicting likely features of classes in future developments. The research in this paper ties together work in object-based coupling and World Wide Web structures.


title: The Evolution of the Computerized Database

abstract: Databases, collections of related data, are as old as the written word. A database can be anything from a homemaker's metal recipe file to a sophisticated data warehouse. Yet today, when we think of a database we invariably think of computerized data and their DBMSs (database management systems). How did we go from organizing our data in a simple metal filing box or cabinet to storing our data in a sophisticated computerized database? How did the computerized database evolve? This paper defines what we mean by a database. It traces the evolution of the database, from its start as a non-computerized set of related data, to the, now standard, computerized RDBMS (relational database management system). Early computerized storage methods are reviewed including both the ISAM (Indexed Sequential Access Method) and VSAM (Virtual Storage Access Method) storage methods. Early database models are explored including the network and hierarchical database models. Eventually, the relational, object-relational and object-oriented databases models are discussed. An appendix of diagrams, including hierarchical occurrence tree, network schema, ER (entity relationship) and UML (unified modeling language) diagrams, is included to support the text. This paper concludes with an exploration of current and future trends in DBMS development. It discusses the factors affecting these trends. It delves into the relationship between DBMSs and the increasingly popular object-oriented development methodologies. Finally, it speculates on the future of the DBMS.


title: Periodicity and Unbordered Words: A Proof of the Extended Duval Conjecture

abstract: The relationship between the length of a word and the maximum length of its unbordered factors is investigated in this paper. Consider a finite word w of length n. We call a word bordered, if it has a proper prefix which is also a suffix of that word. Let f(w) denote the maximum length of all unbordered factors of w, and let p(w) denote the period of w. Clearly, f(w) < p(w)+1. We establish that f(w) = p(w), if w has an unbordered prefix of length f(w) and n > 2f(w)-2. This bound is tight and solves the stronger version of a 21 years old conjecture by Duval. It follows from this result that, in general, n > 3f(w)-3 implies f(w) = p(w) which gives an improved bound for the question asked by Ehrenfeucht and Silberger in 1979.


title: Bounded LTL Model Checking with Stable Models

abstract: In this paper bounded model checking of asynchronous concurrent systems is introduced as a promising application area for answer set programming. As the model of asynchronous systems a generalisation of communicating automata, 1-safe Petri nets, are used. It is shown how a 1-safe Petri net and a requirement on the behaviour of the net can be translated into a logic program such that the bounded model checking problem for the net can be solved by computing stable models of the corresponding program. The use of the stable model semantics leads to compact encodings of bounded reachability and deadlock detection tasks as well as the more general problem of bounded model checking of linear temporal logic. Correctness proofs of the devised translations are given, and some experimental results using the translation and the Smodels system are presented.


title: Factorization of Language Models through Backing-Off Lattices

abstract: Factorization of statistical language models is the task that we resolve the most discriminative model into factored models and determine a new model by combining them so as to provide better estimate. Most of previous works mainly focus on factorizing models of sequential events, each of which allows only one factorization manner. To enable parallel factorization, which allows a model event to be resolved in more than one ways at the same time, we propose a general framework, where we adopt a backing-off lattice to reflect parallel factorizations and to define the paths along which a model is resolved into factored models, we use a mixture model to combine parallel paths in the lattice, and generalize Katz's backing-off method to integrate all the mixture models got by traversing the entire lattice. Based on this framework, we formulate two types of model factorizations that are used in natural language modeling.


title: Untraceable Email Cluster Bombs: On Agent-Based Distributed Denial of Service

abstract: We uncover a vulnerability that allows for an attacker to perform an email-based attack on selected victims, using only standard scripts and agents. What differentiates the attack we describe from other, already known forms of distributed denial of service (DDoS) attacks is that an attacker does not need to infiltrate the network in any manner -- as is normally required to launch a DDoS attack. Thus, we see this type of attack as a poor man's DDoS. Not only is the attack easy to mount, but it is also almost impossible to trace back to the perpetrator. Along with descriptions of our attack, we demonstrate its destructive potential with (limited and contained) experimental results. We illustrate the potential impact of our attack by describing how an attacker can disable an email account by flooding its inbox; block competition during on-line auctions; harm competitors with an on-line presence; disrupt phone service to a given victim; cheat in SMS-based games; disconnect mobile corporate leaders from their networks; and disrupt electronic elections. Finally, we propose a set of countermeasures that are light-weight, do not require modifications to the infrastructure, and can be deployed in a gradual manner.


title: Modeling of aerodynamic Space-to-Surface flight with optimal trajectory for targeting

abstract: Modeling has been created for a Space-to-Surface system defined for an optimal trajectory for targeting in terminal phase. The modeling includes models for simulation atmosphere, speed of sound, aerodynamic flight and navigation by an infrared system. The modeling simulation includes statistical analysis of the modeling results.


title: Updating beliefs with incomplete observations

abstract: Currently, there is renewed interest in the problem, raised by Shafer in 1985, of updating probabilities when observations are incomplete. This is a fundamental problem in general, and of particular interest for Bayesian networks. Recently, Grunwald and Halpern have shown that commonly used updating strategies fail in this case, except under very special assumptions. In this paper we propose a new method for updating probabilities with incomplete observations. Our approach is deliberately conservative: we make no assumptions about the so-called incompleteness mechanism that associates complete with incomplete observations. We model our ignorance about this mechanism by a vacuous lower prevision, a tool from the theory of imprecise probabilities, and we use only coherence arguments to turn prior into posterior probabilities. In general, this new approach to updating produces lower and upper posterior probabilities and expectations, as well as partially determinate decisions. This is a logical consequence of the existing ignorance about the incompleteness mechanism. We apply the new approach to the problem of classification of new evidence in probabilistic expert systems, where it leads to a new, so-called conservative updating rule. In the special case of Bayesian networks constructed using expert knowledge, we provide an exact algorithm for classification based on our updating rule, which has linear-time complexity for a class of networks wider than polytrees. This result is then extended to the more general framework of credal networks, where computations are often much harder than with Bayesian nets. Using an example, we show that our rule appears to provide a solid basis for reliable updating with incomplete observations, when no strong assumptions about the incompleteness mechanism are justified.


title: Semiclassical Quantum Computation Solutions to the Count to Infinity Problem: A Brief Discussion

abstract: In this paper we briefly define distance vector routing algorithms, their advantages and possible drawbacks. On these possible drawbacks, currently widely used methods split horizon and poisoned reverse are defined and compared. The count to infinity problem is specified and it is classified to be a halting problem and a proposition stating that entangled states used in quantum computation can be used to handle this problem is examined. Several solutions to this problem by using entangled states are proposed and a very brief introduction to entangled states is presented.


title: Applications of Intuitionistic Logic in Answer Set Programming

abstract: We present some applications of intermediate logics in the field of Answer Set Programming (ASP). A brief, but comprehensive introduction to the answer set semantics, intuitionistic and other intermediate logics is given. Some equivalence notions and their applications are discussed. Some results on intermediate logics are shown, and applied later to prove properties of answer sets. A characterization of answer sets for logic programs with nested expressions is provided in terms of intuitionistic provability, generalizing a recent result given by Pearce. It is known that the answer set semantics for logic programs with nested expressions may select non-minimal models. Minimal models can be very important in some applications, therefore we studied them; in particular we obtain a characterization, in terms of intuitionistic logic, of answer sets which are also minimal models. We show that the logic G3 characterizes the notion of strong equivalence between programs under the semantic induced by these models. Finally we discuss possible applications and consequences of our results. They clearly state interesting links between ASP and intermediate logics, which might bring research in these two areas together.


title: CASTOR status and evolution

abstract: In January 1999, CERN began to develop CASTOR ("CERN Advanced STORage manager"). This Hierarchical Storage Manager targetted at HEP applications has been in full production at CERN since May 2001. It now contains more than two Petabyte of data in roughly 9 million files. In 2002, 350 Terabytes of data were stored for COMPASS at 45 MB/s and a Data Challenge was run for ALICE in preparation for the LHC startup in 2007 and sustained a data transfer to tape of 300 MB/s for one week (180 TB). The major functionality improvements were the support for files larger than 2 GB (in collaboration with IN2P3) and the development of Grid interfaces to CASTOR: GridFTP and SRM ("Storage Resource Manager"). An ongoing effort is taking place to copy the existing data from obsolete media like 9940 A to better cost effective offerings. CASTOR has also been deployed at several HEP sites with little effort. In 2003, we plan to continue working on Grid interfaces and to improve performance not only for Central Data Recording but also for Data Analysis applications where thousands of processes possibly access the same hot data. This could imply the selection of another filesystem or the use of replication (hardware or software).


title: 2D Electrophoresis Gel Image and Diagnosis of a Disease

abstract: The process of diagnosing a disease from the 2D gel electrophoresis image is a challenging problem. This is due to technical difficulties of generating reproducible images with a normalized form and the effect of negative stain. In this paper, we will discuss a new concept of interpreting the 2D images and overcoming the aforementioned technical difficulties using mathematical transformation. The method makes use of 2D gel images of proteins in serums and we explain a way of representing the images into vectors in order to apply machine-learning methods, such as the support vector machine.


title: The Athena Data Dictionary and Description Language

abstract: Athena is the ATLAS off-line software framework, based upon the GAUDI architecture from LHCb. As part of ATLAS' continuing efforts to enhance and customise the architecture to meet our needs, we have developed a data object description tool suite and service for Athena. The aim is to provide a set of tools to describe, manage, integrate and use the Event Data Model at a design level according to the concepts of the Athena framework (use of patterns, relationships, ...). Moreover, to ensure stability and reusability this must be fully independent from the implementation details. After an extensive investigation into the many options, we have developed a language grammar based upon a description language (IDL, ODL) to provide support for object integration in Athena. We have then developed a compiler front end based upon this language grammar, JavaCC, and a Java Reflection API-like interface. We have then used these tools to develop several compiler back ends which meet specific needs in ATLAS such as automatic generation of object converters, and data object scripting interfaces. We present here details of our work and experience to date on the Athena Definition Language and Athena Data Dictionary.


title: Towards automation of computing fabrics using tools from the fabric management workpackage of the EU DataGrid project

abstract: The EU DataGrid project workpackage 4 has as an objective to provide the necessary tools for automating the management of medium size to very large computing fabrics. At the end of the second project year subsystems for centralized configuration management (presented at LISA'02) and performance/exception monitoring have been delivered. This will soon be augmented with a subsystem for node installation and service configuration, which is based on existing widely used standards where available (e.g. rpm, kickstart, init.d scripts) and clean interfaces to OS dependent components (e.g. base installation and service management). The three subsystems together allow for centralized management of very large computer farms. Finally, a fault tolerance system is being developed for tying together the above subsystems to form a complete framework for automated enterprise computing management by 3Q03. All software developed is open source covered by the EU DataGrid project license agreements. This article describes the architecture behind the designed fabric management system and the status of the different developments. It also covers the experience with an existing tool for automated configuration and installation that have been adapted and used from the beginning to manage the EU DataGrid testbed, which is now used for LHC data challenges.


title: Sharp Bounds for Bandwidth of Clique Products

abstract: The bandwidth of a graph is the labeling of vertices with minimum maximum edge difference. For many graph families this is NP-complete. A classic result computes the bandwidth for the hypercube. We generalize this result to give sharp lower bounds for products of cliques. This problem turns out to be equivalent to one in communication over multiple channels in which channels can fail and the information sent over those channels is lost. The goal is to create an encoding that minimizes the difference between the received and the original information while having as little redundancy as possible. Berger-Wolf and Reingold [2] have considered the problem for the equal size cliques (or equal capacity channels). This paper presents a tight lower bound and an algorithm for constructing the labeling for the product of any number of arbitrary size cliques.


title: On the Existence and Convergence Computable Universal Priors

abstract: Solomonoff unified Occam's razor and Epicurus' principle of multiple explanations to one elegant, formal, universal theory of inductive inference, which initiated the field of algorithmic information theory. His central result is that the posterior of his universal semimeasure M converges rapidly to the true sequence generating posterior mu, if the latter is computable. Hence, M is eligible as a universal predictor in case of unknown mu. We investigate the existence and convergence of computable universal (semi)measures for a hierarchy of computability classes: finitely computable, estimable, enumerable, and approximable. For instance, M is known to be enumerable, but not finitely computable, and to dominate all enumerable semimeasures. We define seven classes of (semi)measures based on these four computability concepts. Each class may or may not contain a (semi)measure which dominates all elements of another class. The analysis of these 49 cases can be reduced to four basic cases, two of them being new. The results hold for discrete and continuous semimeasures. We also investigate more closely the types of convergence, possibly implied by universality: in difference and in ratio, with probability 1, in mean sum, and for Martin-Loef random sequences. We introduce a generalized concept of randomness for individual sequences and use it to exhibit difficulties regarding these issues.


title: Developing Open Data Models for Linguistic Field Data

abstract: The UQ Flint Archive houses the field notes and elicitation recordings made by Elwyn Flint in the 1950's and 1960's during extensive linguistic survey work across Queensland, Australia. The process of digitizing the contents of the UQ Flint Archive provides a number of interesting challenges in the context of EMELD. Firstly, all of the linguistic data is for languages which are either endangered or extinct, and as such forms a valuable ethnographic repository. Secondly, the physical format of the data is itself in danger of decline, and as such digitization is an important preservation task in the short to medium term. Thirdly, the adoption of open standards for the encoding and presentation of text and audio data for linguistic field data, whilst enabling preservation, represents a new field of research in itself where best practice has yet to be formalised. Fourthly, the provision of this linguistic data online as a new data source for future research introduces concerns of data portability and longevity. This paper will outline the origins of the data model, the content creation components, presentation forms based on the data model, data capture tools and media conversion components. It will also address some of the larger questions regarding the digitization and annotation of linguistic field work based on experience gained through work with the Flint Archive contents.


title: A Monitoring System for the BaBar INFN Computing Cluster

abstract: Monitoring large clusters is a challenging problem. It is necessary to observe a large quantity of devices with a reasonably short delay between consecutive observations. The set of monitored devices may include PCs, network switches, tape libraries and other equipments. The monitoring activity should not impact the performances of the system. In this paper we present PerfMC, a monitoring system for large clusters. PerfMC is driven by an XML configuration file, and uses the Simple Network Management Protocol (SNMP) for data collection. SNMP is a standard protocol implemented by many networked equipments, so the tool can be used to monitor a wide range of devices. System administrators can display informations on the status of each device by connecting to a WEB server embedded in PerfMC. The WEB server can produce graphs showing the value of different monitored quantities as a function of time; it can also produce arbitrary XML pages by applying XSL Transformations to an internal XML representation of the cluster's status. XSL Transformations may be used to produce HTML pages which can be displayed by ordinary WEB browsers. PerfMC aims at being relatively easy to configure and operate, and highly efficient. It is currently being used to monitor the Italian Reprocessing farm for the BaBar experiment, which is made of about 200 dual-CPU Linux machines.


title: Goodness-of-fit of the Heston model

abstract: An analytical formula for the probability distribution of stock-market returns, derived from the Heston model assuming a mean-reverting stochastic volatility, was recently proposed by Dragulescu and Yakovenko in Quantitative Finance 2002. While replicating their results, we found two significant weaknesses in their method to pre-process the data, which cast a shadow over the effective goodness-of-fit of the model. We propose a new method, more truly capturing the market, and perform a Kolmogorov-Smirnov test and a Chi Square test on the resulting probability distribution. The results raise some significant questions for large time lags -- 40 to 250 days -- where the smoothness of the data does not require such a complex model; nevertheless, we also provide some statistical evidence in favour of the Heston model for small time lags -- 1 and 5 days -- compared with the traditional Gaussian model assuming constant volatility.


title: Configuration Database for BaBar On-line

abstract: The configuration database is one of the vital systems in the BaBar on-line system. It provides services for the different parts of the data acquisition system and control system, which require run-time parameters. The original design and implementation of the configuration database played a significant role in the successful BaBar operations since the beginning of experiment. Recent additions to the design of the configuration database provide better means for the management of data and add new tools to simplify main configuration tasks. We describe the design of the configuration database, its implementation with the Objectivity/DB object-oriented database, and our experience collected during the years of operation.


title: The Persint visualization program for the ATLAS experiment

abstract: The Persint program is designed for the three-dimensional representation of objects and for the interfacing and access to a variety of independent applications, in a fully interactive way. Facilities are provided for the spatial navigation and the definition of the visualization properties, in order to interactively set the viewing and viewed points, and to obtain the desired perspective. In parallel, applications may be launched through the use of dedicated interfaces, such as the interactive reconstruction and display of physics events. Recent developments have focalized on the interfacing to the XML ATLAS General Detector Description AGDD, making it a widely used tool for XML developers. The graphics capabilities of this program were exploited in the context of the ATLAS 2002 Muon Testbeam where it was used as an online event display, integrated in the online software framework and participating in the commissioning and debug of the detector system.


title: ATLAS and CMS applications on the WorldGrid testbed

abstract: WorldGrid is an intercontinental testbed spanning Europe and the US integrating architecturally different Grid implementations based on the Globus toolkit. It has been developed in the context of the DataTAG and iVDGL projects, and successfully demonstrated during the WorldGrid demos at IST2002 (Copenhagen) and SC2002 (Baltimore). Two HEP experiments, ATLAS and CMS, successful exploited the WorldGrid testbed for executing jobs simulating the response of their detectors to physics eve nts produced by real collisions expected at the LHC accelerator starting from 2007. This data intensive activity has been run since many years on local dedicated computing farms consisting of hundreds of nodes and Terabytes of disk and tape storage. Within the WorldGrid testbed, for the first time HEP simulation jobs were submitted and run indifferently on US and European resources, despite of their underlying different Grid implementations, and produced data which could be retrieved and further analysed on the submitting machine, or simply stored on the remote resources and registered on a Replica Catalogue which made them available to the Grid for further processing. In this contribution we describe the job submission from Europe for both ATLAS and CMS applications, performed through the GENIUS portal operating on top of an EDG User Interface submitting to an EDG Resource Broker, pointing out the chosen interoperability solutions which made US and European resources equivalent from the applications point of view, the data management in the WorldGrid environment, and the CMS specific production tools which were interfaced to the GENIUS portal.


title: EU DataGRID testbed management and support at CERN

abstract: In this paper we report on the first two years of running the CERN testbed site for the EU DataGRID project. The site consists of about 120 dual-processor PCs distributed over several testbeds used for different purposes: software development, system integration, and application tests. Activities at the site included test productions of MonteCarlo data for LHC experiments, tutorials and demonstrations of GRID technologies, and support for individual users analysis. This paper focuses on node installation and configuration techniques, service management, user support in a gridified environment, and includes considerations on scalability and security issues and comparisons with "traditional" production systems, as seen from the administrator point of view.


title: Performance comparison between iSCSI and other hardware and software solutions

abstract: We report on our investigations on some technologies that can be used to build disk servers and networks of disk servers using commodity hardware and software solutions. It focuses on the performance that can be achieved by these systems and gives measured figures for different configurations. It is divided into two parts : iSCSI and other technologies and hardware and software RAID solutions. The first part studies different technologies that can be used by clients to access disk servers using a gigabit ethernet network. It covers block access technologies (iSCSI, hyperSCSI, ENBD). Experimental figures are given for different numbers of clients and servers. The second part compares a system based on 3ware hardware RAID controllers, a system using linux software RAID and IDE cards and a system mixing both hardware RAID and software RAID. Performance measurements for reading and writing are given for different RAID levels.


title: A Secure Infrastructure For System Console and Reset Access

abstract: During the last years large farms have been built using commodity hardware. This hardware lacks components for remote and automated administration. Products that can be retrofitted to these systems are either costly or inherently insecure. We present a system based on serial ports and simple machine controlled relays. We report on experience gained by setting up a 50-machine test environment as well as current work in progress in the area.


title: DIAMOnDS - DIstributed Agents for MObile & Dynamic Services

abstract: Distributed Services Architecture with support for mobile agents between services, offer significantly improved communication and computational flexibility. The uses of agents allow execution of complex operations that involve large amounts of data to be processed effectively using distributed resources. The prototype system Distributed Agents for Mobile and Dynamic Services (DIAMOnDS), allows a service to send agents on its behalf, to other services, to perform data manipulation and processing. Agents have been implemented as mobile services that are discovered using the Jini Lookup mechanism and used by other services for task management and communication. Agents provide proxies for interaction with other services as well as specific GUI to monitor and control the agent activity. Thus agents acting on behalf of one service cooperate with other services to carry out a job, providing inter-operation of loosely coupled services in a semi-autonomous way. Remote file system access functionality has been incorporated by the agent framework and allows services to dynamically share and browse the file system resources of hosts, running the services. Generic database access functionality has been implemented in the mobile agent framework that allows performing complex data mining and processing operations efficiently in distributed system. A basic data searching agent is also implemented that performs a query based search in a file system. The testing of the framework was carried out on WAN by moving Connectivity Test agents between AgentStations in CERN, Switzerland and NUST, Pakistan.


title: McRunjob: A High Energy Physics Workflow Planner for Grid Production Processing

abstract: McRunjob is a powerful grid workflow manager used to manage the generation of large numbers of production processing jobs in High Energy Physics. In use at both the DZero and CMS experiments, McRunjob has been used to manage large Monte Carlo production processing since 1999 and is being extended to uses in regular production processing for analysis and reconstruction. Described at CHEP 2001, McRunjob converts core metadata into jobs submittable in a variety of environments. The powerful core metadata description language includes methods for converting the metadata into persistent forms, job descriptions, multi-step workflows, and data provenance information. The language features allow for structure in the metadata by including full expressions, namespaces, functional dependencies, site specific parameters in a grid environment, and ontological definitions. It also has simple control structures for parallelization of large jobs. McRunjob features a modular design which allows for easy expansion to new job description languages or new application level tasks.


title: The use of Ethernet in the DataFlow of the ATLAS Trigger & DAQ

abstract: The article analyzes a proposed network topology for the ATLAS DAQ DataFlow, and identifies the Ethernet features required for a proper operation of the network: MAC address table size, switch performance in terms of throughput and latency, the use of Flow Control, Virtual LANs and Quality of Service. We investigate these features on some Ethernet switches, and conclude on their usefulness for the ATLAS DataFlow network.


title: A Generic Multi-node State Monitoring Subsystem

abstract: The BaBar online data acquisition (DAQ) system includes approximately fifty Unix systems that collectively implement the level-three trigger. These systems all run the same code. Each of these systems has its own state, and this state is expected to change in response to changes in the overall DAQ system. A specialized subsystem has been developed to initiate processing on this collection of systems, and to monitor them both for error conditions and to ensure that they all follow the same state trajectory within a specifiable period of time. This subsystem receives start commands from the main DAQ run control system, and reports major coherent state changes, as well as error conditions, back to the run control system. This state monitoring subsystem has the novel feature that it does not know anything about the state machines that it is monitoring, and hence does not introduce any fundamentally new state machine into the overall system. This feature makes it trivially applicable to other multi-node subsystems. Indeed it has already found a second application beyond the level-three trigger, within the BaBar experiment.