title:
Long Nonbinary Codes Exceeding the Gilbert - Varshamov Bound for any
  Fixed Distance

abstract:
  Let A(q,n,d) denote the maximum size of a q-ary code of length n and distance
d. We study the minimum asymptotic redundancy \rho(q,n,d)=n-log_q A(q,n,d) as n
grows while q and d are fixed. For any d and q<=d-1, long algebraic codes are
designed that improve on the BCH codes and have the lowest asymptotic
redundancy \rho(q,n,d) <= ((d-3)+1/(d-2)) log_q n known to date. Prior to this
work, codes of fixed distance that asymptotically surpass BCH codes and the
Gilbert-Varshamov bound were designed only for distances 4,5 and 6.


title: Alchemistry of the P versus NP question

abstract:
  Are P and NP provably inseparable ? Take a look at some unorthodox, guilty
mentioned folklore and related unpublished results.


title: Non-Termination Inference of Logic Programs

abstract:
  We present a static analysis technique for non-termination inference of logic
programs. Our framework relies on an extension of the subsumption test, where
some specific argument positions can be instantiated while others are
generalized. We give syntactic criteria to statically identify such argument
positions from the text of a program. Atomic left looping queries are generated
bottom-up from selected subsets of the binary unfoldings of the program of
interest. We propose a set of correct algorithms for automating the approach.
Then, non-termination inference is tailored to attempt proofs of optimality of
left termination conditions computed by a termination inference tool. An
experimental evaluation is reported. When termination and non-termination
analysis produce complementary results for a logic procedure, then with respect
to the leftmost selection rule and the language used to describe sets of atomic
queries, each analysis is optimal and together, they induce a characterization
of the operational behavior of the logic procedure.


title: Business Process Measures

abstract:
  The paper proposes a new methodology for defining business process measures
and their computation. The approach is based on metamodeling according to MOF.
Especially, a metamodel providing precise definitions of typical process
measures for UML activity diagram-like notation is proposed, including precise
definitions how measures should be aggregated for composite process elements.
The proposed approach allows defining values in a natural way, and measurement
of data, which are of interest to business, without deep investigation into
specific technical solutions. This provides new possibilities for business
process measurement, decreasing the gap between technical solutions and asset
management methodologies.


title:
The Computational Complexity of Orientation Search Problems in
  Cryo-Electron Microscopy

abstract:
  In this report we study the problem of determining three-dimensional
orientations for noisy projections of randomly oriented identical particles.
The problem is of central importance in the tomographic reconstruction of the
density map of macromolecular complexes from electron microscope images and it
has been studied intensively for more than 30 years.
  We analyze the computational complexity of the orientation problem and show
that while several variants of the problem are $NP$-hard, inapproximable and
fixed-parameter intractable, some restrictions are polynomial-time approximable
within a constant factor or even solvable in logarithmic space. The orientation
search problem is formalized as a constrained line arrangement problem that is
of independent interest. The negative complexity results give a partial
justification for the heuristic methods used in orientation search, and the
positive complexity results on the orientation search have some positive
implications also to the problem of finding functionally analogous genes.
  A preliminary version ``The Computational Complexity of Orientation Search in
Cryo-Electron Microscopy'' appeared in Proc. ICCS 2004, LNCS 3036, pp.
231--238. Springer-Verlag 2004.


title: On the Computational Complexity of the Forcing Chromatic Number

abstract:
  We consider vertex colorings of graphs in which adjacent vertices have
distinct colors. A graph is $s$-chromatic if it is colorable in $s$ colors and
any coloring of it uses at least $s$ colors. The forcing chromatic number
$F(G)$ of an $s$-chromatic graph $G$ is the smallest number of vertices which
must be colored so that, with the restriction that $s$ colors are used, every
remaining vertex has its color determined uniquely. We estimate the
computational complexity of $F(G)$ relating it to the complexity class US
introduced by Blass and Gurevich. We prove that recognizing if $F(G)\le 2$ is
US-hard with respect to polynomial-time many-one reductions. Moreover, this
problem is coNP-hard even under the promises that $F(G)\le 3$ and $G$ is
3-chromatic. On the other hand, recognizing if $F(G)\le k$, for each constant
$k$, is reducible to a problem in US via disjunctive truth-table reduction.
  Similar results are obtained also for forcing variants of the clique and the
domination numbers of a graph.


title: Online Searching with Turn Cost

abstract:
  We consider the problem of searching for an object on a line at an unknown
