title: Answering Subcognitive Turing Test Questions: A Reply to French

abstract:
  Robert French has argued that a disembodied computer is incapable of passing
a Turing Test that includes subcognitive questions. Subcognitive questions are
designed to probe the network of cultural and perceptual associations that
humans naturally develop as we live, embodied and embedded in the world. In
this paper, I show how it is possible for a disembodied computer to answer
subcognitive questions appropriately, contrary to French's claim. My approach
to answering subcognitive questions is to use statistical information extracted
from a very large collection of text. In particular, I show how it is possible
to answer a sample of subcognitive questions taken from French, by issuing
queries to a search engine that indexes about 350 million Web pages. This
simple algorithm may shed light on the nature of human (sub-) cognition, but
the scope of this paper is limited to demonstrating that French is mistaken: a
disembodied computer can answer subcognitive questions.


title:
Complexity of the Exact Domatic Number Problem and of the Exact Conveyor
  Flow Shop Problem

abstract:
  We prove that the exact versions of the domatic number problem are complete
for the levels of the boolean hierarchy over NP. The domatic number problem,
which arises in the area of computer networks, is the problem of partitioning a
given graph into a maximum number of disjoint dominating sets. This number is
called the domatic number of the graph. We prove that the problem of
determining whether or not the domatic number of a given graph is {\em exactly}
one of k given values is complete for the 2k-th level of the boolean hierarchy
over NP. In particular, for k = 1, it is DP-complete to determine whether or
not the domatic number of a given graph equals exactly a given integer. Note
that DP is the second level of the boolean hierarchy over NP. We obtain similar
results for the exact versions of generalized dominating set problems and of
the conveyor flow shop problem. Our reductions apply Wagner's conditions
sufficient to prove hardness for the levels of the boolean hierarchy over NP.


title: Classes of Spatiotemporal Objects and Their Closure Properties

abstract:
  We present a data model for spatio-temporal databases. In this model
spatio-temporal data is represented as a finite union of objects described by
means of a spatial reference object, a temporal object and a geometric
transformation function that determines the change or movement of the reference
object in time.
  We define a number of practically relevant classes of spatio-temporal
objects, and give complete results concerning closure under Boolean set
operators for these classes. Since only few classes are closed under all set
operators, we suggest an extension of the model, which leads to better closure
properties, and therefore increased practical applicability. We also discuss a
normal form for this extended data model.


title:
Real numbers having ultimately periodic representations in abstract
  numeration systems

abstract:
  Using a genealogically ordered infinite regular language, we know how to
represent an interval of R. Numbers having an ultimately periodic
representation play a special role in classical numeration systems. The aim of
this paper is to characterize the numbers having an ultimately periodic
representation in generalized systems built on a regular language. The
syntactical properties of these words are also investigated. Finally, we show
the equivalence of the classical "theta"-expansions with our generalized
representations in some special case related to a Pisot number "theta".


title: Thinking, Learning, and Autonomous Problem Solving

abstract:
  Ever increasing computational power will require methods for automatic
programming. We present an alternative to genetic programming, based on a
general model of thinking and learning. The advantage is that evolution takes
place in the space of constructs and can thus exploit the mathematical
structures of this space. The model is formalized, and a macro language is
presented which allows for a formal yet intuitive description of the problem
under consideration. A prototype has been developed to implement the scheme in
PERL. This method will lead to a concentration on the analysis of problems, to
a more rapid prototyping, to the treatment of new problem classes, and to the
investigation of philosophical problems. We see fields of application in
nonlinear differential equations, pattern recognition, robotics, model
building, and animated pictures.


title: Learning Algorithms for Keyphrase Extraction

abstract:
  Many academic journals ask their authors to provide a list of about five to
fifteen keywords, to appear on the first page of each article. Since these key
words are often phrases of two or more words, we prefer to call them
keyphrases. There is a wide variety of tasks for which keyphrases are useful,
as we discuss in this paper. We approach the problem of automatically
extracting keyphrases from text as a supervised learning task. We treat a
document as a set of phrases, which the learning algorithm must learn to
classify as positive or negative examples of keyphrases. Our first set of
experiments applies the C4.5 decision tree induction algorithm to this learning
task. We evaluate the performance of nine different configurations of C4.5. The
second set of experiments applies the GenEx algorithm to the task. We developed
the GenEx algorithm specifically for automatically extracting keyphrases from
text. The experimental results support the claim that a custom-designed
algorithm (GenEx), incorporating specialized procedural domain knowledge, can
generate better keyphrases than a generalpurpose algorithm (C4.5). Subjective
human evaluation of the keyphrases generated by Extractor suggests that about
80% of the keyphrases are acceptable to human readers. This level of
performance should be satisfactory for a wide variety of applications.


title:
A Simple Model of Unbounded Evolutionary Versatility as a Largest-Scale
  Trend in Organismal Evolution

abstract:
  The idea that there are any large-scale trends in the evolution of biological
organisms is highly controversial. It is commonly believed, for example, that
there is a large-scale trend in evolution towards increasing complexity, but
empirical and theoretical arguments undermine this belief. Natural selection
results in organisms that are well adapted to their local environments, but it
is not clear how local adaptation can produce a global trend. In this paper, I
present a simple computational model, in which local adaptation to a randomly
changing environment results in a global trend towards increasing evolutionary
versatility. In this model, for evolutionary versatility to increase without
bound, the environment must be highly dynamic. The model also shows that
unbounded evolutionary versatility implies an accelerating evolutionary pace. I
believe that unbounded increase in evolutionary versatility is a large-scale
trend in evolution. I discuss some of the testable predictions about organismal
evolution that are suggested by the model.


title: Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments

abstract:
  We develop and analyze algorithms for dispersing a swarm of primitive robots
in an unknown environment, R. The primary objective is to minimize the
makespan, that is, the time to fill the entire region. An environment is
composed of pixels that form a connected subset of the integer grid.
  There is at most one robot per pixel and robots move horizontally or
vertically at unit speed. Robots enter R by means of k>=1 door pixels
  Robots are primitive finite automata, only having local communication, local
sensors, and a constant-sized memory.
  We first give algorithms for the single-door case (i.e., k=1), analyzing the
algorithms both theoretically and experimentally. We prove that our algorithms
have optimal makespan 2A-1, where A is the area of R.
  We next give an algorithm for the multi-door case (k>1), based on a
wall-following version of the leader-follower strategy. We prove that our
strategy is O(log(k+1))-competitive, and that this bound is tight for our
strategy and other related strategies.


title: How to Shift Bias: Lessons from the Baldwin Effect

abstract:
  An inductive learning algorithm takes a set of data as input and generates a
hypothesis as output. A set of data is typically consistent with an infinite
number of hypotheses; therefore, there must be factors other than the data that
determine the output of the learning algorithm. In machine learning, these
other factors are called the bias of the learner. Classical learning algorithms
have a fixed bias, implicit in their design. Recently developed learning
algorithms dynamically adjust their bias as they search for a hypothesis.
Algorithms that shift bias in this manner are not as well understood as
classical algorithms. In this paper, we show that the Baldwin effect has
implications for the design and analysis of bias shifting algorithms. The
Baldwin effect was proposed in 1896, to explain how phenomena that might appear
to require Lamarckian evolution (inheritance of acquired characteristics) can
arise from purely Darwinian evolution. Hinton and Nowlan presented a
computational model of the Baldwin effect in 1987. We explore a variation on
their model, which we constructed explicitly to illustrate the lessons that the
Baldwin effect has for research in bias shifting algorithms. The main lesson is
that it appears that a good strategy for shift of bias in a learning algorithm
is to begin with a weak bias and gradually shift to a strong bias.


title: Unsupervised Language Acquisition: Theory and Practice

abstract:
  In this thesis I present various algorithms for the unsupervised machine
learning of aspects of natural languages using a variety of statistical models.
The scientific object of the work is to examine the validity of the so-called
Argument from the Poverty of the Stimulus advanced in favour of the proposition
that humans have language-specific innate knowledge. I start by examining an a
priori argument based on Gold's theorem, that purports to prove that natural
languages cannot be learned, and some formal issues related to the choice of
statistical grammars rather than symbolic grammars. I present three novel
algorithms for learning various parts of natural languages: first, an algorithm
for the induction of syntactic categories from unlabelled text using
distributional information, that can deal with ambiguous and rare words;
secondly, a set of algorithms for learning morphological processes in a variety
of languages, including languages such as Arabic with non-concatenative
morphology; thirdly an algorithm for the unsupervised induction of a
context-free grammar from tagged text. I carefully examine the interaction
between the various components, and show how these algorithms can form the
basis for a empiricist model of language acquisition. I therefore conclude that
the Argument from the Poverty of the Stimulus is unsupported by the evidence.


title: Searching for Plannable Domains can Speed up Reinforcement Learning

abstract:
  Reinforcement learning (RL) involves sequential decision making in uncertain
environments. The aim of the decision-making agent is to maximize the benefit
of acting in its environment over an extended period of time. Finding an
optimal policy in RL may be very slow. To speed up learning, one often used
solution is the integration of planning, for example, Sutton's Dyna algorithm,
or various other methods using macro-actions.
  Here we suggest to separate plannable, i.e., close to deterministic parts of
the world, and focus planning efforts in this domain. A novel reinforcement
learning method called plannable RL (pRL) is proposed here. pRL builds a simple
model, which is used to search for macro actions. The simplicity of the model
makes planning computationally inexpensive. It is shown that pRL finds an
optimal policy, and that plannable macro actions found by pRL are near-optimal.
In turn, it is unnecessary to try large numbers of macro actions, which enables
fast learning. The utility of pRL is demonstrated by computer simulations.


title: A Generalization of the Lifting Lemma for Logic Programming

abstract:
  Since the seminal work of J. A. Robinson on resolution, many lifting lemmas
