title: Exact Complexity of the Winner Problem for Young Elections

abstract:
  In 1977, Young proposed a voting scheme that extends the Condorcet Principle
based on the fewest possible number of voters whose removal yields a Condorcet
winner. We prove that both the winner and the ranking problem for Young
elections is complete for the class of problems solvable in polynomial time by
parallel access to NP. Analogous results for Lewis Carroll's 1876 voting scheme
were recently established by Hemaspaandra et al. In contrast, we prove that the
winner and ranking problems in Fishburn's homogeneous variant of Carroll's
voting scheme can be solved efficiently by linear programming.


title: Faster Algorithm of String Comparison

abstract:
  In many applications, it is necessary to determine the string similarity.
Edit distance[WF74] approach is a classic method to determine Field Similarity.
A well known dynamic programming algorithm [GUS97] is used to calculate edit
distance with the time complexity O(nm). (for worst case, average case and even
best case) Instead of continuing with improving the edit distance approach,
[LL+99] adopted a brand new approach-token-based approach. Its new concept of
token-base-retain the original semantic information, good time complex-O(nm)
(for worst, average and best case) and good experimental performance make it a
milestone paper in this area. Further study indicates that there is still room
for improvement of its Field Similarity algorithm. Our paper is to introduce a
package of substring-based new algorithms to determine Field Similarity.
Combined together, our new algorithms not only achieve higher accuracy but also
gain the time complexity O(knm) (k<0.75) for worst case, O(*n) where <6 for
average case and O(1) for best case. Throughout the paper, we use the approach
of comparative examples to show higher accuracy of our algorithms compared to
the one proposed in [LL+99]. Theoretical analysis, concrete examples and
experimental result show that our algorithms can significantly improve the
accuracy and time complexity of the calculation of Field Similarity. [US97] D.
Guseld. Algorithms on Strings, Trees and Sequences, in Computer Science and
Computational Biology. [LL+99] Mong Li Lee, Cleansing data for mining and
warehousing, In Proceedings of the 10th International Conference on Database
and Expert Systems Applications (DEXA99), pages 751-760,August 1999. [WF74] R.
Wagner and M. Fisher, The String to String Correction Problem, JACM 21 pages
168-173, 1974.


title:
Lower Bound on the Chromatic Number by Spectra of Weighted Adjacency
  Matrices

abstract:
  A lower bound on the chromatic number of a graph is derived by majorization
of spectra of weighted adjacency matrices. These matrices are given by Hadamard
products of the adjacency matrix and arbitrary Hermitian matrices.


title: Media Objects in Time - A Multimedia Streaming System

abstract:
  The widespread availability of networked multimedia potentials embedded in an
infrastructure of qualitative superior kind gives rise to new approaches in the
areas of teleteaching and internet presentation: The distribution of
professionally styled multimedia streams has fallen in the realm of
possibility. This paper presents a prototype - both model and runtime
environment - of a time directed media system treating any kind of
presentational contribution as reusable media object components. The plug-in
free runtime system is based on a database and allows for a flexible support of
static media types as well as for easy extensions by streaming media servers.
The prototypic implementation includes a preliminary Web Authoring platform.


title: Lower Bounds for Matrix Product

abstract:
  We prove lower bounds on the number of product gates in bilinear and
quadratic circuits that compute the product of two $n \cross n$ matrices over
finite fields. In particular we obtain the following results:
  1. We show that the number of product gates in any bilinear (or quadratic)
circuit that computes the product of two $n \cross n$ matrices over $F_2$ is at
least $3 n^2 - o(n^2)$.
  2. We show that the number of product gates in any bilinear circuit that
computes the product of two $n \cross n$ matrices over $F_p$ is at least $(2.5
+ \frac{1.5}{p^3 -1})n^2 -o(n^2)$.
  These results improve the former results of Bshouty '89 and Blaser '99 who
proved lower bounds of $2.5 n^2 - o(n^2)$.


title: Incremental Construction of Compact Acyclic NFAs

abstract:
  This paper presents and analyzes an incremental algorithm for the
construction of Acyclic Non-deterministic Finite-state Automata (NFA). Automata
of this type are quite useful in computational linguistics, especially for
storing lexicons. The proposed algorithm produces compact NFAs, i.e. NFAs that
do not contain equivalent states. Unlike Deterministic Finite-state Automata
(DFA), this property is not sufficient to ensure minimality, but still the
resulting NFAs are considerably smaller than the minimal DFAs for the same
languages.


