title: Secure History Preservation Through Timeline Entanglement

abstract: A secure timeline is a tamper-evident historic record of the states through which a system goes throughout its operational history. Secure timelines can help us reason about the temporal ordering of system states in a provable manner. We extend secure timelines to encompass multiple, mutually distrustful services, using timeline entanglement. Timeline entanglement associates disparate timelines maintained at independent systems, by linking undeniably the past of one timeline to the future of another. Timeline entanglement is a sound method to map a time step in the history of one service onto the timeline of another, and helps clients of entangled services to get persistent temporal proofs for services rendered that survive the demise or non-cooperation of the originating service. In this paper we present the design and implementation of Timeweave, our service development framework for timeline entanglement based on two novel disk-based authenticated data structures. We evaluate Timeweave's performance characteristics and show that it can be efficiently deployed in a loosely-coupled distributed system of a few hundred services with overhead of roughly 2-8% of the processing resources of a PC-grade system.


title: Approximate Computation of Reach Sets in Hybrid Systems

abstract: One of the most important problems in hybrid systems is the {\em reachability problem}. The reachability problem has been shown to be undecidable even for a subclass of {\em linear} hybrid systems. In view of this, the main focus in the area of hybrid systems has been to find {\em effective} semi-decision procedures for this problem. Such an algorithmic approach involves finding methods of computation and representation of reach sets of the continuous variables within a discrete state of a hybrid system. In this paper, after presenting a brief introduction to hybrid systems and reachability problem, we propose a computational method for obtaining the reach sets of continuous variables in a hybrid system. In addition to this, we also describe a new algorithm to over-approximate with polyhedra the reach sets of the continuous variables with linear dynamics and polyhedral initial set. We illustrate these algorithms with typical interesting examples.


title: Steady State Resource Allocation Analysis of the Stochastic Diffusion Search

abstract: This article presents the long-term behaviour analysis of Stochastic Diffusion Search (SDS), a distributed agent-based system for best-fit pattern matching. SDS operates by allocating simple agents into different regions of the search space. Agents independently pose hypotheses about the presence of the pattern in the search space and its potential distortion. Assuming a compositional structure of hypotheses about pattern matching agents perform an inference on the basis of partial evidence from the hypothesised solution. Agents posing mutually consistent hypotheses about the pattern support each other and inhibit agents with inconsistent hypotheses. This results in the emergence of a stable agent population identifying the desired solution. Positive feedback via diffusion of information between the agents significantly contributes to the speed with which the solution population is formed. The formulation of the SDS model in terms of interacting Markov Chains enables its characterisation in terms of the allocation of agents, or computational resources. The analysis characterises the stationary probability distribution of the activity of agents, which leads to the characterisation of the solution population in terms of its similarity to the target pattern.


title: CUP: Controlled Update Propagation in Peer-to-Peer Networks

abstract: Recently the problem of indexing and locating content in peer-to-peer networks has received much attention. Previous work suggests caching index entries at intermediate nodes that lie on the paths taken by search queries, but until now there has been little focus on how to maintain these intermediate caches. This paper proposes CUP, a new comprehensive architecture for Controlled Update Propagation in peer-to-peer networks. CUP asynchronously builds caches of index entries while answering search queries. It then propagates updates of index entries to maintain these caches. Under unfavorable conditions, when compared with standard caching based on expiration times, CUP reduces the average miss latency by as much as a factor of three. Under favorable conditions, CUP can reduce the average miss latency by more than a factor of ten. CUP refreshes intermediate caches, reduces query latency, and reduces network load by coalescing bursts of queries for the same item. CUP controls and confines propagation to updates whose cost is likely to be recovered by subsequent queries. CUP gives peer-to-peer nodes the flexibility to use their own incentive-based policies to determine when to receive and when to propagate updates. Finally, the small propagation overhead incurred by CUP is more than compensated for by its savings in cache misses.


title: Non-negative sparse coding

abstract: Non-negative sparse coding is a method for decomposing multivariate data into non-negative sparse components. In this paper we briefly describe the motivation behind this type of data representation and its relation to standard sparse coding and non-negative matrix factorization. We then give a simple yet efficient multiplicative algorithm for finding the optimal values of the hidden components. In addition, we show how the basis vectors can be learned from the observed data. Simulations demonstrate the effectiveness of the proposed method.


title: Using parametric set constraints for locating errors in CLP programs

abstract: This paper introduces a framework of parametric descriptive directional types for constraint logic programming (CLP). It proposes a method for locating type errors in CLP programs and presents a prototype debugging tool. The main technique used is checking correctness of programs w.r.t. type specifications. The approach is based on a generalization of known methods for proving correctness of logic programs to the case of parametric specifications. Set-constraint techniques are used for formulating and checking verification conditions for (parametric) polymorphic type specifications. The specifications are expressed in a parametric extension of the formalism of term grammars. The soundness of the method is proved and the prototype debugging tool supporting the proposed approach is illustrated on examples. The paper is a substantial extension of the previous work by the same authors concerning monomorphic directional types.


title: Small Strictly Convex Quadrilateral Meshes of Point Sets

abstract: In this paper, we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that $3{\lfloor\frac{n}{2}\rfloor}$ internal Steiner points are always sufficient for a convex quadrilateral mesh of $n$ points in the plane. Furthermore, for any given $n\geq 4$, there are point sets for which $\lceil\frac{n-3}{2}\rceil-1$ Steiner points are necessary for a convex quadrilateral mesh.


title: Logic program specialisation through partial deduction: Control issues

abstract: Program specialisation aims at improving the overall performance of programs by performing source to source transformations. A common approach within functional and logic programming, known respectively as partial evaluation and partial deduction, is to exploit partial knowledge about the input. It is achieved through a well-automated application of parts of the Burstall-Darlington unfold/fold transformation framework. The main challenge in developing systems is to design automatic control that ensures correctness, efficiency, and termination. This survey and tutorial presents the main developments in controlling partial deduction over the past 10 years and analyses their respective merits and shortcomings. It ends with an assessment of current achievements and sketches some remaining research challenges.


title: The SDSS SkyServer: Public Access to the Sloan Digital Sky Server Data

abstract: The SkyServer provides Internet access to the public Sloan Digi-tal Sky Survey (SDSS) data for both astronomers and for science education. This paper describes the SkyServer goals and archi-tecture. It also describes our experience operating the SkyServer on the Internet. The SDSS data is public and well-documented so it makes a good test platform for research on database algorithms and performance.


title: Data Mining the SDSS SkyServer Database

abstract: An earlier paper (Szalay et. al. "Designing and Mining MultiTerabyte Astronomy Archives: The Sloan Digital Sky Survey," ACM SIGMOD 2000) described the Sloan Digital Sky Survey's (SDSS) data management needs by defining twenty database queries and twelve data visualization tasks that a good data management system should support. We built a database and interfaces to support both the query load and also a website for ad-hoc access. This paper reports on the database design, describes the data loading pipeline, and reports on the query implementation and performance. The queries typically translated to a single SQL statement. Most queries run in less than 20 seconds, allowing scientists to interactively explore the database. This paper is an in-depth tour of those queries. Readers should first have studied the companion overview paper Szalay et. al. "The SDSS SkyServer, Public Access to the Sloan Digital Sky Server Data" ACM SIGMOND 2002.


title: Combinatorial Auctions with Decreasing Marginal Utilities

abstract: In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such submodular buyers. The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property. Those last valuations are shown to form a zero-measure subset of the submodular valuations that have positive measure. While we show that the allocation problem among submodular valuations is NP-hard, we present an efficient greedy 2-approximation algorithm for this case and generalize it to the case of limited complementarities. No such approximation algorithm exists in a setting allowing for arbitrary complementarities. Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented.


title: Linear Programming helps solving large multi-unit combinatorial auctions

abstract: Previous works suggested the use of Branch and Bound techniques for finding the optimal allocation in (multi-unit) combinatorial auctions. They remarked that Linear Programming could provide a good upper-bound to the optimal allocation, but they went on using lighter and less tight upper-bound heuristics, on the ground that LP was too time-consuming to be used repetitively to solve large combinatorial auctions. We present the results of extensive experiments solving large (multi-unit) combinatorial auctions generated according to distributions proposed by different researchers. Our surprising conclusion is that Linear Programming is worth using. Investing almost all of one's computing time in using LP to bound from above the value of the optimal solution in order to prune aggressively pays off. We present a way to save on the number of calls to the LP routine and experimental results comparing different heuristics for choosing the bid to be considered next. Those results show that the ordering based on the square root of the size of the bids that was shown to be theoretically optimal in a previous paper by the authors performs surprisingly better than others in practice. Choosing to deal first with the bid with largest coefficient (typically 1) in the optimal solution of the relaxed LP problem, is also a good choice. The gap between the lower bound provided by greedy heuristics and the upper bound provided by LP is typically small and pruning is therefore extensive. For most distributions, auctions of a few hundred goods among a few thousand bids can be solved in practice. All experiments were run on a PC under Matlab.


title: Truth Revelation in Approximately Efficient Combinatorial Auctions