for simplifying proofs of completeness of resolution have been proposed in the
literature. In the logic programming framework, they may also help to detect
some infinite derivations while proving goals under the SLD-resolution. In this
paper, we first generalize a version of the lifting lemma, by extending the
relation "is more general than" so that it takes into account only some
arguments of the atoms. The other arguments, which we call neutral arguments,
are disregarded. Then we propose two syntactic conditions of increasing power
for identifying neutral arguments from mere inspection of the text of a logic
program.


title: Qualitative Study of a Robot Arm as a Hamiltonian System

abstract:
  A double pendulum subject to external torques is used as a model to study the
stability of a planar manipulator with two links and two rotational driven
joints. The hamiltonian equations of motion and the fixed points (stationary
solutions) in phase space are determined. Under suitable conditions, the
presence of constant torques does not change the number of fixed points, and
preserves the topology of orbits in their linear neighborhoods; two equivalent
invariant manifolds are observed, each corresponding to a saddle-center fixed
point.


title: Technical Note: Bias and the Quantification of Stability

abstract:
  Research on bias in machine learning algorithms has generally been concerned
with the impact of bias on predictive accuracy. We believe that there are other
factors that should also play a role in the evaluation of bias. One such factor
is the stability of the algorithm; in other words, the repeatability of the
results. If we obtain two sets of data from the same phenomenon, with the same
underlying probability distribution, then we would like our learning algorithm
to induce approximately the same concepts from both sets of data. This paper
introduces a method for quantifying stability, based on a measure of the
agreement between concepts. We also discuss the relationships among stability,
predictive accuracy, and bias.


title: A Theory of Cross-Validation Error

abstract:
  This paper presents a theory of error in cross-validation testing of
algorithms for predicting real-valued attributes. The theory justifies the
claim that predicting real-valued attributes requires balancing the conflicting
demands of simplicity and accuracy. Furthermore, the theory indicates precisely
how these conflicting demands must be balanced, in order to minimize
cross-validation error. A general theory is presented, then it is developed in
detail for linear regression and instance-based learning.


title:
Theoretical Analyses of Cross-Validation Error and Voting in
  Instance-Based Learning

abstract:
  This paper begins with a general theory of error in cross-validation testing
of algorithms for supervised learning from examples. It is assumed that the
examples are described by attribute-value pairs, where the values are symbolic.
Cross-validation requires a set of training examples and a set of testing
examples. The value of the attribute that is to be predicted is known to the
learner in the training set, but unknown in the testing set. The theory
demonstrates that cross-validation error has two components: error on the
training set (inaccuracy) and sensitivity to noise (instability). This general
theory is then applied to voting in instance-based learning. Given an example
in the testing set, a typical instance-based learning algorithm predicts the
designated attribute by voting among the k nearest neighbors (the k most
similar examples) to the testing example in the training set. Voting is
intended to increase the stability (resistance to noise) of instance-based
learning, but a theoretical analysis shows that there are circumstances in
which voting can be destabilizing. The theory suggests ways to minimize
cross-validation error, by insuring that voting is stable and does not
adversely affect accuracy.


title:
Contextual Normalization Applied to Aircraft Gas Turbine Engine
  Diagnosis

abstract:
  Diagnosing faults in aircraft gas turbine engines is a complex problem. It
involves several tasks, including rapid and accurate interpretation of patterns
in engine sensor data. We have investigated contextual normalization for the
development of a software tool to help engine repair technicians with
interpretation of sensor data. Contextual normalization is a new strategy for
employing machine learning. It handles variation in data that is due to
contextual factors, rather than the health of the engine. It does this by
normalizing the data in a context-sensitive manner. This learning strategy was
developed and tested using 242 observations of an aircraft gas turbine engine
in a test cell, where each observation consists of roughly 12,000 numbers,
gathered over a 12 second interval. There were eight classes of observations:
seven deliberately implanted classes of faults and a healthy class. We compared
two approaches to implementing our learning strategy: linear regression and
instance-based learning. We have three main results. (1) For the given problem,
instance-based learning works better than linear regression. (2) For this
problem, contextual normalization works better than other common forms of
normalization. (3) The algorithms described here can be the basis for a useful
software tool for assisting technicians with the interpretation of sensor data.


title:
Thumbs Up or Thumbs Down? Semantic Orientation Applied to Unsupervised
  Classification of Reviews

abstract:
  This paper presents a simple unsupervised learning algorithm for classifying
