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

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


title: An Integrated Framework for Treebanks and Multilayer Annotations

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


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

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


title:
New Results on Monotone Dualization and Generating Hypergraph
  Transversals

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


title: On the Computational Complexity of Consistent Query Answers

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


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

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


title: Exploiting Synergy Between Ontologies and Recommender Systems

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


title: The Sketch of a Polymorphic Symphony

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


title: An Assessment of the Consistency for Software Measurement Methods

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


title: Design Patterns for Functional Strategic Programming

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


title: Making Abstract Domains Condensing

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


title: Solitaire Clobber

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


title: A Framework for Datatype Transformation

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


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

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


title:
Seven Dimensions of Portability for Language Documentation and
  Description

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


title: Factual and Legal Risks regarding wireless Computer Networks

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


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

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


title: Computational Phonology

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


title: The Geometric Maximum Traveling Salesman Problem

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


title: Phonology

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


title: Querying Databases of Annotated Speech

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


title: Integrating selectional preferences in WordNet

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


title: Decision Lists for English and Basque

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


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

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


title: Fast Hands-free Writing by Gaze Direction

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


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

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


title: Belief Revision and Rational Inference

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


title: Randomized selection revisited

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


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

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


title:
Semantic Properties for Lightweight Specification in Knowledgeable
  Development Environments

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


title: Semantic Component Composition

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


title: Kolmogorov's Structure Functions and Model Selection

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


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

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


title: Precongruence Formats for Decorated Trace Semantics

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


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

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


title: Trust Brokerage Systems for the Internet

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


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

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


title: Learning from Scarce Experience

abstract:
  Searching the space of policies directly for the optimal policy has been one
popular method for solving partially observable reinforcement learning
problems. Typically, with each change of the target policy, its value is
estimated from the results of following that very policy. This requires a large
number of interactions with the environment as different polices are
considered. We present a family of algorithms based on likelihood ratio
estimation that use data gathered when executing one policy (or collection of
policies) to estimate the value of a different policy. The algorithms combine
estimation and optimization stages. The former utilizes experience to build a
non-parametric representation of an optimized function. The latter performs
optimization on this estimate. We show positive empirical results and provide
the sample complexity bound.


title: Robust Global Localization Using Clustered Particle Filtering

abstract:
  Global mobile robot localization is the problem of determining a robot's pose
in an environment, using sensor data, when the starting position is unknown. A
family of probabilistic algorithms known as Monte Carlo Localization (MCL) is
currently among the most popular methods for solving this problem. MCL
algorithms represent a robot's belief by a set of weighted samples, which
approximate the posterior probability of where the robot is located by using a
Bayesian formulation of the localization problem. This article presents an
extension to the MCL algorithm, which addresses its problems when localizing in
highly symmetrical environments; a situation where MCL is often unable to
correctly track equally probable poses for the robot. The problem arises from
the fact that sample sets in MCL often become impoverished, when samples are
generated according to their posterior likelihood. Our approach incorporates
the idea of clusters of samples and modifies the proposal distribution
considering the probability mass of those clusters. Experimental results are
presented that show that this new extension to the MCL algorithm successfully
localizes in symmetric environments where ordinary MCL often fails.


title: Some applications of logic to feasibility in higher types

abstract:
  In this paper we demonstrate that the class of basic feasible functionals has
recursion theoretic properties which naturally generalize the corresponding
properties of the class of feasible functions. We also improve the Kapron -
Cook result on mashine representation of basic feasible functionals. Our proofs
are based on essential applications of logic. We introduce a weak fragment of
second order arithmetic with second order variables ranging over functions from
N into N which suitably characterizes basic feasible functionals, and show that
it is a useful tool for investigating the properties of basic feasible
functionals. In particular, we provide an example how one can extract feasible
"programs" from mathematical proofs which use non-feasible functionals (like
second order polynomials).


title: Optimal Aggregation Algorithms for Middleware

abstract:
  Let D be a database of N objects where each object has m fields. The objects
are given in m sorted lists (where the ith list is sorted according to the ith
field). Our goal is to find the top k objects according to a monotone
aggregation function t, while minimizing access to the lists. The problem
arises in several contexts. In particular Fagin (JCSS 1999) considered it for
the purpose of aggregating information in a multimedia database system.
  We are interested in instance optimality, i.e. that our algorithm will be as
good as any other (correct) algorithm on any instance. We provide and analyze
several instance optimal algorithms for the task, with various access costs and
models.


title: Sampling Strategies for Mining in Data-Scarce Domains

abstract:
  Data mining has traditionally focused on the task of drawing inferences from
large datasets. However, many scientific and engineering domains, such as fluid
dynamics and aircraft design, are characterized by scarce data, due to the
expense and complexity of associated experiments and simulations. In such
data-scarce domains, it is advantageous to focus the data collection effort on
only those regions deemed most important to support a particular data mining
objective. This paper describes a mechanism that interleaves bottom-up data
mining, to uncover multi-level structures in spatial data, with top-down
sampling, to clarify difficult decisions in the mining process. The mechanism
exploits relevant physical properties, such as continuity, correspondence, and
locality, in a unified framework. This leads to effective mining and sampling
decisions that are explainable in terms of domain knowledge and data
characteristics. This approach is demonstrated in two diverse applications --
mining pockets in spatial data, and qualitative determination of Jordan forms
of matrices.


title:
Economic-based Distributed Resource Management and Scheduling for Grid
  Computing

abstract:
  Computational Grids, emerging as an infrastructure for next generation
computing, enable the sharing, selection, and aggregation of geographically
distributed resources for solving large-scale problems in science, engineering,
and commerce. As the resources in the Grid are heterogeneous and geographically
distributed with varying availability and a variety of usage and cost policies
for diverse users at different times and, priorities as well as goals that vary
with time. The management of resources and application scheduling in such a
large and distributed environment is a complex task. This thesis proposes a
distributed computational economy as an effective metaphor for the management
of resources and application scheduling. It proposes an architectural framework
that supports resource trading and quality of services based scheduling. It
enables the regulation of supply and demand for resources and provides an
incentive for resource owners for participating in the Grid and motives the
users to trade-off between the deadline, budget, and the required level of
quality of service. The thesis demonstrates the capability of economic-based
systems for peer-to-peer distributed computing by developing users'
quality-of-service requirements driven scheduling strategies and algorithms. It
demonstrates their effectiveness by performing scheduling experiments on the
World-Wide Grid for solving parameter sweep applications.


title: Memory-Based Shallow Parsing

abstract:
  We present memory-based learning approaches to shallow parsing and apply
these to five tasks: base noun phrase identification, arbitrary base phrase
recognition, clause detection, noun phrase parsing and full parsing. We use
feature selection techniques and system combination methods for improving the
performance of the memory-based learner. Our approach is evaluated on standard
data sets and the results are compared with that of other systems. This reveals
that our approach works well for base phrase identification while its
application towards recognizing embedded structures leaves some room for
improvement.


