title: Communities of Practice in the Distributed International Environment

abstract:
  Modern commercial organisations are facing pressures which have caused them
to lose personnel. When they lose people, they also lose their knowledge.
Organisations also have to cope with the internationalisation of business
forcing collaboration and knowledge sharing across time and distance. Knowledge
Management (KM) claims to tackle these issues. This paper looks at an area
where KM does not offer sufficient support, that is, the sharing of knowledge
that is not easy to articulate.
  The focus in this paper is on Communities of Practice in commercial
organisations. We do this by exploring knowledge sharing in Lave and Wenger's
[1] theory of Communities of Practice and investigating how Communities of
Practice may translate to a distributed international environment. The paper
reports on two case studies that explore the functioning of Communities of
Practice across international boundaries.


title: A Classification of Symbolic Transition Systems

abstract:
  We define five increasingly comprehensive classes of infinite-state systems,
called STS1--5, whose state spaces have finitary structure. For four of these
classes, we provide examples from hybrid systems.


title: On the problem of computing the well-founded semantics

abstract:
  The well-founded semantics is one of the most widely studied and used
semantics of logic programs with negation. In the case of finite propositional
programs, it can be computed in polynomial time, more specifically, in
O(|At(P)|size(P)) steps, where size(P) denotes the total number of occurrences
of atoms in a logic program P. This bound is achieved by an algorithm
introduced by Van Gelder and known as the alternating-fixpoint algorithm.
Improving on the alternating-fixpoint algorithm turned out to be difficult. In
this paper we study extensions and modifications of the alternating-fixpoint
approach. We then restrict our attention to the class of programs whose rules
have no more than one positive occurrence of an atom in their bodies. For
programs in that class we propose a new implementation of the
alternating-fixpoint method in which false atoms are computed in a top-down
fashion. We show that our algorithm is faster than other known algorithms and
that for a wide class of programs it is linear and so, asymptotically optimal.


title:
Combinatorial Toolbox for Protein Sequence Design and Landscape Analysis
  in the Grand Canonical Model

abstract:
  In modern biology, one of the most important research problems is to
understand how protein sequences fold into their native 3D structures. To
investigate this problem at a high level, one wishes to analyze the protein
landscapes, i.e., the structures of the space of all protein sequences and
their native 3D structures. Perhaps the most basic computational problem at
this level is to take a target 3D structure as input and design a fittest
protein sequence with respect to one or more fitness functions of the target 3D
structure. We develop a toolbox of combinatorial techniques for protein
landscape analysis in the Grand Canonical model of Sun, Brem, Chan, and Dill.
The toolbox is based on linear programming, network flow, and a linear-size
representation of all minimum cuts of a network. It not only substantially
expands the network flow technique for protein sequence design in Kleinberg's
seminal work but also is applicable to a considerably broader collection of
computational problems than those considered by Kleinberg. We have used this
toolbox to obtain a number of efficient algorithms and hardness results. We
have further used the algorithms to analyze 3D structures drawn from the
Protein Data Bank and have discovered some novel relationships between such
native 3D structures and the Grand Canonical model.


title:
A Dynamic Programming Approach to De Novo Peptide Sequencing via Tandem
  Mass Spectrometry

abstract:
  The tandem mass spectrometry fragments a large number of molecules of the
same peptide sequence into charged prefix and suffix subsequences, and then
measures mass/charge ratios of these ions. The de novo peptide sequencing
problem is to reconstruct the peptide sequence from a given tandem mass
spectral data of k ions. By implicitly transforming the spectral data into an
NC-spectrum graph G=(V,E) where |V|=2k+2, we can solve this problem in
O(|V|+|E|) time and O(|V|) space using dynamic programming. Our approach can be
further used to discover a modified amino acid in O(|V||E|) time and to analyze
data with other types of noise in O(|V||E|) time. Our algorithms have been
implemented and tested on actual experimental data.


title: Checking Properties within Fairness and Behavior Abstractions

abstract:
  This paper is motivated by the fact that verifying liveness properties under
a fairness condition is often problematic, especially when abstraction is used.
It shows that using a more abstract notion than truth under fairness,
specifically the concept of a property being satisfied within fairness can lead
to interesting possibilities. Technically, it is first established that
deciding satisfaction within fairness is a PSPACE-complete problem and it is
shown that properties satisfied within fairness can always be satisfied by some
fair implementation. Thereafter, the interaction between behavior abstraction
and satisfaction within fairness is studied and it is proved that satisfaction
of properties within fairness can be verified on behavior abstractions, if the
abstraction homomorphism is weakly continuation-closed.


title:
GPCG: A Case Study in the Performance and Scalability of Optimization
  Algorithms

abstract:
  GPCG is an algorithm within the Toolkit for Advanced Optimization (TAO) for
solving bound constrained, convex quadratic problems. Originally developed by
More' and Toraldo, this algorithm was designed for large-scale problems but had
been implemented only for a single processor. The TAO implementation is
available for a wide range of high-performance architecture, and has been
tested on up to 64 processors to solve problems with over 2.5 million
variables.


title: General Loss Bounds for Universal Sequence Prediction

abstract:
  The Bayesian framework is ideally suited for induction problems. The
probability of observing $x_t$ at time $t$, given past observations
$x_1...x_{t-1}$ can be computed with Bayes' rule if the true distribution $\mu$
of the sequences $x_1x_2x_3...$ is known. The problem, however, is that in many
cases one does not even have a reasonable estimate of the true distribution. In
order to overcome this problem a universal distribution $\xi$ is defined as a
weighted sum of distributions $\mu_i\inM$, where $M$ is any countable set of
distributions including $\mu$. This is a generalization of Solomonoff
induction, in which $M$ is the set of all enumerable semi-measures. Systems
which predict $y_t$, given $x_1...x_{t-1}$ and which receive loss $l_{x_t y_t}$
if $x_t$ is the true next symbol of the sequence are considered. It is proven
that using the universal $\xi$ as a prior is nearly as good as using the
unknown true distribution $\mu$. Furthermore, games of chance, defined as a
sequence of bets, observations, and rewards are studied. The time needed to
reach the winning zone is bounded in terms of the relative entropy of $\mu$ and
$\xi$. Extensions to arbitrary alphabets, partial and delayed prediction, and
more active systems are discussed.


title: More Robust Multiparty Protocols with Oblivious Transfer

abstract:
  With oblivious transfer multiparty protocols become possible even in the
presence of a faulty majority. But all known protocols can be aborted by just
one disruptor.
  This paper presents more robust solutions for multiparty protocols with
oblivious transfer. This additional robustness against disruptors weakens the
security of the protocol and the guarantee that the result is correct. We can
observe a trade off between robustness against disruption and security and
correctness.
  We give an application to quantum multiparty protocols. These allow the
implementation of oblivious transfer and the protocols of this paper relative
to temporary assumptions, i.e., the security increases after the termination of
the protocol.


title:
A Fast General Methodology for Information-Theoretically Optimal
  Encodings of Graphs

abstract:
  We propose a fast methodology for encoding graphs with
information-theoretically minimum numbers of bits. Specifically, a graph with
property pi is called a pi-graph. If pi satisfies certain properties, then an
n-node m-edge pi-graph G can be encoded by a binary string X such that (1) G
and X can be obtained from each other in O(n log n) time, and (2) X has at most
beta(n)+o(beta(n)) bits for any continuous super-additive function beta(n) so
that there are at most 2^{beta(n)+o(beta(n))} distinct n-node pi-graphs. The
methodology is applicable to general classes of graphs; this paper focuses on
planar graphs. Examples of such pi include all conjunctions over the following
groups of properties: (1) G is a planar graph or a plane graph; (2) G is
directed or undirected; (3) G is triangulated, triconnected, biconnected,
merely connected, or not required to be connected; (4) the nodes of G are
labeled with labels from {1, ..., ell_1} for ell_1 <= n; (5) the edges of G are
labeled with labels from {1, ..., ell_2} for ell_2 <= m; and (6) each node
(respectively, edge) of G has at most ell_3 = O(1) self-loops (respectively,
ell_4 = O(1) multiple edges). Moreover, ell_3 and ell_4 are not required to be
O(1) for the cases of pi being a plane triangulation. These examples are novel
applications of small cycle separators of planar graphs and are the only
nontrivial classes of graphs, other than rooted trees, with known
polynomial-time information-theoretically optimal coding schemes.


title:
Semantics and Termination of Simply-Moded Logic Programs with Dynamic
  Scheduling

abstract:
  In logic programming, dynamic scheduling refers to a situation where the
selection of the atom in each resolution (computation) step is determined at
runtime, as opposed to a fixed selection rule such as the left-to-right one of
Prolog. This has applications e.g. in parallel programming. A mechanism to
control dynamic scheduling is provided in existing languages in the form of
delay declarations.
  Input-consuming derivations were introduced to describe dynamic scheduling
while abstracting from the technical details. In this paper, we first formalise
the relationship between delay declarations and input-consuming derivations,
showing in many cases a one-to-one correspondence. Then, we define a
model-theoretic semantics for input-consuming derivations of simply-moded
programs. Finally, for this class of programs, we provide a necessary and
sufficient criterion for termination.


title: Properties of Input-Consuming Derivations

abstract:
  We study the properties of input-consuming derivations of moded logic
programs. Input-consuming derivations can be used to model the behavior of
logic programs using dynamic scheduling and employing constructs such as delay
declarations.
  We consider the class of nicely-moded programs and queries. We show that for
these programs a weak version of the well-known switching lemma holds also for
input-consuming derivations. Furthermore, we show that, under suitable
conditions, there exists an algebraic characterization of termination of
input-consuming derivations.


title: On-Line Difference Maximization

abstract:
  In this paper we examine problems motivated by on-line financial problems and
stochastic games. In particular, we consider a sequence of entirely arbitrary
distinct values arriving in random order, and must devise strategies for
selecting low values followed by high values in such a way as to maximize the
expected gain in rank from low values to high values.
  First, we consider a scenario in which only one low value and one high value