reviews as recommended (thumbs up) or not recommended (thumbs down). The
classification of a review is predicted by the average semantic orientation of
the phrases in the review that contain adjectives or adverbs. A phrase has a
positive semantic orientation when it has good associations (e.g., "subtle
nuances") and a negative semantic orientation when it has bad associations
(e.g., "very cavalier"). In this paper, the semantic orientation of a phrase is
calculated as the mutual information between the given phrase and the word
"excellent" minus the mutual information between the given phrase and the word
"poor". A review is classified as recommended if the average semantic
orientation of its phrases is positive. The algorithm achieves an average
accuracy of 74% when evaluated on 410 reviews from Epinions, sampled from four
different domains (reviews of automobiles, banks, movies, and travel
destinations). The accuracy ranges from 84% for automobile reviews to 66% for
movie reviews.


title: Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL

abstract:
  This paper presents a simple unsupervised learning algorithm for recognizing
synonyms, based on statistical data acquired by querying a Web search engine.
The algorithm, called PMI-IR, uses Pointwise Mutual Information (PMI) and
Information Retrieval (IR) to measure the similarity of pairs of words. PMI-IR
is empirically evaluated using 80 synonym test questions from the Test of
English as a Foreign Language (TOEFL) and 50 synonym test questions from a
collection of tests for students of English as a Second Language (ESL). On both
tests, the algorithm obtains a score of 74%. PMI-IR is contrasted with Latent
Semantic Analysis (LSA), which achieves a score of 64% on the same 80 TOEFL
questions. The paper discusses potential applications of the new unsupervised
learning algorithm and some implications of the results for LSA and LSI (Latent
Semantic Indexing).


title: Types of Cost in Inductive Concept Learning

abstract:
  Inductive concept learning is the task of learning to assign cases to a
discrete set of classes. In real-world applications of concept learning, there
are many different types of cost involved. The majority of the machine learning
literature ignores all types of cost (unless accuracy is interpreted as a type
of cost measure). A few papers have investigated the cost of misclassification
errors. Very few papers have examined the many other types of cost. In this
paper, we attempt to create a taxonomy of the different types of cost that are
involved in inductive concept learning. This taxonomy may help to organize the
literature on cost-sensitive learning. We hope that it will inspire researchers
to investigate all types of cost in inductive concept learning in more depth.


title: Exploiting Context When Learning to Classify

abstract:
  This paper addresses the problem of classifying observations when features
are context-sensitive, specifically when the testing set involves a context
that is different from the training set. The paper begins with a precise
definition of the problem, then general strategies are presented for enhancing
the performance of classification algorithms on this type of problem. These
strategies are tested on two domains. The first domain is the diagnosis of gas
turbine engines. The problem is to diagnose a faulty engine in one context,
such as warm weather, when the fault has previously been seen only in another
context, such as cold weather. The second domain is speech recognition. The
problem is to recognize words spoken by a new speaker, not represented in the
training set. For both domains, exploiting context results in substantially
more accurate classification.


title: Myths and Legends of the Baldwin Effect

abstract:
  This position paper argues that the Baldwin effect is widely misunderstood by
the evolutionary computation community. The misunderstandings appear to fall
into two general categories. Firstly, it is commonly believed that the Baldwin
effect is concerned with the synergy that results when there is an evolving
population of learning individuals. This is only half of the story. The full
story is more complicated and more interesting. The Baldwin effect is concerned
with the costs and benefits of lifetime learning by individuals in an evolving
population. Several researchers have focussed exclusively on the benefits, but
there is much to be gained from attention to the costs. This paper explains the
two sides of the story and enumerates ten of the costs and benefits of lifetime
learning by individuals in an evolving population. Secondly, there is a cluster
of misunderstandings about the relationship between the Baldwin effect and
Lamarckian inheritance of acquired characteristics. The Baldwin effect is not
Lamarckian. A Lamarckian algorithm is not better for most evolutionary
computing problems than a Baldwinian algorithm. Finally, Lamarckian inheritance
is not a better model of memetic (cultural) evolution than the Baldwin effect.


title: The Management of Context-Sensitive Features: A Review of Strategies

abstract:
  In this paper, we review five heuristic strategies for handling
context-sensitive features in supervised machine learning from examples. We
discuss two methods for recovering lost (implicit) contextual information. We
mention some evidence that hybrid strategies can have a synergetic effect. We
then show how the work of several machine learning researchers fits into this
framework. While we do not claim that these strategies exhaust the
possibilities, it appears that the framework includes all of the techniques
that can be found in the published literature on contextsensitive learning.


title:
The Identification of Context-Sensitive Features: A Formal Definition of
  Context for Concept Learning

abstract:
  A large body of research in machine learning is concerned with supervised
learning from examples. The examples are typically represented as vectors in a
multi-dimensional feature space (also known as attribute-value descriptions). A
teacher partitions a set of training examples into a finite number of classes.
The task of the learning algorithm is to induce a concept from the training
examples. In this paper, we formally distinguish three types of features:
primary, contextual, and irrelevant features. We also formally define what it
means for one feature to be context-sensitive to another feature.
Context-sensitive features complicate the task of the learner and potentially
impair the learner's performance. Our formal definitions make it possible for a
learner to automatically identify context-sensitive features. After
context-sensitive features have been identified, there are several strategies
that the learner can employ for managing the features; however, a discussion of
these strategies is outside of the scope of this paper. The formal definitions
presented here correct a flaw in previously proposed definitions. We discuss
the relationship between our work and a formal definition of relevance.


title:
Low Size-Complexity Inductive Logic Programming: The East-West Challenge
  Considered as a Problem in Cost-Sensitive Classification

abstract:
  The Inductive Logic Programming community has considered proof-complexity and
model-complexity, but, until recently, size-complexity has received little
attention. Recently a challenge was issued "to the international computing
community" to discover low size-complexity Prolog programs for classifying
trains. The challenge was based on a problem first proposed by Ryszard
Michalski, 20 years ago. We interpreted the challenge as a problem in
cost-sensitive classification and we applied a recently developed
cost-sensitive classifier to the competition. Our algorithm was relatively
successful (we won a prize). This paper presents our algorithm and analyzes the
results of the competition.


title: Data Engineering for the Analysis of Semiconductor Manufacturing Data

abstract:
  We have analyzed manufacturing data from several different semiconductor
manufacturing plants, using decision tree induction software called Q-YIELD.
The software generates rules for predicting when a given product should be
rejected. The rules are intended to help the process engineers improve the
yield of the product, by helping them to discover the causes of rejection.
Experience with Q-YIELD has taught us the importance of data engineering --
preprocessing the data to enable or facilitate decision tree induction. This
paper discusses some of the data engineering problems we have encountered with
semiconductor manufacturing data. The paper deals with two broad classes of
problems: engineering the features in a feature vector representation and
engineering the definition of the target concept (the classes). Manufacturing
process data present special problems for feature engineering, since the data
have multiple levels of granularity (detail, resolution). Engineering the
target concept is important, due to our focus on understanding the past, as
opposed to the more common focus in machine learning on predicting the future.


title: Robust Classification with Context-Sensitive Features

abstract:
  This paper addresses the problem of classifying observations when features
are context-sensitive, especially when the testing set involves a context that
is different from the training set. The paper begins with a precise definition
of the problem, then general strategies are presented for enhancing the
performance of classification algorithms on this type of problem. These
strategies are tested on three domains. The first domain is the diagnosis of
gas turbine engines. The problem is to diagnose a faulty engine in one context,
such as warm weather, when the fault has previously been seen only in another
context, such as cold weather. The second domain is speech recognition. The
context is given by the identity of the speaker. The problem is to recognize
words spoken by a new speaker, not represented in the training set. The third
domain is medical prognosis. The problem is to predict whether a patient with
hepatitis will live or die. The context is the age of the patient. For all
three domains, exploiting context results in substantially more accurate
classification.


title: Increasing Evolvability Considered as a Large-Scale Trend in Evolution

abstract:
  Evolvability is the capacity to evolve. This paper introduces a simple
computational model of evolvability and demonstrates that, under certain
conditions, evolvability can increase indefinitely, even when there is no
direct selection for evolvability. The model shows that increasing evolvability
implies an accelerating evolutionary pace. It is suggested that the conditions
for indefinitely increasing evolvability are satisfied in biological and
cultural evolution. We claim that increasing evolvability is a large-scale
trend in evolution. This hypothesis leads to testable predictions about
biological and cultural evolution.


title: Computing Conformal Structure of Surfaces

abstract:
  This paper solves the problem of computing conformal structures of general
2-manifolds represented as triangle meshes. We compute conformal structures in
the following way: first compute homology bases from simplicial complex
structures, then construct dual cohomology bases and diffuse them to harmonic
1-forms. Next, we construct bases of holomorphic differentials. We then obtain
period matrices by integrating holomorphic differentials along homology bases.
We also study the global conformal mapping between genus zero surfaces and
spheres, and between general meshes and planes. Our method of computing
conformal structures can be applied to tackle fundamental problems in computer
aid design and computer graphics, such as geometry classification and
identification, and surface global parametrization.


title:
Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for
  Maximum Matchings and Maximum Traveling Salesman Problems

abstract:
  We consider geometric instances of the Maximum Weighted Matching Problem
(MWMP) and the Maximum Traveling Salesman Problem (MTSP) with up to 3,000,000
vertices. Making use of a geometric duality relationship between MWMP, MTSP,
and the Fermat-Weber-Problem (FWP), we develop a heuristic approach that yields
in near-linear time solutions as well as upper bounds. Using various
computational tools, we get solutions within considerably less than 1% of the
optimum.
  An interesting feature of our approach is that, even though an FWP is hard to
compute in theory and Edmonds' algorithm for maximum weighted matching yields a
polynomial solution for the MWMP, the practical behavior is just the opposite,
and we can solve the FWP with high accuracy in order to find a good heuristic
solution for the MWMP.


title: Local Community Identification through User Access Patterns

abstract:
  Community identification algorithms have been used to enhance the quality of
the services perceived by its users. Although algorithms for community have a
widespread use in the Web, their application to portals or specific subsets of
the Web has not been much studied. In this paper, we propose a technique for
local community identification that takes into account user access behavior
derived from access logs of servers in the Web. The technique takes a departure
from the existing community algorithms since it changes the focus of in terest,
moving from authors to users. Our approach does not use relations imposed by
authors (e.g. hyperlinks in the case of Web pages). It uses information derived
from user accesses to a service in order to infer relationships. The
communities identified are of great interest to content providers since they
can be used to improve quality of their services. We also propose an evaluation
methodology for analyzing the results obtained by the algorithm. We present two
case studies based on actual data from two services: an online bookstore and an
online radio. The case of the online radio is particularly relevant, because it
emphasizes the contribution of the proposed algorithm to find out communities
in an environment (i.e., streaming media service) without links, that represent
the relations imposed by authors (e.g. hyperlinks in the case of Web pages).


title: Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way

abstract:
  In this paper, we introduce a new approach for drawing diagrams that have
applications in software visualization. Our approach is to use a technique we
call confluent drawing for visualizing non-planar diagrams in a planar way.
This approach allows us to draw, in a crossing-free manner, graphs--such as
software interaction diagrams--that would normally have many crossings. The
main idea of this approach is quite simple: we allow groups of edges to be
merged together and drawn as "tracks" (similar to train tracks). Producing such
confluent diagrams automatically from a graph with many crossings is quite
challenging, however, so we offer two heuristic algorithms to test if a
non-planar graph can be drawn efficiently in a confluent way. In addition, we
identify several large classes of graphs that can be completely categorized as
being either confluently drawable or confluently non-drawable.


title: On local equilibrium equations for clustering states

abstract:
  In this note we show that local equilibrium equations (the generalization of
the TAP equations or of the belief propagation equations) do have solutions in
the colorable phase of the coloring problem. The same results extend to other
optimization problems where the solutions has cost zero (e.g.
K-satisfiability). On a random graph the solutions of the local equilibrium
equations are associated to clusters of configurations (clustering states). On
a random graph the local equilibrium equations have solutions almost everywhere
in the uncolored phase; in this case we have to introduce the concept
quasi-solution of the local equilibrium equations.


title: Strategic polymorphism requires just two combinators!

abstract:
  In previous work, we introduced the notion of functional strategies:
first-class generic functions that can traverse terms of any type while mixing
uniform and type-specific behaviour. Functional strategies transpose the notion
of term rewriting strategies (with coverage of traversal) to the functional
programming paradigm. Meanwhile, a number of Haskell-based models and
combinator suites were proposed to support generic programming with functional
strategies.
  In the present paper, we provide a compact and matured reconstruction of
functional strategies. We capture strategic polymorphism by just two primitive
combinators. This is done without commitment to a specific functional language.
We analyse the design space for implementational models of functional
strategies. For completeness, we also provide an operational reference model
for implementing functional strategies (in Haskell). We demonstrate the
generality of our approach by reconstructing representative fragments of the
Strafunski library for functional strategies.


title:
An Ehrenfeucht-Fraisse Game Approach to Collapse Results in Database
  Theory

abstract:
  We present a new Ehrenfeucht-Fraisse game approach to collapse results in
database theory and we show that, in principle, this approach suffices to prove
every natural generic collapse result. Following this approach we can deal with
certain infinite databases where previous, highly involved methods fail. We
prove the natural generic collapse for Z-embeddable databases over any linearly
ordered context structure with arbitrary monadic predicates, and for
N-embeddable databases over the context structure (R,<,+,Mon_Q,Groups). Here,
N, Z, R, denote the sets of natural numbers, integers, and real numbers,
respectively. Groups is the collection of all subgroups of (R,+) that contain
Z, and Mon_Q is the collection of all subsets of a particular infinite subset Q
of N. Restricting the complexity of the formulas that may be used to formulate
queries to Boolean combinations of purely existential first-order formulas, we
even obtain the collapse for N-embeddable databases over any linearly ordered
context structure with arbitrary predicates. Finally, we develop the notion of
N-representable databases, which is a natural generalization of the classical
notion of finitely representable databases. We show that natural generic
collapse results for N-embeddable databases can be lifted to the larger class
of N-representable databases. To obtain, in particular, the collapse result for
(N,<,+,Mon_Q), we explicitly construct a winning strategy for the duplicator in
the presence of the built-in addition relation +. This, as a side product, also
leads to an Ehrenfeucht-Fraisse game proof of the theorem of Ginsburg and
Spanier, stating that the spectra of FO(<,+)-sentences are semi-linear.


title: Open Problems from CCCG 2002

abstract:
  A list of the problems presented on August 12, 2002 at the open-problem
session of the 14th Canadian Conference on Computational Geometry held in
Lethbridge, Alberta, Canada.


title: ExploitingWeb Service Semantics: Taxonomies vs. Ontologies

abstract:
  Comprehensive semantic descriptions of Web services are essential to exploit
them in their full potential, that is, discovering them dynamically, and
enabling automated service negotiation, composition and monitoring. The
semantic mechanisms currently available in service registries which are based
on taxonomies fail to provide the means to achieve this. Although the terms
taxonomy and ontology are sometimes used interchangably there is a critical
difference. A taxonomy indicates only class/subclass relationship whereas an
ontology describes a domain completely. The essential mechanisms that ontology
languages provide include their formal specification (which allows them to be
queried) and their ability to define properties of classes. Through properties
very accurate descriptions of services can be defined and services can be
related to other services or resources. In this paper, we discuss the
advantages of describing service semantics through ontology languages and
describe how to relate the semantics defined with the services advertised in
service registries like UDDI and ebXML.


title:
Improving the Functionality of UDDI Registries through Web Service
  Semantics

abstract:
  In this paper we describe a framework for exploiting the semantics of Web
services through UDDI registries. As a part of this framework, we extend the
DAML-S upper ontology to describe the functionality we find essential for
e-businesses. This functionality includes relating the services with electronic
catalogs, describing the complementary services and finding services according
to the properties of products or services. Once the semantics is defined, there
is a need for a mechanism in the service registry to relate it with the service
advertised. The ontology model developed is general enough to be used with any
service registry. However when it comes to relating the semantics with services
advertised, the capabilities provided by the registry effects how this is
achieved. We demonstrate how to integrate the described service semantics to
UDDI registries.


title: Merging Locally Correct Knowledge Bases: A Preliminary Report

abstract:
  Belief integration methods are often aimed at deriving a single and
consistent knowledge base that retains as much as possible of the knowledge
bases to integrate. The rationale behind this approach is the minimal change
principle: the result of the integration process should differ as less as
possible from the knowledge bases to integrate. We show that this principle can
be reformulated in terms of a more general model of belief revision, based on
the assumption that inconsistency is due to the mistakes the knowledge bases
contain. Current belief revision strategies are based on a specific kind of
mistakes, which however does not include all possible ones. Some alternative
possibilities are discussed.


title:
Improved Compact Visibility Representation of Planar Graph via
  Schnyder's Realizer

abstract:
  Let $G$ be an $n$-node planar graph. In a visibility representation of $G$,
each node of $G$ is represented by a horizontal line segment such that the line
segments representing any two adjacent nodes of $G$ are vertically visible to
each other. In the present paper we give the best known compact visibility
representation of $G$. Given a canonical ordering of the triangulated $G$, our
algorithm draws the graph incrementally in a greedy manner. We show that one of
three canonical orderings obtained from Schnyder's realizer for the
triangulated $G$ yields a visibility representation of $G$ no wider than
$\frac{22n-40}{15}$. Our easy-to-implement O(n)-time algorithm bypasses the
complicated subroutines for four-connected components and four-block trees
required by the best previously known algorithm of Kant. Our result provides a
negative answer to Kant's open question about whether $\frac{3n-6}{2}$ is a
worst-case lower bound on the required width. Also, if $G$ has no degree-three
(respectively, degree-five) internal node, then our visibility representation
for $G$ is no wider than $\frac{4n-9}{3}$ (respectively, $\frac{4n-7}{3}$).
Moreover, if $G$ is four-connected, then our visibility representation for $G$
is no wider than $n-1$, matching the best known result of Kant and He. As a
by-product, we obtain a much simpler proof for a corollary of Wagner's Theorem
on realizers, due to Bonichon, Sa\"{e}c, and Mosbah.


title:
Mathematical foundations of modern cryptography: computational
  complexity perspective

abstract:
  Theoretical computer science has found fertile ground in many areas of
mathematics. The approach has been to consider classical problems through the
prism of computational complexity, where the number of basic computational
steps taken to solve a problem is the crucial qualitative parameter. This new
approach has led to a sequence of advances, in setting and solving new
mathematical challenges as well as in harnessing discrete mathematics to the
task of solving real-world problems.
  In this talk, I will survey the development of modern cryptography -- the
mathematics behind secret communications and protocols -- in this light. I will
describe the complexity theoretic foundations underlying the cryptographic
tasks of encryption, pseudo-randomness number generators and functions, zero
knowledge interactive proofs, and multi-party secure protocols. I will attempt
to highlight the paradigms and proof techniques which unify these foundations,
and which have made their way into the mainstream of complexity theory.


title: On the Work of Madhu Sudan: the 2002 Nevalinna Prize Winner

abstract:
  Madhu Sudan's work spans many areas of computer science theory including
computational complexity theory, the design of efficient algorithms,
algorithmic coding theory, and the theory of program checking and correcting.
  Two results of Sudan stand out in the impact they have had on the mathematics
of computation. The first work shows a probabilistic characterization of the
class NP -- those sets for which short and easily checkable proofs of
membership exist, and demonstrates consequences of this characterization to
classifying the complexity of approximation problems. The second work shows a
polynomial time algorithm for list decoding the Reed Solomon error correcting
codes.
  This short note will be devoted to describing Sudan's work on
probabilistically checkable proofs -- the so called {\it PCP theorem} and its
implications.


title: Least squares fitting of circles and lines

abstract:
  We study theoretical and computational aspects of the least squares fit (LSF)
of circles and circular arcs. First we discuss the existence and uniqueness of
LSF and various parametrization schemes. Then we evaluate several popular
circle fitting algorithms and propose a new one that surpasses the existing
methods in reliability. We also discuss and compare direct (algebraic) circle
fits.


title:
Practical and Robust Stenciled Shadow Volumes for Hardware-Accelerated
  Rendering

abstract:
  Twenty-five years ago, Crow published the shadow volume approach for
determining shadowed regions in a scene. A decade ago, Heidmann described a
hardware-accelerated stencil buffer-based shadow volume algorithm.
  Unfortunately hardware-accelerated stenciled shadow volume techniques have
not been widely adopted by 3D games and applications due in large part to the
lack of robustness of described techniques. This situation persists despite
widely available hardware support. Specifically what has been lacking is a
technique that robustly handles various "hard" situations created by near or
far plane clipping of shadow volumes.
  We describe a robust, artifact-free technique for hardware-accelerated
rendering of stenciled shadow volumes. Assuming existing hardware, we resolve
the issues otherwise caused by shadow volume near and far plane clipping
through a combination of (1) placing the conventional far clip plane "at
infinity", (2) rasterization with infinite shadow volume polygons via
homogeneous coordinates, and (3) adopting a zfail stencil-testing scheme. Depth
clamping, a new rasterization feature provided by NVIDIA's GeForce3, preserves
existing depth precision by not requiring the far plane to be placed at
infinity. We also propose two-sided stencil testing to improve the efficiency
of rendering stenciled shadow volumes.


title: Flavor: A Language for Media Representation

abstract:
  Flavor (Formal Language for Audio-Visual Object Representation) has been
created as a language for describing coded multimedia bitstreams in a formal
way so that the code for reading and writing bitstreams can be automatically
generated. It is an extension of C++ and Java, in which the typing system
incorporates bitstream representation semantics. This allows describing in a
single place both the in-memory representation of data as well as their
bitstream-level (compressed) representation. Flavor also comes with a
translator that automatically generates standard C++ or Java code from the
Flavor source code so that direct access to compressed multimedia information
by application developers can be achieved with essentially zero programming.
Flavor has gone through many enhancements and this paper fully describes the
latest version of the language and the translator. The software has been made
into an open source project as of Version 4.1, and the latest downloadable
Flavor package is available at http://flavor.sourceforge.net.


title: Near Quadratic Matrix Multiplication Modulo Composites

abstract:
  We show how one can use non-prime-power, composite moduli for computing
representations of the product of two $n\times n$ matrices using only
$n^{2+o(1)}$ multiplications.


title: Modelling Delay Jitter in Voice over IP

abstract:
  It has been suggested in voice over IP that an appropriate choice of the
distribution used in modeling the delay jitters, can improve the play-out
algorithm. In this paper, we propose a tool using which, one can determine, at
a given instance, which distribution model best explains the jitter
distribution. This is done using Expectation Maximization, to choose amongst
possible distribution models which include, the i.i.d exponential distribution,
the gamma distribution etc.


title: Temporal plannability by variance of the episode length

abstract:
  Optimization of decision problems in stochastic environments is usually
concerned with maximizing the probability of achieving the goal and minimizing
the expected episode length. For interacting agents in time-critical
applications, learning of the possibility of scheduling of subtasks (events) or
the full task is an additional relevant issue. Besides, there exist highly
stochastic problems where the actual trajectories show great variety from
episode to episode, but completing the task takes almost the same amount of
time. The identification of sub-problems of this nature may promote e.g.,
planning, scheduling and segmenting Markov decision processes. In this work,
formulae for the average duration as well as the standard deviation of the
duration of events are derived. The emerging Bellman-type equation is a simple
extension of Sobel's work (1982). Methods of dynamic programming as well as
methods of reinforcement learning can be applied for our extension. Computer
demonstration on a toy problem serve to highlight the principle.


title: Kalman filter control in the reinforcement learning framework

abstract:
  There is a growing interest in using Kalman-filter models in brain modelling.
In turn, it is of considerable importance to make Kalman-filters amenable for
reinforcement learning. In the usual formulation of optimal control it is
computed off-line by solving a backward recursion. In this technical note we
show that slight modification of the linear-quadratic-Gaussian Kalman-filter
model allows the on-line estimation of optimal control and makes the bridge to
reinforcement learning. Moreover, the learning rule for value estimation
assumes a Hebbian form weighted by the error of the value estimation.


title: Formal Concept Analysis and Resolution in Algebraic Domains

abstract:
  We relate two formerly independent areas: Formal concept analysis and logic
of domains. We will establish a correspondene between contextual attribute
logic on formal contexts resp. concept lattices and a clausal logic on coherent
algebraic cpos. We show how to identify the notion of formal concept in the
domain theoretic setting. In particular, we show that a special instance of the
resolution rule from the domain logic coincides with the concept closure
operator from formal concept analysis. The results shed light on the use of
contexts and domains for knowledge representation and reasoning purposes.


title: A Script Language for Data Integration in Database

abstract:
  A Script Language in this paper is designed to transform the original data
into the target data by the computing formula. The Script Language can be
translated into the corresponding SQL Language, and the computation is finally
implemented by the first type of dynamic SQL. The Script Language has the
operations of insert, update, delete, union, intersect, and minus for the table
in the database.The Script Language is edited by a text file and you can easily
modify the computing formula in the text file to deal with the situations when
the computing formula have been changed. So you only need modify the text of
the script language, but needn't change the programs that have complied.


title:
Comparisons and Computation of Well-founded Semantics for Disjunctive
  Logic Programs

abstract:
  Much work has been done on extending the well-founded semantics to general
disjunctive logic programs and various approaches have been proposed. However,
these semantics are different from each other and no consensus is reached about
which semantics is the most intended. In this paper we look at disjunctive
well-founded reasoning from different angles. We show that there is an
intuitive form of the well-founded reasoning in disjunctive logic programming
which can be characterized by slightly modifying some exisitng approaches to
defining disjunctive well-founded semantics, including program transformations,
argumentation, unfounded sets (and resolution-like procedure). We also provide
a bottom-up procedure for this semantics. The significance of our work is not
only in clarifying the relationship among different approaches, but also shed
some light on what is an intended well-founded semantics for disjunctive logic
programs.


title: Open Network Handles Implemented in DNS

abstract:
  An Open Network Handle System (ONHS) provides an intermediate level of
service between IP numbers and domain names. A handle adheres permanently to an
owner, who may assign and reassign it to different addresses at will. But a
handle is a number, carrying no significance in natural language. Any user
desiring a handle may generate one from a public key. This memo describes a
simple implementation of an Open Network Handle System using the security
extensions to the Domain Name System (DNSSEC).


title: Hard satisfiable formulas for DPLL-type algorithms

abstract:
  We address lower bounds on the time complexity of algorithms solving the
propositional satisfiability problem. Namely, we consider two DPLL-type
algorithms, enhanced with the unit clause and pure literal heuristics.
Exponential lower bounds for solving satisfiability on provably satisfiable
formulas are proven.


title: Independence Properties of Algorithmically Random Sequences

abstract:
  A bounded Kolmogorov-Loveland selection rule is an adaptive strategy for
recursively selecting a subsequence of an infinite binary sequence; such a
subsequence may be interpreted as the query sequence of a time-bounded Turing
machine. In this paper we show that if A is an algorithmically random sequence,
A_0 is selected from A via a bounded Kolmogorov-Loveland selection rule, and
A_1 denotes the sequence of nonselected bits of A, then A_1 is independent of
A_0; that is, A_1 is algorithmically random relative to A_0. This result has
been used by Kautz and Miltersen [1] to show that relative to a random oracle,
NP does not have p-measure zero (in the sense of Lutz [2]).
  [1] S. M. Kautz and P. B. Miltersen. Relative to a random oracle, NP is not
small. Journal of Computer and System Sciences, 53:235-250, 1996.
  [2] J. H. Lutz. Almost everywhere high nonuniform complexity. Journal of
Computer and System Sciences, 44:220-258, 1992.


title: Convergence and Loss Bounds for Bayesian Sequence Prediction

abstract:
  The probability of observing $x_t$ at time $t$, given past observations
$x_1...x_{t-1}$ can be computed with Bayes' rule if the true generating
distribution $\mu$ of the sequences $x_1x_2x_3...$ is known. If $\mu$ is
unknown, but known to belong to a class $M$ one can base ones prediction on the
Bayes mix $\xi$ defined as a weighted sum of distributions $\nu\in M$. Various
convergence results of the mixture posterior $\xi_t$ to the true posterior
$\mu_t$ are presented. In particular a new (elementary) derivation of the
convergence $\xi_t/\mu_t\to 1$ is provided, which additionally gives the rate
of convergence. A general sequence predictor is allowed to choose an action
$y_t$ based on $x_1...x_{t-1}$ and receives loss $\ell_{x_t y_t}$ if $x_t$ is
the next symbol of the sequence. No assumptions are made on the structure of
$\ell$ (apart from being bounded) and $M$. The Bayes-optimal prediction scheme
$\Lambda_\xi$ based on mixture $\xi$ and the Bayes-optimal informed prediction
scheme $\Lambda_\mu$ are defined and the total loss $L_\xi$ of $\Lambda_\xi$ is
bounded in terms of the total loss $L_\mu$ of $\Lambda_\mu$. It is shown that
$L_\xi$ is bounded for bounded $L_\mu$ and $L_\xi/L_\mu\to 1$ for $L_\mu\to
\infty$. Convergence of the instantaneous losses are also proven.


title: Some remarks on the survey decimation algorithm for K-satisfiability

abstract:
  In this note we study the convergence of the survey decimation algorithm. An
analytic formula for the reduction of the complexity during the decimation is
derived. The limit of the converge of the algorithm are estimated in the random
case: interesting phenomena appear near the boundary of convergence.


title: Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps

abstract:
  We prove lower bounds of order $n\log n$ for both the problem to multiply
polynomials of degree $n$, and to divide polynomials with remainder, in the
model of bounded coefficient arithmetic circuits over the complex numbers.
These lower bounds are optimal up to order of magnitude. The proof uses a
recent idea of R. Raz [Proc. 34th STOC 2002] proposed for matrix
multiplication. It reduces the linear problem to multiply a random circulant
matrix with a vector to the bilinear problem of cyclic convolution. We treat
the arising linear problem by extending J. Morgenstern's bound [J. ACM 20, pp.
305-306, 1973] in a unitarily invariant way. This establishes a new lower bound
on the bounded coefficient complexity of linear forms in terms of the singular
values of the corresponding matrix. In addition, we extend these lower bounds
for linear and bilinear maps to a model of circuits that allows a restricted
number of unbounded scalar multiplications.


