title: Sorting with a forklift

abstract:
  A fork stack is a generalised stack which allows pushes and pops of several
items at a time. We consider the problem of determining which input streams can
be sorted using a single forkstack, or dually, which permutations of a fixed
input stream can be produced using a single forkstack. An algorithm is given to
solve the sorting problem and the minimal unsortable sequences are found. The
results are extended to fork stacks where there are bounds on how many items
can be pushed and popped at one time. In this context we also establish how to
enumerate the collection of sortable sequences.


title:
Evolution and Gravitation: a Computer Simulation of a Non-Walrasian
  Equilibrium Model

abstract:
  The paper contains a computer simulation concerning a basic non-Walrasian
equilibrium system, following the Edmond Malinvaud "short side" approach, as
far as the price adjustment is concerned, and the sequential Hicksian "weeks"
structure with regard of the temporal characterization.


title: Probabilistic Reversible Automata and Quantum Automata

abstract:
  To study relationship between quantum finite automata and probabilistic
finite automata, we introduce a notion of probabilistic reversible automata
(PRA, or doubly stochastic automata). We find that there is a strong
relationship between different possible models of PRA and corresponding models
of quantum finite automata. We also propose a classification of reversible
finite 1-way automata.


title: Reasoning about Evolving Nonmonotonic Knowledge Bases

abstract:
  Recently, several approaches to updating knowledge bases modeled as extended
logic programs have been introduced, ranging from basic methods to incorporate
(sequences of) sets of rules into a logic program, to more elaborate methods
which use an update policy for specifying how updates must be incorporated. In
this paper, we introduce a framework for reasoning about evolving knowledge
bases, which are represented as extended logic programs and maintained by an
update policy. We first describe a formal model which captures various update
approaches, and we define a logical language for expressing properties of
evolving knowledge bases. We then investigate semantical and computational
properties of our framework, where we focus on properties of knowledge states
with respect to the canonical reasoning task of whether a given formula holds
on a given evolving knowledge base. In particular, we present finitary
characterizations of the evolution for certain classes of framework instances,
which can be exploited for obtaining decidability results. In more detail, we
characterize the complexity of reasoning for some meaningful classes of
evolving knowledge bases, ranging from polynomial to double exponential space
complexity.


title: A new definition of the fractional Laplacian

abstract:
  It is noted that the standard definition of the fractional Laplacian leads to
a hyper-singular convolution integral and is also obscure about how to
implement the boundary conditions. This purpose of this note is to introduce a
new definition of the fractional Laplacian to overcome these major drawbacks.


title: Activities, Context and Ubiquitous Computing

abstract:
  Context and context-awareness provides computing environments with the
ability to usefully adapt the services or information they provide. It is the
ability to implicitly sense and automatically derive the user needs that
separates context-aware applications from traditionally designed applications,
and this makes them more attentive, responsive, and aware of their user's
identity, and their user's environment. This paper argues that context-aware
applications capable of supporting complex, cognitive activities can be built
from a model of context called Activity-Centric Context. A conceptual model of
Activity-Centric context is presented. The model is illustrated via a detailed
example.


title:
A Comparison of Different Cognitive Paradigms Using Simple Animats in a
  Virtual Laboratory, with Implications to the Notion of Cognition

abstract:
  In this thesis I present a virtual laboratory which implements five different
models for controlling animats: a rule-based system, a behaviour-based system,
a concept-based system, a neural network, and a Braitenberg architecture.
Through different experiments, I compare the performance of the models and
conclude that there is no "best" model, since different models are better for
different things in different contexts.
  The models I chose, although quite simple, represent different approaches for
studying cognition. Using the results as an empirical philosophical aid,
  I note that there is no "best" approach for studying cognition, since
different approaches have all advantages and disadvantages, because they study
different aspects of cognition from different contexts. This has implications
for current debates on "proper" approaches for cognition: all approaches are a
bit proper, but none will be "proper enough". I draw remarks on the notion of
cognition abstracting from all the approaches used to study it, and propose a
simple classification for different types of cognition.


title: Practical Load Balancing for Content Requests in Peer-to-Peer Networks

abstract:
  This paper studies the problem of load-balancing the demand for content in a
peer-to-peer network across heterogeneous peer nodes that hold replicas of the
content. Previous decentralized load balancing techniques in distributed
systems base their decisions on periodic updates containing information about
load or available capacity observed at the serving entities. We show that these
techniques do not work well in the peer-to-peer context; either they do not
address peer node heterogeneity, or they suffer from significant load
oscillations. We propose a new decentralized algorithm, Max-Cap, based on the
maximum inherent capacities of the replica nodes and show that unlike previous
algorithms, it is not tied to the timeliness or frequency of updates. Yet,
Max-Cap can handle the heterogeneity of a peer-to-peer environment without
suffering from load oscillations.


title:
Errors in Low and Lapsley's article "Optimization Flow Control, I: Basic
  Algorithm and Convergence"

abstract:
  In the note two errors in Low and Lapsley's article "Optimization Flow
Control, I: Basic Algorithm and Convergence", "IEEE/ACM Transactions on
Networking", 7(6), pp. 861-874, 1999, are shown. Because of these errors the
proofs of both theorems presented in the article are incomplete and some
assessments are wrong.


title:
Correction to Low and Lapsley's article "Optimization Flow Control, I:
  Basic Algorithm and Convergence"

abstract:
  In the note an error in Low and Lapsley's article ("Optimization Flow
Control, I: Basic Algorithm and Convergence", IEEE/ACM Transactions on
Networking, 7(6), pp. 861-874, 1999) is pointed out. Because of this error the
proof of the Theorem 2 presented in the article is incomplete and some
assessments are wrong. In the second part of the note the author proposes a
correction to this proof.


title: A universal alphabet and rewrite system

abstract:
  We present two ways in which an infinite universal alphabet may be generated
using a novel rewrite system that conserves zero (a special character of the
alphabet and the symbol for that character) at every step. The recursive method
delivers the entire alphabet in one step when invoked with the zero character
as the initial subset alphabet. The iterative method with the same start
delivers characters that act as ciphers for properties that the developing
subset alphabet contains. These properties emerge in an arbitrary sequence and
there are an infinite number of ways they may be selected. The subset alphabets
in addition to having mathematical interpretation as algebra can also be
constrained to emerge in a minimal way which then has application as a
foundational physical system. Each subset alphabet may itself be the basis of a
rewrite system where rules that operate on symbols (representing characters) or
collections of symbols manipulate the specific properties in a dynamic way.


title: Remarks on d-Dimensional TSP Optimal Tour Length Behaviour

abstract:
  The well-known $O(n^{1-1/d})$ behaviour of the optimal tour length for TSP in
d-dimensional Cartesian space causes breaches of the triangle inequality. Other
practical inadequacies of this model are discussed, including its use as basis
for approximation of the TSP optimal tour length or bounds derivations, which I
attempt to remedy.


title:
Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer
  Systems and Implications for System Design

abstract:
  Despite recent excitement generated by the peer-to-peer (P2P) paradigm and
the surprisingly rapid deployment of some P2P applications, there are few
quantitative evaluations of P2P systems behavior. The open architecture,
achieved scale, and self-organizing structure of the Gnutella network make it
an interesting P2P architecture to study. Like most other P2P applications,
Gnutella builds, at the application level, a virtual network with its own
routing mechanisms. The topology of this virtual network and the routing
mechanisms used have a significant influence on application properties such as
performance, reliability, and scalability. We have built a "crawler" to extract
the topology of Gnutella's application level network. In this paper we analyze
the topology graph and evaluate generated network traffic. Our two major
findings are that: (1) although Gnutella is not a pure power-law network, its
current configuration has the benefits and drawbacks of a power-law structure,
and (2) the Gnutella virtual network topology does not match well the
underlying Internet topology, hence leading to ineffective use of the physical
networking infrastructure. These findings guide us to propose changes to the
Gnutella protocol and implementations that may bring significant performance
and scalability improvements. We believe that our findings as well as our
measurement and analysis techniques have broad applicability to P2P systems and
provide unique insights into P2P system design tradeoffs.


title: A generalization of Amdahl's law and relative conditions of parallelism

abstract:
  In this work I present a generalization of Amdahl's law on the limits of a
parallel implementation with many processors. In particular I establish some
mathematical relations involving the number of processors and the dimension of
the treated problem, and with these conditions I define, on the ground of the
reachable speedup, some classes of parallelism for the implementations. I also
derive a condition for obtaining superlinear speedup. The used mathematical
technics are those of differential calculus. I describe some examples from
classical problems offered by the specialized literature on the subject.


title: Extremal Optimization: an Evolutionary Local-Search Algorithm

abstract:
  A recently introduced general-purpose heuristic for finding high-quality
solutions for many hard optimization problems is reviewed. The method is
inspired by recent progress in understanding far-from-equilibrium phenomena in
terms of {\em self-organized criticality,} a concept introduced to describe
emergent complexity in physical systems. This method, called {\em extremal
optimization,} successively replaces the value of extremely undesirable
variables in a sub-optimal solution with new, random ones. Large,
avalanche-like fluctuations in the cost function self-organize from this
dynamics, effectively scaling barriers to explore local optima in distant
neighborhoods of the configuration space while eliminating the need to tune
parameters. Drawing upon models used to simulate the dynamics of granular
media, evolution, or geology, extremal optimization complements approximation
methods inspired by equilibrium statistical physics, such as {\em simulated
annealing}. It may be but one example of applying new insights into {\em
non-equilibrium phenomena} systematically to hard optimization problems. This
method is widely applicable and so far has proved competitive with -- and even
superior to -- more elaborate general-purpose heuristics on testbeds of
constrained optimization problems with up to $10^5$ variables, such as
bipartitioning, coloring, and satisfiability. Analysis of a suitable model
predicts the only free parameter of the method in accordance with all
experimental results.


title: Locating Data in (Small-World?) Peer-to-Peer Scientific Collaborations