abstract: Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a difficult optimization problem. This is true of mechanisms for combinatorial auctions, which have in recent years assumed practical importance, and in particular of the gold standard for combinatorial auctions, the Generalized Vickrey Auction (GVA). Traditional analysis of these mechanisms - in particular, their truth revelation properties - assumes that the optimization problems are solved precisely. In reality, these optimization problems can usually be solved only in an approximate fashion. We investigate the impact on such mechanisms of replacing exact solutions by approximate ones. Specifically, we look at a particular greedy optimization method. We show that the GVA payment scheme does not provide for a truth revealing mechanism. We introduce another scheme that does guarantee truthfulness for a restricted class of players. We demonstrate the latter property by identifying natural properties for combinatorial auctions and showing that, for our restricted class of players, they imply that truthful strategies are dominant. Those properties have applicability beyond the specific auction studied.


title: Nonmonotonic Logics and Semantics

abstract: Tarski gave a general semantics for deductive reasoning: a formula a may be deduced from a set A of formulas iff a holds in all models in which each of the elements of A holds. A more liberal semantics has been considered: a formula a may be deduced from a set A of formulas iff a holds in all of the "preferred" models in which all the elements of A hold. Shoham proposed that the notion of "preferred" models be defined by a partial ordering on the models of the underlying language. A more general semantics is described in this paper, based on a set of natural properties of choice functions. This semantics is here shown to be equivalent to a semantics based on comparing the relative "importance" of sets of models, by what amounts to a qualitative probability measure. The consequence operations defined by the equivalent semantics are then characterized by a weakening of Tarski's properties in which the monotonicity requirement is replaced by three weaker conditions. Classical propositional connectives are characterized by natural introduction-elimination rules in a nonmonotonic setting. Even in the nonmonotonic setting, one obtains classical propositional logic, thus showing that monotonicity is not required to justify classical propositional connectives.


title: Hypernets -- Good (G)news for Gnutella

abstract: Criticism of Gnutella network scalability has rested on the bandwidth attributes of the original interconnection topology: a Cayley tree. Trees, in general, are known to have lower aggregate bandwidth than higher dimensional topologies e.g., hypercubes, meshes and tori. Gnutella was intended to support thousands to millions of peers. Studies of interconnection topologies in the literature, however, have focused on hardware implementations which are limited by cost to a few thousand nodes. Since the Gnutella network is virtual, hyper-topologies are relatively unfettered by such constraints. We present performance models for several plausible hyper-topologies and compare their query throughput up to millions of peers. The virtual hypercube and the virtual hypertorus are shown to offer near linear scalability subject to the number of peer TCP/IP connections that can be simultaneously kept open.


title: The Mysterious Optimality of Naive Bayes: Estimation of the Probability in the System of "Classifiers"

abstract: Bayes Classifiers are widely used currently for recognition, identification and knowledge discovery. The fields of application are, for example, image processing, medicine, chemistry (QSAR). But by mysterious way the Naive Bayes Classifier usually gives a very nice and good presentation of a recognition. It can not be improved considerably by more complex models of Bayes Classifier. We demonstrate here a very nice and simple proof of the Naive Bayes Classifier optimality, that can explain this interesting fact.The derivation in the current paper is based on arXiv:cs/0202020v1


title: Nonmonotonic Reasoning, Preferential Models and Cumulative Logics

abstract: Many systems that exhibit nonmonotonic behavior have been described and studied already in the literature. The general notion of nonmonotonic reasoning, though, has almost always been described only negatively, by the property it does not enjoy, i.e. monotonicity. We study here general patterns of nonmonotonic reasoning and try to isolate properties that could help us map the field of nonmonotonic reasoning by reference to positive properties. We concentrate on a number of families of nonmonotonic consequence relations, defined in the style of Gentzen. Both proof-theoretic and semantic points of view are developed in parallel. The former point of view was pioneered by D. Gabbay, while the latter has been advocated by Y. Shoham in. Five such families are defined and characterized by representation theorems, relating the two points of view. One of the families of interest, that of preferential relations, turns out to have been studied by E. Adams. The "preferential" models proposed here are a much stronger tool than Adams' probabilistic semantics. The basic language used in this paper is that of propositional logic. The extension of our results to first order predicate calculi and the study of the computational complexity of the decision problems described in this paper will be treated in another paper.


title: What does a conditional knowledge base entail?

abstract: This paper presents a logical approach to nonmonotonic reasoning based on the notion of a nonmonotonic consequence relation. A conditional knowledge base, consisting of a set of conditional assertions of the type "if ... then ...", represents the explicit defeasible knowledge an agent has about the way the world generally behaves. We look for a plausible definition of the set of all conditional assertions entailed by a conditional knowledge base. In a previous paper, S. Kraus and the authors defined and studied "preferential" consequence relations. They noticed that not all preferential relations could be considered as reasonable inference procedures. This paper studies a more restricted class of consequence relations, "rational" relations. It is argued that any reasonable nonmonotonic inference procedure should define a rational relation. It is shown that the rational relations are exactly those that may be represented by a "ranked" preferential model, or by a (non-standard) probabilistic model. The rational closure of a conditional knowledge base is defined and shown to provide an attractive answer to the question of the title. Global properties of this closure operation are proved: it is a cumulative operation. It is also computationally tractable. This paper assumes the underlying language is propositional.


abstract: A model for decision making that generalizes Expected Utility Maximization is presented. This model, Expected Qualitative Utility Maximization, encompasses the Maximin criterion. It relaxes both the Independence and the Continuity postulates. Its main ingredient is the definition of a qualitative order on nonstandard models of the real numbers and the consideration of nonstandard utilities. Expected Qualitative Utility Maximization is characterized by an original weakening of von Neumann-Morgenstern's postulates. Subjective probabilities may be defined from those weakened postulates, as Anscombe and Aumann did from the original postulates. Subjective probabilities are numbers, not matrices as in the Subjective Expected Lexicographic Utility approach. JEL no.: D81 Keywords: Utility Theory, Non-Standard Utilities, Qualitative Decision Theory


title: A note on Darwiche and Pearl

abstract: It is shown that Darwiche and Pearl's postulates imply an interesting property, not noticed by the authors.


title: Distance Semantics for Belief Revision

abstract: A vast and interesting family of natural semantics for belief revision is defined. Suppose one is given a distance d between any two models. One may then define the revision of a theory K by a formula a as the theory defined by the set of all those models of a that are closest, by d, to the set of models of K. This family is characterized by a set of rationality postulates that extends the AGM postulates. The new postulates describe properties of iterated revisions.


title: Preferred History Semantics for Iterated Updates

abstract: We give a semantics to iterated update by a preference relation on possible developments. An iterated update is a sequence of formulas, giving (incomplete) information about successive states of the world. A development is a sequence of models, describing a possible trajectory through time. We assume a principle of inertia and prefer those developments, which are compatible with the information, and avoid unnecessary changes. The logical properties of the updates defined in this way are considered, and a representation result is proved.


title: BSML: A Binding Schema Markup Language for Data Interchange in Problem Solving Environments (PSEs)

abstract: We describe a binding schema markup language (BSML) for describing data interchange between scientific codes. Such a facility is an important constituent of scientific problem solving environments (PSEs). BSML is designed to integrate with a PSE or application composition system that views model specification and execution as a problem of managing semistructured data. The data interchange problem is addressed by three techniques for processing semistructured data: validation, binding, and conversion. We present BSML and describe its application to a PSE for wireless communications system design.


title: Classes of service under perfect competition and technological change: a model for the dynamics of the Internet?

abstract: Certain services may be provided in a continuous, one-dimensional, ordered range of different qualities and a customer requiring a service of quality q can only be offered a quality superior or equal to q. Only a discrete set of different qualities will be offered, and a service provider will provide the same service (of fixed quality b) to all customers requesting qualities of service inferior or equal to b. Assuming all services (of quality b) are priced identically, a monopolist will choose the qualities of service and the prices that maximize profit but, under perfect competition, a service provider will choose the (inferior) quality of service that can be priced at the lowest price. Assuming significant economies of scale, two fundamentally different regimes are possible: either a number of different classes of service are offered (DC regime), or a unique class of service offers an unbounded quality of service (UC regime). The DC regime appears in one of two sub-regimes: one, BDC, in which a finite number of classes is offered, the qualities of service offered are bounded and requests for high-quality services are not met, or UDC in which an infinite number of classes of service are offered and every request is met. The types of the demand curve and of the economies of scale, not the pace of technological change, determine the regime and the class boundaries. The price structure in the DC regime obeys very general laws.


title: Nonstandard numbers for qualitative decision making

abstract: The consideration of nonstandard models of the real numbers and the definition of a qualitative ordering on those models provides a generalization of the principle of maximization of expected utility. It enables the decider to assign probabilities of different orders of magnitude to different events or to assign utilities of different orders of magnitude to different outcomes. The properties of this generalized notion of rationality are studied in the frameworks proposed by von Neumann and Morgenstern and later by Anscombe and Aumann. It is characterized by an original weakening of their postulates in two different situations: nonstandard probabilities and standard utilities on one hand and standard probabilities and nonstandard utilities on the other hand. This weakening concerns both Independence and Continuity. It is orthogonal with the weakening proposed by lexicographic orderings.


title: Generalized Qualitative Probability: Savage revisited