title:
Completeness and Decidability Properties for Functional Dependencies in
  XML

abstract:
  XML is of great importance in information storage and retrieval because of
its recent emergence as a standard for data representation and interchange on
the Internet. However XML provides little semantic content and as a result
several papers have addressed the topic of how to improve the semantic
expressiveness of XML. Among the most important of these approaches has been
that of defining integrity constraints in XML. In a companion paper we defined
strong functional dependencies in XML(XFDs). We also presented a set of axioms
for reasoning about the implication of XFDs and showed that the axiom system is
sound for arbitrary XFDs. In this paper we prove that the axioms are also
complete for unary XFDs (XFDs with a single path on the l.h.s.). The second
contribution of the paper is to prove that the implication problem for unary
XFDs is decidable and to provide a linear time algorithm for it.


title:
Novel Runtime Systems Support for Adaptive Compositional Modeling on the
  Grid

abstract:
  Grid infrastructures and computing environments have progressed significantly
in the past few years. The vision of truly seamless Grid usage relies on
runtime systems support that is cognizant of the operational issues underlying
grid computations and, at the same time, is flexible enough to accommodate
diverse application scenarios. This paper addresses the twin aspects of Grid
infrastructure and application support through a novel combination of two
computational technologies: Weaves - a source-language independent parallel
runtime compositional framework that operates through reverse-analysis of
compiled object files, and runtime recommender systems that aid in dynamic
knowledge-based application composition. Domain-specific adaptivity is
exploited through a novel compositional system that supports runtime
recommendation of code modules and a sophisticated checkpointing and runtime
migration solution that can be transparently deployed over Grid
infrastructures. A core set of "adaptivity schemas" are provided as templates
for adaptive composition of large-scale scientific computations. Implementation
issues, motivating application contexts, and preliminary results are described.