title: Trust enhancement by multiple random beacons

abstract:
  Random beacons-information sources that broadcast a stream of random digits
unknown by anyone beforehand-are useful for various cryptographic purposes. But
such beacons can be easily and undetectably sabotaged, so that their output is
known beforehand by a dishonest party, who can use this information to defeat
the cryptographic protocols supposedly protected by the beacon. We explore a
strategy to reduce this hazard by combining the outputs from several
noninteracting (eg spacelike-separated) beacons by XORing them together to
produce a single digit stream which is more trustworthy than any individual
beacon, being random and unpredictable if at least one of the contributing
beacons is honest. If the contributing beacons are not spacelike separated, so
that a dishonest beacon can overhear and adapt to earlier outputs of other
beacons, the beacons' trustworthiness can still be enhanced to a lesser extent
by a time sharing strategy. We point out some disadvantages of alternative
trust amplification methods based on one-way hash functions.


title: Analysis of Non-Gaussian Nature of Network Traffic

abstract:
  To study mechanisms that cause the non-Gaussian nature of network traffic, we
analyzed IP flow statistics. For greedy flows in particular, we investigated
the hop counts between source and destination nodes, and classified
applications by the port number. We found that the main flows contributing to
the non-Gaussian nature of network traffic were HTTP flows with relatively
small hop counts compared with the average hop counts of all flows.


title: Sharpening Occam's Razor

abstract:
  We provide a new representation-independent formulation of Occam's razor
theorem, based on Kolmogorov complexity. This new formulation allows us to:
  (i) Obtain better sample complexity than both length-based and VC-based
versions of Occam's razor theorem, in many applications.
  (ii) Achieve a sharper reverse of Occam's razor theorem than previous work.
  Specifically, we weaken the assumptions made in an earlier publication, and
extend the reverse to superpolynomial running times.

categories: cs.LG cond-mat.dis-nn cs.AI cs.CC math.PR physics.data-an


title:
On the Importance of Having an Identity or, is Consensus really
  Universal?

abstract:
  We show that Naming-- the existence of distinct IDs known to all-- is a
hidden but necessary assumption of Herlihy's universality result for Consensus.
We then show in a very precise sense that Naming is harder than Consensus and
bring to the surface some important differences existing between popular shared
memory models.


title: Algorithm for generating orthogonal matrices with rational elements

abstract:
  Special orthogonal matrices with rational elements form the group SO(n,Q),
where Q is the field of rational numbers. A theorem describing the structure of
an arbitrary matrix from this group is proved. This theorem yields an algorithm
for generating such matrices by means of random number routines.


title:
Using Tree Automata and Regular Expressions to Manipulate Hierarchically
  Structured Data

abstract:
  Information, stored or transmitted in digital form, is often structured.
Individual data records are usually represented as hierarchies of their
elements. Together, records form larger structures. Information processing
applications have to take account of this structuring, which assigns different
semantics to different data elements or records. Big variety of structural
schemata in use today often requires much flexibility from applications--for
example, to process information coming from different sources. To ensure
application interoperability, translators are needed that can convert one
structure into another. This paper puts forward a formal data model aimed at
supporting hierarchical data processing in a simple and flexible way. The model
is based on and extends results of two classical theories, studying finite
string and tree automata. The concept of finite automata and regular languages
is applied to the case of arbitrarily structured tree-like hierarchical data
records, represented as "structured strings." These automata are compared with
classical string and tree automata; the model is shown to be a superset of the
classical models. Regular grammars and expressions over structured strings are
introduced. Regular expression matching and substitution has been widely used
for efficient unstructured text processing; the model described here brings the
power of this proven technique to applications that deal with information
trees. A simple generic alternative is offered to replace today's specialised
ad-hoc approaches. The model unifies structural and content transformations,
providing applications with a single data type. An example scenario of how to
build applications based on this theory is discussed. Further research
directions are outlined.


title: The performance of the batch learner algorithm

abstract:
  We analyze completely the convergence speed of the \emph{batch learning
algorithm}, and compare its speed to that of the memoryless learning algorithm
and of learning with memory. We show that the batch learning algorithm is never
worse than the memoryless learning algorithm (at least asymptotically). Its
performance \emph{vis-a-vis} learning with full memory is less clearcut, and
depends on certain probabilistic assumptions.


title: Bundling Equilibrium in Combinatorial auctions

abstract:
  This paper analyzes individually-rational ex post equilibrium in the VC