title: Computing Homotopic Shortest Paths Efficiently

abstract:
  This paper addresses the problem of finding shortest paths homotopic to a
given disjoint set of paths that wind amongst point obstacles in the plane. We
present a faster algorithm than previously known.


title: Parrondo Strategies for Artificial Traders

abstract:
  On markets with receding prices, artificial noise traders may consider
alternatives to buy-and-hold. By simulating variations of the Parrondo
strategy, using real data from the Swedish stock market, we produce first
indications of a buy-low-sell-random Parrondo variation outperforming
buy-and-hold. Subject to our assumptions, buy-low-sell-random also outperforms
the traditional value and trend investor strategies. We measure the success of
the Parrondo variations not only through their performance compared to other
kinds of strategies, but also relative to varying levels of perfect
information, received through messages within a multi-agent system of
artificial traders.


title:
Required sample size for learning sparse Bayesian networks with many
  variables

abstract:
  Learning joint probability distributions on n random variables requires
exponential sample size in the generic case. Here we consider the case that a
temporal (or causal) order of the variables is known and that the (unknown)
graph of causal dependencies has bounded in-degree Delta. Then the joint
measure is uniquely determined by the probabilities of all (2 Delta+1)-tuples.
Upper bounds on the sample size required for estimating their probabilities can
be given in terms of the VC-dimension of the set of corresponding cylinder
sets. The sample size grows less than linearly with n.


title: Qualitative Analysis of Correspondence for Experimental Algorithmics

abstract:
  Correspondence identifies relationships among objects via similarities among
their components; it is ubiquitous in the analysis of spatial datasets,
including images, weather maps, and computational simulations. This paper
develops a novel multi-level mechanism for qualitative analysis of
correspondence. Operators leverage domain knowledge to establish
correspondence, evaluate implications for model selection, and leverage
identified weaknesses to focus additional data collection. The utility of the
mechanism is demonstrated in two applications from experimental algorithmics --
matrix spectral portrait analysis and graphical assessment of Jordan forms of
matrices. Results show that the mechanism efficiently samples computational
experiments and successfully uncovers high-level problem properties. It
overcomes noise and data sparsity by leveraging domain knowledge to detect
mutually reinforcing interpretations of spatial data.


title: Navigating the Small World Web by Textual Cues

abstract:
  Can a Web crawler efficiently locate an unknown relevant page? While this
question is receiving much empirical attention due to its considerable
commercial value in the search engine community
[Cho98,Chakrabarti99,Menczer00,Menczer01], theoretical efforts to bound the
performance of focused navigation have only exploited the link structure of the
Web graph, neglecting other features [Kleinberg01,Adamic01,Kim02]. Here I
investigate the connection between linkage and a content-induced topology of
Web pages, suggesting that efficient paths can be discovered by decentralized
navigation algorithms based on textual cues.


title:
Intelligent Search of Correlated Alarms for GSM Networks with
  Model-based Constraints

abstract:
  In order to control the process of data mining and focus on the things of
interest to us, many kinds of constraints have been added into the algorithms
of data mining. However, discovering the correlated alarms in the alarm
database needs deep domain constraints. Because the correlated alarms greatly
depend on the logical and physical architecture of networks. Thus we use the
network model as the constraints of algorithms, including Scope constraint,
Inter-correlated constraint and Intra-correlated constraint, in our proposed
algorithm called SMC (Search with Model-based Constraints). The experiments
show that the SMC algorithm with Inter-correlated or Intra-correlated
constraint is about two times faster than the algorithm with no constraints.


title: Trading Agents for Roaming Users

abstract:
  Some roaming users need services to manipulate autonomous processes. Trading
agents running on agent trade servers are used as a case in point. We present a
solution that provides the agent owners with means to upkeeping their desktop
environment, and maintaining their agent trade server processes, via a
briefcase service.


title: A Calculus for End-to-end Statistical Service Guarantees

abstract:
  The deterministic network calculus offers an elegant framework for
determining delays and backlog in a network with deterministic service
guarantees to individual traffic flows. This paper addresses the problem of
extending the network calculus to a probabilistic framework with statistical
service guarantees. Here, the key difficulty relates to expressing, in a
statistical setting, an end-to-end (network) service curve as a concatenation
of per-node service curves. The notion of an effective service curve is
developed as a probabilistic bound on the service received by an individual
flow. It is shown that per-node effective service curves can be concatenated to
yield a network effective service curve.


title: A Polynomial Description of the Rijndael Advanced Encryption Standard

abstract:
  The paper gives a polynomial description of the Rijndael Advanced Encryption
Standard recently adopted by the National Institute of Standards and
Technology. Special attention is given to the structure of the S-Box.


title: The prospects for mathematical logic in the twenty-first century

abstract:
  The four authors present their speculations about the future developments of
mathematical logic in the twenty-first century. The areas of recursion theory,
proof theory and logic for computer science, model theory, and set theory are
discussed independently.


title:
Weaves: A Novel Direct Code Execution Interface for Parallel High
  Performance Scientific Codes

abstract:
  Scientific codes are increasingly being used in compositional settings,
especially problem solving environments (PSEs). Typical compositional modeling
frameworks require significant buy-in, in the form of commitment to a
particular style of programming (e.g., distributed object components). While
this solution is feasible for newer generations of component-based scientific
codes, large legacy code bases present a veritable software engineering
nightmare. We introduce Weaves a novel framework that enables modeling,
composition, direct code execution, performance characterization, adaptation,
and control of unmodified high performance scientific codes. Weaves is an
efficient generalized framework for parallel compositional modeling that is a
proper superset of the threads and processes models of programming. In this
paper, our focus is on the transparent code execution interface enabled by
Weaves. We identify design constraints, their impact on implementation
alternatives, configuration scenarios, and present results from a prototype
implementation on Intel x86 architectures.


title:
PSPACE-Completeness of Sliding-Block Puzzles and Other Problems through
  the Nondeterministic Constraint Logic Model of Computation

abstract:
  We present a nondeterministic model of computation based on reversing edge
directions in weighted directed graphs with minimum in-flow constraints on
vertices. Deciding whether this simple graph model can be manipulated in order
to reverse the direction of a particular edge is shown to be PSPACE-complete by
a reduction from Quantified Boolean Formulas. We prove this result in a variety
of special cases including planar graphs and highly restricted vertex
configurations, some of which correspond to a kind of passive constraint logic.
Our framework is inspired by (and indeed a generalization of) the ``Generalized
Rush Hour Logic'' developed by Flake and Baum.
  We illustrate the importance of our model of computation by giving simple