title: Smoothed Analysis of Interior-Point Algorithms: Termination

abstract:
  We perform a smoothed analysis of the termination phase of an interior-point
method. By combining this analysis with the smoothed analysis of Renegar's
interior-point algorithm by Dunagan, Spielman and Teng, we show that the
smoothed complexity of an interior-point algorithm for linear programming is $O
(m^{3} \log (m/\sigma))$. In contrast, the best known bound on the worst-case
complexity of linear programming is $O (m^{3} L)$, where $L$ could be as large
as $m$. We include an introduction to smoothed analysis and a tutorial on proof
techniques that have been useful in smoothed analyses.


title: Differential Fault Analysis on A.E.S

abstract:
  We explain how a differential fault analysis (DFA) works on AES 128, 192 or
256 bits.


title: PHORMA: Perfectly Hashable Order Restricted Multidimensional Arrays

abstract:
  In this paper we propose a simple and efficient data structure yielding a
perfect hashing of quite general arrays. The data structure is named phorma,
which is an acronym for perfectly hashable order restricted multidimensional
array.
  Keywords: Perfect hash function, Digraph, Implicit enumeration,
Nijenhuis-Wilf combinatorial family.


title: Homomorphic public-key cryptosystems and encrypting boolean circuits

abstract:
  In this paper homomorphic cryptosystems are designed for the first time over
any finite group. Applying Barrington's construction we produce for any boolean
circuit of the logarithmic depth its encrypted simulation of a polynomial size
over an appropriate finitely generated group.


title: A semantic framework for preference handling in answer set programming

abstract:
  We provide a semantic framework for preference handling in answer set
programming. To this end, we introduce preference preserving consequence
operators. The resulting fixpoint characterizations provide us with a uniform
semantic framework for characterizing preference handling in existing
approaches. Although our approach is extensible to other semantics by means of
an alternating fixpoint theory, we focus here on the elaboration of preferences
under answer set semantics. Alternatively, we show how these approaches can be
characterized by the concept of order preservation. These uniform semantic
characterizations provide us with new insights about interrelationships and
moreover about ways of implementation.


title: Complexity and Completeness of Immanants

abstract:
  Immanants are polynomial functions of n by n matrices attached to irreducible