may be selected. We give an optimal on-line algorithm for this scenario, and
analyze it to show that, surprisingly, the expected gain is n-O(1), and so
differs from the best possible off-line gain by only a constant additive term
(which is, in fact, fairly small -- at most 15).
  In a second scenario, we allow multiple nonoverlapping low/high selections,
where the total gain for our algorithm is the sum of the individual pair gains.
We also give an optimal on-line algorithm for this problem, where the expected
gain is n^2/8-\Theta(n\log n). An analysis shows that the optimal expected
off-line gain is n^2/6+\Theta(1), so the performance of our on-line algorithm
is within a factor of 3/4 of the best off-line strategy.


title: Decomposing Non-Redundant Sharing by Complementation

abstract:
  Complementation, the inverse of the reduced product operation, is a technique
for systematically finding minimal decompositions of abstract domains. File'
and Ranzato advanced the state of the art by introducing a simple method for
computing a complement. As an application, they considered the extraction by
complementation of the pair-sharing domain PS from the Jacobs and Langen's
set-sharing domain SH. However, since the result of this operation was still
SH, they concluded that PS was too abstract for this. Here, we show that the
source of this result lies not with PS but with SH and, more precisely, with
the redundant information contained in SH with respect to ground-dependencies
and pair-sharing. In fact, a proper decomposition is obtained if the
non-redundant version of SH, PSD, is substituted for SH. To establish the
results for PSD, we define a general schema for subdomains of SH that includes
PSD and Def as special cases. This sheds new light on the structure of PSD and
exposes a natural though unexpected connection between Def and PSD. Moreover,
we substantiate the claim that complementation alone is not sufficient to
obtain truly minimal decompositions of domains. The right solution to this
problem is to first remove redundancies by computing the quotient of the domain
with respect to the observable behavior, and only then decompose it by
complementation.


title:
Deterministic computations whose history is independent of the order of
  asynchronous updating

abstract:
  Consider a network of processors (sites) in which each site x has a finite
set N(x) of neighbors. There is a transition function f that for each site x
computes the next state \xi(x) from the states in N(x). But these transitions
(updates) are applied in arbitrary order, one or many at a time. If the state
of site x at time t is \eta(x,t) then let us define the sequence \zeta(x,0),
\zeta(x,1), ... by taking the sequence \eta(x,0), \eta(x,1), ..., and deleting
repetitions. The function f is said to have invariant histories if the sequence
\zeta(x,i), (while it lasts, in case it is finite) depends only on the initial
configuration, not on the order of updates.
  This paper shows that though the invariant history property is typically
undecidable, there is a useful simple sufficient condition, called
commutativity: For any configuration, for any pair x,y of neighbors, if the
updating would change both \xi(x) and \xi(y) then the result of updating first
x and then y is the same as the result of doing this in the reverse order.


title:
Open Archives Initiative protocol development and implementation at
  arXiv

abstract:
  I outline the involvement of the Los Alamos e-print archive (arXiv) within
the Open Archives Initiative (OAI) and describe the implementation of the data
provider side of the OAI protocol v1.0. I highlight the ways in which we map
the existing structure of arXiv onto elements of the protocol.


title: Optimal Constructions of Hybrid Algorithms

abstract:
  We study on-line strategies for solving problems with hybrid algorithms.
There is a problem Q and w basic algorithms for solving Q. For some lambda <=
w, we have a computer with lambda disjoint memory areas, each of which can be
used to run a basic algorithm and store its intermediate results. In the worst
case, only one basic algorithm can solve Q in finite time, and all the other
basic algorithms run forever without solving Q. To solve Q with a hybrid
algorithm constructed from the basic algorithms, we run a basic algorithm for
some time, then switch to another, and continue this process until Q is solved.
The goal is to solve Q in the least amount of time. Using competitive ratios to
measure the efficiency of a hybrid algorithm, we construct an optimal
deterministic hybrid algorithm and an efficient randomized hybrid algorithm.
This resolves an open question on searching with multiple robots posed by
Baeza-Yates, Culberson and Rawlins. We also prove that our randomized algorithm
is optimal for lambda = 1, settling a conjecture of Kao, Reif and Tate.


title: Tap Tips: Lightweight Discovery of Touchscreen Targets

abstract:
  We describe tap tips, a technique for providing touch-screen target location
hints. Tap tips are lightweight in that they are non-modal, appear only when
needed, require a minimal number of user gestures, and do not add to the
standard touchscreen gesture vocabulary. We discuss our implementation of tap
tips in an electronic guidebook system and some usability test results.


title: Tree Contractions and Evolutionary Trees

abstract:
  An evolutionary tree is a rooted tree where each internal vertex has at least
two children and where the leaves are labeled with distinct symbols
representing species. Evolutionary trees are useful for modeling the
evolutionary history of species. An agreement subtree of two evolutionary trees
is an evolutionary tree which is also a topological subtree of the two given
trees. We give an algorithm to determine the largest possible number of leaves
in any agreement subtree of two trees T_1 and T_2 with n leaves each. If the
maximum degree d of these trees is bounded by a constant, the time complexity
is O(n log^2(n)) and is within a log(n) factor of optimal. For general d, this
algorithm runs in O(n d^2 log(d) log^2(n)) time or alternatively in O(n d
sqrt(d) log^3(n)) time.


title: Cavity Matchings, Label Compressions, and Unrooted Evolutionary Trees

abstract:
  We present an algorithm for computing a maximum agreement subtree of two
unrooted evolutionary trees. It takes O(n^{1.5} log n) time for trees with
unbounded degrees, matching the best known time complexity for the rooted case.
Our algorithm allows the input trees to be mixed trees, i.e., trees that may
contain directed and undirected edges at the same time. Our algorithm adopts a
recursive strategy exploiting a technique called label compression. The
backbone of this technique is an algorithm that computes the maximum weight
matchings over many subgraphs of a bipartite graph as fast as it takes to
compute a single matching.


title:
Total Protection of Analytic Invariant Information in Cross Tabulated
  Tables

abstract:
  To protect sensitive information in a cross tabulated table, it is a common
practice to suppress some of the cells in the table. An analytic invariant is a
power series in terms of the suppressed cells that has a unique feasible value
and a convergence radius equal to +\infty. Intuitively, the information
contained in an invariant is not protected even though the values of the
suppressed cells are not disclosed. This paper gives an optimal linear-time
algorithm for testing whether there exist nontrivial analytic invariants in
terms of the suppressed cells in a given set of suppressed cells. This paper
also presents NP-completeness results and an almost linear-time algorithm for
the problem of suppressing the minimum number of cells in addition to the
sensitive ones so that the resulting table does not leak analytic invariant
information about a given set of suppressed cells.


title: Linear-Time Succinct Encodings of Planar Graphs via Canonical Orderings

abstract:
  Let G be an embedded planar undirected graph that has n vertices, m edges,
and f faces but has no self-loop or multiple edge. If G is triangulated, we can
encode it using {4/3}m-1 bits, improving on the best previous bound of about
1.53m bits. In case exponential time is acceptable, roughly 1.08m bits have
been known to suffice. If G is triconnected, we use at most
(2.5+2\log{3})\min\{n,f\}-7 bits, which is at most 2.835m bits and smaller than
the best previous bound of 3m bits. Both of our schemes take O(n) time for
encoding and decoding.


title: Data Security Equals Graph Connectivity

abstract:
  To protect sensitive information in a cross tabulated table, it is a common
practice to suppress some of the cells in the table. This paper investigates
four levels of data security of a two-dimensional table concerning the
effectiveness of this practice. These four levels of data security protect the
information contained in, respectively, individual cells, individual rows and
columns, several rows or columns as a whole, and a table as a whole. The paper
presents efficient algorithms and NP-completeness results for testing and
achieving these four levels of data security. All these complexity results are
obtained by means of fundamental equivalences between the four levels of data
security of a table and four types of connectivity of a graph constructed from
that table.


title:
The Guidebook, the Friend, and the Room: Visitor Experience in a
  Historic House

abstract:
  In this paper, we describe an electronic guidebook prototype and report on a
study of its use in a historic house. Supported by mechanisms in the guidebook,
visitors constructed experiences that had a high degree of interaction with
three entities: the guidebook, their companions, and the house and its
contents. For example, we found that most visitors played audio descriptions
played through speakers (rather than using headphones or reading textual
descriptions) to facilitate communication with their companions.


title: The Generalized Universal Law of Generalization

abstract:
  It has been argued by Shepard that there is a robust psychological law that
relates the distance between a pair of items in psychological space and the
probability that they will be confused with each other. Specifically, the
probability of confusion is a negative exponential function of the distance
between the pair of items. In experimental contexts, distance is typically
defined in terms of a multidimensional Euclidean space-but this assumption
seems unlikely to hold for complex stimuli. We show that, nonetheless, the
Universal Law of Generalization can be derived in the more complex setting of
arbitrary stimuli, using a much more universal measure of distance. This
universal distance is defined as the length of the shortest program that
transforms the representations of the two items of interest into one another:
the algorithmic information distance. It is universal in the sense that it
minorizes every computable distance: it is the smallest computable distance. We
show that the universal law of generalization holds with probability going to
one-provided the confusion probabilities are computable. We also give a
mathematically more appealing form


title: Benchmarking Optimization Software with Performance Profiles

abstract:
  We propose performance profiles-distribution functions for a performance
metric-as a tool for benchmarking and comparing optimization software. We show
that performance profiles combine the best features of other tools for
performance evaluation.


title: On the Automated Classification of Web Sites

abstract:
  In this paper we discuss several issues related to automated text
classification of web sites. We analyze the nature of web content and metadata
in relation to requirements for text features. We find that HTML metatags are a
good source of text features, but are not in wide use despite their role in
search engine rankings. We present an approach for targeted spidering including
metadata extraction and opportunistic crawling of specific semantic hyperlinks.
We describe a system for automatically classifying web sites into industry
categories and present performance results based on different combinations of
text features and training data. This system can serve as the basis for a
generalized framework for automated metadata creation.