reductions to show that several motion-planning problems are PSPACE-hard. Our
main result along these lines is that classic unrestricted sliding-block
puzzles are PSPACE-hard, even if the pieces are restricted to be all dominoes
(1x2 blocks) and the goal is simply to move a particular piece. No prior
complexity results were known about these puzzles. This result can be seen as a
strengthening of the existing result that the restricted Rush Hour puzzles are
PSPACE-complete, of which we also give a simpler proof. Finally, we strengthen
the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete,
by showing that it is PSPACE-complete even if no barriers are allowed.


title:
Unsupervised discovery of morphologically related words based on
  orthographic and semantic similarity

abstract:
  We present an algorithm that takes an unannotated corpus as its input, and
returns a ranked list of probable morphologically related pairs as its output.
The algorithm tries to discover morphologically related pairs by looking for
pairs that are both orthographically and semantically similar, where
orthographic similarity is measured in terms of minimum edit distance, and
semantic similarity is measured in terms of mutual information. The procedure
does not rely on a morpheme concatenation model, nor on distributional
properties of word substrings (such as affix frequency). Experiments with
German and English input give encouraging results, both in terms of precision
(proportion of good pairs found at various cutoff points of the ranked list),
and in terms of a qualitative analysis of the types of morphological patterns
discovered by the algorithm.


title: On-Line Paging against Adversarially Biased Random Inputs

abstract:
  In evaluating an algorithm, worst-case analysis can be overly pessimistic.
Average-case analysis can be overly optimistic. An intermediate approach is to
show that an algorithm does well on a broad class of input distributions.
Koutsoupias and Papadimitriou recently analyzed the least-recently-used (LRU)
paging strategy in this manner, analyzing its performance on an input sequence
generated by a so-called diffuse adversary -- one that must choose each request
probabilitistically so that no page is chosen with probability more than some
fixed epsilon>0. They showed that LRU achieves the optimal competitive ratio
(for deterministic on-line algorithms), but they didn't determine the actual
ratio.
  In this paper we estimate the optimal ratios within roughly a factor of two
for both deterministic strategies (e.g. least-recently-used and
first-in-first-out) and randomized strategies. Around the threshold epsilon ~
1/k (where k is the cache size), the optimal ratios are both Theta(ln k). Below
the threshold the ratios tend rapidly to O(1). Above the threshold the ratio is
unchanged for randomized strategies but tends rapidly to Theta(k) for
deterministic ones.
  We also give an alternate proof of the optimality of LRU.


title: Improved Bicriteria Existence Theorems for Scheduling

abstract:
  Two common objectives for evaluating a schedule are the makespan, or schedule
length, and the average completion time. This short note gives improved bounds
on the existence of schedules that simultaneously optimize both criteria. In
particular, for any rho> 0, there exists a schedule of makespan at most 1+rho
times the minimum, with average completion time at most (1-e)^rho times the
minimum. The proof uses an infininite-dimensional linear program to generalize
and strengthen a previous analysis by Cliff Stein and Joel Wein (1997).


title: Mostly-Unsupervised Statistical Segmentation of Japanese Kanji Sequences

abstract:
  Given the lack of word delimiters in written Japanese, word segmentation is
generally considered a crucial first step in processing Japanese texts. Typical
Japanese segmentation algorithms rely either on a lexicon and syntactic
analysis or on pre-segmented data; but these are labor-intensive, and the
lexico-syntactic techniques are vulnerable to the unknown word problem. In
contrast, we introduce a novel, more robust statistical method utilizing
unsegmented training data. Despite its simplicity, the algorithm yields
performance on long kanji sequences comparable to and sometimes surpassing that
of state-of-the-art morphological analyzers over a variety of error metrics.
The algorithm also outperforms another mostly-unsupervised statistical
algorithm previously proposed for Chinese.
  Additionally, we present a two-level annotation scheme for Japanese to
incorporate multiple segmentation granularities, and introduce two novel
evaluation metrics, both based on the notion of a compatible bracket, that can
account for multiple granularities simultaneously.


title: Approximate Data Structures with Applications

abstract:
  This paper explores the notion of approximate data structures, which return
approximately correct answers to queries, but run faster than their exact
counterparts. The paper describes approximate variants of the van Emde Boas
data structure, which support the same dynamic operations as the standard van
Emde Boas data structure (min, max, successor, predecessor, and existence
queries, as well as insertion and deletion), except that answers to queries are
approximate. The variants support all operations in constant time provided the
performance guarantee is 1+1/polylog(n), and in O(loglogn) time provided the
performance guarantee is 1+1/polynomial(n), for n elements in the data
structure.
  Applications described include Prim's minimum-spanning-tree algorithm,
Dijkstra's single-source shortest paths algorithm, and an on-line variant of
Graham's convex hull algorithm. To obtain output which approximates the desired
output with the performance guarantee tending to 1, Prim's algorithm requires
only linear time, Dijkstra's algorithm requires O(mloglogn) time, and the
on-line variant of Graham's algorithm requires constant amortized time per
operation.


title: On Strongly Connected Digraphs with Bounded Cycle Length

abstract:
  The MEG (minimum equivalent graph) problem is, given a directed graph, to
find a small subset of the edges that maintains all reachability relations
between nodes. The problem is NP-hard. This paper gives a proof that, for
graphs where each directed cycle has at most three edges, the MEG problem is
equivalent to maximum bipartite matching, and therefore solvable in polynomial
time. This leads to an improvement in the performance guarantee of the
previously best approximation algorithm for the general problem in
``Approximating the Minimum Equivalent Digraph'' (1995).


title: Polynomial-Time Approximation Scheme for Data Broadcast

abstract:
  The data broadcast problem is to find a schedule for broadcasting a given set
of messages over multiple channels. The goal is to minimize the cost of the
broadcast plus the expected response time to clients who periodically and
probabilistically tune in to wait for particular messages.
  The problem models disseminating data to clients in asymmetric communication
environments, where there is a much larger capacity from the information source
to the clients than in the reverse direction. Examples include satellites,
cable TV, internet broadcast, and mobile phones. Such environments favor the
``push-based'' model where the server broadcasts (pushes) its information on
the communication medium and multiple clients simultaneously retrieve the
specific information of individual interest.
  This paper presents the first polynomial-time approximation scheme (PTAS) for
data broadcast with O(1) channels and when each message has arbitrary
probability, unit length and bounded cost. The best previous polynomial-time
approximation algorithm for this case has a performance ratio of 9/8.


title: Computing stable models: worst-case performance estimates

abstract:
  We study algorithms for computing stable models of propositional logic
programs and derive estimates on their worst-case performance that are
asymptotically better than the trivial bound of O(m 2^n), where m is the size
of an input program and n is the number of its atoms. For instance, for
programs, whose clauses consist of at most two literals (counting the head) we
design an algorithm to compute stable models that works in time O(m\times
1.44225^n). We present similar results for several broader classes of programs,
as well.