characters of the symmetric group S_n, or equivalently to Young diagrams of
size n. Immanants include determinants and permanents as extreme cases. Valiant
proved that computation of permanents is a complete problem in his algebraic
model of NP theory, i.e., it is VNP-complete. We prove that computation of
immanants is VNP-complete if the immanants are attached to a family of diagrams
whose separation is $\Omega(n^\delta)$ for some $\delta>0$. We define the
separation of a diagram to be the largest number of overhanging boxes contained
in a single row. Our theorem proves a conjecture of Buergisser for a large
variety of families, and in particular we recover with new proofs his
VNP-completeness results for hooks and rectangles.


title: PHORMA: Perfectly Hashed Order Restricted Multidimensional Array

abstract:
  In this paper we propose a simple and efficient strategy to obtain a data
structure generator to accomplish a perfect hash of quite general order
restricted multidimensional arrays named {\em phormas}. The constructor of such
objects gets two parameters as input: an n-vector a of non negative integers
and a boolean function B on the types of order restrictions on the coordinates
of the valid n-vectors bounded by a. At compiler time, the phorma constructor
builds, from the pair a,B, a digraph G(a,B) with a single source s and a single
sink t such that the st-paths are in 1-1 correspondence with the members of the
B-restricted a-bounded array A(a,B). Besides perfectly hashing A(a,B), G(a,B)
is an instance of an NW-family. This permits other useful computational tasks
on it.


title: Double-Negation Elimination in Some Propositional Logics

abstract:
  This article answers two questions (posed in the literature), each concerning
the guaranteed existence of proofs free of double negation. A proof is free of
double negation if none of its deduced steps contains a term of the form
n(n(t)) for some term t, where n denotes negation. The first question asks for
conditions on the hypotheses that, if satisfied, guarantee the existence of a
double-negation-free proof when the conclusion is free of double negation. The
second question asks about the existence of an axiom system for classical
propositional calculus whose use, for theorems with a conclusion free of double
negation, guarantees the existence of a double-negation-free proof. After
giving conditions that answer the first question, we answer the second question
by focusing on the Lukasiewicz three-axiom system. We then extend our studies
to infinite-valued sentential calculus and to intuitionistic logic and
generalize the notion of being double-negation free. The double-negation proofs
of interest rely exclusively on the inference rule condensed detachment, a rule
that combines modus ponens with an appropriately general rule of substitution.
The automated reasoning program OTTER played an indispensable role in this
study.


title: A comparison of four approaches to the calculation of conservation laws

abstract:
  The paper compares computational aspects of four approaches to compute
conservation laws of single differential equations (DEs) or systems of them,
ODEs and PDEs. The only restriction, required by two of the four corresponding
computer algebra programs, is that each DE has to be solvable for a leading
derivative. Extra constraints for the conservation laws can be specified.
Examples include new conservation laws that are non-polynomial in the
functions, that have an explicit variable dependence and families of
conservation laws involving arbitrary functions. The following equations are
investigated in examples: Ito, Liouville, Burgers, Kadomtsev-Petviashvili,
Karney-Sen-Chu-Verheest, Boussinesq, Tzetzeica, Benney.


title:
The integration of systems of linear PDEs using conservation laws of
  syzygies

abstract:
  A new integration technique is presented for systems of linear partial
differential equations (PDEs) for which syzygies can be formulated that obey
conservation laws. These syzygies come for free as a by-product of the
differential Groebner Basis computation. Compared with the more obvious way of
integrating a single equation and substituting the result in other equations
the new technique integrates more than one equation at once and therefore
introduces temporarily fewer new functions of integration that in addition
depend on fewer variables. Especially for high order PDE systems in many
variables the conventional integration technique may lead to an explosion of
the number of functions of integration which is avoided with the new method. A
further benefit is that redundant free functions in the solution are either
prevented or that their number is at least reduced.


title: Size reduction and partial decoupling of systems of equations

abstract:
  A method is presented that reduces the number of terms of systems of linear
equations (algebraic, ordinary and partial differential equations). As a
byproduct these systems have a tendency to become partially decoupled and are
more likely to be factorizable or integrable. A variation of this method is
applicable to non-linear systems. Modifications to improve efficiency are given
and examples are shown. This procedure can be used in connection with the
computation of the radical of a differential ideal (differential Groebner
basis).


title: Bounds on the Number of Longest Common Subsequences

abstract:
  This paper performs the analysis necessary to bound the running time of
known, efficient algorithms for generating all longest common subsequences.
That is, we bound the running time as a function of input size for algorithms
with time essentially proportional to the output size. This paper considers
both the case of computing all distinct LCSs and the case of computing all LCS
embeddings. Also included is an analysis of how much better the efficient
algorithms are than the standard method of generating LCS embeddings. A full
analysis is carried out with running times measured as a function of the total
number of input characters, and much of the analysis is also provided for cases
in which the two input sequences are of the same specified length or of two
independently specified lengths.


title: Fine-Grain Authorization for Resource Management in the Grid Environment

abstract:
  In this document we describe our work-in-progress for enabling fine-grain
authorization of resource management. In particular, we address the needs of
Virtual Organizations (VOs) to enforce their own policies in addition to those
of the resource owners.


title: Subclassing errors, OOP, and practically checkable rules to prevent them

abstract:
  This paper considers an example of Object-Oriented Programming (OOP) leading
to subtle errors that break separation of interface and implementations. A
comprehensive principle that guards against such errors is undecidable. The
paper introduces a set of mechanically verifiable rules that prevent these
insidious problems. Although the rules seem restrictive, they are powerful and
expressive, as we show on several familiar examples. The rules contradict both
the spirit and the letter of the OOP. The present examples as well as available
theoretical and experimental results pose a question if OOP is conducive to
software development at all.


title: Computational Grids in Action: The Natinal Fusion Collaboratory

abstract:
  The National Fusion Collaboratory (NFC) project was created to advance
scientific understanding and innovation in magnetic fusion research by enabling
more efficient use of existing experimental facilities through more effective
integration of experiment, theory, and modeling. To achieve this objective, NFC
introduced the concept of "network services", which build on top of
computational Grids, and provide Fusion codes, together with their maintenance
and hardware resources as a service to the community. This mode of operation
requires the development of new authorization and enforcement capabilities. In
addition, the nature of Fusion experiments places strident quality of service
requirements on codes run during the experimental cycle. In this paper, we
describe Grid computing requirements of the Fusion community, and present our
first experiments in meeting those requirements.


title: Computing the Number of Longest Common Subsequences

abstract:
  This note provides very simple, efficient algorithms for computing the number
of distinct longest common subsequences of two input strings and for computing
the number of LCS embeddings.


title: On the Complexity of Buffer Allocation in Message Passing Systems

abstract:
  Message passing programs commonly use buffers to avoid unnecessary
synchronizations and to improve performance by overlapping communication with
computation. Unfortunately, using buffers makes the program no longer portable,
potentially unable to complete on systems without a sufficient number of
buffers. Effective buffer use entails that the minimum number needed for a safe
execution be allocated.
  We explore a variety of problems related to buffer allocation for safe and
efficient execution of message passing programs. We show that determining the
minimum number of buffers or verifying a buffer assignment are intractable
problems. However, we give a polynomial time algorithm to determine the minimum
number of buffers needed to allow for asynchronous execution. We extend these
results to several different buffering schemes, which in some cases make the
problems tractable.


title: Algorithms using Java for Spreadsheet Dependent Cell Recomputation

abstract:
  Java implementations of algorithms used by spreadsheets to automatically
recompute the set of cells dependent on a changed cell are described using a
mathematical model for spreadsheets based on graph theory. These solutions
comprise part of a Java API that allows a client application to read, modify,
and maintain spreadsheet data without using the spreadsheet application program
that produced it. Features of the Java language that successfully improve the
running time performance of the algorithms are also described.


title:
Many Hard Examples in Exact Phase Transitions with Application to
  Generating Hard Satisfiable Instances

abstract:
  This paper first analyzes the resolution complexity of two random CSP models
(i.e. Model RB/RD) for which we can establish the existence of phase
transitions and identify the threshold points exactly. By encoding CSPs into
CNF formulas, it is proved that almost all instances of Model RB/RD have no
tree-like resolution proofs of less than exponential size. Thus, we not only
introduce new families of CNF formulas hard for resolution, which is a central
task of Proof-Complexity theory, but also propose models with both many hard
instances and exact phase transitions. Then, the implications of such models
are addressed. It is shown both theoretically and experimentally that an
application of Model RB/RD might be in the generation of hard satisfiable
instances, which is not only of practical importance but also related to some
open problems in cryptography such as generating one-way functions.
Subsequently, a further theoretical support for the generation method is shown
by establishing exponential lower bounds on the complexity of solving random
satisfiable and forced satisfiable instances of RB/RD near the threshold.
Finally, conclusions are presented, as well as a detailed comparison of Model
RB/RD with the Hamiltonian cycle problem and random 3-SAT, which, respectively,
exhibit three different kinds of phase transition behavior in NP-complete
problems.


title: Optimizing GoTools' Search Heuristics using Genetic Algorithms

abstract:
  GoTools is a program which solves life & death problems in the game of Go.
This paper describes experiments using a Genetic Algorithm to optimize
heuristic weights used by GoTools' tree-search. The complete set of heuristic
weights is composed of different subgroups, each of which can be optimized with
a suitable fitness function. As a useful side product, an MPI interface for
FreePascal was implemented to allow the use of a parallelized fitness function
running on a Beowulf cluster. The aim of this exercise is to optimize the
current version of GoTools, and to make tools available in preparation of an
extension of GoTools for solving open boundary life & death problems, which
will introduce more heuristic parameters to be fine tuned.


title: Approximate analysis of search algorithms with "physical" methods

abstract:
  An overview of some methods of statistical physics applied to the analysis of
algorithms for optimization problems (satisfiability of Boolean constraints,
vertex cover of graphs, decoding, ...) with distributions of random inputs is
proposed. Two types of algorithms are analyzed: complete procedures with
backtracking (Davis-Putnam-Loveland-Logeman algorithm) and incomplete, local
search procedures (gradient descent, random walksat, ...). The study of
complete algorithms makes use of physical concepts such as phase transitions,
dynamical renormalization flow, growth processes, ... As for local search
procedures, the connection between computational complexity and the structure
of the cost function landscape is questioned, with emphasis on the notion of
metastability.