title:
Fast Pricing of European Asian Options with Provable Accuracy:
  Single-stock and Basket Options

abstract:
  This paper develops three polynomial-time pricing techniques for European
Asian options with provably small errors, where the stock prices follow
binomial trees or trees of higher-degree. The first technique is the first
known Monte Carlo algorithm with analytical error bounds suitable for pricing
single-stock options with meaningful confidence and speed. The second technique
is a general recursive bucketing-based scheme that can use the
Aingworth-Motwani-Oldham aggregation algorithm, Monte-Carlo simulation and
possibly others as the base-case subroutine. This scheme enables robust
trade-offs between accuracy and time over subtrees of different sizes. For
long-term options or high frequency price averaging, it can price single-stock
options with smaller errors in less time than the base-case algorithms
themselves. The third technique combines Fast Fourier Transform with
bucketing-based schemes for pricing basket options. This technique takes
polynomial time in the number of days and the number of stocks, and does not
add any errors to those already incurred in the companion bucketing scheme.
This technique assumes that the price of each underlying stock moves
independently.


title: Computational Geometry Column 41

abstract:
  The recent result that n congruent balls in R^d have at most 4 distinct
geometric permutations is described.


title:
Compact Encodings of Planar Graphs via Canonical Orderings and Multiple
  Parentheses

abstract:
  Let G be a plane graph of n nodes, m edges, f faces, and no self-loop. G need
not be connected or simple (i.e., free of multiple edges). We give three sets
of coding schemes for G which all take O(m+n) time for encoding and decoding.
Our schemes employ new properties of canonical orderings for planar graphs and
new techniques of processing strings of multiple types of parentheses.
  For applications that need to determine in O(1) time the adjacency of two
nodes and the degree of a node, we use 2m+(5+1/k)n + o(m+n) bits for any
constant k > 0 while the best previous bound by Munro and Raman is 2m+8n +
o(m+n). If G is triconnected or triangulated, our bit count decreases to 2m+3n
+ o(m+n) or 2m+2n + o(m+n), respectively. If G is simple, our bit count is
(5/3)m+(5+1/k)n + o(n) for any constant k > 0. Thus, if a simple G is also
triconnected or triangulated, then 2m+2n + o(n) or 2m+n + o(n) bits suffice,
respectively.
  If only adjacency queries are supported, the bit counts for a general G and a
simple G become 2m+(14/3)n + o(m+n) and (4/3)m+5n + o(n), respectively.
  If we only need to reconstruct G from its code, a simple and triconnected G
uses roughly 2.38m + O(1) bits while the best previous bound by He, Kao, and Lu
is 2.84m.


title: Orderly Spanning Trees with Applications

abstract:
  We introduce and study the {\em orderly spanning trees} of plane graphs. This
algorithmic tool generalizes {\em canonical orderings}, which exist only for
triconnected plane graphs. Although not every plane graph admits an orderly
spanning tree, we provide an algorithm to compute an {\em orderly pair} for any
connected planar graph $G$, consisting of a plane graph $H$ of $G$, and an
orderly spanning tree of $H$. We also present several applications of orderly
spanning trees: (1) a new constructive proof for Schnyder's Realizer Theorem,
(2) the first area-optimal 2-visibility drawing of $G$, and (3) the best known
encodings of $G$ with O(1)-time query support. All algorithms in this paper run
in linear time.


title: Common-Face Embeddings of Planar Graphs

abstract:
  Given a planar graph G and a sequence C_1,...,C_q, where each C_i is a family
of vertex subsets of G, we wish to find a plane embedding of G, if any exists,
such that for each i in {1,...,q}, there is a face F_i in the embedding whose
boundary contains at least one vertex from each set in C_i. This problem has
applications to the recovery of topological information from geographical data
and the design of constrained layouts in VLSI. Let I be the input size, i.e.,
the total number of vertices and edges in G and the families C_i, counting
multiplicity. We show that this problem is NP-complete in general. We also show
that it is solvable in O(I log I) time for the special case where for each
input family C_i, each set in C_i induces a connected subgraph of the input
graph G. Note that the classical problem of simply finding a planar embedding
is a further special case of this case with q=0. Therefore, the processing of
the additional constraints C_1,...,C_q only incurs a logarithmic factor of
overhead.


title: Optimal Bid Sequences for Multiple-Object Auctions with Unequal Budgets

abstract:
  In a multiple-object auction, every bidder tries to win as many objects as
possible with a bidding algorithm. This paper studies position-randomized
auctions, which form a special class of multiple-object auctions where a
bidding algorithm consists of an initial bid sequence and an algorithm for
randomly permuting the sequence. We are especially concerned with situations
where some bidders know the bidding algorithms of others. For the case of only
two bidders, we give an optimal bidding algorithm for the disadvantaged bidder.
Our result generalizes previous work by allowing the bidders to have unequal
budgets. One might naturally anticipate that the optimal expected numbers of
objects won by the bidders would be proportional to their budgets.
Surprisingly, this is not true. Our new algorithm runs in optimal O(n) time in
a straightforward manner. The case with more than two bidders is open.


title:
Optimal Augmentation for Bipartite Componentwise Biconnectivity in
  Linear Time

abstract:
  A graph is componentwise biconnected if every connected component either is
an isolated vertex or is biconnected. We present a linear-time algorithm for
the problem of adding the smallest number of edges to make a bipartite graph
componentwise biconnected while preserving its bipartiteness. This algorithm
has immediate applications for protecting sensitive information in statistical
tables.


title: The Enhanced Double Digest Problem for DNA Physical Mapping

abstract:
  The double digest problem is a common NP-hard approach to constructing
physical maps of DNA sequences. This paper presents a new approach called the
enhanced double digest problem. Although this new problem is also NP-hard, it
can be solved in linear time in certain theoretically interesting cases.


title: A Price Dynamics in Bandwidth Markets for Point-to-point Connections

abstract:
  We simulate a network of N routers and M network users making concurrent
point-to-point connections by buying and selling router capacity from each
other. The resources need to be acquired in complete sets, but there is only
one spot market for each router. In order to describe the internal dynamics of
the market, we model the observed prices by N-dimensional Ito-processes.
Modeling using stochastic processes is novel in this context of describing
interactions between end-users in a system with shared resources, and allows a
standard set of mathematical tools to be applied. The derived models can also
be used to price contingent claims on network capacity and thus to price
complex network services such as quality of service levels, multicast, etc.


title: Chaos for Stream Cipher

abstract:
  This paper discusses mixing of chaotic systems as a dependable method for
secure communication. Distribution of the entropy function for steady state as
well as plaintext input sequences are analyzed. It is shown that the mixing of
chaotic sequences results in a sequence that does not have any state dependence
on the information encrypted by them. The generated output states of such a
cipher approach the theoretical maximum for both complexity measures and cycle
length. These features are then compared with some popular ciphers.


title:
Quantum Multi-Prover Interactive Proof Systems with Limited Prior
  Entanglement

abstract:
  This paper gives the first formal treatment of a quantum analogue of
multi-prover interactive proof systems. It is proved that the class of
languages having quantum multi-prover interactive proof systems is necessarily
contained in NEXP, under the assumption that provers are allowed to share at
most polynomially many prior-entangled qubits. This implies that, in
particular, if provers do not share any prior entanglement with each other, the
class of languages having quantum multi-prover interactive proof systems is
equal to NEXP. Related to these, it is shown that, in the case a prover does
not have his private qubits, the class of languages having quantum
single-prover interactive proof systems is also equal to NEXP.


title:
On the predictability of Rainfall in Kerala- An application of ABF
  Neural Network

abstract:
  Rainfall in Kerala State, the southern part of Indian Peninsula in particular