abstract:
  Data-sharing scientific collaborations have particular characteristics,
potentially different from the current peer-to-peer environments. In this paper
we advocate the benefits of exploiting emergent patterns in self-configuring
networks specialized for scientific data-sharing collaborations. We speculate
that a peer-to-peer scientific collaboration network will exhibit small-world
topology, as do a large number of social networks for which the same pattern
has been documented. We propose a solution for locating data in decentralized,
scientific, data-sharing environments that exploits the small-worlds topology.
The research challenge we raise is: what protocols should be used to allow a
self-configuring peer-to-peer network to form small worlds similar to the way
in which the humans that use the network do in their social interactions?


title: Complexity Results on DPLL and Resolution

abstract:
  DPLL and resolution are two popular methods for solving the problem of
propositional satisfiability. Rather than algorithms, they are families of
algorithms, as their behavior depend on some choices they face during
execution: DPLL depends on the choice of the literal to branch on; resolution
depends on the choice of the pair of clauses to resolve at each step. The
complexity of making the optimal choice is analyzed in this paper. Extending
previous results, we prove that choosing the optimal literal to branch on in
DPLL is Delta[log]^2-hard, and becomes NP^PP-hard if branching is only allowed
on a subset of variables. Optimal choice in regular resolution is both NP-hard
and CoNP-hard. The problem of determining the size of the optimal proofs is
also analyzed: it is CoNP-hard for DPLL, and Delta[log]^2-hard if a conjecture
we make is true. This problem is CoNP-hard for regular resolution.


title:
Preemptive Scheduling of Equal-Length Jobs to Maximize Weighted
  Throughput

abstract:
  We study the problem of computing a preemptive schedule of equal-length jobs
with given release times, deadlines and weights. Our goal is to maximize the
weighted throughput, which is the total weight of completed jobs. In Graham's
notation this problem is described as (1 | r_j;p_j=p;pmtn | sum w_j U_j). We
provide an O(n^4)-time algorithm for this problem, improving the previous bound
of O(n^{10}) by Baptiste.


title:
An Algorithmic Study of Manufacturing Paperclips and Other Folded
  Structures

abstract:
  We study algorithmic aspects of bending wires and sheet metal into a