title: Ultimate approximations in nonmonotonic knowledge representation systems

abstract:
  We study fixpoints of operators on lattices. To this end we introduce the
notion of an approximation of an operator. We order approximations by means of
a precision ordering. We show that each lattice operator O has a unique most
precise or ultimate approximation. We demonstrate that fixpoints of this
ultimate approximation provide useful insights into fixpoints of the operator
O.
  We apply our theory to logic programming and introduce the ultimate
Kripke-Kleene, well-founded and stable semantics. We show that the ultimate
Kripke-Kleene and well-founded semantics are more precise then their standard
counterparts We argue that ultimate semantics for logic programming have
attractive epistemological properties and that, while in general they are
computationally more complex than the standard semantics, for many classes of
theories, their complexity is no worse.


title: Instabilities of Robot Motion

abstract:
  Instabilities of robot motion are caused by topological reasons. In this
paper we find a relation between the topological properties of a configuration
space (the structure of its cohomology algebra) and the character of
instabilities, which are unavoidable in any motion planning algorithm. More
specifically, let $X$ denote the space of all admissible configurations of a
mechanical system. A {\it motion planner} is given by a splitting $X\times X =
F_1\cup F_2\cup ... \cup F_k$ (where $F_1, ..., F_k$ are pairwise disjoint
ENRs, see below) and by continuous maps $s_j: F_j \to PX,$ such that $E\circ
s_j =1_{F_j}$. Here $PX$ denotes the space of all continuous paths in $X$
(admissible motions of the system) and $E: PX\to X\times X$ denotes the map
which assigns to a path the pair of its initial -- end points. Any motion
planner determines an algorithm of motion planning for the system. In this
paper we apply methods of algebraic topology to study the minimal number of
sets $F_j$ in any motion planner in $X$. We also introduce a new notion of {\it
order of instability} of a motion planner; it describes the number of
essentially distinct motions which may occur as a result of small perturbations
of the input data. We find the minimal order of instability, which may have
motion planners on a given configuration space $X$. We study a number of
specific problems: motion of a rigid body in $\R^3$, a robot arm, motion in
$\R^3$ in the presence of obstacles, and others.


title: From Alife Agents to a Kingdom of N Queens

abstract:
  This paper presents a new approach to solving N-queen problems, which
involves a model of distributed autonomous agents with artificial life (ALife)
and a method of representing N-queen constraints in an agent environment. The
distributed agents locally interact with their living environment, i.e., a
chessboard, and execute their reactive behaviors by applying their behavioral
rules for randomized motion, least-conflict position searching, and cooperating
with other agents etc. The agent-based N-queen problem solving system evolves
through selection and contest according to the rule of Survival of the Fittest,
in which some agents will die or be eaten if their moving strategies are less
efficient than others. The experimental results have shown that this system is
capable of solving large-scale N-queen problems. This paper also provides a
model of ALife agents for solving general CSPs.


title: Ellogon: A New Text Engineering Platform

abstract:
  This paper presents Ellogon, a multi-lingual, cross-platform, general-purpose
text engineering environment. Ellogon was designed in order to aid both
researchers in natural language processing, as well as companies that produce
language engineering systems for the end-user. Ellogon provides a powerful
TIPSTER-based infrastructure for managing, storing and exchanging textual data,
embedding and managing text processing components as well as visualising
textual data and their associated linguistic information. Among its key
features are full Unicode support, an extensive multi-lingual graphical user
interface, its modular architecture and the reduced hardware requirements.


title: Typed Generic Traversal With Term Rewriting Strategies

abstract:
  A typed model of strategic term rewriting is developed. The key innovation is
that generic traversal is covered. To this end, we define a typed rewriting
calculus S'_{gamma}. The calculus employs a many-sorted type system extended by
designated generic strategy types gamma. We consider two generic strategy
types, namely the types of type-preserving and type-unifying strategies.
S'_{gamma} offers traversal combinators to construct traversals or schemes
thereof from many-sorted and generic strategies. The traversal combinators
model different forms of one-step traversal, that is, they process the
immediate subterms of a given term without anticipating any scheme of recursion
into terms. To inhabit generic types, we need to add a fundamental combinator
to lift a many-sorted strategy $s$ to a generic type gamma. This step is called
strategy extension. The semantics of the corresponding combinator states that s
is only applied if the type of the term at hand fits, otherwise the extended
strategy fails. This approach dictates that the semantics of strategy
application must be type-dependent to a certain extent. Typed strategic term
rewriting with coverage of generic term traversal is a simple but expressive
model of generic programming. It has applications in program transformation and
program analysis.


title:
Distance function wavelets - Part I: Helmholtz and convection-diffusion
  transforms and series

abstract:
  This report aims to present my research updates on distance function wavelets
(DFW) based on the fundamental solutions and the general solutions of the
Helmholtz, modified Helmholtz, and convection-diffusion equations, which
include the isotropic Helmholtz-Fourier (HF) transform and series, the
Helmholtz-Laplace (HL) transform, and the anisotropic convection-diffusion
wavelets and ridgelets. The latter is set to handle discontinuous and track
data problems. The edge effect of the HF series is addressed. Alternative
existence conditions for the DFW transforms are proposed and discussed. To
simplify and streamline the expression of the HF and HL transforms, a new
dimension-dependent function notation is introduced. The HF series is also used
to evaluate the analytical solutions of linear diffusion problems of arbitrary
dimensionality and geometry. The weakness of this report is lacking of rigorous
mathematical analysis due to the author's limited mathematical knowledge.


title: A quasi-RBF technique for numerical discretization of PDE's

abstract:
  Atkinson developed a strategy which splits solution of a PDE system into
homogeneous and particular solutions, where the former have to satisfy the
boundary and governing equation, while the latter only need to satisfy the
governing equation without concerning geometry. Since the particular solution
can be solved irrespective of boundary shape, we can use a readily available
fast Fourier or orthogonal polynomial technique O(NlogN) to evaluate it in a
regular box or sphere surrounding physical domain. The distinction of this
study is that we approximate homogeneous solution with nonsingular general
solution RBF as in the boundary knot method. The collocation method using
general solution RBF has very high accuracy and spectral convergent speed and
is a simple, truly meshfree approach for any complicated geometry. More
importantly, the use of nonsingular general solution avoids the controversial
artificial boundary in the method of fundamental solution due to the
singularity of fundamental solution.


title: An Overview of a Grid Architecture for Scientific Computing

abstract:
  This document gives an overview of a Grid testbed architecture proposal for
the NorduGrid project. The aim of the project is to establish an inter-Nordic
testbed facility for implementation of wide area computing and data handling.
The architecture is supposed to define a Grid system suitable for solving data
intensive problems at the Large Hadron Collider at CERN. We present the various
architecture components needed for such a system. After that we go on to give a
description of the dynamics by showing the task flow.