is caused by the two monsoons and the two cyclones every year. In general,
climate and rainfall are highly nonlinear phenomena in nature giving rise to
what is known as the `butterfly effect'. We however attempt to train an ABF
neural network on the time series rainfall data and show for the first time
that in spite of the fluctuations resulting from the nonlinearity in the
system, the trends in the rainfall pattern in this corner of the globe have
remained unaffected over the past 87 years from 1893 to 1980. We also
successfully filter out the chaotic part of the system and illustrate that its
effects are marginal over long term predictions.


title:
Non-convex cost functionals in boosting algorithms and methods for panel
  selection

abstract:
  In this document we propose a new improvement for boosting techniques as
proposed in Friedman '99 by the use of non-convex cost functional. The idea is
to introduce a correlation term to better deal with forecasting of additive
time series. The problem is discussed in a theoretical way to prove the
existence of minimizing sequence, and in a numerical way to propose a new
"ArgMin" algorithm. The model has been used to perform the touristic presence
forecast for the winter season 1999/2000 in Trentino (italian Alps).


title: A Scientific Data Management System for Irregular Applications

abstract:
  Many scientific applications are I/O intensive and generate or access large
data sets, spanning hundreds or thousands of "files." Management, storage,
efficient access, and analysis of this data present an extremely challenging
task. We have developed a software system, called Scientific Data Manager
(SDM), that uses a combination of parallel file I/O and database support for
high-performance scientific data management. SDM provides a high-level API to
the user and internally, uses a parallel file system to store real data and a
database to store application-related metadata. In this paper, we describe how
we designed and implemented SDM to support irregular applications. SDM can
efficiently handle the reading and writing of data in an irregular mesh as well
as the distribution of index values. We describe the SDM user interface and how
we implemented it to achieve high performance. SDM makes extensive use of
MPI-IO's noncontiguous collective I/O functions. SDM also uses the concept of a
history file to optimize the cost of the index distribution using the metadata
stored in the database. We present performance results with two irregular
applications, a CFD code called FUN3D and a Rayleigh-Taylor instability code,
on the SGI Origin2000 at Argonne National Laboratory.


title:
Components and Interfaces of a Process Management System for Parallel
  Programs

abstract:
  Parallel jobs are different from sequential jobs and require a different type
of process management. We present here a process management system for parallel
programs such as those written using MPI. A primary goal of the system, which
we call MPD (for multipurpose daemon), is to be scalable. By this we mean that
startup of interactive parallel jobs comprising thousands of processes is
quick, that signals can be quickly delivered to processes, and that stdin,
stdout, and stderr are managed intuitively. Our primary target is parallel
machines made up of clusters of SMPs, but the system is also useful in more
tightly integrated environments. We describe how MPD enables much faster
startup and better runtime management of parallel jobs. We show how close
control of stdio can support the easy implementation of a number of convenient
system utilities, even a parallel debugger. We describe a simple but general
interface that can be used to separate any process manager from a parallel
library, which we use to keep MPD separate from MPICH.


title: An effective Procedure for Speeding up Algorithms

abstract:
  The provably asymptotically fastest algorithm within a factor of 5 for
formally described problems will be constructed. The main idea is to enumerate
all programs provably equivalent to the original problem by enumerating all
proofs. The algorithm could be interpreted as a generalization and improvement
of Levin search, which is, within a multiplicative constant, the fastest
algorithm for inverting functions. Blum's speed-up theorem is avoided by taking
into account only programs for which a correctness proof exists. Furthermore,
it is shown that the fastest program that computes a certain function is also
one of the shortest programs provably computing this function. To quantify this
statement, the definition of Kolmogorov complexity is extended, and two new
natural measures for the complexity of a function are defined.


title: Easy and Hard Constraint Ranking in OT: Algorithms and Complexity

abstract:
  We consider the problem of ranking a set of OT constraints in a manner
consistent with data.
  We speed up Tesar and Smolensky's RCD algorithm to be linear on the number of
constraints. This finds a ranking so each attested form x_i beats or ties a
particular competitor y_i. We also generalize RCD so each x_i beats or ties all
possible competitors.
  Alas, this more realistic version of learning has no polynomial algorithm
unless P=NP! Indeed, not even generation does. So one cannot improve
qualitatively upon brute force:
  Merely checking that a single (given) ranking is consistent with given forms
is coNP-complete if the surface forms are fully observed and Delta_2^p-complete
if not. Indeed, OT generation is OptP-complete. As for ranking, determining
whether any consistent ranking exists is coNP-hard (but in Delta_2^p) if the
forms are fully observed, and Sigma_2^p-complete if not.
  Finally, we show that generation and ranking are easier in derivational
theories: in P, and NP-complete.


title: Multi-Syllable Phonotactic Modelling

abstract:
  This paper describes a novel approach to constructing phonotactic models. The
underlying theoretical approach to phonological description is the
multisyllable approach in which multiple syllable classes are defined that
reflect phonotactically idiosyncratic syllable subcategories. A new
finite-state formalism, OFS Modelling, is used as a tool for encoding,
automatically constructing and generalising phonotactic descriptions.
Language-independent prototype models are constructed which are instantiated on
the basis of data sets of phonological strings, and generalised with a
clustering algorithm. The resulting approach enables the automatic construction
of phonotactic models that encode arbitrarily close approximations of a
language's set of attested phonological forms. The approach is applied to the
construction of multi-syllable word-level phonotactic models for German,
English and Dutch.


title: Taking Primitive Optimality Theory Beyond the Finite State

abstract:
  Primitive Optimality Theory (OTP) (Eisner, 1997a; Albro, 1998), a
computational model of Optimality Theory (Prince and Smolensky, 1993), employs
a finite state machine to represent the set of active candidates at each stage
of an Optimality Theoretic derivation, as well as weighted finite state
machines to represent the constraints themselves. For some purposes, however,
it would be convenient if the set of candidates were limited by some set of
criteria capable of being described only in a higher-level grammar formalism,
such as a Context Free Grammar, a Context Sensitive Grammar, or a Multiple
Context Free Grammar (Seki et al., 1991). Examples include reduplication and
phrasal stress models. Here we introduce a mechanism for OTP-like Optimality
Theory in which the constraints remain weighted finite state machines, but sets
of candidates are represented by higher-level grammars. In particular, we use
multiple context-free grammars to model reduplication in the manner of
Correspondence Theory (McCarthy and Prince, 1995), and develop an extended
version of the Earley Algorithm (Earley, 1970) to apply the constraints to a
reduplicating candidate set.


title:
Finite-State Phonology: Proceedings of the 5th Workshop of the ACL
  Special Interest Group in Computational Phonology (SIGPHON)

abstract:
  Home page of the workshop proceedings, with pointers to the individually
archived papers. Includes front matter from the printed version of the
proceedings.


title: Factored Notation for Interval I/O

abstract:
  This note addresses the input and output of intervals in the sense of
interval arithmetic and interval constraints. The most obvious, and so far most
widely used notation, for intervals has drawbacks that we remedy with a new
notation that we propose to call factored notation. It is more compact and
allows one to find a good trade-off between interval width and ease of reading.
We describe how such a trade-off can be based on the information yield (in the
sense of information theory) of the last decimal shown.


title: P-Immune Sets with Holes Lack Self-Reducibility Properties

abstract: No P-immune set having exponential gaps is positive-Turing self-reducible.


title: An Effective Fixpoint Semantics for Linear Logic Programs

abstract:
  In this paper we investigate the theoretical foundation of a new bottom-up
semantics for linear logic programs, and more precisely for the fragment of
LinLog that consists of the language LO enriched with the constant 1. We use
constraints to symbolically and finitely represent possibly infinite
collections of provable goals. We define a fixpoint semantics based on a new
operator in the style of Tp working over constraints. An application of the
fixpoint operator can be computed algorithmically. As sufficient conditions for
termination, we show that the fixpoint computation is guaranteed to converge
for propositional LO. To our knowledge, this is the first attempt to define an
effective fixpoint semantics for linear logic programs. As an application of
our framework, we also present a formal investigation of the relations between
LO and Disjunctive Logic Programming. Using an approach based on abstract
interpretation, we show that DLP fixpoint semantics can be viewed as an
abstraction of our semantics for LO. We prove that the resulting abstraction is
correct and complete for an interesting class of LO programs encoding Petri
Nets.


title:
Mathematical Model of Word Length on the Basis of the Cebanov-Fucks
  Distribution with Uniform Parameter Distribution

abstract:
  The data on 13 typologically different languages have been processed using a
two-parameter word length model, based on 1-displaced uniform Poisson
distribution. Statistical dependencies of the 2nd parameter on the 1st one are
revealed for the German texts and genre of letters.


title:
Gene Expression Programming: a New Adaptive Algorithm for Solving
  Problems

abstract:
  Gene expression programming, a genotype/phenotype genetic algorithm (linear
and ramified), is presented here for the first time as a new technique for the
creation of computer programs. Gene expression programming uses character
linear chromosomes composed of genes structurally organized in a head and a
tail. The chromosomes function as a genome and are subjected to modification by
means of mutation, transposition, root transposition, gene transposition, gene
recombination, and one- and two-point recombination. The chromosomes encode
expression trees which are the object of selection. The creation of these
separate entities (genome and expression tree) with distinct functions allows
the algorithm to perform with high efficiency that greatly surpasses existing
adaptive techniques. The suite of problems chosen to illustrate the power and
versatility of gene expression programming includes symbolic regression,
sequence induction with and without constant creation, block stacking, cellular
automata rules for the density-classification problem, and two problems of
boolean concept learning: the 11-multiplexer and the GP rule problem.


title: Communities of Practice: Going Virtual

abstract:
  With the current trends towards downsizing, outsourcing and globalisation,
modern organisations are reducing the numbers of people they employ. In
addition, organisations now have to cope with the increasing
internationalisation of business forcing collaboration and knowledge sharing
across time and distance simultaneously. There is a need for new ways of
thinking about how knowledge is shared in distributed groups. In this paper we
explore a relatively new approach to knowledge sharing using Lave and Wenger's
(1991) theory of Communities of Practice (CoPs). We investigate whether CoPs
might translate to a geographically distributed international environment
through a case study that explores the functioning of a CoP across national
boundaries.


title: Computer based Information Systems and Managers' Work

abstract:
  This paper identifies three categories of model: the Technology Impact Model;
the Social Impact Model and the Integrationist Model, which imply different
views of the "impact" of Information Technology on work organisation. These
models are used to structure data from case studies conducted by the authors to
explore the implications of the use of computer-based information systems for
managers' work. The paper argues that the "impact" of information systems is
not a single stable and predictable outcome but a non-linear ongoing process
that changes and evolves over time. It also argues that the actions of
individuals and groups within an organisation are not wholly determined by
outside forces: people can and do react to, and shape, systems in different
ways. In this sense, the "impact" of computer-based information systems on
managers' work reflects decisions made by managers themselves about how the
technology is used.


title: Soundness, Idempotence and Commutativity of Set-Sharing

abstract:
  It is important that practical data-flow analyzers are backed by reliably
proven theoretical results. Abstract interpretation provides a sound
mathematical framework and necessary generic properties for an abstract domain
to be well-defined and sound with respect to the concrete semantics. In logic
programming, the abstract domain Sharing is a standard choice for sharing
analysis for both practical work and further theoretical study. In spite of
this, we found that there were no satisfactory proofs for the key properties of
commutativity and idempotence that are essential for Sharing to be well-defined
and that published statements of the soundness of Sharing assume the
occurs-check. This paper provides a generalization of the abstraction function
for Sharing that can be applied to any language, with or without the
occurs-check. Results for soundness, idempotence and commutativity for abstract
unification using this abstraction function are proven.


title: Construction of an algorithm in parallel for the Fast Fourier Transform

abstract:
  It has been designed,built and executed a code for the Fast Fourier Transform
(FFT),compiled and executed in a cluster of 2^n computers under the operating
system MacOS and using the routines MacMPI. As practical application,the code
has been used to obtain the transformed from an astronomic imagen,to execute a
filter on its and with a transformed inverse to recover the image with the
variates given by the filter.The computers arrangement are installed in the
Observatorio Astronomico National in Colombia under the name OAN Cluster and in
this has been executed several applications.


title:
Quantitative Neural Network Model of the Tip-of-the-Tongue Phenomenon
  Based on Synthesized Memory-Psycholinguistic-Metacognitive Approach

abstract:
  A new three-stage computer artificial neural network model of the
tip-of-the-tongue phenomenon is proposed. Each word's node is build from some
interconnected learned auto-associative two-layer neural networks each of which
represents separate word's semantic, lexical, or phonological components. The
model synthesizes memory, psycholinguistic, and metamemory approaches, bridges
speech errors and naming chronometry research traditions, and can explain
quantitatively many tip-of-the-tongue effects.


title: Learning Policies with External Memory

abstract:
  In order for an agent to perform well in partially observable domains, it is
usually necessary for actions to depend on the history of observations. In this
paper, we explore a {\it stigmergic} approach, in which the agent's actions
include the ability to set and clear bits in an external memory, and the
external memory is included as part of the input to the agent. In this case, we
need to learn a reactive policy in a highly non-Markovian domain. We explore
two algorithms: SARSA(\lambda), which has had empirical success in partially
observable domains, and VAPS, a new algorithm due to Baird and Moore, with
convergence guarantees in partially observable domains. We compare the
performance of these two algorithms on benchmark problems.


title:
Rapid Application Evolution and Integration Through Document
  Metamorphosis

abstract:
  The Harland document management system implements a data model in which
document (object) structure can be altered by mixin-style multiple inheritance
at any time. This kind of structural fluidity has long been supported by
knowledge-base management systems, but its use has primarily been in support of
reasoning and inference. In this paper, we report our experiences building and
supporting several non-trivial applications on top of this data model. Based on
these experiences, we argue that structural fluidity is convenient for
data-intensive applications other than knowledge-base management. Specifically,
we suggest that this flexible data model is a natural fit for the decoupled
programming methodology that arises naturally when using enterprise component
frameworks.


title: Source-Filter Decomposition of Harmonic Sounds

abstract:
  This paper describes a method for decomposing steady-state instrument data
into excitation and formant filter components. The input data, taken from
several series of recordings of acoustical instruments is analyzed in the
frequency domain, and for each series a model is built, which most accurately
represents the data as a source-filter system. The source part is taken to be a
harmonic excitation system with frequency-invariant magnitudes, and the filter
part is considered to be responsible for all spectral inhomogenieties. This
method has been applied to the SHARC database of steady state instrument data
to create source-filter models for a large number of acoustical instruments.
Subsequent use of such models can have a wide variety of applications,
including improvements to wavetable and physical modeling synthesis, high
quality pitch shifting, and creation of "hybrid" instrument timbres.


title: Flexible Software Framework for Modal Synthesis

abstract:
  Modal synthesis is an important area of physical modeling whose exploration
in the past has been held back by a large number of control parameters, the
scarcity of general-purpose design tools and the difficulty of obtaining the
computational power required for real-time synthesis. This paper presents an
overview of a flexible software framework facilitating the design and control
of instruments based on modal synthesis. The framework is designed as a
hierarchy of polymorphic synthesis objects, representing modal structures of
various complexity. As a method of generalizing all interactions among the
elements of a modal system, an abstract notion of {\it energy} is introduced,
and a set of energy transfer functions is provided. Such abstraction leads to a
design where the dynamics of interactions can be largely separated from the
specifics of particular modal structures, yielding an easily configurable and
expandable system. A real-time version of the framework has been implemented as
a set of C++ classes along with an integrating shell and a GUI, and is
currently being used to design and play modal instruments, as well as to survey
fundamental properties of various modal algorithms.


title: Two-parameter Model of Word Length "Language - Genre"

abstract:
  A two-parameter model of word length measured by the number of syllables
comprising it is proposed. The first parameter is dependent on language type,
the second one - on text genre and reflects the degree of completion of
synergetic processes of language optimization.


title: The Limits of Horn Logic Programs

abstract:
  Given a sequence $\{\Pi_n\}$ of Horn logic programs, the limit $\Pi$ of
$\{\Pi_n\}$ is the set of the clauses such that every clause in $\Pi$ belongs
to almost every $\Pi_n$ and every clause in infinitely many $\Pi_n$'s belongs
to $\Pi$ also. The limit program $\Pi$ is still Horn but may be infinite. In
this paper, we consider if the least Herbrand model of the limit of a given
Horn logic program sequence $\{\Pi_n\}$ equals the limit of the least Herbrand
models of each logic program $\Pi_n$. It is proved that this property is not
true in general but holds if Horn logic programs satisfy an assumption which
can be syntactically checked and be satisfied by a class of Horn logic
programs. Thus, under this assumption we can approach the least Herbrand model
of the limit $\Pi$ by the sequence of the least Herbrand models of each finite
program $\Pi_n$. We also prove that if a finite Horn logic program satisfies
this assumption, then the least Herbrand model of this program is recursive.
Finally, by use of the concept of stability from dynamical systems, we prove
that this assumption is exactly a sufficient condition to guarantee the
stability of fixed points for Horn logic programs.


title: Toward an architecture for quantum programming

abstract:
  It is becoming increasingly clear that, if a useful device for quantum
computation will ever be built, it will be embodied by a classical computing
machine with control over a truly quantum subsystem, this apparatus performing
a mixture of classical and quantum computation.
  This paper investigates a possible approach to the problem of programming
such machines: a template high level quantum language is presented which
complements a generic general purpose classical language with a set of quantum
primitives. The underlying scheme involves a run-time environment which
calculates the byte-code for the quantum operations and pipes it to a quantum
device controller or to a simulator.
  This language can compactly express existing quantum algorithms and reduce
them to sequences of elementary operations; it also easily lends itself to
automatic, hardware independent, circuit simplification. A publicly available
preliminary implementation of the proposed ideas has been realized using the
C++ language.


title:
Magical Number Seven Plus or Minus Two: Syntactic Structure Recognition
  in Japanese and English Sentences

abstract:
  George A. Miller said that human beings have only seven chunks in short-term
memory, plus or minus two. We counted the number of bunsetsus (phrases) whose
modifiees are undetermined in each step of an analysis of the dependency
structure of Japanese sentences, and which therefore must be stored in
short-term memory. The number was roughly less than nine, the upper bound of
seven plus or minus two. We also obtained similar results with English
sentences under the assumption that human beings recognize a series of words,
such as a noun phrase (NP), as a unit. This indicates that if we assume that
the human cognitive units in Japanese and English are bunsetsu and NP
respectively, analysis will support Miller's $7 \pm 2$ theory.


title:
A Machine-Learning Approach to Estimating the Referential Properties of
  Japanese Noun Phrases

abstract:
  The referential properties of noun phrases in the Japanese language, which
has no articles, are useful for article generation in Japanese-English machine
translation and for anaphora resolution in Japanese noun phrases. They are
generally classified as generic noun phrases, definite noun phrases, and
indefinite noun phrases. In the previous work, referential properties were
estimated by developing rules that used clue words. If two or more rules were
in conflict with each other, the category having the maximum total score given
by the rules was selected as the desired category. The score given by each rule
was established by hand, so the manpower cost was high. In this work, we
automatically adjusted these scores by using a machine-learning method and
succeeded in reducing the amount of manpower needed to adjust these scores.


title:
Meaning Sort - Three examples: dictionary construction, tagged corpus
  construction, and information presentation system

abstract:
  It is often useful to sort words into an order that reflects relations among
their meanings as obtained by using a thesaurus. In this paper, we introduce a
method of arranging words semantically by using several types of `{\sf is-a}'
thesauri and a multi-dimensional thesaurus. We also describe three major
applications where a meaning sort is useful and show the effectiveness of a
meaning sort. Since there is no doubt that a word list in meaning-order is
easier to use than a word list in some random order, a meaning sort, which can
easily produce a word list in meaning-order, must be useful and effective.