specified structure. Problems of this type are closely related to the question
of deciding whether a simple non-self-intersecting wire structure (a
carpenter's ruler) can be straightened, a problem that was open for several
years and has only recently been solved in the affirmative.
  If we impose some of the constraints that are imposed by the manufacturing
process, we obtain quite different results. In particular, we study the variant
of the carpenter's ruler problem in which there is a restriction that only one
joint can be modified at a time. For a linkage that does not self-intersect or
self-touch, the recent results of Connelly et al. and Streinu imply that it can
always be straightened, modifying one joint at a time. However, we show that
for a linkage with even a single vertex degeneracy, it becomes NP-hard to
decide if it can be straightened while altering only one joint at a time. If we
add the restriction that each joint can be altered at most once, we show that
the problem is NP-complete even without vertex degeneracies.
  In the special case, arising in wire forming manufacturing, that each joint
can be altered at most once, and must be done sequentially from one or both
ends of the linkage, we give an efficient algorithm to determine if a linkage
can be straightened.


title: Edsger Wybe Dijkstra (1930 -- 2002): A Portrait of a Genius

abstract:
  We discuss the scientific contributions of Edsger Wybe Dijkstra, his opinions
and his legacy.


title:
GridBank: A Grid Accounting Services Architecture (GASA) for Distributed
  Systems Sharing and Integration

abstract:
  Computational Grids are emerging as new infrastructure for Internet-based
parallel and distributed computing. They enable the sharing, exchange,
discovery, and aggregation of resources distributed across multiple
administrative domains, organizations and enterprises. To accomplish this,
Grids need infrastructure that supports various services: security, uniform
access, resource management, scheduling, application composition, computational
economy, and accountability. Many Grid projects have developed technologies
that provide many of these services with an exception of accountability. To
overcome this limitation, we propose a new infrastructure called Grid Bank that
provides services for accounting. This paper presents requirements of Grid
accountability and different models within which it can operate and proposes
Grid Bank Services Architecture that meets them. The paper highlights
implementation issues with detailed discussion on format for various
records/database that the GridBank need to maintain. It also presents protocols
for interaction between GridBank and various components within Grid computing
environments.


title: On the Reflexivity of Point Sets

abstract:
  We introduce a new measure for planar point sets S that captures a
combinatorial distance that S is from being a convex set: The reflexivity
rho(S) of S is given by the smallest number of reflex vertices in a simple
polygonalization of S. We prove various combinatorial bounds and provide
efficient algorithms to compute reflexivity, both exactly (in special cases)
and approximately (in general). Our study considers also some closely related
quantities, such as the convex cover number kappa_c(S) of a planar point set,
which is the smallest number of convex chains that cover S, and the convex
partition number kappa_p(S), which is given by the smallest number of convex
chains with pairwise-disjoint convex hulls that cover S. We have proved that it
is NP-complete to determine the convex cover or the convex partition number and
have given logarithmic-approximation algorithms for determining each.


title: Revising Partially Ordered Beliefs

abstract:
  This paper deals with the revision of partially ordered beliefs. It proposes
a semantic representation of epistemic states by partial pre-orders on
interpretations and a syntactic representation by partially ordered belief
bases. Two revision operations, the revision stemming from the history of
observations and the possibilistic revision, defined when the epistemic state
is represented by a total pre-order, are generalized, at a semantic level, to
the case of a partial pre-order on interpretations, and at a syntactic level,
to the case of a partially ordered belief base. The equivalence between the two
representations is shown for the two revision operations.


title: Positive time fractional derivative

abstract:
  In mathematical modeling of the non-squared frequency-dependent diffusions,
also known as the anomalous diffusions, it is desirable to have a positive real
Fourier transform for the time derivative of arbitrary fractional or odd
integer order. The Fourier transform of the fractional time derivative in the
Riemann-Liouville and Caputo senses, however, involves a complex power function
of the fractional order. In this study, a positive time derivative of
fractional or odd integer order is introduced to respect the positivity in
modeling the anomalous diffusions.


title: Dynamic Ordered Sets with Exponential Search Trees

abstract:
  We introduce exponential search trees as a novel technique for converting
static polynomial space search structures for ordered sets into fully-dynamic
linear space data structures.
  This leads to an optimal bound of O(sqrt(log n/loglog n)) for searching and
updating a dynamic set of n integer keys in linear space. Here searching an
integer y means finding the maximum key in the set which is smaller than or
equal to y. This problem is equivalent to the standard text book problem of
maintaining an ordered set (see, e.g., Cormen, Leiserson, Rivest, and Stein:
Introduction to Algorithms, 2nd ed., MIT Press, 2001).
  The best previous deterministic linear space bound was O(log n/loglog n) due
Fredman and Willard from STOC 1990. No better deterministic search bound was
known using polynomial space.
  We also get the following worst-case linear space trade-offs between the
number n, the word length w, and the maximal key U < 2^w: O(min{loglog n+log
n/log w, (loglog n)(loglog U)/(logloglog U)}). These trade-offs are, however,
not likely to be optimal.
  Our results are generalized to finger searching and string searching,
providing optimal results for both in terms of n.


title: Compilability of Abduction

abstract:
  Abduction is one of the most important forms of reasoning; it has been
successfully applied to several practical problems such as diagnosis. In this
paper we investigate whether the computational complexity of abduction can be
reduced by an appropriate use of preprocessing. This is motivated by the fact
that part of the data of the problem (namely, the set of all possible
assumptions and the theory relating assumptions and manifestations) are often
known before the rest of the problem. In this paper, we show some complexity
results about abduction when compilation is allowed.


title: Cellular automata and communication complexity

abstract:
  The model of cellular automata is fascinating because very simple local rules
can generate complex global behaviors. The relationship between local and
global function is subject of many studies. We tackle this question by using
results on communication complexity theory and, as a by-product, we provide
(yet another) classification of cellular automata.


title:
On the Cell-based Complexity of Recognition of Bounded Configurations by
  Finite Dynamic Cellular Automata

abstract:
  This paper studies complexity of recognition of classes of bounded
configurations by a generalization of conventional cellular automata (CA) --
finite dynamic cellular automata (FDCA). Inspired by the CA-based models of
biological and computer vision, this study attempts to derive the properties of
a complexity measure and of the classes of input configurations that make it
beneficial to realize the recognition via a two-layered automaton as compared
to a one-layered automaton. A formalized model of an image pattern recognition
task is utilized to demonstrate that the derived conditions can be satisfied
for a non-empty set of practical problems.


title:
A Random Structure for Optimum Cache Size Distributed hash table (DHT)
  Peer-to-Peer design

abstract:
  We propose a new and easily-realizable distributed hash table (DHT)
peer-to-peer structure, incorporating a random caching strategy that allows for
{\em polylogarithmic search time} while having only a {\em constant cache}
size. We also show that a very large class of deterministic caching strategies,
which covers almost all previously proposed DHT systems, can not achieve
polylog search time with constant cache size. In general, the new scheme is the
first known DHT structure with the following highly-desired properties: (a)
Random caching strategy with constant cache size; (b) Average search time of
$O(log^{2}(N))$; (c) Guaranteed search time of $O(log^{3}(N))$; (d) Truly local
cache dynamics with constant overhead for node deletions and additions; (e)
Self-organization from any initial network state towards the desired structure;
and (f) Allows a seamless means for various trade-offs, e.g., search speed or
anonymity at the expense of larger cache size.


title: A Note on Induction Schemas in Bounded Arithmetic

abstract:
  As is well known, Buss' theory of bounded arithmetic $S^{1}_{2}$ proves
$\Sigma_{0}^{b}(\Sigma_{1}^{b})-LIND$; however, we show that Allen's
$D_{2}^{1}$ does not prove $\Sigma_{0}^{b}(\Sigma_{1}^{b})-LLIND$ unless $P =
NC$. We also give some interesting alternative axiomatisations of $S^{1}_{2}$.


title:
Selection of future events from a time series in relation to estimations
  of forecasting uncertainty

abstract:
  A new general procedure for a priori selection of more predictable events
from a time series of observed variable is proposed. The procedure is
applicable to time series which contains different types of events that feature
significantly different predictability, or, in other words, to heteroskedastic
time series. A priori selection of future events in accordance to expected
uncertainty of their forecasts may be helpful for making practical decisions.
The procedure first implies creation of two neural network based forecasting
models, one of which is aimed at prediction of conditional mean and other -
conditional dispersion, and then elaboration of the rule for future event
selection into groups of more and less predictable events. The method is
demonstrated and tested by the example of the computer generated time series,
and then applied to the real world time series, Dow Jones Industrial Average
index.


title: On the Sum-of-Squares Algorithm for Bin Packing

abstract:
  In this paper we present a theoretical analysis of the deterministic on-line
{\em Sum of Squares} algorithm ($SS$) for bin packing introduced and studied
experimentally in \cite{CJK99}, along with several new variants. $SS$ is
applicable to any instance of bin packing in which the bin capacity $B$ and
item sizes $s(a)$ are integral (or can be scaled to be so), and runs in time
$O(nB)$. It performs remarkably well from an average case point of view: For
any discrete distribution in which the optimal expected waste is sublinear,
$SS$ also has sublinear expected waste. For any discrete distribution where the
optimal expected waste is bounded, $SS$ has expected waste at most $O(\log n)$.
In addition, we discuss several interesting variants on $SS$, including a
randomized $O(nB\log B)$-time on-line algorithm $SS^*$, based on $SS$, whose
expected behavior is essentially optimal for all discrete distributions.
Algorithm $SS^*$ also depends on a new linear-programming-based
pseudopolynomial-time algorithm for solving the NP-hard problem of determining,
given a discrete distribution $F$, just what is the growth rate for the optimal
expected waste. This article is a greatly expanded version of the conference
paper \cite{sumsq2000}.


title:
Current state of the Sonix -- the IBR-2 instrument control software and
  plans for future developments

abstract:
  The Sonix is the main control software for the IBR-2 instruments. This is a
modular configurable and flexible system created using the Varman (real time
database) and the X11/OS9 graphical package in the OS-9 environment. In the
last few years we were mostly focused on making this system more reliable and
user friendly. Because the VME hardware and software upgrade is rather
expensive we would like to replace existing VME + OS9 control computers with
the PC+Windows XP ones in the future. This could be done with the help of
VME-PCI adapters.


title:
New Developments in Interval Arithmetic and Their Implications for
  Floating-Point Standardization

abstract:
  We consider the prospect of a processor that can perform interval arithmetic
at the same speed as conventional floating-point arithmetic. This makes it
possible for all arithmetic to be performed with the superior security of
interval methods without any penalty in speed. In such a situation the IEEE
floating-point standard needs to be compared with a version of floating-point
arithmetic that is ideal for the purpose of interval arithmetic. Such a
comparison requires a succinct and complete exposition of interval arithmetic
according to its recent developments. We present such an exposition in this
paper. We conclude that the directed roundings toward the infinities and the
definition of division by the signed zeros are valuable features of the
standard. Because the operations of interval arithmetic are always defined,
exceptions do not arise. As a result neither Nans nor exceptions are needed. Of
the status flags, only the inexact flag may be useful. Denormalized numbers
seem to have no use for interval arithmetic; in the use of interval
constraints, they are a handicap.


title: Compact Floor-Planning via Orderly Spanning Trees

abstract:
  Floor-planning is a fundamental step in VLSI chip design. Based upon the
concept of orderly spanning trees, we present a simple O(n)-time algorithm to
construct a floor-plan for any n-node plane triangulation. In comparison with
previous floor-planning algorithms in the literature, our solution is not only
simpler in the algorithm itself, but also produces floor-plans which require
fewer module types. An equally important aspect of our new algorithm lies in
its ability to fit the floor-plan area in a rectangle of size (n-1)x(2n+1)/3.
Lower bounds on the worst-case area for floor-planning any plane triangulation
are also provided in the paper.


title: A New Interpretation of Amdahl's Law and Geometric Scalability

abstract:
  The multiprocessor effect refers to the loss of computing cycles due to
processing overhead. Amdahl's law and the Multiprocessing Factor (MPF) are two
scaling models used in industry and academia for estimating multiprocessor
capacity in the presence of this multiprocessor effect. Both models express
different laws of diminishing returns. Amdahl's law identifies diminishing
processor capacity with a fixed degree of serialization in the workload, while
the MPF model treats it as a constant geometric ratio. The utility of both
models for performance evaluation stems from the presence of a single parameter
that can be determined easily from a small set of benchmark measurements. This
utility, however, is marred by a dilemma. The two models produce different
results, especially for large processor configurations that are so important
for today's applications. The question naturally arises: Which of these two
models is the correct one to use? Ignoring this question merely reduces
capacity prediction to arbitrary curve-fitting. Removing the dilemma requires a
dynamical interpretation of these scaling models. We present a physical
interpretation based on queueing theory and show that Amdahl's law corresponds
to synchronous queueing in a bus model while the MPF model belongs to a Coxian
server model. The latter exhibits unphysical effects such as sublinear response
times hence, we caution against its use for large multiprocessor
configurations.


title: User software for the next generation

abstract:
  New generations of neutron scattering sources and instrumentation are
providing challenges in data handling for user software. Time-of-Flight
instruments used at pulsed sources typically produce hundreds or thousands of
channels of data for each detector segment. New instruments are being designed
with thousands to hundreds of thousands of detector segments. High intensity
neutron sources make possible parametric studies and texture studies which
further increase data handling requirements. The Integrated Spectral Analysis
Workbench (ISAW) software developed at Argonne handles large numbers of spectra
simultaneously while providing operations to reduce, sort, combine and export
the data. It includes viewers to inspect the data in detail in real time. ISAW
uses existing software components and packages where feasible and takes
advantage of the excellent support for user interface design and network
communication in Java. The included scripting language simplifies repetitive
operations for analyzing many files related to a given experiment. Recent
additions to ISAW include a contour view, a time-slice table view, routines for
finding and fitting peaks in data, and support for data from other facilities
using the NeXus format. In this paper, I give an overview of features and
planned improvements of ISAW. Details of some of the improvements are covered
in other presentations at this conference.


title: A Historic Name-Trail Service

abstract:
  People change the identifiers through which they are reachable online as they
change jobs or residences or Internet service providers. This kind of personal
mobility makes reaching people online error-prone. As people move, they do not
always know who or what has cached their now obsolete identifiers so as to
inform them of the move. Use of these old identifiers can cause delivery
failure of important messages, or worse, may cause delivery of messages to
unintended recipients. For example, a sensitive email message sent to my now
obsolete work address at a former place of employment may reach my unfriendly
former boss instead of me.
  In this paper we describe HINTS, a historic name-trail service. This service
provides a persistent way to name willing participants online using today's
transient online identifiers. HINTS accomplishes this by connecting together
the names a person uses along with the times during which those names were
valid for the person, thus giving people control over the historic use of their
names. A correspondent who wishes to reach a mobile person can use an obsolete
online name for that person, qualified with a time at which the online name was
successfully used; HINTS resolves this historic name to a current valid online
identifier for the intended recipient, if that recipient has chosen to leave a
name trail in HINTS.


title: Tetris is Hard, Even to Approximate

abstract:
  In the popular computer game of Tetris, the player is given a sequence of
tetromino pieces and must pack them into a rectangular gameboard initially
occupied by a given configuration of filled squares; any completely filled row
of the gameboard is cleared and all pieces above it drop by one row. We prove
that in the offline version of Tetris, it is NP-complete to maximize the number
of cleared rows, maximize the number of tetrises (quadruples of rows
simultaneously filled and cleared), minimize the maximum height of an occupied
square, or maximize the number of pieces placed before the game ends. We
furthermore show the extreme inapproximability of the first and last of these
objectives to within a factor of p^(1-epsilon), when given a sequence of p
pieces, and the inapproximability of the third objective to within a factor of
(2 - epsilon), for any epsilon>0. Our results hold under several variations on
the rules of Tetris, including different models of rotation, limitations on
player agility, and restricted piece sets.


title:
Reconciling MPEG-7 and MPEG-21 Semantics through a Common Event-Aware
  Metadata Model

abstract:
  The "event" concept appears repeatedly when developing metadata models for
the description and management of multimedia content. During the typical life
cycle of multimedia content, events occur at many different levels - from the
events which happen during content creation (directing, acting, camera panning
and zooming) to the events which happen to the physical form (acquisition,
relocation, damage of film or video) to the digital conversion, reformatting,
editing and repackaging events, to the events which are depicted in the actual
content (political, news, sporting) to the usage, ownership and copyright
agreement events and even the metadata attribution events. Support is required
within both MPEG-7 and MPEG-21 for the clear and unambiguous description of all
of these event types which may occur at widely different levels of nesting and
granularity. In this paper we first describe an event-aware model (the ABC
model) which is capable of modeling and yet clearly differentiating between all
of these, often recursive and overlapping events. We then illustrate how this
model can be used as the foundation to facilitate semantic interoperability
between MPEG-7 and MPEG-21. By expressing the semantics of both MPEG-7 and
MPEG-21 metadata terms in RDF Schema (and some DAML+OIL extensions) and
attaching the MPEG-7 and MPEG-21 class and property hierarchies to the
appropriate top-level classes and properties of the ABC model, we are
essentially able to define a single distributed machine-understandable
ontology, which will enable interoperability of data and services across the
entire multimedia content delivery chain.


title: An Elementary Fragment of Second-Order Lambda Calculus

abstract:
  A fragment of second-order lambda calculus (System F) is defined that
characterizes the elementary recursive functions. Type quantification is
restricted to be non-interleaved and stratified, i.e., the types are assigned
levels, and a quantified variable can only be instantiated by a type of smaller
level, with a slightly liberalized treatment of the level zero.


title: Geometric Aspects of Multiagent Systems

abstract:
  Recent advances in Multiagent Systems (MAS) and Epistemic Logic within
Distributed Systems Theory, have used various combinatorial structures that
model both the geometry of the systems and the Kripke model structure of models
for the logic. Examining one of the simpler versions of these models,
interpreted systems, and the related Kripke semantics of the logic $S5_n$ (an
epistemic logic with $n$-agents), the similarities with the geometric /
homotopy theoretic structure of groupoid atlases is striking. These latter
objects arise in problems within algebraic K-theory, an area of algebra linked
to the study of decomposition and normal form theorems in linear algebra. They
have a natural well structured notion of path and constructions of path
objects, etc., that yield a rich homotopy theory.


title: The Lazy Bureaucrat Scheduling Problem

abstract:
  We introduce a new class of scheduling problems in which the optimization is
performed by the worker (single ``machine'') who performs the tasks. A typical
worker's objective is to minimize the amount of work he does (he is ``lazy''),
or more generally, to schedule as inefficiently (in some sense) as possible.
The worker is subject to the constraint that he must be busy when there is work
that he can do; we make this notion precise both in the preemptive and
nonpreemptive settings. The resulting class of ``perverse'' scheduling
problems, which we denote ``Lazy Bureaucrat Problems,'' gives rise to a rich
set of new questions that explore the distinction between maximization and
minimization in computing optimal schedules.


title: An Algorithm for Pattern Discovery in Time Series

abstract:
  We present a new algorithm for discovering patterns in time series and other
sequential data. We exhibit a reliable procedure for building the minimal set
of hidden, Markovian states that is statistically capable of producing the
behavior exhibited in the data -- the underlying process's causal states.
Unlike conventional methods for fitting hidden Markov models (HMMs) to data,
our algorithm makes no assumptions about the process's causal architecture (the
number of hidden states and their transition structure), but rather infers it
from the data. It starts with assumptions of minimal structure and introduces
complexity only when the data demand it. Moreover, the causal states it infers
have important predictive optimality properties that conventional HMM states
lack. We introduce the algorithm, review the theory behind it, prove its
asymptotic reliability, use large deviation theory to estimate its rate of
convergence, and compare it to other algorithms which also construct HMMs from
data. We also illustrate its behavior on an example process, and report
selected numerical results from an implementation.