title: The Traits of the Personable

abstract:
  Information personalization is fertile ground for application of AI
techniques. In this article I relate personalization to the ability to capture
partial information in an information-seeking interaction. The specific focus
is on personalizing interactions at web sites. Using ideas from partial
evaluation and explanation-based generalization, I present a modeling
methodology for reasoning about personalization. This approach helps identify
seven tiers of `personable traits' in web sites.


title: Performance evaluation of the GridFTP within the NorduGrid project

abstract:
  This report presents results of the tests measuring the performance of
multi-threaded file transfers, using the GridFTP implementation of the Globus
project over the NorduGrid network resources. Point to point WAN tests, carried
out between the sites of Copenhagen, Lund, Oslo and Uppsala, are described. It
was found that multiple threaded download via the high performance GridFTP
protocol can significantly improve file transfer performance, and can serve as
a reliable data


title:
A (non)static 0-order statistical model and its implementation for
  compressing virtually uncompressible data

abstract:
  We give an implementation of a statistical model, which can be successfully
applied for compressing of a sequence of binary digits with behavior close to
random.


title: Bootstrapping Structure into Language: Alignment-Based Learning

abstract:
  This thesis introduces a new unsupervised learning framework, called
Alignment-Based Learning, which is based on the alignment of sentences and
Harris's (1951) notion of substitutability. Instances of the framework can be
applied to an untagged, unstructured corpus of natural language sentences,
resulting in a labelled, bracketed version of that corpus.
  Firstly, the framework aligns all sentences in the corpus in pairs, resulting
in a partition of the sentences consisting of parts of the sentences that are
equal in both sentences and parts that are unequal. Unequal parts of sentences
can be seen as being substitutable for each other, since substituting one
unequal part for the other results in another valid sentence. The unequal parts
of the sentences are thus considered to be possible (possibly overlapping)
constituents, called hypotheses.
  Secondly, the selection learning phase considers all hypotheses found by the
alignment learning phase and selects the best of these. The hypotheses are
selected based on the order in which they were found, or based on a
probabilistic function.
  The framework can be extended with a grammar extraction phase. This extended
framework is called parseABL. Instead of returning a structured version of the
unstructured input corpus, like the ABL system, this system also returns a
stochastic context-free or tree substitution grammar.
  Different instances of the framework have been tested on the English ATIS
corpus, the Dutch OVIS corpus and the Wall Street Journal corpus. One of the
interesting results, apart from the encouraging numerical results, is that all
instances can (and do) learn recursive structures.


title: Monads for natural language semantics

abstract:
  Accounts of semantic phenomena often involve extending types of meanings and
revising composition rules at the same time. The concept of monads allows many
such accounts -- for intensionality, variable binding, quantification and focus
-- to be stated uniformly and compositionally.


title: A variable-free dynamic semantics

abstract:
  I propose a variable-free treatment of dynamic semantics. By "dynamic
semantics" I mean analyses of donkey sentences ("Every farmer who owns a donkey
beats it") and other binding and anaphora phenomena in natural language where
meanings of constituents are updates to information states, for instance as
proposed by Groenendijk and Stokhof. By "variable-free" I mean denotational
semantics in which functional combinators replace variable indices and
assignment functions, for instance as advocated by Jacobson.
  The new theory presented here achieves a compositional treatment of dynamic
anaphora that does not involve assignment functions, and separates the
combinatorics of variable-free semantics from the particular linguistic
phenomena it treats. Integrating variable-free semantics and dynamic semantics
gives rise to interactions that make new empirical predictions, for example
"donkey weak crossover" effects.


title: NLTK: The Natural Language Toolkit

abstract:
  NLTK, the Natural Language Toolkit, is a suite of open source program
modules, tutorials and problem sets, providing ready-to-use computational
linguistics courseware. NLTK covers symbolic and statistical natural language
processing, and is interfaced to annotated corpora. Students augment and
replace existing components, learn structured programming by example, and
manipulate sophisticated models from the outset.


title: A Codebook Generation Algorithm for Document Image Compression

abstract:
  Pattern-matching-based document-compression systems (e.g. for faxing) rely on
finding a small set of patterns that can be used to represent all of the ink in
the document. Finding an optimal set of patterns is NP-hard; previous
compression schemes have resorted to heuristics. This paper describes an
extension of the cross-entropy approach, used previously for measuring pattern
similarity, to this problem. This approach reduces the problem to a k-medians
problem, for which the paper gives a new algorithm with a provably good
performance guarantee. In comparison to previous heuristics (First Fit, with
and without generalized Lloyd's/k-means postprocessing steps), the new
algorithm generates a better codebook, resulting in an overall improvement in
compression performance of almost 17%.


title: Approximation Algorithms for Covering/Packing Integer Programs

abstract:
  Given matrices A and B and vectors a, b, c and d, all with non-negative
entries, we consider the problem of computing min {c.x: x in Z^n_+, Ax > a, Bx
< b, x < d}. We give a bicriteria-approximation algorithm that, given epsilon
in (0, 1], finds a solution of cost O(ln(m)/epsilon^2) times optimal, meeting
the covering constraints (Ax > a) and multiplicity constraints (x < d), and
satisfying Bx < (1 + epsilon)b + beta, where beta is the vector of row sums
beta_i = sum_j B_ij. Here m denotes the number of rows of A.
  This gives an O(ln m)-approximation algorithm for CIP -- minimum-cost
covering integer programs with multiplicity constraints, i.e., the special case
when there are no packing constraints Bx < b. The previous best approximation
ratio has been O(ln(max_j sum_i A_ij)) since 1982. CIP contains the set cover
problem as a special case, so O(ln m)-approximation is the best possible unless
P=NP.


title: Lecture Notes on Evasiveness of Graph Properties

abstract:
  This report presents notes from the first eight lectures of the class Many
Models of Complexity taught by Laszlo Lovasz at Princeton University in the
fall of 1990. The topic is evasiveness of graph properties: given a graph
property, how many edges of the graph an algorithm must check in the worst case
before it knows whether the property holds.


title: On-Line End-to-End Congestion Control

abstract:
  Congestion control in the current Internet is accomplished mainly by TCP/IP.
To understand the macroscopic network behavior that results from TCP/IP and
similar end-to-end protocols, one main analytic technique is to show that the
the protocol maximizes some global objective function of the network traffic.
Here we analyze a particular end-to-end, MIMD (multiplicative-increase,
multiplicative-decrease) protocol. We show that if all users of the network use
the protocol, and all connections last for at least logarithmically many
rounds, then the total weighted throughput (value of all packets received) is
near the maximum possible. Our analysis includes round-trip-times, and (in
contrast to most previous analyses) gives explicit convergence rates, allows
connections to start and stop, and allows capacities to change.


title: On-Line File Caching

abstract:
  In the on-line file-caching problem problem, the input is a sequence of
requests for files, given on-line (one at a time). Each file has a non-negative
size and a non-negative retrieval cost. The problem is to decide which files to
keep in a fixed-size cache so as to minimize the sum of the retrieval costs for
files that are not in the cache when requested. The problem arises in web
caching by browsers and by proxies. This paper describes a natural
generalization of LRU called Landlord and gives an analysis showing that it has
an optimal performance guarantee (among deterministic on-line algorithms).
  The paper also gives an analysis of the algorithm in a so-called ``loosely''
competitive model, showing that on a ``typical'' cache size, either the
performance guarantee is O(1) or the total retrieval cost is insignificant.


title:
Data-Collection for the Sloan Digital Sky Survey: a Network-Flow
  Heuristic

abstract:
  The goal of the Sloan Digital Sky Survey is ``to map in detail one-quarter of
the entire sky, determining the positions and absolute brightnesses of more
than 100 million celestial objects''. The survey will be performed by taking
``snapshots'' through a large telescope. Each snapshot can capture up to 600
objects from a small circle of the sky. This paper describes the design and
implementation of the algorithm that is being used to determine the snapshots
so as to minimize their number. The problem is NP-hard in general; the
algorithm described is a heuristic, based on Lagriangian-relaxation and
min-cost network flow. It gets within 5-15% of a naive lower bound, whereas
using a ``uniform'' cover only gets within 25-35%.


title:
Simple Strategies for Large Zero-Sum Games with Applications to
  Complexity Theory

abstract:
  Von Neumann's Min-Max Theorem guarantees that each player of a zero-sum
matrix game has an optimal mixed strategy. This paper gives an elementary proof
that each player has a near-optimal mixed strategy that chooses uniformly at
random from a multiset of pure strategies of size logarithmic in the number of
pure strategies available to the opponent.
  For exponentially large games, for which even representing an optimal mixed
strategy can require exponential space, it follows that there are near-optimal,
linear-size strategies. These strategies are easy to play and serve as small
witnesses to the approximate value of the game.
  As a corollary, it follows that every language has small ``hard'' multisets
of inputs certifying that small circuits can't decide the language. For
example, if SAT does not have polynomial-size circuits, then, for each n and c,
there is a set of n^(O(c)) Boolean formulae of size n such that no circuit of
size n^c (or algorithm running in time n^c) classifies more than two-thirds of
the formulae succesfully.


title: Randomized Rounding without Solving the Linear Program

abstract:
  Randomized rounding is a standard method, based on the probabilistic method,
for designing combinatorial approximation algorithms. In Raghavan's seminal
paper introducing the method (1988), he writes: "The time taken to solve the
linear program relaxations of the integer programs dominates the net running
time theoretically (and, most likely, in practice as well)."
  This paper explores how this bottleneck can be avoided for randomized
rounding algorithms for packing and covering problems (linear programs, or
mixed integer linear programs, having no negative coefficients). The resulting
algorithms are greedy algorithms, and are faster and simpler to implement than
standard randomized-rounding algorithms.
  This approach can also be used to understand Lagrangian-relaxation algorithms
for packing/covering linear programs: such algorithms can be viewed as as
(derandomized) randomized-rounding schemes.


title:
A Primal-Dual Parallel Approximation Technique Applied to Weighted Set
  and Vertex Cover

abstract:
  The paper describes a simple deterministic parallel/distributed
(2+epsilon)-approximation algorithm for the minimum-weight vertex-cover problem
and its dual (edge/element packing).


title: Competitive Paging Algorithms

abstract:
  The paging problem is that of deciding which pages to keep in a memory of k
pages in order to minimize the number of page faults. This paper introduces the
marking algorithm, a simple randomized on-line algorithm for the paging
problem, and gives a proof that its performance guarantee (competitive ratio)
is O(log k). In contrast, no deterministic on-line algorithm can have a
performance guarantee better than k.


title: Sequential and Parallel Algorithms for Mixed Packing and Covering

abstract:
  Mixed packing and covering problems are problems that can be formulated as
linear programs using only non-negative coefficients. Examples include
multicommodity network flow, the Held-Karp lower bound on TSP, fractional
relaxations of set cover, bin-packing, knapsack, scheduling problems,
minimum-weight triangulation, etc. This paper gives approximation algorithms
for the general class of problems. The sequential algorithm is a simple greedy
algorithm that can be implemented to find an epsilon-approximate solution in
O(epsilon^-2 log m) linear-time iterations. The parallel algorithm does
comparable work but finishes in polylogarithmic time.
  The results generalize previous work on pure packing and covering (the
special case when the constraints are all "less-than" or all "greater-than") by
Michael Luby and Noam Nisan (1993) and Naveen Garg and Jochen Konemann (1998).


title: Approximating the Minimum Equivalent Digraph

abstract:
  The MEG (minimum equivalent graph) problem is, given a directed graph, to
find a small subset of the edges that maintains all reachability relations
between nodes. The problem is NP-hard. This paper gives an approximation
algorithm with performance guarantee of pi^2/6 ~ 1.64. The algorithm and its
analysis are based on the simple idea of contracting long cycles. (This result
is strengthened slightly in ``On strongly connected digraphs with bounded cycle
length'' (1996).) The analysis applies directly to 2-Exchange, a simple ``local
improvement'' algorithm, showing that its performance guarantee is 1.75.


title: Faster Parametric Shortest Path and Minimum Balance Algorithms

abstract:
  The parametric shortest path problem is to find the shortest paths in graph
where the edge costs are of the form w_ij+lambda where each w_ij is constant
and lambda is a parameter that varies. The problem is to find shortest path
trees for every possible value of lambda.
  The minimum-balance problem is to find a ``weighting'' of the vertices so
that adjusting the edge costs by the vertex weights yields a graph in which,
for every cut, the minimum weight of any edge crossing the cut in one direction
equals the minimum weight of any edge crossing the cut in the other direction.
  The paper presents fast algorithms for both problems. The algorithms run in
O(nm+n^2 log n) time. The paper also describes empirical studies of the
algorithms on random graphs, suggesting that the expected time for finding a
minimum-mean cycle (an important special case of both problems) is O(n log(n) +
m).


title: Orienting Graphs to Optimize Reachability

abstract:
  The paper focuses on two problems: (i) how to orient the edges of an
undirected graph in order to maximize the number of ordered vertex pairs (x,y)
such that there is a directed path from x to y, and (ii) how to orient the
edges so as to minimize the number of such pairs. The paper describes a
quadratic-time algorithm for the first problem, and a proof that the second
problem is NP-hard to approximate within some constant 1+epsilon > 1. The
latter proof also shows that the second problem is equivalent to
``comparability graph completion''; neither problem was previously known to be
NP-hard.


title: Low-Degree Spanning Trees of Small Weight

abstract:
  The degree-d spanning tree problem asks for a minimum-weight spanning tree in
which the degree of each vertex is at most d. When d=2 the problem is TSP, and
in this case, the well-known Christofides algorithm provides a
1.5-approximation algorithm (assuming the edge weights satisfy the triangle
inequality).
  In 1984, Christos Papadimitriou and Umesh Vazirani posed the challenge of
finding an algorithm with performance guarantee less than 2 for Euclidean
graphs (points in R^n) and d > 2. This paper gives the first answer to that
challenge, presenting an algorithm to compute a degree-3 spanning tree of cost
at most 5/3 times the MST. For points in the plane, the ratio improves to 3/2
and the algorithm can also find a degree-4 spanning tree of cost at most 5/4
times the MST.


title: The K-Server Dual and Loose Competitiveness for Paging

abstract:
  This paper has two results. The first is based on the surprising observation
that the well-known ``least-recently-used'' paging algorithm and the
``balance'' algorithm for weighted caching are linear-programming primal-dual
algorithms. This observation leads to a strategy (called ``Greedy-Dual'') that
generalizes them both and has an optimal performance guarantee for weighted
caching.
  For the second result, the paper presents empirical studies of paging
algorithms, documenting that in practice, on ``typical'' cache sizes and
sequences, the performance of paging strategies are much better than their
worst-case analyses in the standard model suggest. The paper then presents
theoretical results that support and explain this. For example: on any input
sequence, with almost all cache sizes, either the performance guarantee of
least-recently-used is O(log k) or the fault rate (in an absolute sense) is
insignificant.
  Both of these results are strengthened and generalized in``On-line File
Caching'' (1998).


title: Balancing Minimum Spanning and Shortest Path Trees

abstract:
  This paper give a simple linear-time algorithm that, given a weighted
digraph, finds a spanning tree that simultaneously approximates a shortest-path
tree and a minimum spanning tree. The algorithm provides a continuous
trade-off: given the two trees and epsilon > 0, the algorithm returns a
spanning tree in which the distance between any vertex and the root of the
shortest-path tree is at most 1+epsilon times the shortest-path distance, and
yet the total weight of the tree is at most 1+2/epsilon times the weight of a
minimum spanning tree. This is the best tradeoff possible. The paper also
describes a fast parallel implementation.


title:
On the Number of Iterations for Dantzig-Wolfe Optimization and
  Packing-Covering Approximation Algorithms

abstract:
  We give a lower bound on the iteration complexity of a natural class of
Lagrangean-relaxation algorithms for approximately solving packing/covering
linear programs. We show that, given an input with $m$ random 0/1-constraints
on $n$ variables, with high probability, any such algorithm requires
$\Omega(\rho \log(m)/\epsilon^2)$ iterations to compute a
$(1+\epsilon)$-approximate solution, where $\rho$ is the width of the input.
The bound is tight for a range of the parameters $(m,n,\rho,\epsilon)$.
  The algorithms in the class include Dantzig-Wolfe decomposition, Benders'
decomposition, Lagrangean relaxation as developed by Held and Karp [1971] for
lower-bounding TSP, and many others (e.g. by Plotkin, Shmoys, and Tardos [1988]
and Grigoriadis and Khachiyan [1996]). To prove the bound, we use a discrepancy
argument to show an analogous lower bound on the support size of
$(1+\epsilon)$-approximate mixed strategies for random two-player zero-sum
0/1-matrix games.


title: K-Medians, Facility Location, and the Chernoff-Wald Bound

abstract:
  The paper gives approximation algorithms for the k-medians and
facility-location problems (both NP-hard). For k-medians, the algorithm returns
a solution using at most ln(n+n/epsilon)k medians and having cost at most
(1+epsilon) times the cost of the best solution that uses at most k medians.
Here epsilon > 0 is an input to the algorithm. In comparison, the best previous
algorithm (Jyh-Han Lin and Jeff Vitter, 1992) had a (1+1/epsilon)ln(n) term
instead of the ln(n+n/epsilon) term in the performance guarantee. For facility
location, the algorithm returns a solution of cost at most d+ln(n) k, provided
there exists a solution of cost d+k where d is the assignment cost and k is the
facility cost. In comparison, the best previous algorithm (Dorit Hochbaum,
1982) returned a solution of cost at most ln(n)(d+k). For both problems, the
algorithms currently provide the best performance guarantee known for the
general (non-metric) problems.
  The paper also introduces a new probabilistic bound (called "Chernoff-Wald
bound") for bounding the expectation of the maximum of a collection of sums of
random variables, when each sum contains a random number of terms. The bound is
used to analyze the randomized rounding scheme that underlies the algorithms.


title: Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme

abstract:
  We give a polynomial-time approximation scheme for the generalization of
Huffman Coding in which codeword letters have non-uniform costs (as in Morse
code, where the dash is twice as long as the dot). The algorithm computes a
(1+epsilon)-approximate solution in time O(n + f(epsilon) log^3 n), where n is
the input size.


title: Prefix Codes: Equiprobable Words, Unequal Letter Costs

abstract:
  Describes a near-linear-time algorithm for a variant of Huffman coding, in
which the letters may have non-uniform lengths (as in Morse code), but with the
restriction that each word to be encoded has equal probability. [See also
``Huffman Coding with Unequal Letter Costs'' (2002).]


title:
A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning
  Trees

abstract:
  The problem considered is the following. Given a graph with edge weights
satisfying the triangle inequality, and a degree bound for each vertex, compute
a low-weight spanning tree such that the degree of each vertex is at most its
specified bound. The problem is NP-hard (it generalizes Traveling Salesman
(TSP)). This paper describes a network-flow heuristic for modifying a given
tree T to meet the constraints. Choosing T to be a minimum spanning tree (MST)
yields approximation algorithms with performance guarantee less than 2 for the
problem on geometric graphs with L_p-norms. The paper also describes a
Euclidean graph whose minimum TSP costs twice the MST, disproving a conjecture
made in ``Low-Degree Spanning Trees of Small Weight'' (1996).


title: Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut

abstract:
  The multiway-cut problem is, given a weighted graph and k >= 2 terminal
nodes, to find a minimum-weight set of edges whose removal separates all the
terminals. The problem is NP-hard, and even NP-hard to approximate within
1+delta for some small delta > 0.
  Calinescu, Karloff, and Rabani (1998) gave an algorithm with performance
guarantee 3/2-1/k, based on a geometric relaxation of the problem. In this
paper, we give improved randomized rounding schemes for their relaxation,
yielding a 12/11-approximation algorithm for k=3 and a 1.3438-approximation
algorithm in general.
  Our approach hinges on the observation that the problem of designing a
randomized rounding scheme for a geometric relaxation is itself a linear
programming problem. The paper explores computational solutions to this
problem, and gives a proof that for a general class of geometric relaxations,
there are always randomized rounding schemes that match the integrality gap.


title: Three-Tiered Specification of Micro-Architectures

abstract:
  A three-tiered specification approach is developed to formally specify
collections of collaborating objects, say micro-architectures. (i) The
structural properties to be maintained in the collaboration are specified in
the lowest tier. (ii) The behaviour of the object methods in the classes is
specified in the middle tier. (iii) The interaction of the objects in the
micro-architecture is specified in the third tier. The specification approach
is based on Larch and accompanying notations and tools. The approach enables
the unambiguous and complete specification of reusable collections of
collaborating objects. The layered, formal approach is compared to other
approaches including the mainstream UML approach.


title:
Sotto Voce: Exploring the Interplay of Conversation and Mobile Audio
  Spaces

abstract:
  In addition to providing information to individual visitors, electronic
guidebooks have the potential to facilitate social interaction between visitors
and their companions. However, many systems impede visitor interaction. By
contrast, our electronic guidebook, Sotto Voce, has social interaction as a
primary design goal. The system enables visitors to share audio information -
specifically, they can hear each other's guidebook activity using a
technologically mediated audio eavesdropping mechanism. We conducted a study of
visitors using Sotto Voce while touring a historic house. The results indicate
that visitors are able to use the system effectively, both as a conversational
resource and as an information appliance. More surprisingly, our results
suggest that the technologically mediated audio often cohered the visitors'
conversation and activity to a far greater degree than audio delivered through
the open air.


title:
Eavesdropping on Electronic Guidebooks: Observing Learning Resources in
  Shared Listening Environments

abstract:
  We describe an electronic guidebook, Sotto Voce, that enables visitors to
share audio information by eavesdropping on each other's guidebook activity. We
have conducted three studies of visitors using electronic guidebooks in a
historic house: one study with open air audio played through speakers and two
studies with eavesdropped audio. An analysis of visitor interaction in these
studies suggests that eavesdropped audio provides more social and interactive
learning resources than open air audio played through speakers.


title:
Practical Strategies for Integrating a Conversation Analyst in an
  Iterative Design Process

abstract:
  We present a case study of an iterative design process that includes a
conversation analyst. We discuss potential benefits of conversation analysis
for design, and we describe our strategies for integrating the conversation
analyst in the design process. Since the analyst on our team had no previous
exposure to design or engineering, and none of the other members of our team
had any experience with conversation analysis, we needed to build a foundation
for our interaction. One of our key strategies was to pair the conversation
analyst with a designer in a highly interactive collaboration. Our tactics have
been effective on our project, leading to valuable results that we believe we
could not have obtained using another method. We hope that this paper can serve
as a practical guide to those interested in establishing a productive and
efficient working relationship between a conversation analyst and the other
members of a design team.


title: Parameterized Intractability of Motif Search Problems

abstract:
  We show that Closest Substring, one of the most important problems in the
field of biological sequence analysis, is W[1]-hard when parameterized by the
number k of input strings (and remains so, even over a binary alphabet). This
problem is therefore unlikely to be solvable in time O(f(k)\cdot n^{c}) for any
function f of k and constant c independent of k. The problem can therefore be
expected to be intractable, in any practical sense, for k>=3. Our result
supports the intuition that Closest Substring is computationally much harder
than the special case of Closest String, although both problems are
NP-complete. We also prove W[1]-hardness for other parameterizations in the
case of unbounded alphabet size. Our W[1]-hardness result for Closest Substring
generalizes to Consensus Patterns, a problem of similar significance in
computational biology.


title: Unsupervised Discovery of Morphemes

abstract:
  We present two methods for unsupervised segmentation of words into
morpheme-like units. The model utilized is especially suited for languages with
a rich morphology, such as Finnish. The first method is based on the Minimum
Description Length (MDL) principle and works online. In the second method,
Maximum Likelihood (ML) optimization is used. The quality of the segmentations
is measured using an evaluation method that compares the segmentations produced
to an existing morphological analysis. Experiments on both Finnish and English
corpora show that the presented methods perform well compared to a current
state-of-the-art system.


title: Content Distribution in Unicast Replica Meshes

abstract:
  We propose centralized algorithm of data distribution in the unicast p2p
network. Good example of such networks are meshes of WWW and FTP mirrors.
Simulation of data propogation for different network topologies is performed
and it is shown that proposed method performs up to 200% better then common
apporaches


title: A Connection-Centric Survey of Recommender Systems Research

abstract:
  Recommender systems attempt to reduce information overload and retain
customers by selecting a subset of items from a universal set based on user
preferences. While research in recommender systems grew out of information
retrieval and filtering, the topic has steadily advanced into a legitimate and
challenging research area of its own. Recommender systems have traditionally
been studied from a content-based filtering vs. collaborative design
perspective. Recommendations, however, are not delivered within a vacuum, but
rather cast within an informal community of users and social context.
Therefore, ultimately all recommender systems make connections among people and
thus should be surveyed from such a perspective. This viewpoint is
under-emphasized in the recommender systems literature. We therefore take a
connection-oriented viewpoint toward recommender systems research. We posit
that recommendation has an inherently social element and is ultimately intended
to connect people either directly as a result of explicit user modeling or
indirectly through the discovery of relationships implicit in extant data.
Thus, recommender systems are characterized by how they model users to bring
people together: explicitly or implicitly. Finally, user modeling and the
connection-centric viewpoint raise broadening and social issues--such as
evaluation, targeting, and privacy and trust--which we also briefly address.


title: Optimizing Queries Using a Meta-level Database

abstract:
  Graph simulation (using graph schemata or data guides) has been successfully
proposed as a technique for adding structure to semistructured data. Design
patterns for description (such as meta-classes and homomorphisms between schema
layers), which are prominent in the object-oriented programming community,
constitute a generalization of this graph simulation approach.
  In this paper, we show description applicable to a wide range of data models
that have some notion of object (-identity), and propose to turn it into a data
model primitive much like, say, inheritance. We argue that such an extension
fills a practical need in contemporary data management. Then, we present
algebraic techniques for query optimization (using the notions of described and
description queries). Finally, in the semistructured setting, we discuss the
pruning of regular path queries (with nested conditions) using description
meta-data. In this context, our notion of meta-data extends graph schemata and
data guides by meta-level values, allowing to boost query performance and to
reduce the redundancy of data.


title: Aging, double helix and small world property in genetic algorithms

abstract:
  Over a quarter of century after the invention of genetic algorithms and
miriads of their modifications, as well as successful implementations, we are
still lacking many essential details of thorough analysis of it's inner
working. One of such fundamental questions is: how many generations do we need
to solve the optimization problem? This paper tries to answer this question,
albeit in a fuzzy way, making use of the double helix concept. As a byproduct
we gain better understanding of the ways, in which the genetic algorithm may be
fine tuned.