title: CRL at Ntcir2

abstract:
  We have developed systems of two types for NTCIR2. One is an enhenced version
of the system we developed for NTCIR1 and IREX. It submitted retrieval results
for JJ and CC tasks. A variety of parameters were tried with the system. It
used such characteristics of newspapers as locational information in the CC
tasks. The system got good results for both of the tasks. The other system is a
portable system which avoids free parameters as much as possible. The system
submitted retrieval results for JJ, JE, EE, EJ, and CC tasks. The system
automatically determined the number of top documents and the weight of the
original query used in automatic-feedback retrieval. It also determined
relevant terms quite robustly. For EJ and JE tasks, it used document expansion
to augment the initial queries. It achieved good results, except on the CC
tasks.


title:
Faster-than-light effects and negative group delays in optics and
  electronics, and their applications

abstract:
  Recent manifestations of apparently faster-than-light effects confirmed our
predictions that the group velocity in transparent optical media can exceed c.
Special relativity is not violated by these phenomena. Moreover, in the
electronic domain, the causality principle does not forbid negative group
delays of analytic signals in electronic circuits, in which the peak of an
output pulse leaves the exit port of a circuit before the peak of the input
pulse enters the input port. Furthermore, pulse distortion for these
superluminal analytic signals can be negligible in both the optical and
electronic domains. Here we suggest an extension of these ideas to the
microelectronic domain. The underlying principle is that negative feedback can
be used to produce negative group delays. Such negative group delays can be
used to cancel out the positive group delays due to transistor latency (e.g.,
the finite RC rise time of MOSFETS caused by their intrinsic gate capacitance),
as well as the propagation delays due to the interconnects between transistors.
Using this principle, it is possible to speed up computer systems.


title: Fitness Uniform Selection to Preserve Genetic Diversity

abstract:
  In evolutionary algorithms, the fitness of a population increases with time
by mutating and recombining individuals and by a biased selection of more fit
individuals. The right selection pressure is critical in ensuring sufficient
optimization progress on the one hand and in preserving genetic diversity to be
able to escape from local optima on the other. We propose a new selection
scheme, which is uniform in the fitness values. It generates selection pressure
towards sparsely populated fitness regions, not necessarily towards higher
fitness, as is the case for all other selection schemes. We show that the new
selection scheme can be much more effective than standard selection schemes.