distance OPT from the original position of the searcher, in the presence of a
cost of d for each time the searcher changes direction. This is a
generalization of the well-studied linear-search problem. We describe a
strategy that is guaranteed to find the object at a cost of at most 9*OPT + 2d,
which has the optimal competitive ratio 9 with respect to OPT plus the minimum
corresponding additive term. Our argument for upper and lower bound uses an
infinite linear program, which we solve by experimental solution of an infinite
series of approximating finite linear programs, estimating the limits, and
solving the resulting recurrences. We feel that this technique is interesting
in its own right and should help solve other searching problems. In particular,
we consider the star search or cow-path problem with turn cost, where the
hidden object is placed on one of m rays emanating from the original position
of the searcher. For this problem we give a tight bound of
(1+(2(m^m)/((m-1)^(m-1))) OPT + m ((m/(m-1))^(m-1) - 1) d. We also discuss
tradeoff between the corresponding coefficients, and briefly consider
randomized strategies on the line.


title: Cheap Recovery: A Key to Self-Managing State

abstract:
  Cluster hash tables (CHTs) are a key persistent-storage component of many
large-scale Internet services due to their high performance and scalability. We
show that a correctly-designed CHT can also be as easy to manage as a farm of
stateless servers. Specifically, we trade away some consistency to obtain
reboot-based recovery that is simple, maintains full data availability, and
only has modest impact on performance. This simplifies management in two ways.
First, it simplifies failure detection by lowering the cost of acting on false
positives, allowing us to use simple but aggressive statistical techniques to
quickly detect potential failures and node degradations; even when a false
alarm is raised or when rebooting will not fix the problem, attempting recovery
by rebooting is relatively non-intrusive to system availability and
performance. Second, it allows us to re-cast online repartitioning as failure
plus recovery, simplifying dynamic scaling and capacity planning. These
properties make it possible for the system to be continuously self-adjusting, a
key property of self-managing, autonomic systems.


title: Self-organizing neural networks in classification and image recognition

abstract:
  Self-organizing neural networks are used for brick finding in OPERA
experiment. Self-organizing neural networks and wavelet analysis used for
recognition and extraction of car numbers from images.


title: On Expanders Graphs: Parameters and Applications

abstract:
  We give a new lower bound on the expansion coefficient of an edge-vertex
graph of a $d$-regular graph. As a consequence, we obtain an improvement on the
lower bound on relative minimum distance of the expander codes constructed by
Sipser and Spielman. We also derive some improved results on the vertex
expansion of graphs that help us in improving the parameters of the expander
codes of Alon, Bruck, Naor, Naor, and Roth.


title:
A Fast, Vectorizable Algorithm for Producing Single-Precision
  Sine-Cosine Pairs

abstract:
  This paper presents an algorithm for computing Sine-Cosine pairs to modest
accuracy, but in a manner which contains no conditional tests or branching,
making it highly amenable to vectorization. An exemplary implementation for
PowerPC AltiVec processors is included, but the algorithm should be easily
portable to other achitectures, such as Intel SSE.


title: Finite-Length Scaling for Iteratively Decoded LDPC Ensembles

abstract:
  In this paper we investigate the behavior of iteratively decoded low-density
parity-check codes over the binary erasure channel in the so-called ``waterfall
region." We show that the performance curves in this region follow a very basic
scaling law. We conjecture that essentially the same scaling behavior applies
in a much more general setting and we provide some empirical evidence to
support this conjecture. The scaling law, together with the error floor
expressions developed previously, can be used for fast finite-length
optimization.


title: Stable Outcomes for Two-Sided Contract Choice Problems

abstract:
  We show, that a simple generalization of the Deferred Acceptance Procedure
with firms proposing due to Gale and Shapley(1962), yeild outcomes for a
two-sided contract choice problem, which necessarily belong to the core and are
Weakly Pareto Optimal for firms. Under additional assumptions: (a) given any
two distinct workers, the set of yields acheivable by a firm with the first
worker is disjoint from the set of yields acheivable by it with the second, and
(b) the contract choice problem is pair-wise efficient, we prove that there is
no stable outcome at which a firm can get more than what it gets at the unique
outcome of our procedure.


title: NoSEBrEaK - Attacking Honeynets

abstract:
  It is usually assumed that Honeynets are hard to detect and that attempts to
detect or disable them can be unconditionally monitored. We scrutinize this
assumption and demonstrate a method how a host in a honeynet can be completely
controlled by an attacker without any substantial logging taking place.


title:
Approximation Algorithms for Minimum PCR Primer Set Selection with
  Amplification Length and Uniqueness Constraints

abstract:
  A critical problem in the emerging high-throughput genotyping protocols is to
minimize the number of polymerase chain reaction (PCR) primers required to
amplify the single nucleotide polymorphism loci of interest. In this paper we
study PCR primer set selection with amplification length and uniqueness
constraints from both theoretical and practical perspectives. We give a greedy
algorithm that achieves a logarithmic approximation factor for the problem of
minimizing the number of primers subject to a given upperbound on the length of
PCR amplification products. We also give, using randomized rounding, the first
non-trivial approximation algorithm for a version of the problem that requires
unique amplification of each amplification target. Empirical results on
randomly generated testcases as well as testcases extracted from the from the
National Center for Biotechnology Information's genomic databases show that our
algorithms are highly scalable and produce better results compared to previous
heuristics.


title: Building a linguistic corpus from bee dance data

abstract:
  This paper discusses the problems and possibility of collecting bee dance
data in a linguistic \textit{corpus} and use linguistic instruments such as
Zipf's law and entropy statistics to decide on the question whether the dance
carries information of any kind. We describe this against the historical
background of attempts to analyse non-human communication systems.


title: Web Services: A Process Algebra Approach

abstract:
  It is now well-admitted that formal methods are helpful for many issues
raised in the Web service area. In this paper we present a framework for the
design and verification of WSs using process algebras and their tools. We
define a two-way mapping between abstract specifications written using these
calculi and executable Web services written in BPEL4WS. Several choices are
available: design and correct errors in BPEL4WS, using process algebra
verification tools, or design and correct in process algebra and automatically
obtaining the corresponding BPEL4WS code. The approaches can be combined.
Process algebra are not useful only for temporal logic verification: we remark
the use of simulation/bisimulation both for verification and for the
hierarchical refinement design method. It is worth noting that our approach
allows the use of any process algebra depending on the needs of the user at
different levels (expressiveness, existence of reasoning tools, user
expertise).


title: P=NP

abstract: We claim to resolve the P=?NP problem via a formal argument for P=NP.


title: Modelling the costs and benefits of Honeynets

abstract:
  For many IT-security measures exact costs and benefits are not known. This
makes it difficult to allocate resources optimally to different security
measures. We present a model for costs and benefits of so called Honeynets.
This can foster informed reasoning about the deployment of honeynet technology.


title: Proofs of Zero Knowledge

abstract:
  We present a protocol for verification of ``no such entry'' replies from
databases. We introduce a new cryptographic primitive as the underlying
structure, the keyed hash tree, which is an extension of Merkle's hash tree. We
compare our scheme to Buldas et al.'s Undeniable Attesters and Micali et al.'s
Zero Knowledge Sets.


title: Ermittlung von Verwundbarkeiten mit elektronischen Koedern

abstract:
  Electronic bait (honeypots) are network resources whose value consists of
being attacked and compromised. These are often computers which do not have a
task in the network, but are otherwise indestinguishable from regular
computers. Such bait systems could be interconnected (honeynets). These
honeynets are equipped with special software, facilitating forensic anylisis of
incidents. Taking average of the wide variety of recorded data it is possible
to learn considerable more about the behaviour of attackers in networks than
with traditional methods. This article is an introduction into electronic bait
and a description of the setup and first experiences of such a network deployed
at RWTH Aachen University.
  -----
  Als elektronische Koeder (honeypots) bezeichnet man Netzwerkressourcen, deren
Wert darin besteht, angegriffen und kompromittiert zu werden. Oft sind dies
Computer, die keine spezielle Aufgabe im Netzwerk haben, aber ansonsten nicht
von regulaeren Rechnern zu unterscheiden sind. Koeder koennen zu
Koeder-Netzwerken (honeynets) zusammengeschlossen werden. Sie sind mit
spezieller Software ausgestattet, die die Forensik einer eingetretenen
Schutzzielverletzung erleichtert. Durch die Vielfalt an mitgeschnittenen Daten
kann man deutlich mehr ueber das Verhalten von Angreifern in Netzwerken lernen
als mit herkoemmlichen forensischen Methoden. Dieser Beitrag stellt die
Philosophie der Koeder-Netzwerke vor und beschreibt die ersten Erfahrungen, die
mit einem solchen Netzwerk an der RWTH Aachen gemacht wurden.


title:
Well-Definedness and Semantic Type-Checking in the Nested Relational
  Calculus and XQuery

abstract:
  Two natural decision problems regarding the XML query language XQuery are
well-definedness and semantic type-checking. We study these problems in the
setting of a relational fragment of XQuery. We show that well-definedness and
semantic type-checking are undecidable, even in the positive-existential case.
Nevertheless, for a ``pure'' variant of XQuery, in which no identification is
made between an item and the singleton containing that item, the problems
become decidable. We also consider the analogous problems in the setting of the
nested relational calculus.


title: The Complexity of Agreement

abstract:
  A celebrated 1976 theorem of Aumann asserts that honest, rational Bayesian
agents with common priors will never "agree to disagree": if their opinions
about any topic are common knowledge, then those opinions must be equal.
Economists have written numerous papers examining the assumptions behind this
theorem. But two key questions went unaddressed: first, can the agents reach
agreement after a conversation of reasonable length? Second, can the
computations needed for that conversation be performed efficiently? This paper
answers both questions in the affirmative, thereby strengthening Aumann's
original conclusion.
  We first show that, for two agents with a common prior to agree within
epsilon about the expectation of a [0,1] variable with high probability over
their prior, it suffices for them to exchange order 1/epsilon^2 bits. This
bound is completely independent of the number of bits n of relevant knowledge
that the agents have. We then extend the bound to three or more agents; and we
give an example where the economists' "standard protocol" (which consists of
repeatedly announcing one's current expectation) nearly saturates the bound,
while a new "attenuated protocol" does better. Finally, we give a protocol that
would cause two Bayesians to agree within epsilon after exchanging order
1/epsilon^2 messages, and that can be simulated by agents with limited
computational resources. By this we mean that, after examining the agents'
knowledge and a transcript of their conversation, no one would be able to
distinguish the agents from perfect Bayesians. The time used by the simulation
procedure is exponential in 1/epsilon^6 but not in n.


title:
Global Grids and Software Toolkits: A Study of Four Grid Middleware
  Technologies

abstract:
  Grid is an infrastructure that involves the integrated and collaborative use
of computers, networks, databases and scientific instruments owned and managed
by multiple organizations. Grid applications often involve large amounts of
data and/or computing resources that require secure resource sharing across
organizational boundaries. This makes Grid application management and
deployment a complex undertaking. Grid middlewares provide users with seamless
computing ability and uniform access to resources in the heterogeneous Grid
environment. Several software toolkits and systems have been developed, most of
which are results of academic research projects, all over the world. This
chapter will focus on four of these middlewares--UNICORE, Globus, Legion and
Gridbus. It also presents our implementation of a resource broker for UNICORE
as this functionality was not supported in it. A comparison of these systems on
the basis of the architecture, implementation model and several other features
is included.


title: Annotating Predicate-Argument Structure for a Parallel Treebank

abstract:
  We report on a recently initiated project which aims at building a
multi-layered parallel treebank of English and German. Particular attention is
devoted to a dedicated predicate-argument layer which is used for aligning
translationally equivalent sentences of the two languages. We describe both our
conceptual decisions and aspects of their technical realisation. We discuss
some selected problems and conclude with a few remarks on how this project
relates to similar projects in the field.


title: Insertion Sort is O(n log n)

abstract:
  Traditional Insertion Sort runs in O(n^2) time because each insertion takes
O(n) time. When people run Insertion Sort in the physical world, they leave
gaps between items to accelerate insertions. Gaps help in computers as well.
This paper shows that Gapped Insertion Sort has insertion times of O(log n)
with high probability, yielding a total running time of O(n log n) with high
probability.


title: Zero-error communication over networks

abstract:
  Zero-Error communication investigates communication without any error. By
defining channels without probabilities, results from Elias can be used to
completely characterize which channel can simulate which other channels. We
introduce the ambiguity of a channel, which completely characterizes the
possibility in principle of a channel to simulate any other channel. In the
second part we will look at networks of players connected by channels, while
some players may be corrupted. We will show how the ambiguity of a virtual
channel connecting two arbitrary players can be calculated. This means that we
can exactly specify what kind of zero-error communication is possible between
two players in any network of players connected by channels.


title: Statistical Machine Translation by Generalized Parsing

abstract:
  Designers of statistical machine translation (SMT) systems have begun to
employ tree-structured translation models. Systems involving tree-structured
translation models tend to be complex. This article aims to reduce the
conceptual complexity of such systems, in order to make them easier to design,
implement, debug, use, study, understand, explain, modify, and improve. In
service of this goal, the article extends the theory of semiring parsing to
arrive at a novel abstract parsing algorithm with five functional parameters: a
logic, a grammar, a semiring, a search strategy, and a termination condition.
The article then shows that all the common algorithms that revolve around
tree-structured translation models, including hierarchical alignment, inference
for parameter estimation, translation, and structured evaluation, can be
derived by generalizing two of these parameters -- the grammar and the logic.
The article culminates with a recipe for using such generalized parsers to
train, apply, and evaluate an SMT system that is driven by tree-structured
translation models.


title: Predicate Abstraction with Indexed Predicates

abstract:
  Predicate abstraction provides a powerful tool for verifying properties of
infinite-state systems using a combination of a decision procedure for a subset
of first-order logic and symbolic methods originally developed for finite-state
model checking. We consider models containing first-order state variables,
where the system state includes mutable functions and predicates. Such a model
can describe systems containing arbitrarily large memories, buffers, and arrays
of identical processes. We describe a form of predicate abstraction that
constructs a formula over a set of universally quantified variables to describe
invariant properties of the first-order state variables. We provide a formal
justification of the soundness of our approach and describe how it has been
used to verify several hardware and software designs, including a
directory-based cache coherence protocol.


title: The semijoin algebra and the guarded fragment

abstract:
  The semijoin algebra is the variant of the relational algebra obtained by
replacing the join operator by the semijoin operator. We discuss some
interesting connections between the semijoin algebra and the guarded fragment
of first-order logic. We also provide an Ehrenfeucht-Fraisse game,
characterizing the discerning power of the semijoin algebra. This game gives a
method for showing that certain queries are not expressible in the semijoin
algebra.


title:
Autogenic Training With Natural Language Processing Modules: A Recent
  Tool For Certain Neuro Cognitive Studies

abstract:
  Learning to respond to voice-text input involves the subject's ability in
understanding the phonetic and text based contents and his/her ability to
communicate based on his/her experience. The neuro-cognitive facility of the
subject has to support two important domains in order to make the learning
process complete. In many cases, though the understanding is complete, the
response is partial. This is one valid reason why we need to support the
information from the subject with scalable techniques such as Natural Language
Processing (NLP) for abstraction of the contents from the output. This paper
explores the feasibility of using NLP modules interlaced with Neural Networks
to perform the required task in autogenic training related to medical
applications.


title:
Search Using N-gram Technique Based Statistical Analysis for Knowledge
  Extraction in Case Based Reasoning Systems

abstract:
  Searching techniques for Case Based Reasoning systems involve extensive
methods of elimination. In this paper, we look at a new method of arriving at
the right solution by performing a series of transformations upon the data.
These involve N-gram based comparison and deduction of the input data with the
case data, using Morphemes and Phonemes as the deciding parameters. A similar
technique for eliminating possible errors using a noise removal function is
performed. The error tracking and elimination is performed through a
statistical analysis of obtained data, where the entire data set is analyzed as
sub-categories of various etymological derivatives. A probability analysis for
the closest match is then performed, which yields the final expression. This
final expression is referred to the Case Base. The output is redirected through
an Expert System based on best possible match. The threshold for the match is
customizable, and could be set by the Knowledge-Architect.


title:
Improved error bounds for the erasure/list scheme: the binary and
  spherical cases

abstract:
  We derive improved bounds on the error and erasure rate for spherical codes
and for binary linear codes under Forney's erasure/list decoding scheme and
prove some related results.


title:
Distance distribution of binary codes and the error probability of
  decoding

abstract:
  We address the problem of bounding below the probability of error under
maximum likelihood decoding of a binary code with a known distance distribution
used on a binary symmetric channel. An improved upper bound is given for the
maximum attainable exponent of this probability (the reliability function of
the channel). In particular, we prove that the ``random coding exponent'' is
the true value of the channel reliability for code rate $R$ in some interval
immediately below the critical rate of the channel. An analogous result is
obtained for the Gaussian channel.


title:
A Taxonomy and Survey of Grid Resource Planning and Reservation Systems
  for Grid Enabled Analysis Environment

abstract:
  The concept of coupling geographically distributed resources for solving
large scale problems is becoming increasingly popular forming what is popularly
called grid computing. Management of resources in the Grid environment becomes
complex as the resources are geographically distributed, heterogeneous in
nature and owned by different individuals and organizations each having their
own resource management policies and different access and cost models. There
have been many projects that have designed and implemented the resource
management systems with a variety of architectures and services. In this paper
we have presented the general requirements that a Resource Management system
should satisfy. The taxonomy has also been defined based on which survey of
resource management systems in different existing Grid projects has been
conducted to identify the key areas where these systems lack the desired
functionality.


title:
Distributed Analysis and Load Balancing System for Grid Enabled Analysis
  on Hand-held devices using Multi-Agents Systems

abstract:
  Handheld devices, while growing rapidly, are inherently constrained and lack
the capability of executing resource hungry applications. This paper presents
the design and implementation of distributed analysis and load-balancing system
for hand-held devices using multi-agents system. This system enables low
resource mobile handheld devices to act as potential clients for Grid enabled
applications and analysis environments. We propose a system, in which mobile
agents will transport, schedule, execute and return results for heavy
computational jobs submitted by handheld devices. Moreover, in this way, our
system provides high throughput computing environment for hand-held devices.


title:
A Grid-enabled Interface to Condor for Interactive Analysis on Handheld
  and Resource-limited Devices

abstract: This paper was withdrawn by the authors.


title: Resource Bounded Immunity and Simplicity

abstract:
  Revisiting the thirty years-old notions of resource-bounded immunity and
simplicity, we investigate the structural characteristics of various immunity
notions: strong immunity, almost immunity, and hyperimmunity as well as their
corresponding simplicity notions. We also study limited immunity and
simplicity, called k-immunity and feasible k-immunity, and their simplicity
notions. Finally, we propose the k-immune hypothesis as a working hypothesis
that guarantees the existence of simple sets in NP.


title: Learning for Adaptive Real-time Search

abstract:
  Real-time heuristic search is a popular model of acting and learning in
intelligent autonomous agents. Learning real-time search agents improve their
performance over time by acquiring and refining a value function guiding the
application of their actions. As computing the perfect value function is
typically intractable, a heuristic approximation is acquired instead. Most
studies of learning in real-time search (and reinforcement learning) assume
that a simple value-function-greedy policy is used to select actions. This is
in contrast to practice, where high-performance is usually attained by
interleaving planning and acting via a lookahead search of a non-trivial depth.
In this paper, we take a step toward bridging this gap and propose a novel
algorithm that (i) learns a heuristic function to be used specifically with a
lookahead-based policy, (ii) selects the lookahead depth adaptively in each
state, (iii) gives the user control over the trade-off between exploration and
exploitation. We extensively evaluate the algorithm in the sliding tile puzzle
testbed comparing it to the classical LRTA* and the more recent weighted LRTA*,
bounded LRTA*, and FALCONS. Improvements of 5 to 30 folds in convergence speed
are observed.


title:
A Low Cost Distributed Computing Approach to Pulsar Searches at a Small
  College

abstract:
  We describe a distributed processing cluster of inexpensive Linux machines
developed jointly by the Astronomy and Computer Science departments at
Haverford College which has been successfully used to search a large volume of
data from a recent radio pulsar survey. Analysis of radio pulsar surveys
requires significant computational resources to handle the demanding data
storage and processing needs. One goal of this project was to explore issues
encountered when processing a large amount of pulsar survey data with limited
computational resources. This cluster, which was developed and activated in
only a few weeks by supervised undergraduate summer research students, used
existing decommissioned computers, the campus network, and a script-based,
client-oriented, self-scheduled data distribution approach to process the data.
This setup provided simplicity, efficiency, and "on-the-fly" scalability at low
cost. The entire 570 GB data set from the pulsar survey was processed at
Haverford over the course of a ten-week summer period using this cluster. We
conclude that this cluster can serve as a useful computational model in cases
where data processing must be carried out on a limited budget. We have also
constructed a DVD archive of the raw survey data in order to investigate the
feasibility of using DVD as an inexpensive and easily accessible raw data
storage format for pulsar surveys. DVD-based storage has not been widely
explored in the pulsar community, but it has several advantages. The DVD
archive we have constructed is reliable, portable, inexpensive, and can be
easily read by any standard modern machine.


title:
An algorithm for two-dimensional mesh generation based on the pinwheel
  tiling

abstract:
  We propose a new two-dimensional meshing algorithm called PINW able to
generate meshes that accurately approximate the distance between any two domain
points by paths composed only of cell edges. This technique is based on an
extension of pinwheel tilings proposed by Radin and Conway. We prove that the
algorithm produces triangles of bounded aspect ratio. This kind of mesh would
be useful in cohesive interface finite element modeling when the crack
propagation pathis an outcome of a simulation process.


title: Stochastic fuzzy controller

abstract:
  A standard approach to building a fuzzy controller based on stochastic logic
uses binary random signals with an average (expected value of a random
variable) in the range [0, 1]. A different approach is presented, founded on a
representation of the membership functions with the probability density
functions.


title: Minimum Enclosing Polytope in High Dimensions

abstract:
  We study the problem of covering a given set of $n$ points in a high,
$d$-dimensional space by the minimum enclosing polytope of a given arbitrary
shape. We present algorithms that work for a large family of shapes, provided
either only translations and no rotations are allowed, or only rotation about a
fixed point is allowed; that is, one is allowed to only scale and translate a
given shape, or scale and rotate the shape around a fixed point. Our algorithms
start with a polytope guessed to be of optimal size and iteratively moves it
based on a greedy principle: simply move the current polytope directly towards
any outside point till it touches the surface. For computing the minimum
enclosing ball, this gives a simple greedy algorithm with running time
$O(nd/\eps)$ producing a ball of radius $1+\eps$ times the optimal. This simple
principle generalizes to arbitrary convex shape when only translations are
allowed, requiring at most $O(1/\eps^2)$ iterations. Our algorithm implies that
{\em core-sets} of size $O(1/\eps^2)$ exist not only for minimum enclosing ball
but also for any convex shape with a fixed orientation. A {\em Core-Set} is a
small subset of $poly(1/\eps)$ points whose minimum enclosing polytope is
almost as large as that of the original points. Although we are unable to
combine our techniques for translations and rotations for general shapes, for
the min-cylinder problem, we give an algorithm similar to the one in
\cite{HV03}, but with an improved running time of $2^{O(\frac{1}{\eps^2}\log
\frac{1}{\eps})} nd$.


title:
Multi-agent coordination using nearest neighbor rules: revisiting the
  Vicsek model

abstract:
  Recently, Jadbabaie, Lin, and Morse (IEEE TAC, 48(6)2003:988-1001) offered a
mathematical analysis of the discrete time model of groups of mobile autonomous
agents raised by Vicsek et al. in 1995. In their paper, Jadbabaie et al. showed
that all agents shall move in the same heading, provided that these agents are
periodically linked together. This paper sharpens this result by showing that
coordination will be reached under a very weak condition that requires all
agents are finally linked together. This condition is also strictly weaker than
the one Jadbabaie et al. desired.


title:
Solving Elliptic Finite Element Systems in Near-Linear Time with Support
  Preconditioners

abstract:
  We consider linear systems arising from the use of the finite element method
for solving scalar linear elliptic problems. Our main result is that these
linear systems, which are symmetric and positive semidefinite, are well
approximated by symmetric diagonally dominant matrices. Our framework for
defining matrix approximation is support theory. Significant graph theoretic
work has already been developed in the support framework for preconditioners in
the diagonally dominant case, and in particular it is known that such systems
can be solved with iterative methods in nearly linear time. Thus, our
approximation result implies that these graph theoretic techniques can also
solve a class of finite element problems in nearly linear time. We show that
the support number bounds, which control the number of iterations in the
preconditioned iterative solver, depend on mesh quality measures but not on the
problem size or shape of the domain.


title: Efficient Hashing with Lookups in two Memory Accesses

abstract:
  The study of hashing is closely related to the analysis of balls and bins. It
is well-known that instead of using a single hash function if we randomly hash
a ball into two bins and place it in the smaller of the two, then this
dramatically lowers the maximum load on bins. This leads to the concept of
two-way hashing where the largest bucket contains $O(\log\log n)$ balls with
high probability. The hash look up will now search in both the buckets an item
hashes to. Since an item may be placed in one of two buckets, we could
potentially move an item after it has been initially placed to reduce maximum
load. with a maximum load of We show that by performing moves during inserts, a
maximum load of 2 can be maintained on-line, with high probability, while
supporting hash update operations. In fact, with $n$ buckets, even if the space
for two items are pre-allocated per bucket, as may be desirable in hardware
implementations, more than $n$ items can be stored giving a high memory
utilization. We also analyze the trade-off between the number of moves
performed during inserts and the maximum load on a bucket. By performing at
most $h$ moves, we can maintain a maximum load of $O(\frac{\log \log n}{h
\log(\log\log n/h)})$. So, even by performing one move, we achieve a better
bound than by performing no moves at all.


title: An agent-based intelligent environmental monitoring system

abstract:
  Fairly rapid environmental changes call for continuous surveillance and
on-line decision making. There are two main areas where IT technologies can be
valuable. In this paper we present a multi-agent system for monitoring and
assessing air-quality attributes, which uses data coming from a meteorological
station. A community of software agents is assigned to monitor and validate
measurements coming from several sensors, to assess air-quality, and, finally,
to fire alarms to appropriate recipients, when needed. Data mining techniques
have been used for adding data-driven, customized intelligence into agents. The
architecture of the developed system, its domain ontology, and typical agent
interactions are presented. Finally, the deployment of a real-world test case
is demonstrated.


title: An agent framework for dynamic agent retraining: Agent academy

abstract:
  Agent Academy (AA) aims to develop a multi-agent society that can train new
agents for specific or general tasks, while constantly retraining existing
agents in a recursive mode. The system is based on collecting information both
from the environment and the behaviors of the acting agents and their related
successes/failures to generate a body of data, stored in the Agent Use
Repository, which is mined by the Data Miner module, in order to generate
useful knowledge about the application domain. Knowledge extracted by the Data
Miner is used by the Agent Training Module as to train new agents or to enhance
the behavior of agents already running. In this paper the Agent Academy
framework is introduced, and its overall architecture and functionality are
presented. Training issues as well as agent ontologies are discussed. Finally,
a scenario, which aims to provide environmental alerts to both individuals and
public authorities, is described an AA-based use case.


title: Summarizing Encyclopedic Term Descriptions on the Web

abstract:
  We are developing an automatic method to compile an encyclopedic corpus from
the Web. In our previous work, paragraph-style descriptions for a term are
extracted from Web pages and organized based on domains. However, these
descriptions are independent and do not comprise a condensed text as in
hand-crafted encyclopedias. To resolve this problem, we propose a summarization
method, which produces a single text from multiple descriptions. The resultant
summary concisely describes a term from different viewpoints. We also show the
effectiveness of our method by means of experiments.


title: Unsupervised Topic Adaptation for Lecture Speech Retrieval

abstract:
  We are developing a cross-media information retrieval system, in which users
can view specific segments of lecture videos by submitting text queries. To
produce a text index, the audio track is extracted from a lecture video and a
transcription is generated by automatic speech recognition. In this paper, to
improve the quality of our retrieval system, we extensively investigate the
effects of adapting acoustic and language models on speech recognition. We
perform an MLLR-based method to adapt an acoustic model. To obtain a corpus for
language model adaptation, we use the textbook for a target lecture to search a
Web collection for the pages associated with the lecture topic. We show the
effectiveness of our method by means of experiments.


title: Effects of Language Modeling on Speech-driven Question Answering

abstract:
  We integrate automatic speech recognition (ASR) and question answering (QA)
to realize a speech-driven QA system, and evaluate its performance. We adapt an
N-gram language model to natural language questions, so that the input of our
system can be recognized with a high accuracy. We target WH-questions which
consist of the topic part and fixed phrase used to ask about something. We
first produce a general N-gram model intended to recognize the topic and
emphasize the counts of the N-grams that correspond to the fixed phrases. Given
a transcription by the ASR engine, the QA engine extracts the answer candidates
from target documents. We propose a passage retrieval method robust against
recognition errors in the transcription. We use the QA test collection produced
in NTCIR, which is a TREC-style evaluation workshop, and show the effectiveness
of our method by means of experiments.


title: Static versus Dynamic Arbitrage Bounds on Multivariate Option Prices

abstract:
  We compare static arbitrage price bounds on basket calls, i.e. bounds that
only involve buy-and-hold trading strategies, with the price range obtained
within a multi-variate generalization of the Black-Scholes model. While there
is no gap between these two sets of prices in the univariate case, we observe
here that contrary to our intuition about model risk for at-the-money calls,
there is a somewhat large gap between model prices and static arbitrage prices,
hence a similarly large set of prices on which a multivariate Black-Scholes
model cannot be calibrated but where no conclusion can be drawn on the presence
or not of a static arbitrage opportunity.


title: Scheduling with Fuzzy Methods

abstract:
  Nowadays, manufacturing industries -- driven by fierce competition and rising
customer requirements -- are forced to produce a broader range of individual
products of rising quality at the same (or preferably lower) cost. Meeting
these demands implies an even more complex production process and thus also an
appropriately increasing request to its scheduling. Aggravatingly, vagueness of
scheduling parameters -- such as times and conditions -- are often inherent in
the production process. In addition, the search for an optimal schedule
normally leads to very difficult problems (NP-hard problems in the complexity
theoretical sense), which cannot be solved effciently. With the intent to
minimize these problems, the introduced heuristic method combines standard
scheduling methods with fuzzy methods to get a nearly optimal schedule within
an appropriate time considering vagueness adequately.


title: On Modal Logics of Partial Recursive Functions

abstract:
  The classical propositional logic is known to be sound and complete with
respect to the set semantics that interprets connectives as set operations. The
paper extends propositional language by a new binary modality that corresponds
to partial recursive function type constructor under the above interpretation.
The cases of deterministic and non-deterministic functions are considered and
for both of them semantically complete modal logics are described and
decidability of these logics is established.


title:
Exposing Software Defined Radio Functionality To Native Operating System
  Applications via Virtual Devices

abstract:
  Many reconfigurable platforms require that applications be written
specifically to take advantage of the reconfigurable hardware. In a PC-based
environment, this presents an undesirable constraint in that the many already
available applications cannot leverage on such hardware. Greatest benefit can
only be derived from reconfigurable devices if even native OS applications can
transparently utilize reconfigurable devices as they would normal full-fledged
hardware devices. This paper presents how Proteus Virtual Devices are used to
expose reconfigurable hardware in a transparent manner for use by typical
native OS applications.


title: Track Layouts of Graphs

abstract:
  A \emph{$(k,t)$-track layout} of a graph $G$ consists of a (proper) vertex
$t$-colouring of $G$, a total order of each vertex colour class, and a
(non-proper) edge $k$-colouring such that between each pair of colour classes
no two monochromatic edges cross. This structure has recently arisen in the
study of three-dimensional graph drawings. This paper presents the beginnings
of a theory of track layouts. First we determine the maximum number of edges in
a $(k,t)$-track layout, and show how to colour the edges given fixed linear
orderings of the vertex colour classes. We then describe methods for the
manipulation of track layouts. For example, we show how to decrease the number
of edge colours in a track layout at the expense of increasing the number of
tracks, and vice versa. We then study the relationship between track layouts
and other models of graph layout, namely stack and queue layouts, and geometric
thickness. One of our principle results is that the queue-number and
track-number of a graph are tied, in the sense that one is bounded by a
function of the other. As corollaries we prove that acyclic chromatic number is
bounded by both queue-number and stack-number. Finally we consider track
layouts of planar graphs. While it is an open problem whether planar graphs
have bounded track-number, we prove bounds on the track-number of outerplanar
graphs, and give the best known lower bound on the track-number of planar
graphs.


title: On the Complexity of Case-Based Planning

abstract:
  We analyze the computational complexity of problems related to case-based
planning: planning when a plan for a similar instance is known, and planning
from a library of plans. We prove that planning from a single case has the same
complexity than generative planning (i.e., planning "from scratch"); using an
extended definition of cases, complexity is reduced if the domain stored in the
case is similar to the one to search plans for. Planning from a library of
cases is shown to have the same complexity. In both cases, the complexity of
planning remains, in the worst case, PSPACE-complete.


title: A Framework for High-Accuracy Privacy-Preserving Mining

abstract:
  To preserve client privacy in the data mining process, a variety of
techniques based on random perturbation of data records have been proposed
recently. In this paper, we present a generalized matrix-theoretic model of
random perturbation, which facilitates a systematic approach to the design of
perturbation mechanisms for privacy-preserving mining. Specifically, we
demonstrate that (a) the prior techniques differ only in their settings for the
model parameters, and (b) through appropriate choice of parameter settings, we
can derive new perturbation techniques that provide highly accurate mining
results even under strict privacy guarantees. We also propose a novel
perturbation mechanism wherein the model parameters are themselves
characterized as random variables, and demonstrate that this feature provides
significant improvements in privacy at a very marginal cost in accuracy.
  While our model is valid for random-perturbation-based privacy-preserving
mining in general, we specifically evaluate its utility here with regard to
frequent-itemset mining on a variety of real datasets. The experimental results
indicate that our mechanisms incur substantially lower identity and support
errors as compared to the prior techniques.


title: All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs

abstract:
  We describe algorithms, based on Avis and Fukuda's reverse search paradigm,
for listing all maximal independent sets in a sparse graph in polynomial time
and delay per output. For bounded degree graphs, our algorithms take constant
time per set generated; for minor-closed graph families, the time is O(n) per
set, and for more general sparse graph families we achieve subquadratic time
per set. We also describe new data structures for maintaining a dynamic vertex
set S in a sparse or minor-closed graph family, and querying the number of
vertices not dominated by S; for minor-closed graph families the time per
update is constant, while it is sublinear for any sparse graph family. We can
also maintain a dynamic vertex set in an arbitrary m-edge graph and test the
independence of the maintained set in time O(sqrt m) per update. We use the
domination data structures as part of our enumeration algorithms.


title: Generalized Evolutionary Algorithm based on Tsallis Statistics

abstract:
  Generalized evolutionary algorithm based on Tsallis canonical distribution is
proposed. The algorithm uses Tsallis generalized canonical distribution to
weigh the configurations for `selection' instead of Gibbs-Boltzmann
distribution. Our simulation results show that for an appropriate choice of
non-extensive index that is offered by Tsallis statistics, evolutionary
algorithms based on this generalization outperform algorithms based on
Gibbs-Boltzmann distribution.


title: Model Checking of Statechart Models: Survey and Research Directions

abstract:
  We survey existing approaches to the formal verification of statecharts using
model checking. Although the semantics and subset of statecharts used in each
approach varies considerably, along with the model checkers and their
specification languages, most approaches rely on translating the hierarchical
structure into the flat representation of the input language of the model
checker. This makes model checking difficult to scale to industrial models, as
the state space grows exponentially with flattening. We look at current
approaches to model checking hierarchical structures and find that their
semantics is significantly different from statecharts. We propose to address
the problem of state space explosion using a combination of techniques, which
are proposed as directions for further research.


title: On the Convergence Speed of MDL Predictions for Bernoulli Sequences

abstract:
  We consider the Minimum Description Length principle for online sequence
prediction. If the underlying model class is discrete, then the total expected
square loss is a particularly interesting performance measure: (a) this
quantity is bounded, implying convergence with probability one, and (b) it
additionally specifies a `rate of convergence'. Generally, for MDL only
exponential loss bounds hold, as opposed to the linear bounds for a Bayes
mixture. We show that this is even the case if the model class contains only
Bernoulli distributions. We derive a new upper bound on the prediction error
for countable Bernoulli classes. This implies a small bound (comparable to the
one for Bayes mixtures) for certain important model classes. The results apply
to many Machine Learning tasks including classification and hypothesis testing.
We provide arguments that our theorems generalize to countable classes of
i.i.d. models.


title: Decomposition Based Search - A theoretical and experimental evaluation

abstract:
  In this paper we present and evaluate a search strategy called Decomposition
Based Search (DBS) which is based on two steps: subproblem generation and
subproblem solution. The generation of subproblems is done through value
ranking and domain splitting. Subdomains are explored so as to generate,
according to the heuristic chosen, promising subproblems first.
  We show that two well known search strategies, Limited Discrepancy Search
(LDS) and Iterative Broadening (IB), can be seen as special cases of DBS. First
we present a tuning of DBS that visits the same search nodes as IB, but avoids
restarts. Then we compare both theoretically and computationally DBS and LDS
using the same heuristic. We prove that DBS has a higher probability of being
successful than LDS on a comparable number of nodes, under realistic
assumptions. Experiments on a constraint satisfaction problem and an
optimization problem show that DBS is indeed very effective if compared to LDS.


title: Exploiting Semidefinite Relaxations in Constraint Programming

abstract:
  Constraint programming uses enumeration and search tree pruning to solve
combinatorial optimization problems. In order to speed up this solution
process, we investigate the use of semidefinite relaxations within constraint
programming. In principle, we use the solution of a semidefinite relaxation to
guide the traversal of the search tree, using a limited discrepancy search
strategy. Furthermore, a semidefinite relaxation produces a bound for the
solution value, which is used to prune parts of the search tree. Experimental
results on stable set and maximum clique problem instances show that constraint
programming can indeed greatly benefit from semidefinite relaxations.


title: Postponing Branching Decisions

abstract:
  Solution techniques for Constraint Satisfaction and Optimisation Problems
often make use of backtrack search methods, exploiting variable and value
ordering heuristics. In this paper, we propose and analyse a very simple method
to apply in case the value ordering heuristic produces ties: postponing the
branching decision. To this end, we group together values in a tie, branch on
this sub-domain, and defer the decision among them to lower levels of the
search tree. We show theoretically and experimentally that this simple
modification can dramatically improve the efficiency of the search strategy.
Although in practise similar methods may have been applied already, to our
knowledge, no empirical or theoretical study has been proposed in the
literature to identify when and to what extent this strategy should be used.


title: A Hyper-Arc Consistency Algorithm for the Soft Alldifferent Constraint

abstract:
  This paper presents an algorithm that achieves hyper-arc consistency for the
soft alldifferent constraint. To this end, we prove and exploit the equivalence
with a minimum-cost flow problem. Consistency of the constraint can be checked
in O(nm) time, and hyper-arc consistency is achieved in O(m) time, where n is
the number of variables involved and m is the sum of the cardinalities of the
domains. It improves a previous method that did not ensure hyper-arc
consistency.


title: Reduced cost-based ranking for generating promising subproblems

abstract:
  In this paper, we propose an effective search procedure that interleaves two
steps: subproblem generation and subproblem solution. We mainly focus on the
first part. It consists of a variable domain value ranking based on reduced
costs. Exploiting the ranking, we generate, in a Limited Discrepancy Search
tree, the most promising subproblems first. An interesting result is that
reduced costs provide a very precise ranking that allows to almost always find
the optimal solution in the first generated subproblem, even if its dimension
is significantly smaller than that of the original problem. Concerning the
proof of optimality, we exploit a way to increase the lower bound for
subproblems at higher discrepancies. We show experimental results on the TSP
and its time constrained variant to show the effectiveness of the proposed
approach, but the technique could be generalized for other problems.


title: The First-Order Theory of Sets with Cardinality Constraints is Decidable

abstract:
  We show that the decidability of the first-order theory of the language that
combines Boolean algebras of sets of uninterpreted elements with Presburger
arithmetic operations. We thereby disprove a recent conjecture that this theory
is undecidable. Our language allows relating the cardinalities of sets to the
values of integer variables, and can distinguish finite and infinite sets. We
use quantifier elimination to show the decidability and obtain an elementary
upper bound on the complexity.
  Precise program analyses can use our decidability result to verify
representation invariants of data structures that use an integer field to
represent the number of stored elements.


title: A Bimachine Compiler for Ranked Tagging Rules

abstract:
  This paper describes a novel method of compiling ranked tagging rules into a
deterministic finite-state device called a bimachine. The rules are formulated
in the framework of regular rewrite operations and allow unrestricted regular
expressions in both left and right rule contexts. The compiler is illustrated
by an application within a speech synthesis system.


title: Channel-Independent and Sensor-Independent Stimulus Representations

abstract:
  This paper shows how a machine, which observes stimuli through an
uncharacterized, uncalibrated channel and sensor, can glean machine-independent
information (i.e., channel- and sensor-independent information) about the
stimuli. First, we demonstrate that a machine defines a specific coordinate
system on the stimulus state space, with the nature of that coordinate system
depending on the device's channel and sensor. Thus, machines with different
channels and sensors "see" the same stimulus trajectory through state space,
but in different machine-specific coordinate systems. For a large variety of
physical stimuli, statistical properties of that trajectory endow the stimulus
configuration space with differential geometric structure (a metric and
parallel transfer procedure), which can then be used to represent relative
stimulus configurations in a coordinate-system-independent manner (and,
therefore, in a channel- and sensor-independent manner). The resulting
description is an "inner" property of the stimulus time series in the sense
that it does not depend on extrinsic factors like the observer's choice of a
coordinate system in which the stimulus is viewed (i.e., the observer's choice
of channel and sensor). This methodology is illustrated with analytic examples
and with a numerically simulated experiment. In an intelligent sensory device,
this kind of representation "engine" could function as a "front-end" that
passes channel/sensor-independent stimulus representations to a pattern
recognition module. After a pattern recognizer has been trained in one of these
devices, it could be used without change in other devices having different
channels and sensors.


title: Technological networks and the spread of computer viruses

abstract:
  Computer infections such as viruses and worms spread over networks of
contacts between computers, with different types of networks being exploited by
different types of infections. Here we analyze the structures of several of
these networks, exploring their implications for modes of spread and the
control of infection. We argue that vaccination strategies that focus on a
limited number of network nodes, whether targeted or randomly chosen, are in
many cases unlikely to be effective. An alternative dynamic mechanism for the
control of contagion, called throttling, is introduced and argued to be
effective under a range of conditions.


title: Preferred Answer Sets for Ordered Logic Programs

abstract:
  We extend answer set semantics to deal with inconsistent programs (containing
classical negation), by finding a ``best'' answer set. Within the context of
inconsistent programs, it is natural to have a partial order on rules,
representing a preference for satisfying certain rules, possibly at the cost of
violating less important ones. We show that such a rule order induces a natural
order on extended answer sets, the minimal elements of which we call preferred
answer sets. We characterize the expressiveness of the resulting semantics and
show that it can simulate negation as failure, disjunction and some other
formalisms such as logic programs with ordered disjunction. The approach is
shown to be useful in several application areas, e.g. repairing database, where
minimal repairs correspond to preferred answer sets.
  To appear in Theory and Practice of Logic Programming (TPLP).


title: Modeling and Validating Hybrid Systems Using VDM and Mathematica

abstract:
  Hybrid systems are characterized by the hybrid evolution of their state: A
part of the state changes discretely, the other part changes continuously over
time. Typically, modern control applications belong to this class of systems,
where a digital controller interacts with a physical environment. In this
article we illustrate how a combination of the formal method VDM and the
computer algebra system Mathematica can be used to model and simulate both
aspects: the control logic and the physics involved. A new Mathematica package
emulating VDM-SL has been developed that allows the integration of differential
equation systems into formal specifications. The SAFER example from Kelly
(1997) serves to demonstrate the new simulation capabilities Mathematica adds:
After the thruster selection process, the astronaut's actual position and
velocity is calculated by numerically solving Euler's and Newton's equations
for rotation and translation. Furthermore, interactive validation is supported
by a graphical user interface and data animation.


title: Bug shallowness in open-source, Macintosh software

abstract:
  Central to the power of open-source software is bug shallowness, the relative
ease of finding and fixing bugs. The open-source movement began with Unix
software, so many users were also programmers capable of finding and fixing
bugs given the source code. But as the open-source movement reaches the
Macintosh platform, bugs may not be shallow because few Macintosh users are
programmers. Based on reports from open-source developers, I, however, conclude
that that bugs are as shallow in open-source, Macintosh software as in any
other open-source software.


title:
M@th Desktop and MD Tools - Mathematics and Mathematica Made Easy for
  Students

abstract:
  We present two add-ons for Mathematica for teaching mathematics to
undergraduate and high school students. These two applications, M@th Desktop
(MD) and M@th Desktop Tools (MDTools), include several palettes and notebooks
covering almost every field. The underlying didactic concept is so-called
"blended learning", in which these tools are meant to be used as a complement
to the professor or teacher rather than as a replacement, which other
e-learning applications do. They enable students to avoid the usual problem of
computer-based learning, namely that too large an amount of time is wasted
struggling with computer and program errors instead of actually learning the
mathematical concepts.
  M@th Desktop Tools is palette-based and provides easily accessible and
user-friendly templates for the most important functions in the fields of
Analysis, Algebra, Linear Algebra and Statistics. M@th Desktop, in contrast, is
a modern, interactive teaching and learning software package for mathematics
classes. It is comprised of modules for Differentiation, Integration, and
Statistics, and each module presents its topic with a combination of
interactive notebooks and palettes.
  Both packages can be obtained from Deltasoft's homepage at
http://www.deltasoft.at/ .


title: Design of a Parallel and Distributed Web Search Engine

abstract:
  This paper describes the architecture of MOSE (My Own Search Engine), a
scalable parallel and distributed engine for searching the web. MOSE was
specifically designed to efficiently exploit affordable parallel architectures,
such as clusters of workstations. Its modular and scalable architecture can
easily be tuned to fulfill the bandwidth requirements of the application at
hand. Both task-parallel and data-parallel approaches are exploited within MOSE
in order to increase the throughput and efficiently use communication, storing
and computational resources. We used a collection of html documents as a
benchmark, and conducted preliminary experiments on a cluster of three SMP
Linux PCs.


title: From truth to computability I

abstract:
  The recently initiated approach called computability logic is a formal theory
of interactive computation. See a comprehensive online source on the subject at
http://www.cis.upenn.edu/~giorgi/cl.html . The present paper contains a
soundness and completeness proof for the deductive system CL3 which axiomatizes
the most basic first-order fragment of computability logic called the
finite-depth, elementary-base fragment. Among the potential application areas
for this result are the theory of interactive computation, constructive applied
theories, knowledgebase systems, systems for resource-bound planning and
action. This paper is self-contained as it reintroduces all relevant
definitions as well as main motivations.


title: PELCR: Parallel Environment for Optimal Lambda-Calculus Reduction

abstract:
  In this article we present the implementation of an environment supporting
L\'evy's \emph{optimal reduction} for the $\lambda$-calculus \cite{Lev78} on
parallel (or distributed) computing systems. In a similar approach to Lamping's
one in \cite{Lamping90}, we base our work on a graph reduction technique known
as \emph{directed virtual reduction} \cite{DPR97} which is actually a
restriction of Danos-Regnier virtual reduction \cite{DanosRegnier93}.
  The environment, which we refer to as PELCR (Parallel Environment for optimal
Lambda-Calculus Reduction) relies on a strategy for directed virtual reduction,
namely {\em half combustion}, which we introduce in this article. While
developing PELCR we have adopted both a message aggregation technique, allowing
a reduction of the communication overhead, and a fair policy for distributing
dynamically originated load among processors.
  We also present an experimental study demonstrating the ability of PELCR to
definitely exploit parallelism intrinsic to $\lambda$-terms while performing
the reduction. By the results we show how PELCR allows achieving up to 70/80%
of the ideal speedup on last generation multiprocessor computing systems. As a
last note, the software modules have been developed with the {\tt C} language
and using a standard interface for message passing, i.e. MPI, thus making PELCR
itself a highly portable software package.


title: On the hardness of distinguishing mixed-state quantum computations

abstract:
  This paper considers the following problem. Two mixed-state quantum circuits
Q and R are given, and the goal is to determine which of two possibilities
holds: (i) Q and R act nearly identically on all possible quantum state inputs,
or (ii) there exists some input state that Q and R transform into almost
perfectly distinguishable outputs. This problem may be viewed as an abstraction
of the following problem: given two physical processes described by sequences
of local interactions, are the processes effectively the same or are they
different? We prove that this problem is a complete promise problem for the
class QIP of problems having quantum interactive proof systems, and is
therefore PSPACE-hard. This is in sharp contrast to the fact that the analogous
problem for classical (probabilistic) circuits is in AM, and for unitary
quantum circuits is in QMA.


title: Universal Convergence of Semimeasures on Individual Random Sequences

abstract:
  Solomonoff's central result on induction is that the posterior of a universal
semimeasure M converges rapidly and with probability 1 to the true sequence
generating posterior mu, if the latter is computable. Hence, M is eligible as a
universal sequence predictor in case of unknown mu. Despite some nearby results
and proofs in the literature, the stronger result of convergence for all
(Martin-Loef) random sequences remained open. Such a convergence result would
be particularly interesting and natural, since randomness can be defined in
terms of M itself. We show that there are universal semimeasures M which do not
converge for all random sequences, i.e. we give a partial negative answer to
the open problem. We also provide a positive answer for some non-universal
semimeasures. We define the incomputable measure D as a mixture over all
computable measures and the enumerable semimeasure W as a mixture over all
enumerable nearly-measures. We show that W converges to D and D to mu on all
random sequences. The Hellinger distance measuring closeness of two
distributions plays a central role.


title: Communication-Aware Processor Allocation for Supercomputers

abstract:
  This paper gives processor-allocation algorithms for minimizing the average
number of communication hops between the assigned processors for grid
architectures, in the presence of occupied cells. The simpler problem of
assigning processors on a free grid has been studied by Karp, McKellar, and
Wong who show that the solutions have nontrivial structure; they left open the
complexity of the problem.
  The associated clustering problem is as follows: Given n points in Re^d, find
k points that minimize their average pairwise L1 distance. We present a natural
approximation algorithm and show that it is a 7/4-approximation for 2D grids.
For d-dimensional space, the approximation guarantee is 2-(1/2d), which is
tight. We also give a polynomial-time approximation scheme (PTAS) for constant
dimension d, and report on experimental results.


title: On rational definite summation

abstract:
  We present a partial proof of van Hoeij-Abramov conjecture about the
algorithmic possibility of computation of finite sums of rational functions.
The theoretical results proved in this paper provide an algorithm for
computation of a large class of sums $ S(n) = \sum_{k=0}^{n-1}R(k,n)$.


title: Tight bounds for LDPC and LDGM codes under MAP decoding

abstract:
  A new method for analyzing low density parity check (LDPC) codes and low
density generator matrix (LDGM) codes under bit maximum a posteriori
probability (MAP) decoding is introduced. The method is based on a rigorous
approach to spin glasses developed by Francesco Guerra. It allows to construct
lower bounds on the entropy of the transmitted message conditional to the
received one. Based on heuristic statistical mechanics calculations, we
conjecture such bounds to be tight. The result holds for standard irregular
ensembles when used over binary input output symmetric channels. The method is
first developed for Tanner graph ensembles with Poisson left degree
distribution. It is then generalized to `multi-Poisson' graphs, and, by a
completion procedure, to arbitrary degree distribution.


title: A measure of similarity between graph vertices

abstract:
  We introduce a concept of similarity between vertices of directed graphs. Let
G_A and G_B be two directed graphs. We define a similarity matrix whose (i,
j)-th real entry expresses how similar vertex j (in G_A) is to vertex i (in
G_B. The similarity matrix can be obtained as the limit of the normalized even
iterates of a linear transformation. In the special case where G_A=G_B=G, the
matrix is square and the (i, j)-th entry is the similarity score between the
vertices i and j of G. We point out that Kleinberg's "hub and authority" method
to identify web-pages relevant to a given query can be viewed as a special case
of our definition in the case where one of the graphs has two vertices and a
unique directed edge between them. In analogy to Kleinberg, we show that our
similarity scores are given by the components of a dominant eigenvector of a
non-negative matrix. Potential applications of our similarity concept are
numerous. We illustrate an application for the automatic extraction of synonyms
in a monolingual dictionary.

categories: cs.IR cond-mat.dis-nn cs.DM physics.data-an


title:
Performance Analysis of the Globus Toolkit Monitoring and Discovery
  Service, MDS2

abstract:
  Monitoring and information services form a key component of a distributed
system, or Grid. A quantitative study of such services can aid in understanding
the performance limitations, advise in the deployment of the monitoring system,
and help evaluate future development work. To this end, we examined the
performance of the Globus Toolkit(reg. trdmrk) Monitoring and Discovery Service
(MDS2) by instrumenting its main services using NetLogger. Our study shows a
strong advantage to caching or prefetching the data, as well as the need to
have primary components at well-connected sites.


title: Unfolding Smooth Prismatoids

abstract:
  We define a notion for unfolding smooth, ruled surfaces, and prove that every
smooth prismatoid (the convex hull of two smooth curves lying in parallel
planes), has a nonoverlapping "volcano unfolding." These unfoldings keep the
base intact, unfold the sides outward, splayed around the base, and attach the
top to the tip of some side rib. Our result answers a question for smooth
prismatoids whose analog for polyhedral prismatoids remains unsolved.


title: A Sequent Calculus and a Theorem Prover for Standard Conditional Logics

abstract:
  In this paper we present a cut-free sequent calculus, called SeqS, for some
standard conditional logics, namely CK, CK+ID, CK+MP and CK+MP+ID. The calculus
uses labels and transition formulas and can be used to prove decidability and
space complexity bounds for the respective logics. We also present CondLean, a
theorem prover for these logics implementing SeqS calculi written in SICStus
Prolog.


title:
Word Sense Disambiguation by Web Mining for Word Co-occurrence
  Probabilities

abstract:
  This paper describes the National Research Council (NRC) Word Sense
Disambiguation (WSD) system, as applied to the English Lexical Sample (ELS)
task in Senseval-3. The NRC system approaches WSD as a classical supervised
machine learning problem, using familiar tools such as the Weka machine
learning software and Brill's rule-based part-of-speech tagger. Head words are
represented as feature vectors with several hundred features. Approximately
half of the features are syntactic and the other half are semantic. The main
novelty in the system is the method for generating the semantic features, based
on word \hbox{co-occurrence} probabilities. The probabilities are estimated
using the Waterloo MultiText System with a corpus of about one terabyte of
unlabeled text, collected by a web crawler.


title: ParFORM: Parallel Version of the Symbolic Manipulation Program FORM

abstract:
  After an introduction to the sequential version of FORM and the mechanisms
behind, we report on the status of our project of parallelization. We have now
a parallel version of FORM running on Cluster- and SMP-architectures. This
version can be used to run arbitrary FORM programs in parallel.


title:
Semantic Linking - a Context-Based Approach to Interactivity in
  Hypermedia

abstract:
  The semantic Web initiates new, high level access schemes to online content
and applications. One area of superior need for a redefined content exploration
is given by on-line educational applications and their concepts of
interactivity in the framework of open hypermedia systems. In the present paper
we discuss aspects and opportunities of gaining interactivity schemes from
semantic notions of components. A transition from standard educational
annotation to semantic statements of hyperlinks is discussed. Further on we
introduce the concept of semantic link contexts as an approach to manage a
coherent rhetoric of linking. A practical implementation is introduced, as
well. Our semantic hyperlink implementation is based on the more general
Multimedia Information Repository MIR, an open hypermedia system supporting the
standards XML, Corba and JNDI.


title: Roaming Real-Time Applications - Mobility Services in IPv6 Networks

abstract:
  Emerging mobility standards within the next generation Internet Protocol,
IPv6, promise to continuously operate devices roaming between IP networks.
Associated with the paradigm of ubiquitous computing and communication, network
technology is on the spot to deliver voice and videoconferencing as a standard
internet solution. However, current roaming procedures are too slow, to remain
seamless for real-time applications. Multicast mobility still waits for a
convincing design. This paper investigates the temporal behaviour of mobile
IPv6 with dedicated focus on topological impacts. Extending the hierarchical
mobile IPv6 approach we suggest protocol improvements for a continuous
handover, which may serve bidirectional multicast communication, as well. Along
this line a multicast mobility concept is introduced as a service for clients
and sources, as they are of dedicated importance in multipoint conferencing
applications. The mechanisms introduced do not rely on assumptions of any
specific multicast routing protocol in use.


title: Multi-Embedding of Metric Spaces

abstract:
  Metric embedding has become a common technique in the design of algorithms.
Its applicability is often dependent on how high the embedding's distortion is.
For example, embedding finite metric space into trees may require linear
distortion as a function of its size. Using probabilistic metric embeddings,
the bound on the distortion reduces to logarithmic in the size.
  We make a step in the direction of bypassing the lower bound on the
distortion in terms of the size of the metric. We define "multi-embeddings" of
metric spaces in which a point is mapped onto a set of points, while keeping
the target metric of polynomial size and preserving the distortion of paths.
The distortion obtained with such multi-embeddings into ultrametrics is at most
O(log Delta loglog Delta) where Delta is the aspect ratio of the metric. In
particular, for expander graphs, we are able to obtain constant distortion
embeddings into trees in contrast with the Omega(log n) lower bound for all
previous notions of embeddings.
  We demonstrate the algorithmic application of the new embeddings for two
optimization problems: group Steiner tree and metrical task systems.


title:
Hypermedia Learning Objects System - On the Way to a Semantic
  Educational Web

abstract:
  While eLearning systems become more and more popular in daily education,
available applications lack opportunities to structure, annotate and manage
their contents in a high-level fashion. General efforts to improve these
deficits are taken by initiatives to define rich meta data sets and a
semanticWeb layer. In the present paper we introduce Hylos, an online learning
system. Hylos is based on a cellular eLearning Object (ELO) information model
encapsulating meta data conforming to the LOM standard. Content management is
provisioned on this semantic meta data level and allows for variable,
dynamically adaptable access structures. Context aware multifunctional links
permit a systematic navigation depending on the learners and didactic needs,
thereby exploring the capabilities of the semantic web. Hylos is built upon the
more general Multimedia Information Repository (MIR) and the MIR adaptive
context linking environment (MIRaCLE), its linking extension. MIR is an open
system supporting the standards XML, Corba and JNDI. Hylos benefits from
manageable information structures, sophisticated access logic and high-level
authoring tools like the ELO editor responsible for the semi-manual creation of
meta data and WYSIWYG like content editing.


title: Educational Content Management - A Cellular Approach

abstract:
  In recent times online educational applications more and more are requested
to provide self-consistent learning offers for students at the university
level. Consequently they need to cope with the wide range of complexity and
interrelations university course teaching brings along. An urgent need to
overcome simplistically linked HTMLc ontent pages becomes apparent. In the
present paper we discuss a schematic concept of educational content
construction from information cells and introduce its implementation on the
storage and runtime layer. Starting from cells content is annotated according
to didactic needs, structured for dynamic arrangement, dynamically decorated
with hyperlinks and, as all works are based on XML, open to any presentation
layer. Data can be variably accessed through URIs built on semantic path-names
and edited via an adaptive authoring toolbox. Our content management approach
is based on the more general Multimedia Information Repository MIR. and allows
for personalisation, as well. MIR is an open system supporting the standards
XML, Corba and JNDI.


title: Why Two Sexes?

abstract:
  Evolutionary role of the separation into two sexes from a cyberneticist's
point of view. [I translated this 1965 article from Russian "Nauka i Zhizn"
(Science and Life) in 1988. In a popular form, the article puts forward several
useful ideas not all of which even today are necessarily well known or widely
accepted. Boris Lubachevsky, bdl@bell-labs.com ]


title:
Online convex optimization in the bandit setting: gradient descent
  without a gradient

abstract:
  We consider a the general online convex optimization framework introduced by
Zinkevich. In this setting, there is a sequence of convex functions. Each
period, we must choose a signle point (from some feasible set) and pay a cost
equal to the value of the next function on our chosen point. Zinkevich shows
that, if the each function is revealed after the choice is made, then one can
achieve vanishingly small regret relative the best single decision chosen in
hindsight.
  We extend this to the bandit setting where we do not find out the entire
functions but rather just their value at our chosen point. We show how to get
vanishingly small regret in this setting.
  Our approach uses a simple approximation of the gradient that is computed
from evaluating a function at a single (random) point. We show that this
estimate is sufficient to mimic Zinkevich's gradient descent online analysis,
with access to the gradient (only being able to evaluate the function at a
single point).


title: Iterative Quantization Using Codes On Graphs

abstract:
  We study codes on graphs combined with an iterative message passing algorithm
for quantization. Specifically, we consider the binary erasure quantization
(BEQ) problem which is the dual of the binary erasure channel (BEC) coding
problem. We show that duals of capacity achieving codes for the BEC yield codes
which approach the minimum possible rate for the BEQ. In contrast, low density
parity check codes cannot achieve the minimum rate unless their density grows
at least logarithmically with block length. Furthermore, we show that duals of
efficient iterative decoding algorithms for the BEC yield efficient encoding
algorithms for the BEQ. Hence our results suggest that graphical models may
yield near optimal codes in source coding as well as in channel coding and that
duality plays a key role in such constructions.


title:
Performance Analysis of Multicast Mobility in a Hierarchical Mobile IP
  Proxy Environment

abstract:
  Mobility support in IPv6 networks is ready for release as an RFC, stimulating
major discussions on improvements to meet real-time communication requirements.
Sprawling hot spots of IP-only wireless networks at the same time await voice
and videoconferencing as standard mobile Internet services, thereby adding the
request for multicast support to real-time mobility. This paper briefly
introduces current approaches for seamless multicast extensions to Mobile IPv6.
Key issues of multicast mobility are discussed. Both analytically and in
simulations comparisons are drawn between handover performance characteristics,
dedicating special focus on the M-HMIPv6 approach.


title: A Simple Proportional Conflict Redistribution Rule

abstract:
  One proposes a first alternative rule of combination to WAO (Weighted Average
Operator) proposed recently by Josang, Daniel and Vannoorenberghe, called
Proportional Conflict Redistribution rule (denoted PCR1). PCR1 and WAO are
particular cases of WO (the Weighted Operator) because the conflicting mass is
redistributed with respect to some weighting factors. In this first PCR rule,
the proportionalization is done for each non-empty set with respect to the
non-zero sum of its corresponding mass matrix - instead of its mass column
average as in WAO, but the results are the same as Ph. Smets has pointed out.
Also, we extend WAO (which herein gives no solution) for the degenerate case
when all column sums of all non-empty sets are zero, and then the conflicting
mass is transferred to the non-empty disjunctive form of all non-empty sets
together; but if this disjunctive form happens to be empty, then one considers
an open world (i.e. the frame of discernment might contain new hypotheses) and
thus all conflicting mass is transferred to the empty set. In addition to WAO,
we propose a general formula for PCR1 (WAO for non-degenerate cases).


title: The asymptotic number of binary codes and binary matroids

abstract:
  The asyptotic number of nonequivalent binary n-codes is determined. This is
also the asymptotic number of nonisomorphic binary n-matroids. The connection
to a result of Lefmann, Roedl, Phelps is explored. The latter states that
almost all binary n-codes have a trivial automorphism group.


title:
Three-Dimensional Face Orientation and Gaze Detection from a Single
  Image

abstract:
  Gaze detection and head orientation are an important part of many advanced
human-machine interaction applications. Many systems have been proposed for
gaze detection. Typically, they require some form of user cooperation and
calibration. Additionally, they may require multiple cameras and/or restricted
head positions. We present a new approach for inference of both face
orientation and gaze direction from a single image with no restrictions on the
head position. Our algorithm is based on a face and eye model, deduced from
anthropometric data. This approach allows us to use a single camera and
requires no cooperation from the user. Using a single image avoids the
complexities associated with of a multi-camera system. Evaluation tests show
that our system is accurate, fast and can be used in a variety of applications,
including ones where the user is unaware of the system.


title: Roles Are Really Great!

abstract:
  We present a new role system for specifying changing referencing
relationships of heap objects. The role of an object depends, in large part, on
its aliasing relationships with other objects, with the role of each object
changing as its aliasing relationships change. Roles therefore capture
important object and data structure properties and provide useful information
about how the actions of the program interact with these properties. Our role
system enables the programmer to specify the legal aliasing relationships that
define the set of roles that objects may play, the roles of procedure
parameters and object fields, and the role changes that procedures perform
while manipulating objects. We present an interprocedural, compositional, and
context-sensitive role analysis algorithm that verifies that a program respects
the role constraints.


title: Typestate Checking and Regular Graph Constraints

abstract:
  We introduce regular graph constraints and explore their decidability
properties. The motivation for regular graph constraints is 1) type checking of
changing types of objects in the presence of linked data structures, 2) shape
analysis techniques, and 3) generalization of similar constraints over trees
and grids. We define a subclass of graphs called heaps as an abstraction of the
data structures that a program constructs during its execution. We prove that
determining the validity of implication for regular graph constraints over the
class of heaps is undecidable. We show undecidability by exhibiting a
characterization of certain "corresponder graphs" in terms of presence and
absence of homomorphisms to a finite number of fixed graphs. The undecidability
of implication of regular graph constraints implies that there is no algorithm
that will verify that procedure preconditions are met or that the invariants
are maintained when these properties are expressed in any specification
language at least as expressive as regular graph constraints.


title: On the Theory of Structural Subtyping

abstract:
  We show that the first-order theory of structural subtyping of non-recursive
types is decidable. Let $\Sigma$ be a language consisting of function symbols
(representing type constructors) and $C$ a decidable structure in the
relational language $L$ containing a binary relation $\leq$. $C$ represents
primitive types; $\leq$ represents a subtype ordering. We introduce the notion
of $\Sigma$-term-power of $C$, which generalizes the structure arising in
structural subtyping. The domain of the $\Sigma$-term-power of $C$ is the set
of $\Sigma$-terms over the set of elements of $C$. We show that the
decidability of the first-order theory of $C$ implies the decidability of the
first-order theory of the $\Sigma$-term-power of $C$. Our decision procedure
makes use of quantifier elimination for term algebras and Feferman-Vaught
theorem. Our result implies the decidability of the first-order theory of
structural subtyping of non-recursive types.


title: Lock-Free and Practical Deques using Single-Word Compare-And-Swap

abstract:
  We present an efficient and practical lock-free implementation of a
concurrent deque that is disjoint-parallel accessible and uses atomic
primitives which are available in modern computer systems. Previously known
lock-free algorithms of deques are either based on non-available atomic
synchronization primitives, only implement a subset of the functionality, or
are not designed for disjoint accesses. Our algorithm is based on a doubly
linked list, and only requires single-word compare-and-swap atomic primitives,
even for dynamic memory sizes. We have performed an empirical study using full
implementations of the most efficient algorithms of lock-free deques known. For
systems with low concurrency, the algorithm by Michael shows the best
performance. However, as our algorithm is designed for disjoint accesses, it
performs significantly better on systems with high concurrency and non-uniform
memory architecture.


title: Improved Upper Bound for the Redundancy of Fix-Free Codes

abstract:
  A variable-length code is a fix-free code if no codeword is a prefix or a
suffix of any other codeword. In a fix-free code any finite sequence of
codewords can be decoded in both directions, which can improve the robustness
to channel noise and speed up the decoding process. In this paper we prove a
new sufficient condition of the existence of fix-free codes and improve the
upper bound on the redundancy of optimal fix-free codes.


title: On Role Logic

abstract:
  We present role logic, a notation for describing properties of relational
structures in shape analysis, databases, and knowledge bases. We construct role
logic using the ideas of de Bruijn's notation for lambda calculus, an encoding
of first-order logic in lambda calculus, and a simple rule for implicit
arguments of unary and binary predicates. The unrestricted version of role
logic has the expressive power of first-order logic with transitive closure.
Using a syntactic restriction on role logic formulas, we identify a natural
fragment RL^2 of role logic. We show that the RL^2 fragment has the same
expressive power as two-variable logic with counting C^2 and is therefore
decidable. We present a translation of an imperative language into the
decidable fragment RL^2, which allows compositional verification of programs
that manipulate relational structures. In addition, we show how RL^2 encodes
boolean shape analysis constraints and an expressive description logic.


title: On Generalized Records and Spatial Conjunction in Role Logic

abstract:
  We have previously introduced role logic as a notation for describing
properties of relational structures in shape analysis, databases and knowledge
bases. A natural fragment of role logic corresponds to two-variable logic with
counting and is therefore decidable. We show how to use role logic to describe
open and closed records, as well the dual of records, inverse records. We
observe that the spatial conjunction operation of separation logic naturally
models record concatenation. Moreover, we show how to eliminate the spatial
conjunction of formulas of quantifier depth one in first-order logic with
counting. As a result, allowing spatial conjunction of formulas of quantifier
depth one preserves the decidability of two-variable logic with counting. This
result applies to two-variable role logic fragment as well. The resulting logic
smoothly integrates type system and predicate calculus notation and can be
viewed as a natural generalization of the notation for constraints arising in
role analysis and similar shape analysis approaches.


title: Collaborative Storage Management In Sensor Networks

abstract:
  In this paper, we consider a class of sensor networks where the data is not
required in real-time by an observer; for example, a sensor network monitoring
a scientific phenomenon for later play back and analysis. In such networks, the
data must be stored in the network. Thus, in addition to battery power, storage
is a primary resource: the useful lifetime of the network is constrained by its
ability to store the generated data samples. We explore the use of
collaborative storage technique to efficiently manage data in storage
constrained sensor networks. The proposed collaborative storage technique takes
advantage of spatial correlation among the data collected by nearby sensors to
significantly reduce the size of the data near the data sources. We show that
the proposed approach provides significant savings in the size of the stored
data vs. local buffering, allowing the network to run for a longer time without
running out of storage space and reducing the amount of data that will
eventually be relayed to the observer. In addition, collaborative storage
performs load balancing of the available storage space if data generation rates
are not uniform across sensors (as would be the case in an event driven sensor
network), or if the available storage varies across the network.


title:
An Algorithm for Quasi-Associative and Quasi-Markovian Rules of
  Combination in Information Fusion

abstract:
  In this paper one proposes a simple algorithm of combining the fusion rules,
those rules which first use the conjunctive rule and then the transfer of
conflicting mass to the non-empty sets, in such a way that they gain the
property of associativity and fulfill the Markovian requirement for dynamic
fusion. Also, a new rule, SDL-improved, is presented.


title: Diagnosabilities of regular networks

abstract:
  In this paper, we study diagnosabilities of multiprocessor systems under two
diagnosis models: the PMC model and the comparison model. In each model, we
further consider two different diagnosis strategies: the precise diagnosis
strategy proposed by Preparata et al. and the pessimistic diagnosis strategy
proposed by Friedman. The main result of this paper is to determine
diagnosabilities of regular networks with certain conditions, which include
several widely used multiprocessor systems such as variants of hypercubes and
many others.


title: On Global Warming (Softening Global Constraints)

abstract:
  We describe soft versions of the global cardinality constraint and the
regular constraint, with efficient filtering algorithms maintaining domain
consistency. For both constraints, the softening is achieved by augmenting the
underlying graph. The softened constraints can be used to extend the
meta-constraint framework for over-constrained problems proposed by Petit,
Regin and Bessiere.


title: Non-uniform Information Dissemination for Sensor Networks

abstract:
  Future smart environments will be characterized by multiple nodes that sense,
collect, and disseminate information about environmental phenomena through a
wireless network. In this paper, we define a set of applications that require a
new form of distributed knowledge about the environment, referred to as
non-uniform information granularity. By non-uniform information granularity we
mean that the required accuracy or precision of information is proportional to
the distance between a source node (information producer) and current sink node
(information consumer). That is, as the distance between the source node and
sink node increases, loss in information precision is acceptable. Applications
that can benefit from this type of knowledge range from battlefield scenarios
to rescue operations. The main objectives of this paper are two-fold: first, we
will precisely define non-uniform information granularity, and second, we will
describe different protocols that achieve non-uniform information dissemination
and analyze these protocols based on complexity, energy consumption, and
accuracy of information.


title: Optimizing compilation of constraint handling rules in HAL

abstract:
  In this paper we discuss the optimizing compilation of Constraint Handling
Rules (CHRs). CHRs are a multi-headed committed choice constraint language,
commonly applied for writing incremental constraint solvers. CHRs are usually
implemented as a language extension that compiles to the underlying language.
In this paper we show how we can use different kinds of information in the
compilation of CHRs in order to obtain access efficiency, and a better
translation of the CHR rules into the underlying language, which in this case
is HAL. The kinds of information used include the types, modes, determinism,
functional dependencies and symmetries of the CHR constraints. We also show how
to analyze CHR programs to determine this information about functional
dependencies, symmetries and other kinds of information supporting
optimizations.


title:
Incremental Construction of Minimal Acyclic Sequential Transducers from
  Unsorted Data

abstract:
  This paper presents an efficient algorithm for the incremental construction
of a minimal acyclic sequential transducer (ST) for a dictionary consisting of
a list of input and output strings. The algorithm generalises a known method of
constructing minimal finite-state automata (Daciuk et al. 2000). Unlike the
algorithm published by Mihov and Maurel (2001), it does not require the input
strings to be sorted. The new method is illustrated by an application to
pronunciation dictionaries.