title: Encoding a Taxonomy of Web Attacks with Different-Length Vectors

abstract:
  Web attacks, i.e. attacks exclusively using the HTTP protocol, are rapidly
becoming one of the fundamental threats for information systems connected to
the Internet. When the attacks suffered by web servers through the years are
analyzed, it is observed that most of them are very similar, using a reduced
number of attacking techniques. It is generally agreed that classification can
help designers and programmers to better understand attacks and build more
secure applications. As an effort in this direction, a new taxonomy of web
attacks is proposed in this paper, with the objective of obtaining a
practically useful reference framework for security applications. The use of
the taxonomy is illustrated by means of multiplatform real world web attack
examples. Along with this taxonomy, important features of each attack category
are discussed. A suitable semantic-dependent web attack encoding scheme is
defined that uses different-length vectors. Possible applications are
described, which might benefit from this taxonomy and encoding scheme, such as
intrusion detection systems and application firewalls.


title: A uniform approach to logic programming semantics

abstract:
  Part of the theory of logic programming and nonmonotonic reasoning concerns
the study of fixed-point semantics for these paradigms. Several different
semantics have been proposed during the last two decades, and some have been
more successful and acknowledged than others. The rationales behind those
various semantics have been manifold, depending on one's point of view, which
may be that of a programmer or inspired by commonsense reasoning, and
consequently the constructions which lead to these semantics are technically
very diverse, and the exact relationships between them have not yet been fully
understood. In this paper, we present a conceptually new method, based on level
mappings, which allows to provide uniform characterizations of different
semantics for logic programs. We will display our approach by giving new and
uniform characterizations of some of the major semantics, more particular of
the least model semantics for definite programs, of the Fitting semantics, and
of the well-founded semantics. A novel characterization of the weakly perfect
model semantics will also be provided.


title: Equivalences Among Aggregate Queries with Negation

abstract:
  Query equivalence is investigated for disjunctive aggregate queries with
negated subgoals, constants and comparisons. A full characterization of
equivalence is given for the aggregation functions count, max, sum, prod,
toptwo and parity. A related problem is that of determining, for a given
natural number N, whether two given queries are equivalent over all databases
with at most N constants. We call this problem bounded equivalence. A complete
characterization of decidability of bounded equivalence is given. In
particular, it is shown that this problem is decidable for all the above
aggregation functions as well as for count distinct and average. For
quasilinear queries (i.e., queries where predicates that occur positively are
not repeated) it is shown that equivalence can be decided in polynomial time
for the aggregation functions count, max, sum, parity, prod, toptwo and
average. A similar result holds for count distinct provided that a few
additional conditions hold. The results are couched in terms of abstract
characteristics of aggregation functions, and new proof techniques are used.
Finally, the results above also imply that equivalence, under bag-set
semantics, is decidable for non-aggregate queries with negation.


title:
Integration and interoperability accessing electronic information
  resources in science and technology: the proposal of Brazilian Digital
  Library

abstract:
  This paper describes technological and methodological options to achieve
interoperability in accessing electronic information resources, available in
Internet, in the scope of Brazilian Digital Library in Science and Technology
Project - BDL, developed by Brazilian Institute for Scientific and Technical
Information - IBICT. It stresses the impact of the Web in the publishing and
communication processes in science and technology and also in the information
systems and libraries. The work points out the two major objectives of the BDL
Project: facilitates electronic publishing of different full text materials
such as theses, journal articles, conference papers,grey literature - by
Brazilian scientific community, so amplifying their nationally and
internationally visibility; and achieving, through a unified gateway, thus
avoiding a user to navigate and query across different information resources
individually. The work explains technological options and standards that will
assure interoperability in this context.


title: Intelligence and Cooperative Search by Coupled Local Minimizers

abstract:
  We show how coupling of local optimization processes can lead to better
solutions than multi-start local optimization consisting of independent runs.
This is achieved by minimizing the average energy cost of the ensemble, subject
to synchronization constraints between the state vectors of the individual
local minimizers. From an augmented Lagrangian which incorporates the
synchronization constraints both as soft and hard constraints, a network is
derived wherein the local minimizers interact and exchange information through
the synchronization constraints. From the viewpoint of neural networks, the
array can be considered as a Lagrange programming network for continuous
optimization and as a cellular neural network (CNN). The penalty weights
associated with the soft state synchronization constraints follow from the
solution to a linear program. This expresses that the energy cost of the
ensemble should maximally decrease. In this way successful local minimizers can
implicitly impose their state to the others through a mechanism of master-slave
dynamics resulting into a cooperative search mechanism. Improved information
spreading within the ensemble is obtained by applying the concept of
small-world networks. This work suggests, in an interdisciplinary context, the
importance of information exchange and state synchronization within ensembles,
towards issues as evolution, collective behaviour, optimality and intelligence.


title: The Weaves Reconfigurable Programming Framework

abstract:
  This research proposes a language independent intra-process framework for
object based composition of unmodified code modules. Intuitively, the two major
programming models, threads and processes, can be considered as extremes along
a sharing axis. Multiple threads through a process share all global state,
whereas instances of a process (or independent processes) share no global
state. Weaves provide the generalized framework that allows arbitrary
(selective) sharing of state between multiple control flows through a process.
The Weaves framework supports multiple independent components in a single
process, with flexible state sharing and scheduling, all of which is achieved
without requiring any modification to existing code bases. Furthermore, the
framework allows dynamic instantiation of code modules and control flows
through them. In effect, weaves create intra-process modules (similar to
objects in OOP) from code written in any language. The Weaves paradigm allows
objects to be arbitrarily shared, it is a true superset of both processes as
well as threads, with code sharing and fast context switching time similar to
threads. Weaves does not require any special support from either the language
or application code, practically any code can be weaved. Weaves also include
support for fast automatic checkpointing and recovery with no application
support. This paper presents the elements of the Weaves framework and results
from our implementation that works by reverse-analyzing source-code independent
ELF object files. The current implementation has been validated over Sweep3D, a
benchmark for 3D discrete ordinates neutron transport [Koch et al., 1992], and
a user-level port of the Linux 2.4 family kernel TCP/IP protocol stack.


title: Fast and Simple Computation of All Longest Common Subsequences

abstract:
  This paper shows that a simple algorithm produces the {\em
all-prefixes-LCSs-graph} in $O(mn)$ time for two input sequences of size $m$
and $n$. Given any prefix $p$ of the first input sequence and any prefix $q$ of
the second input sequence, all longest common subsequences (LCSs) of $p$ and
$q$ can be generated in time proportional to the output size, once the
all-prefixes-LCSs-graph has been constructed. The problem can be solved in the
context of generating all the distinct character strings that represent an LCS
or in the context of generating all ways of embedding an LCS in the two input
strings.


title: Programming and Verifying Subgame Perfect Mechanisms

abstract:
  An extension of the WHILE-language is developed for programming
game-theoretic mechanisms involving multiple agents. Examples of such
mechanisms include auctions, voting procedures, and negotiation protocols. A
structured operational semantics is provided in terms of extensive games of
almost perfect information. Hoare-style partial correctness assertions are
proposed to reason about the correctness of these mechanisms, where correctness
is interpreted as the existence of a subgame perfect equilibrium. Using an
extensional approach to pre- and postconditions, we show that an extension of
Hoare's original calculus is sound and complete for reasoning about subgame
perfect equilibria in game-theoretic mechanisms.


title:
Evaluation of the Performance of the Markov Blanket Bayesian Classifier
  Algorithm