(Vickrey-Clarke) combinatorial auctions. If $\Sigma$ is a family of bundles of
goods, the organizer may restrict the participants by requiring them to submit
their bids only for bundles in $\Sigma$. The $\Sigma$-VC combinatorial auctions
(multi-good auctions) obtained in this way are known to be
individually-rational truth-telling mechanisms. In contrast, this paper deals
with non-restricted VC auctions, in which the buyers restrict themselves to
bids on bundles in $\Sigma$, because it is rational for them to do so. That is,
it may be that when the buyers report their valuation of the bundles in
$\Sigma$, they are in an equilibrium. We fully characterize those $\Sigma$ that
induce individually rational equilibrium in every VC auction, and we refer to
the associated equilibrium as a bundling equilibrium. The number of bundles in
$\Sigma$ represents the communication complexity of the equilibrium. A special
case of bundling equilibrium is partition-based equilibrium, in which $\Sigma$
is a field, that is, it is generated by a partition. We analyze the tradeoff
between communication complexity and economic efficiency of bundling
equilibrium, focusing in particular on partition-based equilibrium.


title: A Backward Analysis for Constraint Logic Programs

abstract:
  One recurring problem in program development is that of understanding how to
re-use code developed by a third party. In the context of (constraint) logic
programming, part of this problem reduces to figuring out how to query a
program. If the logic program does not come with any documentation, then the
programmer is forced to either experiment with queries in an ad hoc fashion or
trace the control-flow of the program (backward) to infer the modes in which a
predicate must be called so as to avoid an instantiation error. This paper
presents an abstract interpretation scheme that automates the latter technique.
The analysis presented in this paper can infer moding properties which if
satisfied by the initial query, come with the guarantee that the program and
query can never generate any moding or instantiation errors. Other applications
of the analysis are discussed. The paper explains how abstract domains with
certain computational properties (they condense) can be used to trace
control-flow backward (right-to-left) to infer useful properties of initial
queries. A correctness argument is presented and an implementation is reported.


title: Efficient Groundness Analysis in Prolog

abstract:
  Boolean functions can be used to express the groundness of, and trace
grounding dependencies between, program variables in (constraint) logic
programs. In this paper, a variety of issues pertaining to the efficient Prolog
implementation of groundness analysis are investigated, focusing on the domain
of definite Boolean functions, Def. The systematic design of the representation
of an abstract domain is discussed in relation to its impact on the algorithmic
complexity of the domain operations; the most frequently called operations
should be the most lightweight. This methodology is applied to Def, resulting
in a new representation, together with new algorithms for its domain operations
utilising previously unexploited properties of Def -- for instance,
quadratic-time entailment checking. The iteration strategy driving the analysis
is also discussed and a simple, but very effective, optimisation of induced
magic is described. The analysis can be implemented straightforwardly in Prolog
and the use of a non-ground representation results in an efficient, scalable
tool which does not require widening to be invoked, even on the largest
benchmarks. An extensive experimental evaluation is given


title:
Computing Preferred Answer Sets by Meta-Interpretation in Answer Set
  Programming

abstract:
  Most recently, Answer Set Programming (ASP) is attracting interest as a new
paradigm for problem solving. An important aspect which needs to be supported
is the handling of preferences between rules, for which several approaches have
been presented. In this paper, we consider the problem of implementing
preference handling approaches by means of meta-interpreters in Answer Set
Programming. In particular, we consider the preferred answer set approaches by
Brewka and Eiter, by Delgrande, Schaub and Tompits, and by Wang, Zhou and Lin.
We present suitable meta-interpreters for these semantics using DLV, which is
an efficient engine for ASP. Moreover, we also present a meta-interpreter for
the weakly preferred answer set approach by Brewka and Eiter, which uses the
weak constraint feature of DLV as a tool for expressing and solving an
underlying optimization problem. We also consider advanced meta-interpreters,
which make use of graph-based characterizations and often allow for more
efficient computations. Our approach shows the suitability of ASP in general
and of DLV in particular for fast prototyping. This can be fruitfully exploited
for experimenting with new languages and knowledge-representation formalisms.


title: The Dynamics of AdaBoost Weights Tells You What's Hard to Classify

abstract:
  The dynamical evolution of weights in the Adaboost algorithm contains useful
information about the role that the associated data points play in the built of
the Adaboost model. In particular, the dynamics induces a bipartition of the
data set into two (easy/hard) classes. Easy points are ininfluential in the
making of the model, while the varying relevance of hard points can be gauged
in terms of an entropy value associated to their evolution. Smooth
approximations of entropy highlight regions where classification is most
uncertain. Promising results are obtained when methods proposed are applied in
the Optimal Sampling framework.