abstract: Preferences among acts are analyzed in the style of L. Savage, but as partially ordered. The rationality postulates considered are weaker than Savage's on three counts. The Sure Thing Principle is derived in this setting. The postulates are shown to lead to a characterization of generalized qualitative probability that includes and blends both traditional qualitative probability and the ranked structures used in logical approaches.


title: Nonmonotonic inference operations

abstract: A. Tarski proposed the study of infinitary consequence operations as the central topic of mathematical logic. He considered monotonicity to be a property of all such operations. In this paper, we weaken the monotonicity requirement and consider more general operations, inference operations. These operations describe the nonmonotonic logics both humans and machines seem to be using when infering defeasible information from incomplete knowledge. We single out a number of interesting families of inference operations. This study of infinitary inference operations is inspired by the results of Kraus, Lehmann and Magidor on finitary nonmonotonic operations, but this paper is self-contained.


title: Optimal Solutions for Multi-Unit Combinatorial Auctions: Branch and Bound Heuristics

abstract: Finding optimal solutions for multi-unit combinatorial auctions is a hard problem and finding approximations to the optimal solution is also hard. We investigate the use of Branch-and-Bound techniques: they require both a way to bound from above the value of the best allocation and a good criterion to decide which bids are to be tried first. Different methods for efficiently bounding from above the value of the best allocation are considered. Theoretical original results characterize the best approximation ratio and the ordering criterion that provides it. We suggest to use this criterion.


title: The logical meaning of Expansion

abstract: The Expansion property considered by researchers in Social Choice is shown to correspond to a logical property of nonmonotonic consequence relations that is the {\em pure}, i.e., not involving connectives, version of a previously known weak rationality condition. The assumption that the union of two definable sets of models is definable is needed for the soundness part of the result.


title: Covariance Plasticity and Regulated Criticality

abstract: We propose that a regulation mechanism based on Hebbian covariance plasticity may cause the brain to operate near criticality. We analyze the effect of such a regulation on the dynamics of a network with excitatory and inhibitory neurons and uniform connectivity within and across the two populations. We show that, under broad conditions, the system converges to a critical state lying at the common boundary of three regions in parameter space; these correspond to three modes of behavior: high activity, low activity, oscillation.


title: Sprinkling Selections over Join DAGs for Efficient Query Optimization

abstract: In optimizing queries, solutions based on AND/OR DAG can generate all possible join orderings and select placements before searching for optimal query execution strategy. But as the number of joins and selection conditions increase, the space and time complexity to generate optimal query plan increases exponentially. In this paper, we use join graph for a relational database schema to either pre-compute all possible join orderings that can be executed and store it as a join DAG or, extract joins in the queries to incrementally build a history join DAG as and when the queries are executed. The select conditions in the queries are appropriately placed in the retrieved join DAG (or, history join DAG) to generate optimal query execution strategy. We experimentally evaluate our query optimization technique on TPC-D/H query sets to show their effectiveness over AND/OR DAG query optimization strategy. Finally, we illustrate how our technique can be used for efficient multiple query optimization and selection of materialized views in data warehousing environments.


title: Equivalence and Isomorphism for Boolean Constraint Satisfaction

abstract: A Boolean constraint satisfaction instance is a conjunction of constraint applications, where the allowed constraints are drawn from a fixed set B of Boolean functions. We consider the problem of determining whether two given constraint satisfaction instances are equivalent and prove a Dichotomy Theorem by showing that for all sets C of allowed constraints, this problem is either polynomial-time solvable or coNP-complete, and we give a simple criterion to determine which case holds. A more general problem addressed in this paper is the isomorphism problem, the problem of determining whether there exists a renaming of the variables that makes two given constraint satisfaction instances equivalent in the above sense. We prove that this problem is coNP-hard if the corresponding equivalence problem is coNP-hard, and polynomial-time many-one reducible to the graph isomorphism problem in all other cases.


title: Towards practical meta-querying

abstract: We describe a meta-querying system for databases containing queries in addition to ordinary data. In the context of such databases, a meta-query is a query about queries. Representing stored queries in XML, and using the standard XML manipulation language XSLT as a sublanguage, we show that just a few features need to be added to SQL to turn it into a fully-fledged meta-query language. The good news is that these features can be directly supported by extensible database technology.


title: The efficient generation of unstructured control volumes in 2D and 3D

abstract: Many problems in engineering, chemistry and physics require the representation of solutions in complex geometries. In the paper we deal with a problem of unstructured mesh generation for the control volume method. We propose an algorithm which bases on the spheres generation in central points of the control volumes.

categories: cs.CG cs.CE cs.NA math.NA physics.comp-ph


title: Generalized Cores

abstract: Cores are, besides connectivity components, one among few concepts that provides us with efficient decompositions of large graphs and networks. In the paper a generalization of the notion of core of a graph based on vertex property function is presented. It is shown that for the local monotone vertex property functions the corresponding cores can be determined in $O(m \max (\Delta, \log n))$ time.


title: Towards Generic Refactoring

abstract: We study program refactoring while considering the language or even the programming paradigm as a parameter. We use typed functional programs, namely Haskell programs, as the specification medium for a corresponding refactoring framework. In order to detach ourselves from language syntax, our specifications adhere to the following style. (I) As for primitive algorithms for program analysis and transformation, we employ generic function combinators supporting generic traversal and polymorphic functions refined by ad-hoc cases. (II) As for the language abstractions involved in refactorings, we design a dedicated multi-parameter class. This class can be instantiated for abstractions as present in various languages, e.g., Java, Prolog or Haskell.


title: Another perspective on Default Reasoning

abstract: The lexicographic closure of any given finite set D of normal defaults is defined. A conditional assertion "if a then b" is in this lexicographic closure if, given the defaults D and the fact a, one would conclude b. The lexicographic closure is essentially a rational extension of D, and of its rational closure, defined in a previous paper. It provides a logic of normal defaults that is different from the one proposed by R. Reiter and that is rich enough not to require the consideration of non-normal defaults. A large number of examples are provided to show that the lexicographic closure corresponds to the basic intuitions behind Reiter's logic of defaults.


title: Deductive Nonmonotonic Inference Operations: Antitonic Representations

abstract: We provide a characterization of those nonmonotonic inference operations C for which C(X) may be described as the set of all logical consequences of X together with some set of additional assumptions S(X) that depends anti-monotonically on X (i.e., X is a subset of Y implies that S(Y) is a subset of S(X)). The operations represented are exactly characterized in terms of properties most of which have been studied in Freund-Lehmann(cs.AI/0202031). Similar characterizations of right-absorbing and cumulative operations are also provided. For cumulative operations, our results fit in closely with those of Freund. We then discuss extending finitary operations to infinitary operations in a canonical way and discuss co-compactness properties. Our results provide a satisfactory notion of pseudo-compactness, generalizing to deductive nonmonotonic operations the notion of compactness for monotonic operations. They also provide an alternative, more elegant and more general, proof of the existence of an infinitary deductive extension for any finitary deductive operation (Theorem 7.9 of Freund-Lehmann).


title: Stereotypical Reasoning: Logical Properties

abstract: Stereotypical reasoning assumes that the situation at hand is one of a kind and that it enjoys the properties generally associated with that kind of situation. It is one of the most basic forms of nonmonotonic reasoning. A formal model for stereotypical reasoning is proposed and the logical properties of this form of reasoning are studied. Stereotypical reasoning is shown to be cumulative under weak assumptions.


title: A Framework for Compiling Preferences in Logic Programs

abstract: We introduce a methodology and framework for expressing general preference information in logic programming under the answer set semantics. An ordered logic program is an extended logic program in which rules are named by unique terms, and in which preferences among rules are given by a set of atoms of form s < t where s and t are names. An ordered logic program is transformed into a second, regular, extended logic program wherein the preferences are respected, in that the answer sets obtained in the transformed program correspond with the preferred answer sets of the original program. Our approach allows the specification of dynamic orderings, in which preferences can appear arbitrarily within a program. Static orderings (in which preferences are external to a logic program) are a trivial restriction of the general dynamic case. First, we develop a specific approach to reasoning with preferences, wherein the preference ordering specifies the order in which rules are to be applied. We then demonstrate the wide range of applicability of our framework by showing how other approaches, among them that of Brewka and Eiter, can be captured within our framework. Since the result of each of these transformations is an extended logic program, we can make use of existing implementations, such as dlv and smodels. To this end, we have developed a publicly available compiler as a front-end for these programming systems.


title: Composing Programs in a Rewriting Logic for Declarative Programming

abstract: Constructor-Based Conditional Rewriting Logic is a general framework for integrating first-order functional and logic programming which gives an algebraic semantics for non-deterministic functional-logic programs. In the context of this formalism, we introduce a simple notion of program module as an open program which can be extended together with several mechanisms to combine them. These mechanisms are based on a reduced set of operations. However, the high expressiveness of these operations enable us to model typical constructs for program modularization like hiding, export/import, genericity/instantiation, and inheritance in a simple way. We also deal with the semantic aspects of the proposal by introducing an immediate consequence operator, and studying several alternative semantics for a program module, based on this operator, in the line of logic programming: the operator itself, its least fixpoint (the least model of the module), the set of its pre-fixpoints (term models of the module), and some other variations in order to find a compositional and fully abstract semantics wrt the set of operations and a natural notion of observability.