abstract:
  The Markov Blanket Bayesian Classifier is a recently-proposed algorithm for
construction of probabilistic classifiers. This paper presents an empirical
comparison of the MBBC algorithm with three other Bayesian classifiers: Naive
Bayes, Tree-Augmented Naive Bayes and a general Bayesian network. All of these
are implemented using the K2 framework of Cooper and Herskovits. The
classifiers are compared in terms of their performance (using simple accuracy
measures and ROC curves) and speed, on a range of standard benchmark data sets.
It is concluded that MBBC is competitive in terms of speed and accuracy with
the other algorithms considered.


title: The DLV System for Knowledge Representation and Reasoning

abstract:
  This paper presents the DLV system, which is widely considered the
state-of-the-art implementation of disjunctive logic programming, and addresses
several aspects. As for problem solving, we provide a formal definition of its
kernel language, function-free disjunctive logic programs (also known as
disjunctive datalog), extended by weak constraints, which are a powerful tool
to express optimization problems. We then illustrate the usage of DLV as a tool
for knowledge representation and reasoning, describing a new declarative
programming methodology which allows one to encode complex problems (up to
$\Delta^P_3$-complete problems) in a declarative fashion. On the foundational
side, we provide a detailed analysis of the computational complexity of the
language of DLV, and by deriving new complexity results we chart a complete
picture of the complexity of this language and important fragments thereof.
  Furthermore, we illustrate the general architecture of the DLV system which
has been influenced by these results. As for applications, we overview
application front-ends which have been developed on top of DLV to solve
specific knowledge representation tasks, and we briefly describe the main
international projects investigating the potential of the system for industrial
exploitation. Finally, we report about thorough experimentation and
benchmarking, which has been carried out to assess the efficiency of the
system. The experimental results confirm the solidity of DLV and highlight its
potential for emerging application areas like knowledge management and
information integration.


title:
Prosody Based Co-analysis for Continuous Recognition of Coverbal
  Gestures

abstract:
  Although speech and gesture recognition has been studied extensively, all the
successful attempts of combining them in the unified framework were
semantically motivated, e.g., keyword-gesture cooccurrence. Such formulations
inherited the complexity of natural language processing. This paper presents a
Bayesian formulation that uses a phenomenon of gesture and speech articulation
for improving accuracy of automatic recognition of continuous coverbal
gestures. The prosodic features from the speech signal were coanalyzed with the
visual signal to learn the prior probability of co-occurrence of the prominent
spoken segments with the particular kinematical phases of gestures. It was
found that the above co-analysis helps in detecting and disambiguating visually
small gestures, which subsequently improves the rate of continuous gesture
recognition. The efficacy of the proposed approach was demonstrated on a large
database collected from the weather channel broadcast. This formulation opens
new avenues for bottom-up frameworks of multimodal integration.


title: Maximing the Margin in the Input Space

abstract:
  We propose a novel criterion for support vector machine learning: maximizing
the margin in the input space, not in the feature (Hilbert) space. This
criterion is a discriminative version of the principal curve proposed by Hastie
et al. The criterion is appropriate in particular when the input space is
already a well-designed feature space with rather small dimensionality. The
definition of the margin is generalized in order to represent prior knowledge.
The derived algorithm consists of two alternating steps to estimate the dual
parameters. Firstly, the parameters are initialized by the original SVM. Then
one set of parameters is updated by Newton-like procedure, and the other set is
updated by solving a quadratic programming problem. The algorithm converges in
a few steps to a local optimum under mild conditions and it preserves the
sparsity of support vectors. Although the complexity to calculate temporal
variables increases the complexity to solve the quadratic programming problem
for each step does not change. It is also shown that the original SVM can be
seen as a special case. We further derive a simplified algorithm which enables
us to use the existing code for the original SVM.


title: Approximating Incomplete Kernel Matrices by the em Algorithm

abstract:
  In biological data, it is often the case that observed data are available
only for a subset of samples. When a kernel matrix is derived from such data,
we have to leave the entries for unavailable samples as missing. In this paper,
we make use of a parametric model of kernel matrices, and estimate missing
entries by fitting the model to existing entries. The parametric model is
created as a set of spectral variants of a complete kernel matrix derived from
another information source. For model fitting, we adopt the em algorithm based
on the information geometry of positive definite matrices. We will report
promising results on bacteria clustering experiments using two marker
sequences: 16S and gyrB.


title: Can the whole brain be simpler than its "parts"?

abstract:
  This is the first in a series of connected papers discussing the problem of a
dynamically reconfigurable universal learning neurocomputer that could serve as
a computational model for the whole human brain. The whole series is entitled
"The Brain Zero Project. My Brain as a Dynamically Reconfigurable Universal
Learning Neurocomputer." (For more information visit the website
www.brain0.com.) This introductory paper is concerned with general methodology.
Its main goal is to explain why it is critically important for both neural
modeling and cognitive modeling to pay much attention to the basic requirements
of the whole brain as a complex computing system. The author argues that it can
be easier to develop an adequate computational model for the whole
"unprogrammed" (untrained) human brain than to find adequate formal
representations of some nontrivial parts of brain's performance. (In the same
way as, for example, it is easier to describe the behavior of a complex
analytical function than the behavior of its real and/or imaginary part.) The
"curse of dimensionality" that plagues purely phenomenological ("brainless")
cognitive theories is a natural penalty for an attempt to represent
insufficiently large parts of brain's performance in a state space of
insufficiently high dimensionality. A "partial" modeler encounters "Catch 22."
An attempt to simplify a cognitive problem by artificially reducing its
dimensionality makes the problem more difficult.


title:
Improved Phylogeny Comparisons: Non-Shared Edges Nearest Neighbor
  Interchanges, and Subtree Transfers

abstract:
  The number of the non-shared edges of two phylogenies is a basic measure of
the dissimilarity between the phylogenies. The non-shared edges are also the
building block for approximating a more sophisticated metric called the nearest
neighbor interchange (NNI) distance. In this paper, we give the first
subquadratic-time algorithm for finding the non-shared edges, which are then
used to speed up the existing approximating algorithm for the NNI distance from
$O(n^2)$ time to $O(n \log n)$ time. Another popular distance metric for
phylogenies is the subtree transfer (STT) distance. Previous work on computing
the STT distance considered degree-3 trees only. We give an approximation
algorithm for the STT distance for degree-$d$ trees with arbitrary $d$ and with
generalized STT operations.


title: Efficient Tree Layout in a Multilevel Memory Hierarchy

abstract:
  We consider the problem of laying out a tree with fixed parent/child
structure in hierarchical memory. The goal is to minimize the expected number
of block transfers performed during a search along a root-to-leaf path, subject
to a given probability distribution on the leaves. This problem was previously
considered by Gil and Itai, who developed optimal but slow algorithms when the
block-transfer size B is known. We present faster but approximate algorithms
for the same problem; the fastest such algorithm runs in linear time and
produces a solution that is within an additive constant of optimal.
  In addition, we show how to extend any approximately optimal algorithm to the
cache-oblivious setting in which the block-transfer size is unknown to the
algorithm. The query performance of the cache-oblivious layout is within a
constant factor of the query performance of the optimal known-block-size
layout. Computing the cache-oblivious layout requires only logarithmically many
calls to the layout algorithm for known block size; in particular, the
cache-oblivious layout can be computed in O(N lg N) time, where N is the number
of nodes.
  Finally, we analyze two greedy strategies, and show that they have a
performance ratio between Omega(lg B / lg lg B) and O(lg B) when compared to
the optimal layout.


title: Intersection Types and Lambda Theories

abstract:
  We illustrate the use of intersection types as a semantic tool for showing
properties of the lattice of lambda theories. Relying on the notion of easy
intersection type theory we successfully build a filter model in which the
interpretation of an arbitrary simple easy term is any filter which can be
described in an uniform way by a predicate. This allows us to prove the
consistency of a well-know lambda theory: this consistency has interesting
consequences on the algebraic structure of the lattice of lambda theories.


title: Phase Transitions and all that

abstract:
  The paper (as posted originally) contains several errors. It has been
subsequently split into two papers, the corrected (and accepted for
publication) versions appear in the archive as papers cs.CC/0503082 and
cs.DM/0503083.


title:
Algorithmic scalability in globally constrained conservative parallel
  discrete event simulations of asynchronous systems

abstract:
  We consider parallel simulations for asynchronous systems employing L
processing elements that are arranged on a ring. Processors communicate only
among the nearest neighbors and advance their local simulated time only if it
is guaranteed that this does not violate causality. In simulations with no
constraints, in the infinite L-limit the utilization scales (Korniss et al, PRL
84, 2000); but, the width of the virtual time horizon diverges (i.e., the
measurement phase of the algorithm does not scale). In this work, we introduce
a moving window global constraint, which modifies the algorithm so that the
measurement phase scales as well. We present results of systematic studies in
which the system size (i.e., L and the volume load per processor) as well as
the constraint are varied. The constraint eliminates the extreme fluctuations
in the virtual time horizon, provides a bound on its width, and controls the
average progress rate. The width of the window constraint can serve as a tuning
parameter that, for a given volume load per processor, could be adjusted to
optimize the utilization so as to maximize the efficiency. This result may find
numerous applications in modeling the evolution of general spatially extended
short-range interacting systems with asynchronous dynamics, including dynamic
Monte Carlo studies.

categories: cs.DC cond-mat.stat-mech cs.DS physics.comp-ph


title:
Vanquishing the XCB Question: The Methodology Discovery of the Last
  Shortest Single Axiom for the Equivalential Calculus

abstract:
  With the inclusion of an effective methodology, this article answers in