title: On the Significance of Digits in Interval Notation

abstract:
  To analyse the significance of the digits used for interval bounds, we
clarify the philosophical presuppositions of various interval notations. We use
information theory to determine the information content of the last digit of
the numeral used to denote the interval's bounds. This leads to the notion of
efficiency of a decimal digit: the actual value as percentage of the maximal
value of its information content. By taking this efficiency into account, many
presentations of intervals can be made more readable at the expense of
negligible loss of information.


title: A computer scientist looks at game theory

abstract:
  I consider issues in distributed computation that should be of relevance to
game theory. In particular, I focus on (a) representing knowledge and
uncertainty, (b) dealing with failures, and (c) specification of mechanisms.


title:
Collusion in Unrepeated, First-Price Auctions with an Uncertain Number
  of Participants

abstract:
  We consider the question of whether collusion among bidders (a "bidding
ring") can be supported in equilibrium of unrepeated first-price auctions.
Unlike previous work on the topic such as that by McAfee and McMillan [1992]
and Marshall and Marx [2007], we do not assume that non-colluding agents have
perfect knowledge about the number of colluding agents whose bids are
suppressed by the bidding ring, and indeed even allow for the existence of
multiple cartels. Furthermore, while we treat the association of bidders with
bidding rings as exogenous, we allow bidders to make strategic decisions about
whether to join bidding rings when invited. We identify a bidding ring protocol
that results in an efficient allocation in Bayes{Nash equilibrium, under which
non-colluding agents bid straightforwardly, and colluding agents join bidding
rings when invited and truthfully declare their valuations to the ring center.
We show that bidding rings benefit ring centers and all agents, both members
and non-members of bidding rings, at the auctioneer's expense. The techniques
we introduce in this paper may also be useful for reasoning about other
problems in which agents have asymmetric information about a setting.


title: Long Proteins with Unique Optimal Foldings in the H-P Model

abstract:
  It is widely accepted that (1) the natural or folded state of proteins is a
global energy minimum, and (2) in most cases proteins fold to a unique state
determined by their amino acid sequence. The H-P (hydrophobic-hydrophilic)
model is a simple combinatorial model designed to answer qualitative questions
about the protein folding process. In this paper we consider a problem
suggested by Brian Hayes in 1998: what proteins in the two-dimensional H-P
model have unique optimal (minimum energy) foldings? In particular, we prove
that there are closed chains of monomers (amino acids) with this property for
all (even) lengths; and that there are open monomer chains with this property
for all lengths divisible by four.


title:
Structure from Motion: Theoretical Foundations of a Novel Approach Using
  Custom Built Invariants

abstract:
  We rephrase the problem of 3D reconstruction from images in terms of
intersections of projections of orbits of custom built Lie groups actions. We
then use an algorithmic method based on moving frames "a la Fels-Olver" to
obtain a fundamental set of invariants of these groups actions. The invariants
are used to define a set of equations to be solved by the points of the 3D
object, providing a new technique for recovering 3D structure from motion.


title: A Modal Logic Framework for Multi-agent Belief Fusion

abstract:
  This paper is aimed at providing a uniform framework for reasoning about
beliefs of multiple agents and their fusion. In the first part of the paper, we
develop logics for reasoning about cautiously merged beliefs of agents with
different degrees of reliability. The logics are obtained by combining the
multi-agent epistemic logic and multi-sources reasoning systems. Every ordering
for the reliability of the agents is represented by a modal operator, so we can
reason with the merged results under different situations. The fusion is
cautious in the sense that if an agent's belief is in conflict with those of
higher priorities, then his belief is completely discarded from the merged
result. We consider two strategies for the cautious merging of beliefs. In the
first one, if inconsistency occurs at some level, then all beliefs at the lower
levels are discarded simultaneously, so it is called level cutting strategy.
For the second one, only the level at which the inconsistency occurs is
skipped, so it is called level skipping strategy. The formal semantics and
axiomatic systems for these two strategies are presented. In the second part,
we extend the logics both syntactically and semantically to cover some more
sophisticated belief fusion and revision operators. While most existing
approaches treat belief fusion operators as meta-level constructs, these
operators are directly incorporated into our object logic language. Thus it is
possible to reason not only with the merged results but also about the fusion
process in our logics. The relationship of our extended logics with the
conditional logics of belief revision is also discussed.


title: Learning to Play Games in Extensive Form by Valuation

abstract:
  A valuation for a player in a game in extensive form is an assignment of
numeric values to the players moves. The valuation reflects the desirability
moves. We assume a myopic player, who chooses a move with the highest
valuation. Valuations can also be revised, and hopefully improved, after each
play of the game. Here, a very simple valuation revision is considered, in
which the moves made in a play are assigned the payoff obtained in the play. We
show that by adopting such a learning process a player who has a winning
strategy in a win-lose game can almost surely guarantee a win in a repeated
game. When a player has more than two payoffs, a more elaborate learning
procedure is required. We consider one that associates with each move the
average payoff in the rounds in which this move was made. When all players
adopt this learning procedure, with some perturbations, then, with probability
1, strategies that are close to subgame perfect equilibrium are played after
some time. A single player who adopts this procedure can guarantee only her
individually rational payoff.


title: A theory of experiment

abstract:
  This article aims at clarifying the language and practice of scientific
experiment, mainly by hooking observability on calculability.


title:
Model-Based Software Engineering and Ada: Synergy for the Development of
  Safety-Critical Systems

abstract:
  In this paper we outline a software development process for safety-critical
systems that aims at combining some of the specific strengths of model-based
development with those of programming language based development using
safety-critical subsets of Ada. Model-based software development and
model-based test case generation techniques are combined with code generation
techniques and tools providing a transition from model to code both for a
system itself and for its test cases. This allows developers to combine
domain-oriented, model-based techniques with source code based validation
techniques, as required for conformity with standards for the development of
safety-critical software, such as the avionics standard RTCA/DO-178B. We
introduce the AutoFocus and Validator modeling and validation toolset and
sketch its usage for modeling, test case generation, and code generation in a
combined approach, which is further illustrated by a simplified leading edge
aerospace model with built-in fault tolerance.


title:
Design of statistical quality control procedures using genetic
  algorithms

abstract:
  In general, we can not use algebraic or enumerative methods to optimize a
quality control (QC) procedure so as to detect the critical random and
systematic analytical errors with stated probabilities, while the probability
for false rejection is minimum. Genetic algorithms (GAs) offer an alternative,
as they do not require knowledge of the objective function to be optimized and
search through large parameter spaces quickly. To explore the application of
GAs in statistical QC, we have developed an interactive GAs based computer
program that designs a novel near optimal QC procedure, given an analytical
process. The program uses the deterministic crowding algorithm. An illustrative
application of the program suggests that it has the potential to design QC
procedures that are significantly better than 45 alternative ones that are used
in the clinical laboratories.


title:
Core Services in the Architecture of the National Digital Library for
  Science Education (NSDL)

abstract:
  We describe the core components of the architecture for the (NSDL) National
Science, Mathematics, Engineering, and Technology Education Digital Library.
Over time the NSDL will include heterogeneous users, content, and services. To
accommodate this, a design for a technical and organization infrastructure has
been formulated based on the notion of a spectrum of interoperability. This
paper describes the first phase of the interoperability infrastructure
including the metadata repository, search and discovery services, rights
management services, and user interface portal facilities.


title: An Empirical Model for Volatility of Returns and Option Pricing

abstract:
  In a seminal paper in 1973, Black and Scholes argued how expected
distributions of stock prices can be used to price options. Their model assumed
a directed random motion for the returns and consequently a lognormal
distribution of asset prices after a finite time. We point out two problems
with their formulation. First, we show that the option valuation is not
uniquely determined; in particular, stratergies based on the delta-hedge and
CAMP (Capital Asset Pricing Model) are shown to provide different valuations of
an option. Second, asset returns are known not to be Gaussian distributed.
Empirically, distributions of returns are seen to be much better approximated
by an exponential distribution. This exponential distribution of asset prices
can be used to develop a new pricing model for options that is shown to provide
valuations that agree very well with those used by traders. We show how the
Fokker-Planck formulation of fluctuations (i.e., the dynamics of the
distribution) can be modified to provide an exponential distribution for
returns. We also show how a singular volatility can be used to go smoothly from
exponential to Gaussian returns and thereby illustrate why exponential returns
cannot be reached perturbatively starting from Gaussian ones, and explain how
the theory of 'stochastic volatility' can be obtained from our model by making
a bad approximation. Finally, we show how to calculate put and call prices for
a stretched exponential density.


title: Components of an NSDL Architecture: Technical Scope and Functional Model

abstract:
  We describe work leading toward specification of a technical architecture for
the National Science, Mathematics, Engineering, and Technology Education
Digital Library (NSDL). This includes a technical scope and a functional model,
with some elaboration on the particularly rich set of library services that
NSDL is expected eventually to encompass.


title: Software Validation using Power Profiles

abstract:
  The validation of modern software systems incorporates both functional and
quality requirements. This paper proposes a validation approach for software
quality requirement - its power consumption. This approach validates whether
the software produces the desired results with a minimum expenditure of energy.
We present energy requirements and an approach for their validation using a
power consumption model, test-case specification, software traces, and power
measurements. Three different approaches for power data gathering are
described. The power consumption of mobile phone applications is obtained and
matched against the power consumption model.


title: The Witness Properties and the Semantics of the Prolog Cut

abstract:
  The semantics of the Prolog ``cut'' construct is explored in the context of
some desirable properties of logic programming systems, referred to as the
witness properties. The witness properties concern the operational consistency
of responses to queries. A generalization of Prolog with negation as failure
and cut is described, and shown not to have the witness properties. A
restriction of the system is then described, which preserves the choice and
first-solution behaviour of cut but allows the system to have the witness
properties.
  The notion of cut in the restricted system is more restricted than the Prolog
hard cut, but retains the useful first-solution behaviour of hard cut, not
retained by other proposed cuts such as the ``soft cut''. It is argued that the
restricted system achieves a good compromise between the power and utility of
the Prolog cut and the need for internal consistency in logic programming
systems. The restricted system is given an abstract semantics, which depends on
the witness properties; this semantics suggests that the restricted system has
a deeper connection to logic than simply permitting some computations which are
logical.
  Parts of this paper appeared previously in a different form in the
Proceedings of the 1995 International Logic Programming Symposium.


title: The Deductive Database System LDL++

abstract:
  This paper describes the LDL++ system and the research advances that have
enabled its design and development. We begin by discussing the new nonmonotonic
and nondeterministic constructs that extend the functionality of the LDL++
language, while preserving its model-theoretic and fixpoint semantics. Then, we
describe the execution model and the open architecture designed to support
these new constructs and to facilitate the integration with existing DBMSs and
applications. Finally, we describe the lessons learned by using LDL++ on
various tested applications, such as middleware and datamining.


title: A Refinement Calculus for Logic Programs

abstract:
  Existing refinement calculi provide frameworks for the stepwise development
of imperative programs from specifications. This paper presents a refinement
calculus for deriving logic programs. The calculus contains a wide-spectrum
logic programming language, including executable constructs such as sequential
conjunction, disjunction, and existential quantification, as well as
specification constructs such as general predicates, assumptions and universal
quantification. A declarative semantics is defined for this wide-spectrum
language based on executions. Executions are partial functions from states to
states, where a state is represented as a set of bindings. The semantics is
used to define the meaning of programs and specifications, including parameters
and recursion. To complete the calculus, a notion of correctness-preserving
refinement over programs in the wide-spectrum language is defined and
refinement laws for developing programs are introduced. The refinement calculus
is illustrated using example derivations and prototype tool support is
discussed.


title: Simple Optimal Wait-free Multireader Registers

abstract:
  Multireader shared registers are basic objects used as communication medium
in asynchronous concurrent computation. We propose a surprisingly simple and
natural scheme to obtain several wait-free constructions of bounded 1-writer
multireader registers from atomic 1-writer 1-reader registers, that is easier
to prove correct than any previous construction. Our main construction is the
first symmetric pure timestamp one that is optimal with respect to the
worst-case local use of control bits; the other one is optimal with respect to
global use of control bits; both are optimal in time.


title:
A Qualitative Dynamical Modelling Approach to Capital Accumulation in
  Unregulated Fisheries

abstract:
  Capital accumulation has been a major issue in fisheries economics over the
last two decades, whereby the interaction of the fish and capital stocks were
of particular interest. Because bio-economic systems are intrinsically complex,
previous efforts in this field have relied on a variety of simplifying
assumptions. The model presented here relaxes some of these simplifications.
Problems of tractability are surmounted by using the methodology of qualitative
differential equations (QDE). The theory of QDEs takes into account that
scientific knowledge about particular fisheries is usually limited, and
facilitates an analysis of the global dynamics of systems with more than two
ordinary differential equations. The model is able to trace the evolution of
capital and fish stock in good agreement with observed patterns, and shows that
over-capitalization is unavoidable in unregulated fisheries.


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.