title: Search in Power-Law Networks

abstract:
  Many communication and social networks have power-law link distributions,
containing a few nodes which have a very high degree and many with low degree.
The high connectivity nodes play the important role of hubs in communication
and networking, a fact which can be exploited when designing efficient search
algorithms. We introduce a number of local search strategies which utilize high
degree nodes in power-law graphs and which have costs which scale sub-linearly
with the size of the graph. We also demonstrate the utility of these strategies
on the Gnutella peer-to-peer network.

categories: cs.NI cond-mat.dis-nn cond-mat.stat-mech cs.PF


title: Nice point sets can have nasty Delaunay triangulations

abstract:
  We consider the complexity of Delaunay triangulations of sets of points in
R^3 under certain practical geometric constraints. The spread of a set of
points is the ratio between the longest and shortest pairwise distances. We
show that in the worst case, the Delaunay triangulation of n points in R^3 with
spread D has complexity Omega(min{D^3, nD, n^2}) and O(min{D^4, n^2}). For the
case D = Theta(sqrt{n}), our lower bound construction consists of a uniform
sample of a smooth convex surface with bounded curvature. We also construct a
family of smooth connected surfaces such that the Delaunay triangulation of any
good point sample has near-quadratic complexity.


title:
The Existential Theory of Equations with Rational Constraints in Free
  Groups is PSPACE-Complete

abstract:
  It is known that the existential theory of equations in free groups is
decidable. This is a famous result of Makanin. On the other hand it has been
shown that the scheme of his algorithm is not primitive recursive. In this
paper we present an algorithm that works in polynomial space, even in the more
general setting where each variable has a rational constraint, that is, the
solution has to respect a specification given by a regular word language. Our
main result states that the existential theory of equations in free groups with
rational constraints is PSPACE-complete. We obtain this result as a corollary
of the corresponding statement about free monoids with involution.


title:
On the NP-completeness of Finding an Optimal Strategy in Games with
  Common Payoffs

abstract:
  Consider a very simple class of (finite) games: after an initial move by
nature, each player makes one move. Moreover, the players have common
interests: at each node, all the players get the same payoff. We show that the
problem of determining whether there exists a joint strategy where each player
has an expected payoff of at least r is NP-complete as a function of the number
of nodes in the extensive-form representation of the game.


title: Belief Revision: A Critique

abstract:
  We examine carefully the rationale underlying the approaches to belief change
taken in the literature, and highlight what we view as methodological problems.
We argue that to study belief change carefully, we must be quite explicit about
the ``ontology'' or scenario underlying the belief change process. This is
something that has been missing in previous work, with its focus on postulates.
Our analysis shows that we must pay particular attention to two issues that
have often been taken for granted: The first is how we model the agent's
epistemic state. (Do we use a set of beliefs, or a richer structure, such as an
ordering on worlds? And if we use a set of beliefs, in what language are these
beliefs are expressed?) We show that even postulates that have been called
``beyond controversy'' are unreasonable when the agent's beliefs include
beliefs about her own epistemic state as well as the external world. The second
is the status of observations. (Are observations known to be true, or just
believed? In the latter case, how firm is the belief?) Issues regarding the
status of observations arise particularly when we consider iterated belief
revision, and we must confront the possibility of revising by p and then by
not-p.


title: Quantum Clock Synchronization with one qubit

abstract:
  The clock synchronization problem is to determine the time difference T
between two spatially separated parties. We improve on I. Chuang's quantum
clock synchronization algorithm and show that it is possible to obtain T to n
bits of accuracy while communicating only one qubit in one direction and using
an O(2^n) frequency range. We also prove a quantum lower bound of \Omega(2^n)
for the product of the transmitted qubits and the range of frequencies, thus
showing that our algorithm is optimal.


title:
Secure, Efficient Data Transport and Replica Management for
  High-Performance Data-Intensive Computing

abstract:
  An emerging class of data-intensive applications involve the geographically
dispersed extraction of complex scientific information from very large
collections of measured or computed data. Such applications arise, for example,
in experimental physics, where the data in question is generated by
accelerators, and in simulation science, where the data is generated by
supercomputers. So-called Data Grids provide essential infrastructure for such
applications, much as the Internet provides essential services for applications
such as e-mail and the Web. We describe here two services that we believe are
fundamental to any Data Grid: reliable, high-speed transporet and replica
management. Our high-speed transport service, GridFTP, extends the popular FTP
protocol with new features required for Data Grid applciations, such as
striping and partial file access. Our replica management service integrates a
replica catalog with GridFTP transfers to provide for the creation,
registration, location, and management of dataset replicas. We present the
design of both services and also preliminary performance results. Our
implementations exploit security and other services provided by the Globus
Toolkit.


title: A Dualheap Selection Algorithm - A Call for Analysis

abstract:
  An algorithm is presented that efficiently solves the selection problem:
finding the k-th smallest member of a set. Relevant to a divide-and-conquer
strategy, the algorithm also partitions a set into small and large valued
subsets. Applied recursively, this partitioning results in a sorted set. The
algorithm's applicability is therefore much broader than just the selection
problem. The presented algorithm is based upon R.W. Floyd's 1964 algorithm that
constructs a heap from the bottom-up. Empirically, the presented algorithm's
performance appears competitive with the popular quickselect algorithm, a
variant of C.A.R. Hoare's 1962 quicksort algorithm. Furthermore, constructing a
heap from the bottom-up is an inherently parallel process (processors can work
independently and simultaneously on subheap construction), suggesting a
performance advantage with parallel implementations. Given the presented
algorithm's broad applicability, simplicity, serial performance, and parallel
nature, further study is warranted. Specifically, worst-case analysis is an
important but still unsolved problem.


title: Notes on computing peaks in k-levels and parametric spanning trees

abstract:
  We give an algorithm to compute all the local peaks in the $k$-level of an
arrangement of $n$ lines in $O(n \log n) + \tilde{O}((kn)^{2/3})$ time. We can
also find $\tau$ largest peaks in $O(n \log ^2 n) + \tilde{O}((\tau n)^{2/3})$
time. Moreover, we consider the longest edge in a parametric minimum spanning
tree (in other words, a bottleneck edge for connectivity), and give an
algorithm to compute the parameter value (within a given interval)
maximizing/minimizing the length of the longest edge in MST. The time
complexity is $\tilde{O}(n^{8/7}k^{1/7} + n k^{1/3})$


title: The Anatomy of the Grid - Enabling Scalable Virtual Organizations

abstract:
  "Grid" computing has emerged as an important new field, distinguished from
conventional distributed computing by its focus on large-scale resource
sharing, innovative applications, and, in some cases, high-performance
orientation. In this article, we define this new field. First, we review the
"Grid problem," which we define as flexible, secure, coordinated resource
sharing among dynamic collections of individuals, institutions, and
resources-what we refer to as virtual organizations. In such settings, we
encounter unique authentication, authorization, resource access, resource
discovery, and other challenges. It is this class of problem that is addressed
by Grid technologies. Next, we present an extensible and open Grid
architecture, in which protocols, services, application programming interfaces,
and software development kits are categorized according to their roles in
enabling resource sharing. We describe requirements that we believe any such
mechanisms must satisfy, and we discuss the central role played by the
intergrid protocols that enable interoperability among different Grid systems.
Finally, we discuss how Grid technologies relate to other contemporary
technologies, including enterprise integration, application service provider,
storage service provider, and peer-to-peer computing. We maintain that Grid
concepts and technologies complement and have much to contribute to these other
approaches.


title: A Decision Tree of Bigrams is an Accurate Predictor of Word Sense

abstract:
  This paper presents a corpus-based approach to word sense disambiguation
where a decision tree assigns a sense to an ambiguous word based on the bigrams
that occur nearby. This approach is evaluated using the sense-tagged corpora
from the 1998 SENSEVAL word sense disambiguation exercise. It is more accurate
than the average results reported for 30 of 36 words, and is more accurate than
the best results for 19 of 36 words.


title: Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure

abstract:
  In this paper we introduce a general framework for casting fully dynamic
transitive closure into the problem of reevaluating polynomials over matrices.
With this technique, we improve the best known bounds for fully dynamic
transitive closure. In particular, we devise a deterministic algorithm for
general directed graphs that achieves $O(n^2)$ amortized time for updates,
while preserving unit worst-case cost for queries. In case of deletions only,
our algorithm performs updates faster in O(n) amortized time.
  Our matrix-based approach yields an algorithm for directed acyclic graphs
that breaks through the $O(n^2)$ barrier on the single-operation complexity of
fully dynamic transitive closure. We can answer queries in $O(n^\epsilon)$ time
and perform updates in $O(n^{\omega(1,\epsilon,1)-\epsilon}+n^{1+\epsilon})$
time, for any $\epsilon\in[0,1]$, where $\omega(1,\epsilon,1)$ is the exponent
of the multiplication of an $n\times n^{\epsilon}$ matrix by an
$n^{\epsilon}\times n$ matrix. The current best bounds on
$\omega(1,\epsilon,1)$ imply an $O(n^{0.58})$ query time and an $O(n^{1.58})$
update time. Our subquadratic algorithm is randomized, and has one-side error.


title: Replica Selection in the Globus Data Grid

abstract:
  The Globus Data Grid architecture provides a scalable infrastructure for the
management of storage resources and data that are distributed across Grid
environments. These services are designed to support a variety of scientific
applications, ranging from high-energy physics to computational genomics, that
require access to large amounts of data (terabytes or even petabytes) with
varied quality of service requirements. By layering on a set of core services,
such as data transport, security, and replica cataloging, one can construct
various higher-level services. In this paper, we discuss the design and
implementation of a high-level replica selection service that uses information
regarding replica location and user preferences to guide selection from among
storage replica alternatives. We first present a basic replica selection
service design, then show how dynamic information collected using Globus
information service capabilities concerning storage system properties can help
improve and optimize the selection process. We demonstrate the use of Condor's
ClassAds resource description and matchmaking mechanism as an efficient tool
for representing and matching storage resource capabilities and policies
against application requirements.