detail a question that, for a quarter of a century, remained open despite
intense study by various researchers. Is the formula XCB =
e(x,e(e(e(x,y),e(z,y)),z)) a single axiom for the classical equivalential
calculus when the rules of inference consist of detachment (modus ponens) and
substitution? Where the function e represents equivalence, this calculus can be
axiomatized quite naturally with the formulas e(x,x), e(e(x,y),e(y,x)), and
e(e(x,y),e(e(y,z),e(x,z))), which correspond to reflexivity, symmetry, and
transitivity, respectively. (We note that e(x,x) is dependent on the other two
axioms.) Heretofore, thirteen shortest single axioms for classical equivalence
of length eleven had been discovered, and XCB was the only remaining formula of
that length whose status was undetermined. To show that XCB is indeed such a
single axiom, we focus on the rule of condensed detachment, a rule that
captures detachment together with an appropriately general, but restricted,
form of substitution. The proof we present in this paper consists of
twenty-five applications of condensed detachment, completing with the deduction
of transitivity followed by a deduction of symmetry. We also discuss some
factors that may explain in part why XCB resisted relinquishing its treasure
for so long. Our approach relied on diverse strategies applied by the automated
reasoning program OTTER. Thus ends the search for shortest single axioms for
the equivalential calculus.


title:
XCB, the Last of the Shortest Single Axioms for the Classical
  Equivalential Calculus

abstract:
  It has long been an open question whether the formula XCB = EpEEEpqErqr is,
with the rules of substitution and detachment, a single axiom for the classical
equivalential calculus. This paper answers that question affirmatively, thus
completing a search for all such eleven-symbol single axioms that began seventy
years ago.


title:
Efficient Solving of Quantified Inequality Constraints over the Real
  Numbers

abstract:
  Let a quantified inequality constraint over the reals be a formula in the
first-order predicate language over the structure of the real numbers, where
the allowed predicate symbols are $\leq$ and $<$. Solving such constraints is
an undecidable problem when allowing function symbols such $\sin$ or $\cos$. In
the paper we give an algorithm that terminates with a solution for all, except
for very special, pathological inputs. We ensure the practical efficiency of
this algorithm by employing constraint programming techniques.


title: Probabilistic Parsing Strategies

abstract:
  We present new results on the relation between purely symbolic context-free
parsing strategies and their probabilistic counter-parts. Such parsing
strategies are seen as constructions of push-down devices from grammars. We
show that preservation of probability distribution is possible under two
conditions, viz. the correct-prefix property and the property of strong
predictiveness. These results generalize existing results in the literature
that were obtained by considering parsing strategies in isolation. From our
general results we also derive negative results on so-called generalized LR
parsing.


title: Indexing schemes for similarity search: an illustrated paradigm

abstract:
  We suggest a variation of the Hellerstein--Koutsoupias--Papadimitriou
indexability model for datasets equipped with a similarity measure, with the
aim of better understanding the structure of indexing schemes for
similarity-based search and the geometry of similarity workloads. This in
particular provides a unified approach to a great variety of schemes used to
index into metric spaces and facilitates their transfer to more general
similarity measures such as quasi-metrics. We discuss links between performance
of indexing schemes and high-dimensional geometry. The concepts and results are
illustrated on a very large concrete dataset of peptide fragments equipped with
a biologically significant similarity measure.


title: Schedulers for Rule-based Constraint Programming

abstract:
  We study here schedulers for a class of rules that naturally arise in the
context of rule-based constraint programming. We systematically derive a
scheduler for them from a generic iteration algorithm of Apt [2000]. We apply
this study to so-called membership rules of Apt and Monfroy [2001]. This leads
to an implementation that yields for these rules a considerably better
performance than their execution as standard CHR rules.


title:
Monadic Datalog and the Expressive Power of Languages for Web
  Information Extraction

abstract:
  Research on information extraction from Web pages (wrapping) has seen much
activity recently (particularly systems implementations), but little work has
been done on formally studying the expressiveness of the formalisms proposed or
on the theoretical foundations of wrapping. In this paper, we first study
monadic datalog over trees as a wrapping language. We show that this simple
language is equivalent to monadic second order logic (MSO) in its ability to
specify wrappers. We believe that MSO has the right expressiveness required for
Web information extraction and propose MSO as a yardstick for evaluating and
comparing wrappers. Along the way, several other results on the complexity of
query evaluation and query containment for monadic datalog over trees are
established, and a simple normal form for this language is presented. Using the
above results, we subsequently study the kernel fragment Elog$^-$ of the Elog
wrapping language used in the Lixto system (a visual wrapper generator).
Curiously, Elog$^-$ exactly captures MSO, yet is easier to use. Indeed,
programs in this language can be entirely visually specified.


title: Sequent and Hypersequent Calculi for Abelian and Lukasiewicz Logics

abstract:
  We present two embeddings of infinite-valued Lukasiewicz logic L into Meyer
and Slaney's abelian logic A, the logic of lattice-ordered abelian groups. We
give new analytic proof systems for A and use the embeddings to derive
corresponding systems for L. These include: hypersequent calculi for A and L
and terminating versions of these calculi; labelled single sequent calculi for
A and L of complexity co-NP; unlabelled single sequent calculi for A and L.


title: Arithmetic, First-Order Logic, and Counting Quantifiers

abstract:
  This paper gives a thorough overview of what is known about first-order logic
with counting quantifiers and with arithmetic predicates. As a main theorem we
show that Presburger arithmetic is closed under unary counting quantifiers.
Precisely, this means that for every first-order formula phi(y,z_1,...,z_k)
over the signature {<,+} there is a first-order formula psi(x,z_1,...,z_k)
which expresses over the structure <Nat,<,+> (respectively, over initial
segments of this structure) that the variable x is interpreted exactly by the
number of possible interpretations of the variable y for which the formula
phi(y,z_1,...,z_k) is satisfied. Applying this theorem, we obtain an easy proof
of Ruhl's result that reachability (and similarly, connectivity) in finite
graphs is not expressible in first-order logic with unary counting quantifiers
and addition. Furthermore, the above result on Presburger arithmetic helps to
show the failure of a particular version of the Crane Beach conjecture.


title: SkyQuery: A WebService Approach to Federate Databases

abstract:
  Traditional science searched for new objects and phenomena that led to
discoveries. Tomorrow's science will combine together the large pool of
information in scientific archives and make discoveries. Scienthists are
currently keen to federate together the existing scientific databases. The
major challenge in building a federation of these autonomous and heterogeneous
databases is system integration. Ineffective integration will result in defunct
federations and under utilized scientific data.
  Astronomy, in particular, has many autonomous archives spread over the
Internet. It is now seeking to federate these, with minimal effort, into a
Virtual Observatory that will solve complex distributed computing tasks such as
answering federated spatial join queries.
  In this paper, we present SkyQuery, a successful prototype of an evolving
federation of astronomy archives. It interoperates using the emerging Web
services standard. We describe the SkyQuery architecture and show how it
efficiently evaluates a probabilistic federated spatial join query.


title: Narses: A Scalable Flow-Based Network Simulator

abstract:
  Most popular, modern network simulators, such as ns, are targeted towards
simulating low-level protocol details. These existing simulators are not
intended for simulating large distributed applications with many hosts and many
concurrent connections over long periods of simulated time. We introduce a new
simulator, Narses, targeted towards large distributed applications. The goal of
Narses is to simulate and validate large applications efficiently using network
models of varying levels of detail. We introduce several simplifying
assumptions that allow our simulator to scale to the needs of large distributed
applications while maintaining a reasonable degree of accuracy. Initial results
show up to a 45 times speedup while consuming 28% of the memory used by ns.
Narses maintains a reasonable degree of accuracy -- within 8% on average.


title:
Effective Strong Dimension, Algorithmic Information, and Computational
  Complexity

abstract:
  The two most important notions of fractal dimension are {\it Hausdorff
dimension}, developed by Hausdorff (1919), and {\it packing dimension},
developed by Tricot (1982).
  Lutz (2000) has recently proven a simple characterization of Hausdorff
dimension in terms of {\it gales}, which are betting strategies that generalize
martingales. Imposing various computability and complexity constraints on these
gales produces a spectrum of effective versions of Hausdorff dimension.
  In this paper we show that packing dimension can also be characterized in
terms of gales. Moreover, even though the usual definition of packing dimension
is considerably more complex than that of Hausdorff dimension, our gale
characterization of packing dimension is an exact dual of -- and every bit as
simple as -- the gale characterization of Hausdorff dimension.
  Effectivizing our gale characterization of packing dimension produces a
variety of {\it effective strong dimensions}, which are exact duals of the
effective dimensions mentioned above.
  We develop the basic properties of effective strong dimensions and prove a
number of results relating them to fundamental aspects of randomness,
Kolmogorov complexity, prediction, Boolean circuit-size complexity,
polynomial-time degrees, and data compression.


title: How long is a Proof? - A short note

abstract: Withdrawn. Silly notion and out of context.


title:
Adaptive Development of Koncepts in Virtual Animats: Insights into the
  Development of Knowledge

abstract:
  As a part of our effort for studying the evolution and development of
cognition, we present results derived from synthetic experimentations in a
virtual laboratory where animats develop koncepts adaptively and ground their
meaning through action. We introduce the term "koncept" to avoid confusions and
ambiguity derived from the wide use of the word "concept". We present the
models which our animats use for abstracting koncepts from perceptions,
plastically adapt koncepts, and associate koncepts with actions. On a more
philosophical vein, we suggest that knowledge is a property of a cognitive
system, not an element, and therefore observer-dependent.


title: Thinking Adaptive: Towards a Behaviours Virtual Laboratory

abstract:
  In this paper we name some of the advantages of virtual laboratories; and
propose that a Behaviours Virtual Laboratory should be useful for both
biologists and AI researchers, offering a new perspective for understanding
adaptive behaviour. We present our development of a Behaviours Virtual
Laboratory, which at this stage is focused in action selection, and show some
experiments to illustrate the properties of our proposal, which can be accessed
via Internet.


title:
Modelling intracellular signalling networks using behaviour-based
  systems and the blackboard architecture

abstract:
  This paper proposes to model the intracellular signalling networks using a