title: Two results for proiritized logic programming

abstract: Prioritized default reasoning has illustrated its rich expressiveness and flexibility in knowledge representation and reasoning. However, many important aspects of prioritized default reasoning have yet to be thoroughly explored. In this paper, we investigate two properties of prioritized logic programs in the context of answer set semantics. Specifically, we reveal a close relationship between mutual defeasibility and uniqueness of the answer set for a prioritized logic program. We then explore how the splitting technique for extended logic programs can be extended to prioritized logic programs. We prove splitting theorems that can be used to simplify the evaluation of a prioritized logic program under certain conditions.


title: Computational Geometry Column 43

abstract: The concept of pointed pseudo-triangulations is defined and a few of its applications described.


title: SPINning Parallel Systems Software

abstract: We describe our experiences in using SPIN to verify parts of the Multi Purpose Daemon (MPD) parallel process management system. MPD is a distributed collection of processes connected by Unix network sockets. MPD is dynamic: processes and connections among them are created and destroyed as MPD is initialized, runs user processes, recovers from faults, and terminates. This dynamic nature is easily expressible in the SPIN/PROMELA framework but poses performance and scalability challenges. We present here the results of expressing some of the parallel algorithms of MPD and executing both simulation and verification runs with SPIN.


title: On Learning by Exchanging Advice

abstract: One of the main questions concerning learning in Multi-Agent Systems is: (How) can agents benefit from mutual interaction during the learning process?. This paper describes the study of an interactive advice-exchange mechanism as a possible way to improve agents' learning performance. The advice-exchange technique, discussed here, uses supervised learning (backpropagation), where reinforcement is not directly coming from the environment but is based on advice given by peers with better performance score (higher confidence), to enhance the performance of a heterogeneous group of Learning Agents (LAs). The LAs are facing similar problems, in an environment where only reinforcement information is available. Each LA applies a different, well known, learning technique: Random Walk (hill-climbing), Simulated Annealing, Evolutionary Algorithms and Q-Learning. The problem used for evaluation is a simplified traffic-control simulation. Initial results indicate that advice-exchange can improve learning speed, although bad advice and/or blind reliance can disturb the learning performance.


title: Capturing Knowledge of User Preferences: ontologies on recommender systems

abstract: Tools for filtering the World Wide Web exist, but they are hampered by the difficulty of capturing user preferences in such a dynamic environment. We explore the acquisition of user profiles by unobtrusive monitoring of browsing behaviour and application of supervised machine-learning techniques coupled with an ontological representation to extract user preferences. A multi-class approach to paper classification is used, allowing the paper topic taxonomy to be utilised during profile construction. The Quickstep recommender system is presented and two empirical studies evaluate it in a real work setting, measuring the effectiveness of using a hierarchical topic ontology compared with an extendable flat list.


title: Interface agents: A review of the field

abstract: This paper reviews the origins of interface agents, discusses challenges that exist within the interface agent field and presents a survey of current attempts to find solutions to these challenges. A history of agent systems from their birth in the 1960's to the current day is described, along with the issues they try to address. A taxonomy of interface agent systems is presented, and today's agent systems categorized accordingly. Lastly, an analysis of the machine learning and user modelling techniques used by today's agents is presented.


title: Representing and Aggregating Conflicting Beliefs

abstract: We consider the two-fold problem of representing collective beliefs and aggregating these beliefs. We propose modular, transitive relations for collective beliefs. They allow us to represent conflicting opinions and they have a clear semantics. We compare them with the quasi-transitive relations often used in Social Choice. Then, we describe a way to construct the belief state of an agent informed by a set of sources of varying degrees of reliability. This construction circumvents Arrow's Impossibility Theorem in a satisfactory manner. Finally, we give a simple set-theory-based operator for combining the information of multiple agents. We show that this operator satisfies the desirable invariants of idempotence, commutativity, and associativity, and, thus, is well-behaved when iterated, and we describe a computationally effective way of computing the resulting belief state.


title: Active Virtual Network Management Prediction: Complexity as a Framework for Prediction, Optimization, and Assurance

abstract: Research into active networking has provided the incentive to re-visit what has traditionally been classified as distinct properties and characteristics of information transfer such as protocol versus service; at a more fundamental level this paper considers the blending of computation and communication by means of complexity. The specific service examined in this paper is network self-prediction enabled by Active Virtual Network Management Prediction. Computation/communication is analyzed via Kolmogorov Complexity. The result is a mechanism to understand and improve the performance of active networking and Active Virtual Network Management Prediction in particular. The Active Virtual Network Management Prediction mechanism allows information, in various states of algorithmic and static form, to be transported in the service of prediction for network management. The results are generally applicable to algorithmic transmission of information. Kolmogorov Complexity is used and experimentally validated as a theory describing the relationship among algorithmic compression, complexity, and prediction accuracy within an active network. Finally, the paper concludes with a complexity-based framework for Information Assurance that attempts to take a holistic view of vulnerability analysis.


title: Towards Experimental Nanosound Using Almost Disjoint Set Theory

abstract: Music composition using digital audio sequence editors is increasingly performed in a visual workspace where sound complexes are built from discrete sound objects, called gestures that are arranged in time and space to generate a continuous composition. The visual workspace, common to most industry standard audio loop sequencing software, is premised on the arrangement of gestures defined with geometric shape properties. Here, one aspect of fractal set theory was validated using audio-frequency sets to evaluate self-affine scaling behavior when new sound complexes are built through union and intersection operations on discrete musical gestures. Results showed that intersection of two sets revealed lower complexity compared with the union operator, meaning that the intersection of two sound gestures is an almost disjoint set, and in accord with formal logic. These results are also discussed with reference to fuzzy sets, cellular automata, nanotechnology and self-organization to further explore the link between sequenced notation and complexity.


title: Dimension in Complexity Classes

abstract: A theory of resource-bounded dimension is developed using gales, which are natural generalizations of martingales. When the resource bound \Delta (a parameter of the theory) is unrestricted, the resulting dimension is precisely the classical Hausdorff dimension (sometimes called fractal dimension). Other choices of the parameter \Delta yield internal dimension theories in E, E2, ESPACE, and other complexity classes, and in the class of all decidable problems. In general, if C is such a class, then every set X of languages has a dimension in C, which is a real number dim(X|C) in [0,1]. Along with the elements of this theory, two preliminary applications are presented: 1. For every real number \alpha in (0,1/2), the set FREQ(<=\alpha), consisting of all languages that asymptotically contain at most \alpha of all strings, has dimension H(\alpha) -- the binary entropy of \alpha -- in E and in E2. 2. For every real number \alpha in (0,1), the set SIZE(\alpha* (2^n)/n), consisting of all languages decidable by Boolean circuits of at most \alpha*(2^n)/n gates, has dimension \alpha in ESPACE.


title: The Dimensions of Individual Strings and Sequences

abstract: A constructive version of Hausdorff dimension is developed using constructive supergales, which are betting strategies that generalize the constructive supermartingales used in the theory of individual random sequences. This constructive dimension is used to assign every individual (infinite, binary) sequence S a dimension, which is a real number dim(S) in the interval [0,1]. Sequences that are random (in the sense of Martin-Lof) have dimension 1, while sequences that are decidable, \Sigma^0_1, or \Pi^0_1 have dimension 0. It is shown that for every \Delta^0_2-computable real number \alpha in [0,1] there is a \Delta^0_2 sequence S such that \dim(S) = \alpha. A discrete version of constructive dimension is also developed using termgales, which are supergale-like functions that bet on the terminations of (finite, binary) strings as well as on their successive bits. This discrete dimension is used to assign each individual string w a dimension, which is a nonnegative real number dim(w). The dimension of a sequence is shown to be the limit infimum of the dimensions of its prefixes. The Kolmogorov complexity of a string is proven to be the product of its length and its dimension. This gives a new characterization of algorithmic information and a new proof of Mayordomo's recent theorem stating that the dimension of a sequence is the limit infimum of the average Kolmogorov complexity of its first n bits. Every sequence that is random relative to any computable sequence of coin-toss biases that converge to a real number \beta in (0,1) is shown to have dimension \H(\beta), the binary entropy of \beta.


title: Improving Table Compression with Combinatorial Optimization