title: Chain Programs for Writing Deterministic Metainterpreters

abstract:
  Many metainterpreters found in the logic programming literature are
nondeterministic in the sense that the selection of program clauses is not
determined. Examples are the familiar "demo" and "vanilla" metainterpreters.
For some applications this nondeterminism is convenient. In some cases,
however, a deterministic metainterpreter, having an explicit selection of
clauses, is needed. Such cases include (1) conversion of OR parallelism into
AND parallelism for "committed-choice" processors, (2) logic-based,
imperative-language implementation of search strategies, and (3) simulation of
bounded-resource reasoning.
  Deterministic metainterpreters are difficult to write because the programmer
must be concerned about the set of unifiers of the children of a node in the
derivation tree. We argue that it is both possible and advantageous to write
these metainterpreters by reasoning in terms of object programs converted into
a syntactically restricted form that we call "chain" form, where we can forget
about unification, except for unit clauses. We give two transformations
converting logic programs into chain form, one for "moded" programs (implicit
in two existing exhaustive-traversal methods for committed-choice execution),
and one for arbitrary definite programs. As illustrations of our approach we
show examples of the three applications mentioned above.


title:
Secure Counting: counting members of a subset without revealing their
  identities

abstract:
  Suppose there is a group of N people some of whom possess a specific
property. For example, their wealth is above or below a threshold, they voted
for a particular candidate, they have a certain disease, etc. The group wants
to find out how many of its members posses the property -- without revealing
the identities. Unless of course it turns out that all members do or do not
have the attribute of interest. However, in all other cases the counting
algorithm should guarantee that nobody can find out if a particular individual
possesses the property unless all the other N-1 members of the group collude.
  The present article describes a method to solve the confidential counting
problem with only 3*N-2 pairwise communications, or 2*N broadcasts (the last
N-1 pairwise communications are merely to announce the result). The counting
algorithm does not require any trusted third parties. All communications
between parties involved can be conducted in public without compromising the
security of counting.


title: Bootstrapping Structure using Similarity

abstract:
  In this paper a new similarity-based learning algorithm, inspired by string
edit-distance (Wagner and Fischer, 1974), is applied to the problem of
bootstrapping structure from scratch. The algorithm takes a corpus of
unannotated sentences as input and returns a corpus of bracketed sentences. The
method works on pairs of unstructured sentences or sentences partially
bracketed by the algorithm that have one or more words in common. It finds
parts of sentences that are interchangeable (i.e. the parts of the sentences
that are different in both sentences). These parts are taken as possible
constituents of the same type. While this corresponds to the basic
bootstrapping step of the algorithm, further structure may be learned from
comparison with other (similar) sentences.
  We used this method for bootstrapping structure from the flat sentences of
the Penn Treebank ATIS corpus, and compared the resulting structured sentences
to the structured sentences in the ATIS corpus. Similarly, the algorithm was
tested on the OVIS corpus. We obtained 86.04 % non-crossing brackets precision
on the ATIS corpus and 89.39 % non-crossing brackets precision on the OVIS
corpus.


title: ABL: Alignment-Based Learning

abstract:
  This paper introduces a new type of grammar learning algorithm, inspired by
string edit distance (Wagner and Fischer, 1974). The algorithm takes a corpus
of flat sentences as input and returns a corpus of labelled, bracketed
sentences. The method works on pairs of unstructured sentences that have one or
more words in common. When two sentences are divided into parts that are the
same in both sentences and parts that are different, this information is used
to find parts that are interchangeable. These parts are taken as possible
constituents of the same type. After this alignment learning step, the
selection learning step selects the most probable constituents from all
possible constituents.
  This method was used to bootstrap structure on the ATIS corpus (Marcus et
al., 1993) and on the OVIS (Openbaar Vervoer Informatie Systeem (OVIS) stands
for Public Transport Information System.) corpus (Bonnema et al., 1997). While
the results are encouraging (we obtained up to 89.25 % non-crossing brackets
precision), this paper will point out some of the shortcomings of our approach
and will suggest possible solutions.


title: Bootstrapping Syntax and Recursion using Alignment-Based Learning

abstract:
  This paper introduces a new type of unsupervised learning algorithm, based on
the alignment of sentences and Harris's (1951) notion of interchangeability.
The algorithm is applied to an untagged, unstructured corpus of natural
language sentences, resulting in a labelled, bracketed version of the corpus.
Firstly, the algorithm aligns all sentences in the corpus in pairs, resulting
in a partition of the sentences consisting of parts of the sentences that are
similar in both sentences and parts that are dissimilar. This information is
used to find (possibly overlapping) constituents. Next, the algorithm selects
(non-overlapping) constituents. Several instances of the algorithm are applied
to the ATIS corpus (Marcus et al., 1993) and the OVIS (Openbaar Vervoer
Informatie Systeem (OVIS) stands for Public Transport Information System.)
corpus (Bonnema et al., 1997). Apart from the promising numerical results, the
most striking result is that even the simplest algorithm based on alignment
learns recursion.


title: Event Indexing Systems for Efficient Selection and Analysis of HERA Data

abstract:
  The design and implementation of two software systems introduced to improve
the efficiency of offline analysis of event data taken with the ZEUS Detector
at the HERA electron-proton collider at DESY are presented. Two different
approaches were made, one using a set of event directories and the other using
a tag database based on a commercial object-oriented database management
system. These are described and compared. Both systems provide quick direct
access to individual collision events in a sequential data store of several
terabytes, and they both considerably improve the event analysis efficiency. In
particular the tag database provides a very flexible selection mechanism and
can dramatically reduce the computing time needed to extract small subsamples
from the total event sample. Gains as large as a factor 20 have been obtained.


title: Evaluating Recommendation Algorithms by Graph Analysis

abstract:
  We present a novel framework for evaluating recommendation algorithms in