fusion of behaviour-based systems and the blackboard architecture. In virtue of
this fusion, the model developed by us, which has been named Cellulat, allows
to take account two essential aspects of the intracellular signalling networks:
(1) the cognitive capabilities of certain types of networks' components and (2)
the high level of spatial organization of these networks. A simple example of
modelling of Ca2+ signalling pathways using Cellulat is presented here. An
intracellular signalling virtual laboratory is being developed from Cellulat.


title:
Integration of Computational Techniques for the Modelling of Signal
  Transduction

abstract:
  A cell can be seen as an adaptive autonomous agent or as a society of
adaptive autonomous agents, where each can exhibit a particular behaviour
depending on its cognitive capabilities. We present an intracellular signalling
model obtained by integrating several computational techniques into an
agent-based paradigm. Cellulat, the model, takes into account two essential
aspects of the intracellular signalling networks: cognitive capacities and a
spatial organization. Exemplifying the functionality of the system by modelling
the EGFR signalling pathway, we discuss the methodology as well as the purposes
of an intracellular signalling virtual laboratory, presently under development.


title: Redundancy in Logic I: CNF Propositional Formulae

abstract:
  A knowledge base is redundant if it contains parts that can be inferred from
the rest of it. We study the problem of checking whether a CNF formula (a set
of clauses) is redundant, that is, it contains clauses that can be derived from
the other ones. Any CNF formula can be made irredundant by deleting some of its
clauses: what results is an irredundant equivalent subset (I.E.S.) We study the
complexity of some related problems: verification, checking existence of a
I.E.S. with a given size, checking necessary and possible presence of clauses
in I.E.S.'s, and uniqueness. We also consider the problem of redundancy with
different definitions of equivalence.


title:
Solution Bounds for a Hypothetical Polynomial Time Aproximation
  Algorithm for the TSP

abstract:
  Bounds for the optimal tour length for a hypothetical TSP algorithm are
derived.


title: Propositional satisfiability in declarative programming

abstract:
  Answer-set programming (ASP) paradigm is a way of using logic to solve search
problems. Given a search problem, to solve it one designs a theory in the logic
so that models of this theory represent problem solutions. To compute a
solution to a problem one needs to compute a model of the corresponding theory.
Several answer-set programming formalisms have been developed on the basis of
logic programming with the semantics of stable models. In this paper we show
that also the logic of predicate calculus gives rise to effective
implementations of the ASP paradigm, similar in spirit to logic programming
with stable model semantics and with a similar scope of applicability.
Specifically, we propose two logics based on predicate calculus as formalisms
for encoding search problems. We show that the expressive power of these logics
is given by the class NP-search. We demonstrate how to use them in programming
and develop computational tools for model finding. In the case of one of the
logics our techniques reduce the problem to that of propositional
satisfiability and allow one to use off-the-shelf satisfiability solvers. The
language of the other logic has more complex syntax and provides explicit means
to model some high-level constraints. For theories in this logic, we designed
our own solver that takes advantage of the expanded syntax. We present
experimental results demonstrating computational effectiveness of the overall
approach.


title: Monadic Style Control Constructs for Inference Systems

abstract:
  Recent advances in programming languages study and design have established a
standard way of grounding computational systems representation in category
theory. These formal results led to a better understanding of issues of control
and side-effects in functional and imperative languages. Another benefit is a
better way of modelling computational effects in logical frameworks. With this
analogy in mind, we embark on an investigation of inference systems based on
considering inference behaviour as a form of computation. We delineate a
categorical formalisation of control constructs in inference systems. This
representation emphasises the parallel between the modular articulation of the
categorical building blocks (triples) used to account for the inference
architecture and the modular composition of cognitive processes.


title: Typical random 3-SAT formulae and the satisfiability threshold

abstract:
  We present a new structural (or syntatic) approach for estimating the
satisfiability threshold of random 3-SAT formulae. We show its efficiency in
obtaining a jump from the previous upper bounds, lowering them to 4.506. The
method combines well with other techniques, and also applies to other problems,
such as the 3-colourability of random graphs.


title:
Annotations for HTML to VoiceXML Transcoding: Producing Voice WebPages
  with Usability in Mind

abstract:
  Web pages contain a large variety of information, but are largely designed
for use by graphical web browsers. Mobile access to web-based information often
requires presenting HTML web pages using channels that are limited in their
graphical capabilities such as small-screens or audio-only interfaces. Content
transcoding and annotations have been explored as methods for intelligently
presenting HTML documents. Much of this work has focused on transcoding for
small-screen devices such as are found on PDAs and cell phones. Here, we focus
on the use of annotations and transcoding for presenting HTML content through a
voice user interface instantiated in VoiceXML. This transcoded voice interface
is designed with an assumption that it will not be used for extended web
browsing by voice, but rather to quickly gain directed access to information on
web pages. We have found repeated structures that are common in the
presentation of data on web pages that are well suited for voice presentation
and navigation. In this paper, we describe these structures and their use in an
annotation system we have implemented that produces a VoiceXML interface to
information originally embedded in HTML documents. We describe the transcoding
process used to translate HTML into VoiceXML, including transcoding features we
have designed to lead to highly usable VoiceXML code.


title:
Dynamic Adjustment of the Motivation Degree in an Action Selection
  Mechanism

abstract:
  This paper presents a model for dynamic adjustment of the motivation degree,
using a reinforcement learning approach, in an action selection mechanism
previously developed by the authors. The learning takes place in the
modification of a parameter of the model of combination of internal and
external stimuli. Experiments that show the claimed properties are presented,
using a VR simulation developed for such purposes. The importance of adaptation
by learning in action selection is also discussed.


title: Action Selection Properties in a Software Simulated Agent

abstract:
  This article analyses the properties of the Internal Behaviour network, an
action selection mechanism previously proposed by the authors, with the aid of
a simulation developed for such ends. A brief review of the Internal Behaviour
network is followed by the explanation of the implementation of the simulation.
Then, experiments are presented and discussed analysing the properties of the
action selection in the proposed model.


title:
A Model for Combination of External and Internal Stimuli in the Action
  Selection of an Autonomous Agent

abstract:
  This paper proposes a model for combination of external and internal stimuli
for the action selection in an autonomous agent, based in an action selection
mechanism previously proposed by the authors. This combination model includes
additive and multiplicative elements, which allows to incorporate new
properties, which enhance the action selection. A given parameter a, which is
part of the proposed model, allows to regulate the degree of dependence of the
observed external behaviour from the internal states of the entity.


title:
An Approach to Automatic Indexing of Scientific Publications in High
  Energy Physics for Database SPIRES HEP

abstract:
  We introduce an approach to automatic indexing of e-prints based on a
pattern-matching technique making extensive use of an Associative Patterns
Dictionary (APD), developed by us. Entries in the APD consist of natural
language phrases with the same semantic interpretation as a set of keywords
from a controlled vocabulary. The method also allows to recognize within
e-prints formulae written in TeX notations that might also appear as keywords.
We present an automatic indexing system, AUTEX, which we have applied to
keyword index e-prints in selected areas in high energy physics (HEP) making
use of the DESY-HEPI thesaurus as a controlled vocabulary.


title: Database Repairs and Analytic Tableaux

abstract:
  In this article, we characterize in terms of analytic tableaux the repairs of
inconsistent relational databases, that is databases that do not satisfy a
given set of integrity constraints. For this purpose we provide closing and
opening criteria for branches in tableaux that are built for database instances
and their integrity constraints. We use the tableaux based characterization as
a basis for consistent query answering, that is for retrieving from the
database answers to queries that are consistent wrt the integrity constraints.


title: Traveling Salesmen in the Presence of Competition

abstract:
  We propose the ``Competing Salesmen Problem'' (CSP), a 2-player competitive
version of the classical Traveling Salesman Problem. This problem arises when
considering two competing salesmen instead of just one. The concern for a
shortest tour is replaced by the necessity to reach any of the customers before
the opponent does. In particular, we consider the situation where players take
turns, moving along one edge at a time within a graph G=(V,E). The set of
customers is given by a subset V_C V of the vertices. At any given time, both
players know of their opponent's position. A player wins if he is able to reach
a majority of the vertices in V_C before the opponent does. We prove that the
CSP is PSPACE-complete, even if the graph is bipartite, and both players start
at distance 2 from each other. We show that the starting player may lose the
game, even if both players start from the same vertex. For bipartite graphs, we
show that the starting player always can avoid a loss. We also show that the
second player can avoid to lose by more than one customer, when play takes
place on a graph that is a tree T, and V_C consists of leaves of T. For the
case where T is a star and V_C consists of n leaves of T, we give a simple and
fast strategy which is optimal for both players. If V_C consists not only of
leaves, the situation is more involved.


title: Survey propagation: an algorithm for satisfiability

abstract:
  We study the satisfiability of randomly generated formulas formed by $M$
clauses of exactly $K$ literals over $N$ Boolean variables. For a given value
of $N$ the problem is known to be most difficult with $\alpha=M/N$ close to the
experimental threshold $\alpha_c$ separating the region where almost all
formulas are SAT from the region where all formulas are UNSAT. Recent results
from a statistical physics analysis suggest that the difficulty is related to
the existence of a clustering phenomenon of the solutions when $\alpha$ is
close to (but smaller than) $\alpha_c$. We introduce a new type of message
passing algorithm which allows to find efficiently a satisfiable assignment of
the variables in the difficult region. This algorithm is iterative and composed
of two main parts. The first is a message-passing procedure which generalizes
the usual methods like Sum-Product or Belief Propagation: it passes messages
that are surveys over clusters of the ordinary messages. The second part uses
the detailed probabilistic information obtained from the surveys in order to
fix variables and simplify the problem. Eventually, the simplified problem that
remains is solved by a conventional heuristic.


title:
Ownership Confinement Ensures Representation Independence for
  Object-Oriented Programs

abstract:
  Dedicated to the memory of Edsger W.Dijkstra.
  Representation independence or relational parametricity formally