abstract: We study the problem of compressing massive tables within the partition-training paradigm introduced by Buchsbaum et al. [SODA'00], in which a table is partitioned by an off-line training procedure into disjoint intervals of columns, each of which is compressed separately by a standard, on-line compressor like gzip. We provide a new theory that unifies previous experimental observations on partitioning and heuristic observations on column permutation, all of which are used to improve compression rates. Based on the theory, we devise the first on-line training algorithms for table compression, which can be applied to individual files, not just continuously operating sources; and also a new, off-line training algorithm, based on a link to the asymmetric traveling salesman problem, which improves on prior work by rearranging columns prior to partitioning. We demonstrate these results experimentally. On various test files, the on-line algorithms provide 35-55% improvement over gzip with negligible slowdown; the off-line reordering provides up to 20% further improvement over partitioning alone. We also show that a variation of the table compression problem is MAX-SNP hard.


title: GridSim: A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing

abstract: Clusters, grids, and peer-to-peer (P2P) networks have emerged as popular paradigms for next generation parallel and distributed computing. The management of resources and scheduling of applications in such large-scale distributed systems is a complex undertaking. In order to prove the effectiveness of resource brokers and associated scheduling algorithms, their performance needs to be evaluated under different scenarios such as varying number of resources and users with different requirements. In a grid environment, it is hard and even impossible to perform scheduler performance evaluation in a repeatable and controllable manner as resources and users are distributed across multiple organizations with their own policies. To overcome this limitation, we have developed a Java-based discrete-event grid simulation toolkit called GridSim. The toolkit supports modeling and simulation of heterogeneous grid resources (both time- and space-shared), users and application models. It provides primitives for creation of application tasks, mapping of tasks to resources, and their management. To demonstrate suitability of the GridSim toolkit, we have simulated a Nimrod-G like grid resource broker and evaluated the performance of deadline and budget constrained cost- and time-minimization scheduling algorithms.


title: A Deadline and Budget Constrained Cost-Time Optimisation Algorithm for Scheduling Task Farming Applications on Global Grids

abstract: Computational Grids and peer-to-peer (P2P) networks enable the sharing, selection, and aggregation of geographically distributed resources for solving large-scale problems in science, engineering, and commerce. The management and composition of resources and services for scheduling applications, however, becomes a complex undertaking. We have proposed a computational economy framework for regulating the supply and demand for resources and allocating them for applications based on the users quality of services requirements. The framework requires economy driven deadline and budget constrained (DBC) scheduling algorithms for allocating resources to application jobs in such a way that the users requirements are met. In this paper, we propose a new scheduling algorithm, called DBC cost-time optimisation, which extends the DBC cost-optimisation algorithm to optimise for time, keeping the cost of computation at the minimum. The superiority of this new scheduling algorithm, in achieving lower job completion time, is demonstrated by simulating the World-Wide Grid and scheduling task-farming applications for different deadline and budget scenarios using both this new and the cost optimisation scheduling algorithms.


title: NetNeg: A Connectionist-Agent Integrated System for Representing Musical Knowledge

abstract: The system presented here shows the feasibility of modeling the knowledge involved in a complex musical activity by integrating sub-symbolic and symbolic processes. This research focuses on the question of whether there is any advantage in integrating a neural network together with a distributed artificial intelligence approach within the music domain. The primary purpose of our work is to design a model that describes the different aspects a user might be interested in considering when involved in a musical activity. The approach we suggest in this work enables the musician to encode his knowledge, intuitions, and aesthetic taste into different modules. The system captures these aspects by computing and applying three distinct functions: rules, fuzzy concepts, and learning. As a case study, we began experimenting with first species two-part counterpoint melodies. We have developed a hybrid system composed of a connectionist module and an agent-based module to combine the sub-symbolic and symbolic levels to achieve this task. The technique presented here to represent musical knowledge constitutes a new approach for composing polyphonic music.


title: Three Optimisations for Sharing

abstract: In order to improve precision and efficiency sharing analysis should track both freeness and linearity. The abstract unification algorithms for these combined domains are suboptimal, hence there is scope for improving precision. This paper proposes three optimisations for tracing sharing in combination with freeness and linearity. A novel connection between equations and sharing abstractions is used to establish correctness of these optimisations even in the presence of rational trees. A method for pruning intermediate sharing abstractions to improve efficiency is also proposed. The optimisations are lightweight and therefore some, if not all, of these optimisations will be of interest to the implementor.


title: Agent trade servers in financial exchange systems

abstract: New services based on the best-effort paradigm could complement the current deterministic services of an electronic financial exchange. Four crucial aspects of such systems would benefit from a hybrid stance: proper use of processing resources, bandwidth management, fault tolerance, and exception handling. We argue that a more refined view on Quality-of-Service control for exchange systems, in which the principal ambition of upholding a fair and orderly marketplace is left uncompromised, would benefit all interested parties.


title: The structure of broad topics on the Web

abstract: The Web graph is a giant social network whose properties have been measured and modeled extensively in recent years. Most such studies concentrate on the graph structure alone, and do not consider textual properties of the nodes. Consequently, Web communities have been characterized purely in terms of graph structure and not on page content. We propose that a topic taxonomy such as Yahoo! or the Open Directory provides a useful framework for understanding the structure of content-based clusters and communities. In particular, using a topic taxonomy and an automatic classifier, we can measure the background distribution of broad topics on the Web, and analyze the capability of recent random walk algorithms to draw samples which follow such distributions. In addition, we can measure the probability that a page about one broad topic will link to another broad topic. Extending this experiment, we can measure how quickly topic context is lost while walking randomly on the Web graph. Estimates of this topic mixing distance may explain why a global PageRank is still meaningful in the context of broad queries. In general, our measurements may prove valuable in the design of community-specific crawlers and link-based ranking systems.


title: Sufficiently Fat Polyhedra are not 2-castable

abstract: In this note we consider the problem of manufacturing a convex polyhedral object via casting. We consider a generalization of the sand casting process where the object is manufactured by gluing together two identical faces of parts cast with a single piece mold. In this model we show that the class of convex polyhedra which can be enclosed between two concentric spheres of the ratio of their radii less than 1.07 cannot be manufactured using only two cast parts.


title: Conformal Geometry, Euclidean Space and Geometric Algebra

abstract: Projective geometry provides the preferred framework for most implementations of Euclidean space in graphics applications. Translations and rotations are both linear transformations in projective geometry, which helps when it comes to programming complicated geometrical operations. But there is a fundamental weakness in this approach - the Euclidean distance between points is not handled in a straightforward manner. Here we discuss a solution to this problem, based on conformal geometry. The language of geometric algebra is best suited to exploiting this geometry, as it handles the interior and exterior products in a single, unified framework. A number of applications are discussed, including a compact formula for reflecting a line off a general spherical surface.


title: The Algorithms of Updating Sequential Patterns

abstract: Because the data being mined in the temporal database will evolve with time, many researchers have focused on the incremental mining of frequent sequences in temporal database. In this paper, we propose an algorithm called IUS, using the frequent and negative border sequences in the original database for incremental sequence mining. To deal with the case where some data need to be updated from the original database, we present an algorithm called DUS to maintain sequential patterns in the updated database. We also define the negative border sequence threshold: Min_nbd_supp to control the number of sequences in the negative border.


title: When to Update the sequential patterns of stream data?

abstract: In this paper, we first define a difference measure between the old and new sequential patterns of stream data, which is proved to be a distance. Then we propose an experimental method, called TPD (Tradeoff between Performance and Difference), to decide when to update the sequential patterns of stream data by making a tradeoff between the performance of increasingly updating algorithms and the difference of sequential patterns. The experiments for the incremental updating algorithm IUS on two data sets show that generally, as the size of incremental windows grows, the values of the speedup and the values of the difference will decrease and increase respectively. It is also shown experimentally that the incremental ratio determined by the TPD method does not monotonically increase or decrease but changes in a range between 20 and 30 percentage for the IUS algorithm.


title: Forbidden Information

abstract: Goedel Incompleteness Theorem leaves open a way around it, vaguely perceived for a long time but not clearly identified. (Thus, Goedel believed informal arguments can answer any math question.) Closing this loophole does not seem obvious and involves Kolmogorov complexity. (This is unrelated to, well studied before, complexity quantifications of the usual Goedel effects.) I consider extensions U of the universal partial recursive predicate (or, say, Peano Arithmetic). I prove that any U either leaves an n-bit input (statement) unresolved or contains nearly all information about the n-bit prefix of any r.e. real r (which is n bits for some r). I argue that creating significant information about a SPECIFIC math sequence is impossible regardless of the methods used. Similar problems and answers apply to other unsolvability results for tasks allowing multiple solutions, e.g. non-recursive tilings.


title: Source Routing and Scheduling in Packet Networks

abstract: We study {\em routing} and {\em scheduling} in packet-switched networks. We assume an adversary that controls the injection time, source, and destination for each packet injected. A set of paths for these packets is {\em admissible} if no link in the network is overloaded. We present the first on-line routing algorithm that finds a set of admissible paths whenever this is feasible. Our algorithm calculates a path for each packet as soon as it is injected at its source using a simple shortest path computation. The length of a link reflects its current congestion. We also show how our algorithm can be implemented under today's Internet routing paradigms. When the paths are known (either given by the adversary or computed as above) our goal is to schedule the packets along the given paths so that the packets experience small end-to-end delays. The best previous delay bounds for deterministic and distributed scheduling protocols were exponential in the path length. In this paper we present the first deterministic and distributed scheduling protocol that guarantees a polynomial end-to-end delay for every packet. Finally, we discuss the effects of combining routing with scheduling. We first show that some unstable scheduling protocols remain unstable no matter how the paths are chosen. However, the freedom to choose paths can make a difference. For example, we show that a ring with parallel links is stable for all greedy scheduling protocols if paths are chosen intelligently, whereas this is not the case if the adversary specifies the paths.


title: A steady state model for graph power laws

abstract: Power law distribution seems to be an important characteristic of web graphs. Several existing web graph models generate power law graphs by adding new vertices and non-uniform edge connectivities to existing graphs. Researchers have conjectured that preferential connectivity and incremental growth are both required for the power law distribution. In this paper, we propose a different web graph model with power law distribution that does not require incremental growth. We also provide a comparison of our model with several others in their ability to predict web graph clustering behavior.


title: Coin-Moving Puzzles

abstract: We introduce a new family of one-player games, involving the movement of coins from one configuration to another. Moves are restricted so that a coin can be placed only in a position that is adjacent to at least two other coins. The goal of this paper is to specify exactly which of these games are solvable. By introducing the notion of a constant number of extra coins, we give tight theorems characterizing solvable puzzles on the square grid and equilateral-triangle grid. These existence results are supplemented by polynomial-time algorithms for finding a solution.


title: Blind Normalization of Speech From Different Channels and Speakers

abstract: This paper describes representations of time-dependent signals that are invariant under any invertible time-independent transformation of the signal time series. Such a representation is created by rescaling the signal in a non-linear dynamic manner that is determined by recently encountered signal levels. This technique may make it possible to normalize signals that are related by channel-dependent and speaker-dependent transformations, without having to characterize the form of the signal transformations, which remain unknown. The technique is illustrated by applying it to the time-dependent spectra of speech that has been filtered to simulate the effects of different channels. The experimental results show that the rescaled speech representations are largely normalized (i.e., channel-independent), despite the channel-dependence of the raw (unrescaled) speech.


title: Models and Tools for Collaborative Annotation

abstract: The Annotation Graph Toolkit (AGTK) is a collection of software which facilitates development of linguistic annotation tools. AGTK provides a database interface which allows applications to use a database server for persistent storage. This paper discusses various modes of collaborative annotation and how they can be supported with tools built using AGTK and its database interface. We describe the relational database schema and API, and describe a version of the TableTrans tool which supports collaborative annotation. The remainder of the paper discusses a high-level query language for annotation graphs, along with optimizations, in support of expressive and efficient access to the annotations held on a large central server. The paper demonstrates that it is straightforward to support a variety of different levels of collaborative annotation with existing AGTK-based tools, with a minimum of additional programming effort.


title: Creating Annotation Tools with the Annotation Graph Toolkit

abstract: The Annotation Graph Toolkit is a collection of software supporting the development of annotation tools based on the annotation graph model. The toolkit includes application programming interfaces for manipulating annotation graph data and for importing data from other formats. There are interfaces for the scripting languages Tcl and Python, a database interface, specialized graphical user interfaces for a variety of annotation tasks, and several sample applications. This paper describes all the toolkit components for the benefit of would-be application developers.


title: TableTrans, MultiTrans, InterTrans and TreeTrans: Diverse Tools Built on the Annotation Graph Toolkit

abstract: Four diverse tools built on the Annotation Graph Toolkit are described. Each tool associates linguistic codes and structures with time-series data. All are based on the same software library and tool architecture. TableTrans is for observational coding, using a spreadsheet whose rows are aligned to a signal. MultiTrans is for transcribing multi-party communicative interactions recorded using multi-channel signals. InterTrans is for creating interlinear text aligned to audio. TreeTrans is for creating and manipulating syntactic trees. This work demonstrates that the development of diverse tools and re-use of software components is greatly facilitated by a common high-level application programming interface for representing the data and managing input/output, together with a common architecture for managing the interaction of multiple components.


title: An Integrated Framework for Treebanks and Multilayer Annotations

abstract: Treebank formats and associated software tools are proliferating rapidly, with little consideration for interoperability. We survey a wide variety of treebank structures and operations, and show how they can be mapped onto the annotation graph model, and leading to an integrated framework encompassing tree and non-tree annotations alike. This development opens up new possibilities for managing and exploiting multilayer annotations.


title: The tip-of-the-tongue phenomenon: Irrelevant neural network localization or disruption of its interneuron links ?

abstract: On the base of recently proposed three-stage quantitative neural network model of the tip-of-the-tongue (TOT) phenomenon a possibility to occur of TOT states coursed by neural network interneuron links' disruption has been studied. Using a numerical example it was found that TOTs coursed by interneron links' disruption are in (1.5 + - 0.3)x1000 times less probable then those coursed by irrelevant (incomplete) neural network localization. It was shown that delayed TOT states' etiology cannot be related to neural network interneuron links' disruption.


title: New Results on Monotone Dualization and Generating Hypergraph Transversals

abstract: We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in NP-completeness. We present a number of new polynomial time resp. output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism. More precisely, this is feasible in polynomial time with O(chi(n) * log n) suitably guessed bits, where chi(n) is given by \chi(n)^chi(n) = n; note that chi(n) = o(log n). This result sheds new light on the complexity of this important problem.


title: On the Computational Complexity of Consistent Query Answers

abstract: We consider here the problem of obtaining reliable, consistent information from inconsistent databases -- databases that do not have to satisfy given integrity constraints. We use the notion of consistent query answer -- a query answer which is true in every (minimal) repair of the database. We provide a complete classification of the computational complexity of consistent answers to first-order queries w.r.t. functional dependencies and denial constraints. We show how the complexity depends on the {\em type} of the constraints considered, their {\em number}, and the {\em size} of the query. We obtain several new PTIME cases, using new algorithms.


title: Fair Stateless Aggregate Traffic Marking using Active Queue Management Techniques

abstract: In heterogeneous networks such as today's Internet, the differentiated services architecture promises to provide QoS guarantees through scalable service differentiation. Traffic marking is an important component of this framework. In this paper, we propose two new aggregate markers that are stateless, scalable and fair. We leverage stateless Active Queue Management (AQM) algorithms to enable fair and efficient token distribution among individual flows of an aggregate. The first marker, Probabilistic Aggregate Marker (PAM), uses the Token Bucket burst size to probabilistically mark incoming packets to ensure TCP-friendly and proportionally fair marking. The second marker, Stateless Aggregate Fair Marker (F-SAM) approximates fair queueing techniques to isolate flows while marking packets of the aggregate. It distributes tokens evenly among the flows without maintaining per-flow state. Our simulation results show that our marking strategies show upto 30% improvement over other commonly used markers while marking flow aggregates. These improvements are in terms of better average throughput and fairness indices, in scenarios containing heterogeneous traffic consisting of TCP (both long lived elephants and short lived mice) and misbehaving UDP flows. As a bonus, F-SAM helps the mice to win the war against elephants.


title: Exploiting Synergy Between Ontologies and Recommender Systems

abstract: Recommender systems learn about user preferences over time, automatically finding things of similar interest. This reduces the burden of creating explicit queries. Recommender systems do, however, suffer from cold-start problems where no initial information is available early on upon which to base recommendations. Semantic knowledge structures, such as ontologies, can provide valuable domain knowledge and user information. However, acquiring such knowledge and keeping it up to date is not a trivial task and user interests are particularly difficult to acquire and maintain. This paper investigates the synergy between a web-based research paper recommender system and an ontology containing information automatically extracted from departmental databases available on the web. The ontology is used to address the recommender systems cold-start problem. The recommender system addresses the ontology's interest-acquisition problem. An empirical evaluation of this approach is conducted and the performance of the integrated systems measured.


title: The Sketch of a Polymorphic Symphony

abstract: In previous work, we have introduced functional strategies, that is, first-class generic functions that can traverse into terms of any type while mixing uniform and type-specific behaviour. In the present paper, we give a detailed description of one particular Haskell-based model of functional strategies. This model is characterised as follows. Firstly, we employ first-class polymorphism as a form of second-order polymorphism as for the mere types of functional strategies. Secondly, we use an encoding scheme of run-time type case for mixing uniform and type-specific behaviour. Thirdly, we base all traversal on a fundamental combinator for folding over constructor applications. Using this model, we capture common strategic traversal schemes in a highly parameterised style. We study two original forms of parameterisation. Firstly, we design parameters for the specific control-flow, data-flow and traversal characteristics of more concrete traversal schemes. Secondly, we use overloading to postpone commitment to a specific type scheme of traversal. The resulting portfolio of traversal schemes can be regarded as a challenging benchmark for setups for typed generic programming. The way we develop the model and the suite of traversal schemes, it becomes clear that parameterised + typed strategic programming is best viewed as a potent combination of certain bits of parametric, intensional, polytypic, and ad-hoc polymorphism.


title: An Assessment of the Consistency for Software Measurement Methods

abstract: Consistency, defined as the requirement that a series of measurements of the same project carried out by different raters using the same method should produce similar results, is one of the most important aspects to be taken into account in the measurement methods of the software. In spite of this, there is a widespread view that many measurement methods introduce an undesirable amount of subjectivity in the measurement process. This perception has made several organizations develop revisions of the standard methods whose main aim is to improve their consistency by introducing some suitable modifications of those aspects which are believed to introduce a greater degree of subjectivity.Each revision of a method must be empirically evaluated to determine to what extent is the aim of improving its consistency achieved. In this article we will define an homogeneous statistic intended to describe the consistency level of a method, and we will develop the statistical analysis which should be carried out in order to conclude whether or not a measurement method is more consistent than other one.


title: Design Patterns for Functional Strategic Programming

abstract: In previous work, we introduced the fundamentals and a supporting combinator library for \emph{strategic programming}. This an idiom for generic programming based on the notion of a \emph{functional strategy}: a first-class generic function that cannot only be applied to terms of any type, but which also allows generic traversal into subterms and can be customized with type-specific behaviour. This paper seeks to provide practicing functional programmers with pragmatic guidance in crafting their own strategic programs. We present the fundamentals and the support from a user's perspective, and we initiate a catalogue of \emph{strategy design patterns}. These design patterns aim at consolidating strategic programming expertise in accessible form.


title: Making Abstract Domains Condensing

abstract: In this paper we show that reversible analysis of logic languages by abstract interpretation can be performed without loss of precision by systematically refining abstract domains. The idea is to include semantic structures into abstract domains in such a way that the refined abstract domain becomes rich enough to allow approximate bottom-up and top-down semantics to agree. These domains are known as condensing abstract domains. Substantially, an abstract domain is condensing if goal-driven and goal-independent analyses agree, namely no loss of precision is introduced by approximating queries in a goal-independent analysis. We prove that condensation is an abstract domain property and that the problem of making an abstract domain condensing boils down to the problem of making the domain complete with respect to unification. In a general abstract interpretation setting we show that when concrete domains and operations give rise to quantales, i.e. models of propositional linear logic, objects in a complete refined abstract domain can be explicitly characterized by linear logic-based formulations. This is the case for abstract domains for logic program analysis approximating computed answer substitutions where unification plays the role of multiplicative conjunction in a quantale of idempotent substitutions. Condensing abstract domains can therefore be systematically derived by minimally extending any, generally non-condensing domain, by a simple domain refinement operator.


title: Solitaire Clobber

abstract: Clobber is a new two-player board game. In this paper, we introduce the one-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white and black moves. We show that a checkerboard configuration on a single row (or single column) can be reduced to about n/4 stones. For boards with at least two rows and two columns, we show that a checkerboard configuration can be reduced to a single stone if and only if the number of stones is not a multiple of three, and otherwise it can be reduced to two stones. We also show that in general it is NP-complete to decide whether an arbitrary Clobber configuration can be reduced to a single stone.


title: A Framework for Datatype Transformation

abstract: We study one dimension in program evolution, namely the evolution of the datatype declarations in a program. To this end, a suite of basic transformation operators is designed. We cover structure-preserving refactorings, but also structure-extending and -reducing adaptations. Both the object programs that are subject to datatype transformations, and the meta programs that encode datatype transformations are functional programs.


title: Fast Universalization of Investment Strategies with Provably Good Relative Returns

abstract: A universalization of a parameterized investment strategy is an online algorithm whose average daily performance approaches that of the strategy operating with the optimal parameters determined offline in hindsight. We present a general framework for universalizing investment strategies and discuss conditions under which investment strategies are universalizable. We present examples of common investment strategies that fit into our framework. The examples include both trading strategies that decide positions in individual stocks, and portfolio strategies that allocate wealth among multiple stocks. This work extends Cover's universal portfolio work. We also discuss the runtime efficiency of universalization algorithms. While a straightforward implementation of our algorithms runs in time exponential in the number of parameters, we show that the efficient universal portfolio computation technique of Kalai and Vempala involving the sampling of log-concave functions can be generalized to other classes of investment strategies.


title: Seven Dimensions of Portability for Language Documentation and Description

abstract: The process of documenting and describing the world's languages is undergoing radical transformation with the rapid uptake of new digital technologies for capture, storage, annotation and dissemination. However, uncritical adoption of new tools and technologies is leading to resources that are difficult to reuse and which are less portable than the conventional printed resources they replace. We begin by reviewing current uses of software tools and digital technologies for language documentation and description. This sheds light on how digital language documentation and description are created and managed, leading to an analysis of seven portability problems under the following headings: content, format, discovery, access, citation, preservation and rights. After characterizing each problem we provide a series of value statements, and this provides the framework for a broad range of best practice recommendations.


title: Factual and Legal Risks regarding wireless Computer Networks

abstract: The IEEE 802.11b wireless ethernet standart has several serious security flaws. This paper describes this flaws, surveys wireless networks in the Cologne/Bonn area to get an assessment of the security configurations of fielded networks and analizes the legal protections provided to wireless ethernet operators by german law. We conclude that wireless ethernets without additional security measures are not usable for any transmissions which are not meant for a public audience.


title: Annotation Graphs and Servers and Multi-Modal Resources: Infrastructure for Interdisciplinary Education, Research and Development

abstract: Annotation graphs and annotation servers offer infrastructure to support the analysis of human language resources in the form of time-series data such as text, audio and video. This paper outlines areas of common need among empirical linguists and computational linguists. After reviewing examples of data and tools used or under development for each of several areas, it proposes a common framework for future tool development, data annotation and resource sharing based upon annotation graphs and servers.


title: Computational Phonology

abstract: Phonology, as it is practiced, is deeply computational. Phonological analysis is data-intensive and the resulting models are nothing other than specialized data structures and algorithms. In the past, phonological computation - managing data and developing analyses - was done manually with pencil and paper. Increasingly, with the proliferation of affordable computers, IPA fonts and drawing software, phonologists are seeking to move their computation work online. Computational Phonology provides the theoretical and technological framework for this migration, building on methodologies and tools from computational linguistics. This piece consists of an apology for computational phonology, a history, and an overview of current research.


title: The Geometric Maximum Traveling Salesman Problem

abstract: We consider the traveling salesman problem when the cities are points in R^d for some fixed d and distances are computed according to geometric distances, determined by some norm. We show that for any polyhedral norm, the problem of finding a tour of maximum length can be solved in polynomial time. If arithmetic operations are assumed to take unit time, our algorithms run in time O(n^{f-2} log n), where f is the number of facets of the polyhedron determining the polyhedral norm. Thus for example we have O(n^2 log n) algorithms for the cases of points in the plane under the Rectilinear and Sup norms. This is in contrast to the fact that finding a minimum length tour in each case is NP-hard. Our approach can be extended to the more general case of quasi-norms with not necessarily symmetric unit ball, where we get a complexity of O(n^{2f-2} log n). For the special case of two-dimensional metrics with f=4 (which includes the Rectilinear and Sup norms), we present a simple algorithm with O(n) running time. The algorithm does not use any indirect addressing, so its running time remains valid even in comparison based models in which sorting requires Omega(n \log n) time. The basic mechanism of the algorithm provides some intuition on why polyhedral norms allow fast algorithms. Complementing the results on simplicity for polyhedral norms, we prove that for the case of Euclidean distances in R^d for d>2, the Maximum TSP is NP-hard. This sheds new light on the well-studied difficulties of Euclidean distances.


title: Phonology

abstract: Phonology is the systematic study of the sounds used in language, their internal structure, and their composition into syllables, words and phrases. Computational phonology is the application of formal and computational techniques to the representation and processing of phonological information. This chapter will present the fundamentals of descriptive phonology along with a brief overview of computational phonology.


title: Querying Databases of Annotated Speech

abstract: Annotated speech corpora are databases consisting of signal data along with time-aligned symbolic `transcriptions'. Such databases are typically multidimensional, heterogeneous and dynamic. These properties present a number of tough challenges for representation and query. The temporal nature of the data adds an additional layer of complexity. This paper presents and harmonises two independent efforts to model annotated speech databases, one at Macquarie University and one at the University of Pennsylvania. Various query languages are described, along with illustrative applications to a variety of analytical problems. The research reported here forms a part of several ongoing projects to develop platform-independent open-source tools for creating, browsing, searching, querying and transforming linguistic databases, and to disseminate large linguistic databases over the internet.


title: Integrating selectional preferences in WordNet

abstract: Selectional preference learning methods have usually focused on word-to-class relations, e.g., a verb selects as its subject a given nominal class. This paper extends previous statistical models to class-to-class preferences, and presents a model that learns selectional preferences for classes of verbs, together with an algorithm to integrate the learned preferences in WordNet. The theoretical motivation is twofold: different senses of a verb may have different preferences, and classes of verbs may share preferences. On the practical side, class-to-class selectional preferences can be learned from untagged corpora (the same as word-to-class), they provide selectional preferences for less frequent word senses via inheritance, and more important, they allow for easy integration in WordNet. The model is trained on subject-verb and object-verb relationships extracted from a small corpus disambiguated with WordNet senses. Examples are provided illustrating that the theoretical motivations are well founded, and showing that the approach is feasible. Experimental results on a word sense disambiguation task are also provided.


title: Decision Lists for English and Basque

abstract: In this paper we describe the systems we developed for the English (lexical and all-words) and Basque tasks. They were all supervised systems based on Yarowsky's Decision Lists. We used Semcor for training in the English all-words task. We defined different feature sets for each language. For Basque, in order to extract all the information from the text, we defined features that have not been used before in the literature, using a morphological analyzer. We also implemented systems that selected automatically good features and were able to obtain a prefixed precision (85%) at the cost of coverage. The systems that used all the features were identified as BCU-ehu-dlist-all and the systems that selected some features as BCU-ehu-dlist-best.


title: The Basque task: did systems perform in the upperbound?

abstract: In this paper we describe the Senseval 2 Basque lexical-sample task. The task comprised 40 words (15 nouns, 15 verbs and 10 adjectives) selected from Euskal Hiztegia, the main Basque dictionary. Most examples were taken from the Egunkaria newspaper. The method used to hand-tag the examples produced low inter-tagger agreement (75%) before arbitration. The four competing systems attained results well above the most frequent baseline and the best system scored 75% precision at 100% coverage. The paper includes an analysis of the tagging procedure used, as well as the performance of the competing systems. In particular, we argue that inter-tagger agreement is not a real upperbound for the Basque WSD task.


title: Fast Hands-free Writing by Gaze Direction

abstract: We describe a method for text entry based on inverse arithmetic coding that relies on gaze direction and which is faster and more accurate than using an on-screen keyboard. These benefits are derived from two innovations: the writing task is matched to the capabilities of the eye, and a language model is used to make predictable words and phrases easier to write.


title: A Dynamic Approach to Characterizing Termination of General Logic Programs

abstract: We present a new characterization of termination of general logic programs. Most existing termination analysis approaches rely on some static information about the structure of the source code of a logic program, such as modes/types, norms/level mappings, models/interargument relations, and the like. We propose a dynamic approach which employs some key dynamic features of an infinite (generalized) SLDNF-derivation, such as repetition of selected subgoals and recursive increase in term size. We also introduce a new formulation of SLDNF-trees, called generalized SLDNF-trees. Generalized SLDNF-trees deal with negative subgoals in the same way as Prolog and exist for any general logic programs.


title: Belief Revision and Rational Inference

abstract: The (extended) AGM postulates for belief revision seem to deal with the revision of a given theory K by an arbitrary formula, but not to constrain the revisions of two different theories by the same formula. A new postulate is proposed and compared with other similar postulates that have been proposed in the literature. The AGM revisions that satisfy this new postulate stand in one-to-one correspondence with the rational, consistency-preserving relations. This correspondence is described explicitly. Two viewpoints on iterative revisions are distinguished and discussed.


title: Randomized selection revisited

abstract: We show that several versions of Floyd and Rivest's algorithm Select for finding the $k$th smallest of $n$ elements require at most $n+\min\{k,n-k\}+o(n)$ comparisons on average and with high probability. This rectifies the analysis of Floyd and Rivest, and extends it to the case of nondistinct elements. Our computational results confirm that Select may be the best algorithm in practice.


title: Monitoring and Debugging Concurrent and Distributed Object-Oriented Systems

abstract: A major part of debugging, testing, and analyzing a complex software system is understanding what is happening within the system at run-time. Some developers advocate running within a debugger to better understand the system at this level. Others embed logging statements, even in the form of hard-coded calls to print functions, throughout the code. These techniques are all general, rough forms of what we call system monitoring, and, while they have limited usefulness in simple, sequential systems, they are nearly useless in complex, concurrent ones. We propose a set of new mechanisms, collectively known as a monitoring system, for understanding such complex systems, and we describe an example implementation of such a system, called IDebug, for the Java programming language.


title: Semantic Properties for Lightweight Specification in Knowledgeable Development Environments

abstract: Semantic properties are domain-specific specification constructs used to augment an existing language with richer semantics. These properties are taken advantage of in system analysis, design, implementation, testing, and maintenance through the use of documentation and source-code transformation tools. Semantic properties are themselves specified at two levels: loosely with precise natural language, and formally within the problem domain. The refinement relationships between these specification levels, as well as between a semantic property's use and its realization in program code via tools, is specified with a new formal method for reuse called kind theory.


title: Semantic Component Composition

abstract: Building complex software systems necessitates the use of component-based architectures. In theory, of the set of components needed for a design, only some small portion of them are "custom"; the rest are reused or refactored existing pieces of software. Unfortunately, this is an idealized situation. Just because two components should work together does not mean that they will work together. The "glue" that holds components together is not just technology. The contracts that bind complex systems together implicitly define more than their explicit type. These "conceptual contracts" describe essential aspects of extra-system semantics: e.g., object models, type systems, data representation, interface action semantics, legal and contractual obligations, and more. Designers and developers spend inordinate amounts of time technologically duct-taping systems to fulfill these conceptual contracts because system-wide semantics have not been rigorously characterized or codified. This paper describes a formal characterization of the problem and discusses an initial implementation of the resulting theoretical system.


title: Kolmogorov's Structure Functions and Model Selection

abstract: In 1974 Kolmogorov proposed a non-probabilistic approach to statistics and model selection. Let data be finite binary strings and models be finite sets of binary strings. Consider model classes consisting of models of given maximal (Kolmogorov) complexity. The ``structure function'' of the given data expresses the relation between the complexity level constraint on a model class and the least log-cardinality of a model in the class containing the data. We show that the structure function determines all stochastic properties of the data: for every constrained model class it determines the individual best-fitting model in the class irrespective of whether the ``true'' model is in the model class considered or not. In this setting, this happens {\em with certainty}, rather than with high probability as is in the classical case. We precisely quantify the goodness-of-fit of an individual model with respect to individual data. We show that--within the obvious constraints--every graph is realized by the structure function of some data. We determine the (un)computability properties of the various functions contemplated and of the ``algorithmic minimal sufficient statistic.''


title: Technology For Information Engineering (TIE): A New Way of Storing, Retrieving and Analyzing Information

abstract: The theoretical foundations of a new model and paradigm (called TIE) for data storage and access are introduced. Associations between data elements are stored in a single Matrix table, which is usually kept entirely in RAM for quick access. The model ties together a very intuitive "guided" GUI to the Matrix structure, allowing extremely easy complex searches through the data. Although it is an "Associative Model" in that it stores the data associations separately from the data itself, in contrast to other implementations of that model TIE guides the user to only the available information ensuring that every search is always fruitful. Very many diverse applications of the technology are reviewed.


title: Precongruence Formats for Decorated Trace Semantics

abstract: This paper explores the connection between semantic equivalences and preorders for concrete sequential processes, represented by means of labelled transition systems, and formats of transition system specifications using Plotkin's structural approach. For several preorders in the linear time - branching time spectrum a format is given, as general as possible, such that this preorder is a precongruence for all operators specifiable in that format. The formats are derived using the modal characterizations of the corresponding preorders.


title: Self-Optimizing and Pareto-Optimal Policies in General Environments based on Bayes-Mixtures

abstract: The problem of making sequential decisions in unknown probabilistic environments is studied. In cycle $t$ action $y_t$ results in perception $x_t$ and reward $r_t$, where all quantities in general may depend on the complete history. The perception $x_t$ and reward $r_t$ are sampled from the (reactive) environmental probability distribution $\mu$. This very general setting includes, but is not limited to, (partial observable, k-th order) Markov decision processes. Sequential decision theory tells us how to act in order to maximize the total expected reward, called value, if $\mu$ is known. Reinforcement learning is usually used if $\mu$ is unknown. In the Bayesian approach one defines a mixture distribution $\xi$ as a weighted sum of distributions $\nu\in\M$, where $\M$ is any class of distributions including the true environment $\mu$. We show that the Bayes-optimal policy $p^\xi$ based on the mixture $\xi$ is self-optimizing in the sense that the average value converges asymptotically for all $\mu\in\M$ to the optimal value achieved by the (infeasible) Bayes-optimal policy $p^\mu$ which knows $\mu$ in advance. We show that the necessary condition that $\M$ admits self-optimizing policies at all, is also sufficient. No other structural assumptions are made on $\M$. As an example application, we discuss ergodic Markov decision processes, which allow for self-optimizing policies. Furthermore, we show that $p^\xi$ is Pareto-optimal in the sense that there is no other policy yielding higher or equal value in {\em all} environments $\nu\in\M$ and a strictly higher value in at least one.


title: Trust Brokerage Systems for the Internet

abstract: This thesis addresses the problem of providing trusted individuals with confidential information about other individuals, in particular, granting access to databases of personal records using the World-Wide Web. It proposes an access rights management system for distributed databases which aims to create and implement organisation structures based on the wishes of the owners and of demands of the users of the databases. The dissertation describes how current software components could be used to implement this system; it re-examines the theory of collective choice to develop mechanisms for generating hierarchies of authorities; it analyses organisational processes for stability and develops a means of measuring the similarity of their hierarchies.


title: Preprocessing Chains for Fast Dihedral Rotations Is Hard or Even Impossible

abstract: We examine a computational geometric problem concerning the structure of polymers. We model a polymer as a polygonal chain in three dimensions. Each edge splits the polymer into two subchains, and a dihedral rotation rotates one of these chains rigidly about this edge. The problem is to determine, given a chain, an edge, and an angle of rotation, if the motion can be performed without causing the chain to self-intersect. An Omega(n log n) lower bound on the time complexity of this problem is known. We prove that preprocessing a chain of n edges and answering n dihedral rotation queries is 3SUM-hard, giving strong evidence that solving n queries requires Omega(n^2) time in the worst case. For dynamic queries, which also modify the chain if the requested dihedral rotation is feasible, we show that answering n queries is by itself 3SUM-hard, suggesting that sublinear query time is impossible after any amount of preprocessing.