title: Unique Pattern Matching in Strings

abstract:
  Regular expression patterns are a key feature of document processing
languages like Perl and XDuce. It is in this context that the first and longest
match policies have been proposed to disambiguate the pattern matching process.
We formally define a matching semantics with these policies and show that the
generally accepted method of simulating longest match by first match and
recursion is incorrect. We continue by solving the associated type inference
problem, which consists in calculating for every subexpression the set of words
the subexpression can still match when these policies are in effect, and show
how this algorithm can be used to efficiently implement the matching process.


title:
Barnacle: An Assembly Algorithm for Clone-based Sequences of Whole
  Genomes

abstract:
  We propose an assembly algorithm {\sc Barnacle} for sequences generated by
the clone-based approach. We illustrate our approach by assembling the human
genome. Our novel method abandons the original physical-mapping-first
framework. As we show, {\sc Barnacle} more effectively resolves conflicts due
to repeated sequences. The latter is the main difficulty of the sequence
assembly problem. Inaddition, we are able to detect inconsistencies in the
underlying data. We present and compare our results on the December 2001 freeze
of the public working draft of the human genome with NCBI's assembly (Build
28).
  The assembly of December 2001 freeze of the public working draft generated by
{\sc Barnacle} and the source code of {\sc Barnacle} are available at
(http://www.cs.rutgers.edu/~vchoi).


title:
Grid Market Directory: A Web Services based Grid Service Publication
  Directory

abstract:
  As Grids are emerging as the next generation service-oriented computing
platforms, they need to support Grid economy that helps in the management of
supply and demand for resources and offers an economic incentive for Grid
resource providers. To enable this Grid economy, a market-like Grid environment
including an infrastructure that supports the publication of services and their
discovery is needed. As part of the Gridbus project, we proposed and have
developed a Grid Market Directory (GMD) that serves as a registry for
high-level service publication and discovery in Virtual Organisations.


title:
G-Monitor: Gridbus web portal for monitoring and steering application
  execution on global grids

abstract:
  Grids are experiencing a rapid growth in their application and along with
this there is a requirement for a portal which is easy to use and scalable. We
have responded to this requirement by developing an easy to use, scalable,
web-based portal called G-Monitor. This paper proposes a generic architecture
for a web portal into a grid environment and discusses our implementation and
its application.


title:
Visual Environment for Rapid Composition of Parameter-Sweep Applications
  for Distributed Processing on Global Grids

abstract:
  Computational Grids are emerging as a platform for next-generation parallel
and distributed computing. Large-scale parametric studies and parameter sweep
applications find a natural place in the Grid?s distribution model. There is
little or no communication between jobs. The task of parallelizing and
distributing existing applications is conceptually trivial. These properties of
parametric studies make it an ideal place to start developing integrated
development environments (IDEs) for rapidly Grid-enabling applications.
However, the availability of IDEs for scientists to Grid-enable their
applications, without the need of developing them as parallel applications
explicitly, is still lacking. This paper presents a Java based IDE called
Visual Parametric Tool (VPT), developed as part of the Gridbus project, for
rapid creation of parameter sweep (data parallel/SPMD) applications. It
supports automatic creation of parameter script and parameterisation of the
input data files, which is compatible with the Nimrod-G parameter specification
language. The usefulness of VPT is demonstrated by a case study on composition
of molecular docking application as a parameter sweep application. Such
applications can be deployed on clusters using the Nimrod/enFuzion system and
on global Grids using the Nimrod-G grid resource broker.


title: Data Structure for a Time-Based Bandwidth Reservations Problem

abstract:
  We discuss a problem of handling resource reservations. The resource can be
reserved for some time, it can be freed or it can be queried what is the
largest amount of reserved resource during a time interval. We show that the
problem has a lower bound of $\Omega(\log n)$ per operation on average and we
give a matching upper bound algorithm. Our solution also solves a dynamic
version of the related problems of a prefix sum and a partial sum.


title: Authenticated Append-only Skip Lists

abstract:
  In this work we describe, design and analyze the security of a
tamper-evident, append-only data structure for maintaining secure data
sequences in a loosely coupled distributed system where individual system
components may be mutually distrustful. The resulting data structure, called an
Authenticated Append-Only Skip List (AASL), allows its maintainers to produce
one-way digests of the entire data sequence, which they can publish to others
as a commitment on the contents and order of the sequence. The maintainer can
produce efficiently succinct proofs that authenticate a particular datum in a
particular position of the data sequence against a published digest. AASLs are
secure against tampering even by malicious data structure maintainers. First,
we show that a maintainer cannot ``invent'' and authenticate data elements for
the AASL after he has committed to the structure. Second, he cannot equivocate
by being able to prove conflicting facts about a particular position of the
data sequence. This is the case even when the data sequence grows with time and
its maintainer publishes successive commitments at times of his own choosing.
  AASLs can be invaluable in reasoning about the integrity of system logs
maintained by untrusted components of a loosely-coupled distributed system.


title: Smoothed Analysis of Interior-Point Algorithms: Condition Number

abstract:
  We show that the smoothed complexity of the logarithm of Renegar's condition
number is O(log (n/sigma)).


title: The New AI: General & Sound & Relevant for Physics

abstract:
  Most traditional artificial intelligence (AI) systems of the past 50 years
are either very limited, or based on heuristics, or both. The new millennium,
however, has brought substantial progress in the field of theoretically optimal
and practically feasible algorithms for prediction, search, inductive inference
based on Occam's razor, problem solving, decision making, and reinforcement
learning in environments of a very general type. Since inductive inference is
at the heart of all inductive sciences, some of the results are relevant not
only for AI and computer science but also for physics, provoking nontraditional
predictions based on Zuse's thesis of the computer-generated universe.


title: Cg in Two Pages

abstract: Cg is a language for programming GPUs. This paper describes Cg briefly.


title:
An Algorithm for Aligning Sentences in Bilingual Corpora Using Lexical
  Information

abstract:
  In this paper we describe an algorithm for aligning sentences with their
translations in a bilingual corpus using lexical information of the languages.
Existing efficient algorithms ignore word identities and consider only the
sentence lengths (Brown, 1991; Gale and Church, 1993). For a sentence in the
source language text, the proposed algorithm picks the most likely translation
from the target language text using lexical information and certain heuristics.
It does not do statistical analysis using sentence lengths. The algorithm is
language independent. It also aids in detecting addition and deletion of text
in translations. The algorithm gives comparable results with the existing
algorithms in most of the cases while it does better in cases where statistical
algorithms do not give good results.


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

abstract:
  This paper describes a novel approach to unsupervised learning that has been
developed within a framework of "information compression by multiple alignment,
unification and search" (ICMAUS), designed to integrate learning with other AI
functions such as parsing and production of language, fuzzy pattern
recognition, probabilistic and exact forms of reasoning, and others.


title: Data-sharing relationships in the Web

abstract:
  We propose a novel structure, the data-sharing graph, for characterizing
sharing patterns in large-scale data distribution systems. We analyze this
structure in two such systems and uncover small-world patterns for data-sharing
relationships. Using the data-sharing graph for system characterization has
potential both for basic science, because we can identify new structures
emerging in real, dynamic networks; and for system design, because we can
exploit these structures when designing data location and delivery mechanisms.
We conjecture that similar patterns arise in other large-scale systems and that
these patterns can be exploited for mechanism design.


title: A Proposal to Separate Handles from Names on the Internet

abstract:
  Networked communications inherently depend on the ability of the sender of a
message to indicate through some token how the message should be delivered to a
particular recipient. The tokens that refer messages to recipients are
variously known as routes, addresses,handles, and names} ordered by their
relative nearness to network topology vs. human meaning. All four sorts of
token refer in some way to a recipient, but they are controlled by different
authorities and their meanings depend on different contextual parameters.
  Today's global Internet employs dynamically determined routes, IP addresses,
and domain names. Domain names combine the functions of handles and names. The
high value of domain names as names leads to substantial social and legal
dispute about their assignment, degrading their value as handles. The time has
come to provide a distinct open network handle system (ONHS), using handles
that are not meaningful in natural language and are therefore not subject to
the disputes surrounding the use of names.
  A handle service may be deployed easily as a handle domain within the current
Domain Name System. In order to minimize the administrative load, and maximize
their own autonomy, netizens may use public-key cryptography to assign their
own handles.


title:
Guided Google: A Meta Search Engine and its Implementation using the
  Google Distributed Web Services

abstract:
  With the advent of the Internet, search engines have begun sprouting like
mushrooms after a rainfall. Only in recent years, have developers become more
innovative, and came up with guided searching facilities online. The goals of
these applications are to help ease and guide the searching efforts of a novice
web user toward their desired objectives. A number of implementations of such
services are emerging. This paper proposes a guided meta-search engine, called
"Guided Google", as it serves as an interface to the actual Google.com search
engine, using the Google Web Services.


title: Economic and On Demand Brain Activity Analysis on Global Grids

abstract:
  The lack of computational power within an organization for analyzing
scientific data, and the distribution of knowledge (by scientists) and
technologies (advanced scientific devices) are two major problems commonly
observed in scientific disciplines. One such scientific discipline is brain
science. The analysis of brain activity data gathered from the MEG
(Magnetoencephalography) instrument is an important research topic in medical
science since it helps doctors in identifying symptoms of diseases. The data
needs to be analyzed exhaustively to efficiently diagnose and analyze brain
functions and requires access to large-scale computational resources. The
potential platform for solving such resource intensive applications is the
Grid. This paper describes a MEG data analysis system developed by us,
leveraging Grid technologies, primarily Nimrod-G, Gridbus, and Globus. This
paper explains the application of economy-based grid scheduling algorithms to
the problem domain for on-demand processing of analysis jobs.