characterizes the encapsulation provided by language constructs for data
abstraction and justifies reasoning by simulation. Representation independence
has been shown for a variety of languages and constructs but not for shared
references to mutable state; indeed it fails in general for such languages.
This paper formulates representation independence for classes, in an
imperative, object-oriented language with pointers, subclassing and dynamic
dispatch, class oriented visibility control, recursive types and methods, and a
simple form of module. An instance of a class is considered to implement an
abstraction using private fields and so-called representation objects.
Encapsulation of representation objects is expressed by a restriction, called
confinement, on aliasing. Representation independence is proved for programs
satisfying the confinement condition. A static analysis is given for
confinement that accepts common designs such as the observer and factory
patterns. The formalization takes into account not only the usual interface
between a client and a class that provides an abstraction but also the
interface (often called ``protected'') between the class and its subclasses.


title: Minimal-Change Integrity Maintenance Using Tuple Deletions

abstract:
  We address the problem of minimal-change integrity maintenance in the context
of integrity constraints in relational databases. We assume that
integrity-restoration actions are limited to tuple deletions. We identify two
basic computational issues: repair checking (is a database instance a repair of
a given database?) and consistent query answers (is a tuple an answer to a
given query in every repair of a given database?). We study the computational
complexity of both problems, delineating the boundary between the tractable and
the intractable. We consider denial constraints, general functional and
inclusion dependencies, as well as key and foreign key constraints. Our results
shed light on the computational feasibility of minimal-change integrity
maintenance. The tractable cases should lead to practical implementations. The
intractability results highlight the inherent limitations of any integrity
enforcement mechanism, e.g., triggers or referential constraint actions, as a
way of performing minimal-change integrity maintenance.


title: Retractions of Types with Many Atoms

abstract:
  We define a sound and complete proof system for affine beta-eta-retractions
in simple types built over many atoms, and we state simple necessary conditions
for arbitrary beta-eta-retractions in simple and polymorphic types.


title: Use of openMosix for parallel I/O balancing on storage in Linux cluster

abstract:
  In this paper I present some experiences made in the matter of I/O for Linux
Clustering. In particular is illustrated the use of the package openMosix, a
balancer of workload for processes running in a cluster of nodes. I describe
some tests for balancing the load of I/O storage massive processes in a cluster
with four components. This work is been written for the proceedings of the
workshop Linux cluster: the openMosix approach held at CINECA, Bologna, Italy,
on 28 november 2002.


title: Optimized Color Gamuts for Tiled Displays

abstract:
  We consider the problem of finding a large color space that can be generated
by all units in multi-projector tiled display systems. Viewing the problem
geometrically as one of finding a large parallelepiped within the intersection
of multiple parallelepipeds, and using colorimetric principles to define a
volume-based objective function for comparing feasible solutions, we develop an
algorithm for finding the optimal gamut in time O(n^3), where n denotes the
number of projectors in the system. We also discuss more efficient quasiconvex
programming algorithms for alternative objective functions based on maximizing
the quality of the color space extrema.


title:
Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent
  Space Alignment

abstract:
  Nonlinear manifold learning from unorganized data points is a very
challenging unsupervised learning and data visualization problem with a great
variety of applications. In this paper we present a new algorithm for manifold
learning and nonlinear dimension reduction. Based on a set of unorganized data
points sampled with noise from the manifold, we represent the local geometry of
the manifold using tangent spaces learned by fitting an affine subspace in a
neighborhood of each data point. Those tangent spaces are aligned to give the
internal global coordinates of the data points with respect to the underlying
manifold by way of a partial eigendecomposition of the neighborhood connection
matrix. We present a careful error analysis of our algorithm and show that the
reconstruction errors are of second-order accuracy. We illustrate our algorithm
using curves and surfaces both in
  2D/3D and higher dimensional Euclidean spaces, and 64-by-64 pixel face images
with various pose and lighting conditions. We also address several theoretical
and algorithmic issues for further research and improvements.


title:
On the survey-propagation equations for the random K-satisfiability
  problem

abstract:
  In this note we study the existence of a solution to the survey-propagation
equations for the random K-satisfiability problem for a given instance. We
conjecture that when the number of variables goes to infinity, the solution of
these equations for a given instance can be approximated by the solution of the
corresponding equations on an infinite tree. We conjecture (and we bring
numerical evidence) that the survey-propagation equations on the infinite tree
have an unique solution in the suitable range of parameters.


title: JohnnyVon: Self-Replicating Automata in Continuous Two-Dimensional Space

abstract:
  JohnnyVon is an implementation of self-replicating automata in continuous
two-dimensional space. Two types of particles drift about in a virtual liquid.
The particles are automata with discrete internal states but continuous
external relationships. Their internal states are governed by finite state
machines but their external relationships are governed by a simulated physics
that includes brownian motion, viscosity, and spring-like attractive and
repulsive forces. The particles can be assembled into patterns that can encode
arbitrary strings of bits. We demonstrate that, if an arbitrary "seed" pattern
is put in a "soup" of separate individual particles, the pattern will replicate
by assembling the individual particles into copies of itself. We also show
that, given sufficient time, a soup of separate individual particles will
eventually spontaneously form self-replicating patterns. We discuss the
implications of JohnnyVon for research in nanotechnology, theoretical biology,
and artificial life.


title:
Mining the Web for Lexical Knowledge to Improve Keyphrase Extraction:
  Learning from Labeled and Unlabeled Data

abstract:
  Keyphrases are useful for a variety of purposes, including summarizing,
indexing, labeling, categorizing, clustering, highlighting, browsing, and
searching. The task of automatic keyphrase extraction is to select keyphrases
from within the text of a given document. Automatic keyphrase extraction makes
it feasible to generate keyphrases for the huge number of documents that do not
have manually assigned keyphrases. Good performance on this task has been
obtained by approaching it as a supervised learning problem. An input document
is treated as a set of candidate phrases that must be classified as either
keyphrases or non-keyphrases. To classify a candidate phrase as a keyphrase,
the most important features (attributes) appear to be the frequency and
location of the candidate phrase in the document. Recent work has demonstrated
that it is also useful to know the frequency of the candidate phrase as a
manually assigned keyphrase for other documents in the same domain as the given
document (e.g., the domain of computer science). Unfortunately, this
keyphrase-frequency feature is domain-specific (the learning process must be
repeated for each new domain) and training-intensive (good performance requires
a relatively large number of training documents in the given domain, with
manually assigned keyphrases). The aim of the work described here is to remove
these limitations. In this paper, I introduce new features that are derived by
mining lexical knowledge from a very large collection of unlabeled data,
consisting of approximately 350 million Web pages without manually assigned
keyphrases. I present experiments that show that the new features result in
improved keyphrase extraction, although they are neither domain-specific nor
training-intensive.


title:
Unsupervised Learning of Semantic Orientation from a
  Hundred-Billion-Word Corpus

abstract:
  The evaluative character of a word is called its semantic orientation. A
positive semantic orientation implies desirability (e.g., "honest", "intrepid")
and a negative semantic orientation implies undesirability (e.g., "disturbing",
"superfluous"). This paper introduces a simple algorithm for unsupervised
learning of semantic orientation from extremely large corpora. The method
involves issuing queries to a Web search engine and using pointwise mutual
information to analyse the results. The algorithm is empirically evaluated
using a training corpus of approximately one hundred billion words -- the
subset of the Web that is indexed by the chosen search engine. Tested with
3,596 words (1,614 positive and 1,982 negative), the algorithm attains an
accuracy of 80%. The 3,596 test words include adjectives, adverbs, nouns, and
verbs. The accuracy is comparable with the results achieved by Hatzivassiloglou
and McKeown (1997), using a complex four-stage supervised learning algorithm
that is restricted to determining the semantic orientation of adjectives.


title: Learning to Extract Keyphrases from Text

abstract:
  Many academic journals ask their authors to provide a list of about five to
fifteen key words, to appear on the first page of each article. Since these key
words are often phrases of two or more words, we prefer to call them
keyphrases. There is a surprisingly wide variety of tasks for which keyphrases
are useful, as we discuss in this paper. Recent commercial software, such as
Microsoft's Word 97 and Verity's Search 97, includes algorithms that
automatically extract keyphrases from documents. In this paper, we approach the
problem of automatically extracting keyphrases from text as a supervised
learning task. We treat a document as a set of phrases, which the learning
algorithm must learn to classify as positive or negative examples of
keyphrases. Our first set of experiments applies the C4.5 decision tree
induction algorithm to this learning task. The second set of experiments
applies the GenEx algorithm to the task. We developed the GenEx algorithm
specifically for this task. The third set of experiments examines the
performance of GenEx on the task of metadata generation, relative to the
performance of Microsoft's Word 97. The fourth and final set of experiments
investigates the performance of GenEx on the task of highlighting, relative to
Verity's Search 97. The experimental results support the claim that a
specialized learning algorithm (GenEx) can generate better keyphrases than a
general-purpose learning algorithm (C4.5) and the non-learning algorithms that
are used in commercial software (Word 97 and Search 97).


title: Extraction of Keyphrases from Text: Evaluation of Four Algorithms

abstract:
  This report presents an empirical evaluation of four algorithms for
automatically extracting keywords and keyphrases from documents. The four
algorithms are compared using five different collections of documents. For each
document, we have a target set of keyphrases, which were generated by hand. The
target keyphrases were generated for human readers; they were not tailored for
any of the four keyphrase extraction algorithms. Each of the algorithms was
evaluated by the degree to which the algorithm's keyphrases matched the
manually generated keyphrases. The four algorithms were (1) the AutoSummarize
feature in Microsoft's Word 97, (2) an algorithm based on Eric Brill's
part-of-speech tagger, (3) the Summarize feature in Verity's Search 97, and (4)
NRC's Extractor algorithm. For all five document collections, NRC's Extractor
yields the best match with the manually generated keyphrases.