terms of the `jumps' that they make to connect people to artifacts. This
approach emphasizes reachability via an algorithm within the implicit graph
structure underlying a recommender dataset, and serves as a complement to
evaluation in terms of predictive accuracy. The framework allows us to consider
questions relating algorithmic parameters to properties of the datasets. For
instance, given a particular algorithm `jump,' what is the average path length
from a person to an artifact? Or, what choices of minimum ratings and jumps
maintain a connected graph? We illustrate the approach with a common jump
called the `hammock' using movie recommender datasets.


title: Type Arithmetics: Computation based on the theory of types

abstract:
  The present paper shows meta-programming turn programming, which is rich
enough to express arbitrary arithmetic computations. We demonstrate a type
system that implements Peano arithmetics, slightly generalized to negative
numbers. Certain types in this system denote numerals. Arithmetic operations on
such types-numerals - addition, subtraction, and even division - are expressed
as type reduction rules executed by a compiler. A remarkable trait is that
division by zero becomes a type error - and reported as such by a compiler.


title: Potholes on the Royal Road

abstract:
  It is still unclear how an evolutionary algorithm (EA) searches a fitness
landscape, and on what fitness landscapes a particular EA will do well. The
validity of the building-block hypothesis, a major tenet of traditional genetic
algorithm theory, remains controversial despite its continued use to justify
claims about EAs. This paper outlines a research program to begin to answer
some of these open questions, by extending the work done in the royal road
project. The short-term goal is to find a simple class of functions which the
simple genetic algorithm optimizes better than other optimization methods, such
as hillclimbers. A dialectical heuristic for searching for such a class is
introduced. As an example of using the heuristic, the simple genetic algorithm
is compared with a set of hillclimbers on a simple subset of the
hyperplane-defined functions, the pothole functions.


title:
System Support for Bandwidth Management and Content Adaptation in
  Internet Applications

abstract:
  This paper describes the implementation and evaluation of an operating system
module, the Congestion Manager (CM), which provides integrated network flow
management and exports a convenient programming interface that allows
applications to be notified of, and adapt to, changing network conditions. We
describe the API by which applications interface with the CM, and the
architectural considerations that factored into the design. To evaluate the
architecture and API, we describe our implementations of TCP; a streaming
layered audio/video application; and an interactive audio application using the
CM, and show that they achieve adaptive behavior without incurring much
end-system overhead. All flows including TCP benefit from the sharing of
congestion information, and applications are able to incorporate new
functionality such as congestion control and adaptive behavior.


title:
Shooting Over or Under the Mark: Towards a Reliable and Flexible
  Anticipation in the Economy

abstract:
  The real monetary economy is grounded upon monetary flow equilibration or the
activity of actualizing monetary flow continuity at each economic agent except
for the central bank. Every update of monetary flow continuity at each agent
constantly causes monetary flow equilibration at the neighborhood agents. Every
monetary flow equilibration as the activity of shooting the mark identified as
monetary flow continuity turns out to be off the mark, and constantly generate
the similar activities in sequence. Monetary flow equilibration ceaselessly
reverberating in the economy performs two functions. One is to seek an
organization on its own, and the other is to perturb the ongoing organization.
Monetary flow equilibration as the agency of seeking and perturbing its
organization also serves as a means of predicting its behavior. The likely
organizational behavior could be the one that remains most robust against
monetary flow equilibration as an agency of applying perturbations.


title: Tracing a Faint Fingerprint of the Invisible Hand?

abstract:
  Any economic agent constituting the monetary economy maintains the activity
of monetary flow equilibration for fulfilling the condition of monetary flow
continuity in the record, except at the central bank. At the same time,
monetary flow equilibration at one economic agent constantly induces at other
agents in the economy further flow disequilibrium to be eliminated
subsequently. We propose the rate of monetary flow disequilibration as a figure
measuring the progressive movement of the economy. The rate of disequilibration
was read out of both the Japanese and the United States monetary economy
recorded over the last fifty years.


title:
Application of Support Vector Machine to detect an association between a
  disease or trait and multiple SNP variations

abstract:
  After the completion of human genome sequence was anounced, it is evident
that interpretation of DNA sequences is an immediate task to work on. For
understanding their signals, improvement of present sequence analysis tools and
developing new ones become necessary. Along this current trend, we attack one
of the fundamental questions, which set of SNP(single nucleotide polymorphism)
variations is related to a specific disease or trait is. For, in the whole DNA
sequence, it is known that people have different DNAs only at SNP locations,
and moreover, the total SNPs are less than 5 millions, finding an association
between SNP variations and certain disease or trait is believed to be one of
the essential steps not only for genetic researches but for drug design and
discovery. In this paper, we are going to present a method of detecting whether
there is an association between multiple SNP variations and a trait or disease.
The method exploits the Support Vector Machine which has been attracting lots
of attentions recently.


title: The Gibbs Representation of 3D Rotations

abstract:
  This paper revisits the little-known Gibbs-Rodrigues representation of
rotations in a three-dimensional space and demonstrates a set of algorithms for
handling it. In this representation the rotation is itself represented as a
three-dimensional vector. The vector is parallel to the axis of rotation and
its three components transform covariantly on change of coordinates. The
mapping from rotations to vectors is 1:1 apart from computation error. The
discontinuities of the representation require special handling but are not
problematic. The rotation matrix can be generated efficiently from the vector
without the use of transcendental functions, and vice-versa. The representation
is more efficient than Euler angles, has affinities with Hassenpflug's Argyris
angles and is very closely related to the quaternion representation. While the
quaternion representation avoids the discontinuities inherent in any
3-component representation, this problem is readily overcome. The present paper
gives efficient algorithms for computing the set of rotations which map a given
vector to another of the same length and the rotation which maps a given pair
of vectors to another pair of the same length and subtended angle.


title: Local Search Techniques for Constrained Portfolio Selection Problems

abstract:
  We consider the problem of selecting a portfolio of assets that provides the
investor a suitable balance of expected return and risk. With respect to the
seminal mean-variance model of Markowitz, we consider additional constraints on
the cardinality of the portfolio and on the quantity of individual shares. Such
constraints better capture the real-world trading system, but make the problem
more difficult to be solved with exact methods. We explore the use of local
search techniques, mainly tabu search, for the portfolio selection problem. We
compare and combine previous work on portfolio selection that makes use of the
local search approach and we propose new algorithms that combine different
neighborhood relations. In addition, we show how the use of randomization and
of a simple form of adaptiveness simplifies the setting of a large number of
critical parameters. Finally, we show how our techniques perform on public
benchmarks.


title:
Several new domain-type and boundary-type numerical discretization
  schemes with radial basis function

abstract:
  This paper is concerned with a few novel RBF-based numerical schemes
discretizing partial differential equations. For boundary-type methods, we
derive the indirect and direct symmetric boundary knot methods (BKM). The
resulting interpolation matrix of both is always symmetric irrespective of
boundary geometry and conditions. In particular, the direct BKM applies the
practical physical variables rather than expansion coefficients and becomes
very competitive to the boundary element method. On the other hand, based on
the multiple reciprocity principle, we invent the RBF-based boundary particle
method (BPM) for general inhomogeneous problems without a need using inner
nodes. The direct and symmetric BPM schemes are also developed.
  For domain-type RBF discretization schemes, by using the Green integral we
develop a new Hermite RBF scheme called as the modified Kansa method (MKM),
which differs from the symmetric Hermite RBF scheme in that the MKM discretizes
both governing equation and boundary conditions on the same boundary nodes. The
local spline version of the MKM is named as the finite knot method (FKM). Both
MKM and FKM significantly reduce calculation errors at nodes adjacent to
boundary. In addition, the nonsingular high-order fundamental or general
solution is strongly recommended as the RBF in the domain-type methods and dual
reciprocity method approximation of particular solution relating to the BKM.
  It is stressed that all the above discretization methods of boundary-type and
domain-type are symmetric, meshless, and integration-free. The spline-based
schemes will produce desirable symmetric sparse banded interpolation matrix. In
appendix, we present a Hermite scheme to eliminate edge effect on the RBF
geometric modeling and imaging.


title:
Dynamic Nonlocal Language Modeling via Hierarchical Topic-Based
  Adaptation

abstract:
  This paper presents a novel method of generating and applying hierarchical,
dynamic topic-based language models. It proposes and evaluates new cluster
generation, hierarchical smoothing and adaptive topic-probability estimation
techniques. These combined models help capture long-distance lexical
dependencies. Experiments on the Broadcast News corpus show significant
improvement in perplexity (10.5% overall and 33.5% on target vocabulary).


title:
Coaxing Confidences from an Old Friend: Probabilistic Classifications
  from Transformation Rule Lists

abstract:
  Transformation-based learning has been successfully employed to solve many
natural language processing problems. It has many positive features, but one
drawback is that it does not provide estimates of class membership
probabilities.
  In this paper, we present a novel method for obtaining class membership
probabilities from a transformation-based rule list classifier. Three
experiments are presented which measure the modeling accuracy and cross-entropy
of the probabilistic classifier on unseen data and the degree to which the
output probabilities from the classifier can be used to estimate confidences in
its classification decisions.
  The results of these experiments show that, for the task of text chunking,
the estimates produced by this technique are more informative than those
generated by a state-of-the-art decision tree.


title: Disjunction and modular goal-directed proof search

abstract:
  This paper explores goal-directed proof search in first-order multi-modal
logic. The key issue is to design a proof system that respects the modularity
and locality of assumptions of many modal logics. By forcing ambiguities to be
considered independently, modular disjunctions in particular can be used to
construct efficiently executable specifications in reasoning tasks involving
partial information that otherwise might require prohibitive search. To achieve
this behavior requires prior proof-theoretic justifications of logic
programming to be extended, strengthened, and combined with proof-theoretic
analyses of modal deduction in a novel way.


title: Microplanning with Communicative Intentions: The SPUD System

abstract:
  The process of microplanning encompasses a range of problems in Natural
Language Generation (NLG), such as referring expression generation, lexical
choice, and aggregation, problems in which a generator must bridge underlying
domain-specific representations and general linguistic representations. In this
paper, we describe a uniform approach to microplanning based on declarative
representations of a generator's communicative intent. These representations
describe the results of NLG: communicative intent associates the concrete
linguistic structure planned by the generator with inferences that show how the
meaning of that structure communicates needed information about some
application domain in the current discourse context. Our approach, implemented
in the SPUD (sentence planning using description) microplanner, uses the
lexicalized tree-adjoining grammar formalism (LTAG) to connect structure to
meaning and uses modal logic programming to connect meaning to context. At the
same time, communicative intent representations provide a resource for the
process of NLG. Using representations of communicative intent, a generator can
augment the syntax, semantics and pragmatics of an incomplete sentence
simultaneously, and can assess its progress on the various problems of
microplanning incrementally. The declarative formulation of communicative
intent translates into a well-defined methodology for designing grammatical and
conceptual resources which the generator can use to achieve desired
microplanning behavior in a specified domain.


title:
Correction of Errors in a Modality Corpus Used for Machine Translation
  by Using Machine-learning Method

abstract:
  We performed corpus correction on a modality corpus for machine translation
by using such machine-learning methods as the maximum-entropy method. We thus
constructed a high-quality modality corpus based on corpus correction. We
compared several kinds of methods for corpus correction in our experiments and
developed a good method for corpus correction.


title: Man [and Woman] vs. Machine: A Case Study in Base Noun Phrase Learning

abstract:
  A great deal of work has been done demonstrating the ability of machine
learning algorithms to automatically extract linguistic knowledge from
annotated corpora. Very little work has gone into quantifying the difference in
ability at this task between a person and a machine. This paper is a first step
in that direction.


title:
Rule Writing or Annotation: Cost-efficient Resource Usage for Base Noun
  Phrase Chunking

abstract:
  This paper presents a comprehensive empirical comparison between two
approaches for developing a base noun phrase chunker: human rule writing and
active learning using interactive real-time human annotation. Several novel
variations on active learning are investigated, and underlying cost models for
cross-modal machine learning comparison are presented and explored. Results
show that it is more efficient and more successful by several measures to train
a system using active learning annotation rather than hand-crafted rule writing
at a comparable level of human labor investment.


title: Parallel implementation of the TRANSIMS micro-simulation

abstract:
  This paper describes the parallel implementation of the TRANSIMS traffic
micro-simulation. The parallelization method is domain decomposition, which
means that each CPU of the parallel computer is responsible for a different
geographical area of the simulated region. We describe how information between
domains is exchanged, and how the transportation network graph is partitioned.
An adaptive scheme is used to optimize load balancing. We then demonstrate how
computing speeds of our parallel micro-simulations can be systematically
predicted once the scenario and the computer architecture are known. This makes
it possible, for example, to decide if a certain study is feasible with a
certain computing budget, and how to invest that budget. The main ingredients
of the prediction are knowledge about the parallel implementation of the
micro-simulation, knowledge about the characteristics of the partitioning of
the transportation network graph, and knowledge about the interaction of these
quantities with the computer system. In particular, we investigate the
differences between switched and non-switched topologies, and the effects of 10
Mbit, 100 Mbit, and Gbit Ethernet. keywords: Traffic simulation, parallel
computing, transportation planning, TRANSIMS


title: A Complete WordNet1.5 to WordNet1.6 Mapping

abstract:
  We describe a robust approach for linking already existing lexical/semantic
hierarchies. We use a constraint satisfaction algorithm (relaxation labelling)
to select --among a set of candidates-- the node in a target taxonomy that
bests matches each node in a source taxonomy. In this paper we present the
complete mapping of the nominal, verbal, adjectival and adverbial parts of
WordNet 1.5 onto WordNet 1.6.


title:
Reverse Engineering from Assembler to Formal Specifications via Program
  Transformations

abstract:
  The FermaT transformation system, based on research carried out over the last
sixteen years at Durham University, De Montfort University and Software
Migrations Ltd., is an industrial-strength formal transformation engine with
many applications in program comprehension and language migration. This paper
is a case study which uses automated plus manually-directed transformations and
abstractions to convert an IBM 370 Assembler code program into a very
high-level abstract specification.