title: Analytical formulations of Peer-to-Peer Connection Efficiency

abstract:
  Use of Peer-to-Peer (P2P) service networks introduces a new communication
paradigm because peers are both clients and servers and so each peer may
provide/request services to/from other peers. Empirical studies of P2P networks
have been undertaken and reveal useful characteristics. However there is to
date little analytical work to describe P2P networks with respect to their
communication paradigm and their interconnections. This paper provides an
analytical formulation and optimisation of peer connection efficiency, in terms
of minimising the fraction of wasted connection time. Peer connection
efficiency is analysed for both a uni- and multi-connected peer. Given this
fundamental optimisation, the paper optimises the number of connections that
peers should make use of as a function of network load, in terms of minimising
the total queue size that requests in the P2P network experience. The results
of this paper provide a basis for engineering high performance P2P
interconnection networks. The optimisations are useful for reducing bandwidth
and power consumption, e.g. in the case of peers being mobile devices with a
limited power supply. Also these results could be used to determine when a
(virtual) circuit should be switched to support a connection.


title: Building an Open Language Archives Community on the OAI Foundation

abstract:
  The Open Language Archives Community (OLAC) is an international partnership
of institutions and individuals who are creating a worldwide virtual library of
language resources. The Dublin Core (DC) Element Set and the OAI Protocol have
provided a solid foundation for the OLAC framework. However, we need more
precision in community-specific aspects of resource description than is offered
by DC. Furthermore, many of the institutions and individuals who might
participate in OLAC do not have the technical resources to support the OAI
protocol. This paper presents our solutions to these two problems. To address
the first, we have developed an extensible application profile for language
resource metadata. To address the second, we have implemented Vida (the virtual
data provider) and Viser (the virtual service provider), which permit community
members to provide data and services without having to implement the OAI
protocol. These solutions are generic and could be adopted by other specialized
subcommunities.


title: Fault-tolerant routing in peer-to-peer systems

abstract:
  We consider the problem of designing an overlay network and routing mechanism
that permits finding resources efficiently in a peer-to-peer system. We argue
that many existing approaches to this problem can be modeled as the
construction of a random graph embedded in a metric space whose points
represent resource identifiers, where the probability of a connection between
two nodes depends only on the distance between them in the metric space. We
study the performance of a peer-to-peer system where nodes are embedded at grid
points in a simple metric space: a one-dimensional real line. We prove upper
and lower bounds on the message complexity of locating particular resources in
such a system, under a variety of assumptions about failures of either nodes or
the connections between them. Our lower bounds in particular show that the use
of inverse power-law distributions in routing, as suggested by Kleinberg
(1999), is close to optimal. We also give efficient heuristics to dynamically
maintain such a system as new nodes arrive and old nodes depart. Finally, we
give experimental results that suggest promising directions for future work.


title:
Segmentation, Indexing, and Visualization of Extended Instructional
  Videos

abstract:
  We present a new method for segmenting, and a new user interface for indexing
and visualizing, the semantic content of extended instructional videos. Given a
series of key frames from the video, we generate a condensed view of the data
by clustering frames according to media type and visual similarities. Using
various visual filters, key frames are first assigned a media type (board,
class, computer, illustration, podium, and sheet). Key frames of media type
board and sheet are then clustered based on contents via an algorithm with
near-linear cost. A novel user interface, the result of two user studies,
displays related topics using icons linked topologically, allowing users to
quickly locate semantically related portions of the video. We analyze the
accuracy of the segmentation tool on 17 instructional videos, each of which is
from 75 to 150 minutes in duration (a total of 40 hours); the classification
accuracy exceeds 96%.


title: Analysis and Interface for Instructional Video

abstract:
  We present a new method for segmenting, and a new user interface for indexing
and visualizing, the semantic content of extended instructional videos. Using
various visual filters, key frames are first assigned a media type (board,
class, computer, illustration, podium, and sheet). Key frames of media type
board and sheet are then clustered based on contents via an algorithm with
near-linear cost. A novel user interface, the result of two user studies,
displays related topics using icons linked topologically, allowing users to
quickly locate semantically related portions of the video. We analyze the
accuracy of the segmentation tool on 17 instructional videos, each of which is
from 75 to 150 minutes in duration (a total of 40 hours); it exceeds 96%.


title: Cryptographic Randomized Response Techniques

abstract:
  We develop cryptographically secure techniques to guarantee unconditional
privacy for respondents to polls. Our constructions are efficient and
practical, and are shown not to allow cheating respondents to affect the
``tally'' by more than their own vote -- which will be given the exact same
weight as that of other respondents. We demonstrate solutions to this problem
based on both traditional cryptographic techniques and quantum cryptography.


title:
Recursive function templates as a solution of linear algebra expressions
  in C++

abstract:
  The article deals with a kind of recursive function templates in C++, where
the recursion is realized corresponding template parameters to achieve better
computational performance. Some specialization of these template functions ends
the recursion and can be implemented using optimized hardware dependent or
independent routines. The method is applied in addition to the known expression
templates technique to solve linear algebra expressions with the help of the
BLAS library. The whole implementation produces a new library, which keeps
object-oriented benefits and has a higher computational speed represented in
the tests.


title: Tiling space and slabs with acute tetrahedra

abstract:
  We show it is possible to tile three-dimensional space using only tetrahedra
with acute dihedral angles. We present several constructions to achieve this,
including one in which all dihedral angles are less than $77.08^\circ$, and
another which tiles a slab in space.


title:
The Boolean Functions Computed by Random Boolean Formulas OR How to Grow
  the Right Function

abstract:
  Among their many uses, growth processes (probabilistic amplification), were
used for constructing reliable networks from unreliable components, and
deriving complexity bounds of various classes of functions. Hence, determining
the initial conditions for such processes is an important and challenging
problem. In this paper we characterize growth processes by their initial
conditions and derive conditions under which results such as Valiant's (1984)
hold. First, we completely characterize growth processes that use linear
connectives. Second, by extending Savick\'y's (1990) analysis, via
``Restriction Lemmas'', we characterize growth processes that use monotone
connectives, and show that our technique is applicable to growth processes that
use other connectives as well. Additionally, we obtain explicit bounds on the
convergence rates of several growth processes, including the growth process
studied by Savick\'y (1990).


title: Defeasible Logic Programming: An Argumentative Approach

abstract:
  The work reported here introduces Defeasible Logic Programming (DeLP), a
formalism that combines results of Logic Programming and Defeasible
Argumentation. DeLP provides the possibility of representing information in the
form of weak rules in a declarative manner, and a defeasible argumentation
inference mechanism for warranting the entailed conclusions.
  In DeLP an argumentation formalism will be used for deciding between
contradictory goals. Queries will be supported by arguments that could be
defeated by other arguments. A query q will succeed when there is an argument A
for q that is warranted, ie, the argument A that supports q is found undefeated
by a warrant procedure that implements a dialectical analysis.
  The defeasible argumentation basis of DeLP allows to build applications that
deal with incomplete and contradictory information in dynamic domains. Thus,
the resulting approach is suitable for representing agent's knowledge and for
providing an argumentation based reasoning mechanism to agents.


title: The traveling salesman problem for cubic graphs

abstract:
  We show how to find a Hamiltonian cycle in a graph of degree at most three
with n vertices, in time O(2^{n/3}) ~= 1.260^n and linear space. Our algorithm
can find the minimum weight Hamiltonian cycle (traveling salesman problem), in
the same time bound. We can also count or list all Hamiltonian cycles in a
degree three graph in time O(2^{3n/8}) ~= 1.297^n. We also solve the traveling
salesman problem in graphs of degree at most four, by randomized and
deterministic algorithms with runtime O((27/4)^{n/3}) ~= 1.890^n and
O((27/4+epsilon)^{n/3}) respectively. Our algorithms allow the input to specify
a set of forced edges which must be part of any generated cycle. Our cycle
listing algorithm shows that every degree three graph has O(2^{3n/8})
Hamiltonian cycles; we also exhibit a family of graphs with 2^{n/3} Hamiltonian
cycles per graph.


title: Relaxed Scheduling in Dynamic Skin Triangulation

abstract:
  We introduce relaxed scheduling as a paradigm for mesh maintenance and
demonstrate its applicability to triangulating a skin surface in $\Rspace^3$.


title: Empirical Methods for Compound Splitting

abstract:
  Compounded words are a challenge for NLP applications such as machine
translation (MT). We introduce methods to learn splitting rules from
monolingual and parallel corpora. We evaluate them against a gold standard and
measure their impact on performance of statistical MT systems. Results show
accuracy of 99.1% and performance gains for MT of 0.039 BLEU on a
German-English noun phrase translation task.


title:
Experimental Software Schedulability Estimation For Varied Processor
  Frequencies

abstract:
  This paper describes a new approach to experimentally estimate the
application schedulability for various processor frequencies. We use additional
workload generated by an artificial high priority routine to simulate the
frequency decrease of a processor. Then we estimate the schedulability of
applications at different frequencies. The results of such estimation can be
used to determine the frequencies and control algorithms of dynamic voltage
scaling/dynamic frequency scaling (DVS/DFS) implementations. The paper presents
a general problem description, the proposed schedulability estimation method,
its analysis and evaluation.


title: Interest Rate Model Calibration Using Semidefinite Programming

abstract:
  We show that, for the purpose of pricing Swaptions, the Swap rate and the
corresponding Forward rates can be considered lognormal under a single
martingale measure. Swaptions can then be priced as options on a basket of
lognormal assets and an approximation formula is derived for such options. This
formula is centered around a Black-Scholes price with an appropriate
volatility, plus a correction term that can be interpreted as the expected
tracking error. The calibration problem can then be solved very efficiently
using semidefinite programming.