title:
Architecture of monitoring elements for the network element modeling in
  a Grid infrastructure

abstract:
  Several tools exist that collect host-to-host connectivity measurements. To
improve the usability of such measurements, they should be mapped into a
framework consisting of complex subsystems, and the infrastructure that
connects them. We introduce one such framework, and analyze the architectural
implications on the network structure. In our framework, a complex subsystem
consists of several computing facilities and the infrastructure that connects
them: we call it a -monitoring domain-. The task of measuring the connectivity
between -monitoring domains- is considered distinct from the activity of
-storage- and -computing- elements. Therefore we introduce a new element in our
topology: we call it -theodolite- element, since its function is similar to
that of a transponder. Using these basic concepts, we analyze the architectural
implications on the network structure: in a nutshell, if we want that
-theodolites- serve as a reference, than the contribution to the relevant
network metrics due to the -monitoring domain- infrastructure must be
negligible with respect to contributions of the inter-domain infrastructure. In
addition all -theodolites- of a -monitoring domain- must give an image of the
inter-domain infrastructure that is consistent with that experienced by network
applications. We conclude giving a running SQL example of how information about
-monitoring domains- and -theodolites- could be organized, and we outline the
application of such framework in the GLUE schema activity for the network
element


title:
Information Compression by Multiple Alignment, Unification and Search as
  a Unifying Principle in Computing and Cognition

abstract:
  This article presents an overview of the idea that "information compression
by multiple alignment, unification and search" (ICMAUS) may serve as a unifying
principle in computing (including mathematics and logic) and in such aspects of
human cognition as the analysis and production of natural language, fuzzy
pattern recognition and best-match information retrieval, concept hierarchies
with inheritance of attributes, probabilistic reasoning, and unsupervised
inductive learning. The ICMAUS concepts are described together with an outline
of the SP61 software model in which the ICMAUS concepts are currently realised.
A range of examples is presented, illustrated with output from the SP61 model.


title:
Improving the Security and Performance of the BaBar Detector Controls
  System

abstract:
  It starts out innocently enough - users want to monitor Online data and so
run their own copies of the detector control GUIs in their offices and at home.
But over time, the number of processes making requests for values to display on
GUIs, webpages and stripcharts can grow, and affect the performance of an
Input/Output Controller (IOC) such that it is unable to respond to requests
from requests critical to data-taking. At worst, an IOC can hang, its CPU
having been allocated 100% to responding to network requests.
  For the BaBar Online Detector Control System, we were able to eliminate this
problem and make great gains in security by moving all of the IOCs to a
non-routed, virtual LAN and by enlisting a workstation with two network
interface cards to act as the interface between the virtual LAN and the public
BaBar network. On the interface machine, we run the Experimental Physics
Industrial Control System (EPICS) Channel Access (CA) gateway software
(originating from Advanced Photon Source). This software accepts as inputs, all
the channels which are loaded into the EPICS databases on all the IOCs. It
polls them to update its copy of the values. It answers requests from
applications by sending them the currently cached value.
  We adopted the requirement that data-taking would be independent of the
gateway, so that, in the event of a gateway failure, data-taking would be
uninterrupted. In this way, we avoided introducing any new risk elements to
data-taking. Security rules already in use by the IOC were propagated to the
gateway's own security rules and the security of the IOCs themselves was
improved by removing them from the public BaBar network.


title: Deterministic Sampling and Range Counting in Geometric Data Streams

abstract:
  We present memory-efficient deterministic algorithms for constructing
epsilon-nets and epsilon-approximations of streams of geometric data. Unlike
probabilistic approaches, these deterministic samples provide guaranteed bounds
on their approximation factors. We show how our deterministic samples can be
used to answer approximate online iceberg geometric queries on data streams. We
use these techniques to approximate several robust statistics of geometric data
streams, including Tukey depth, simplicial depth, regression depth, the
Thiel-Sen estimator, and the least median of squares. Our algorithms use only a
polylogarithmic amount of memory, provided the desired approximation factors
are inverse-polylogarithmic. We also include a lower bound for non-iceberg
geometric queries.


title: Issues in Communication Game

abstract:
  As interaction between autonomous agents, communication can be analyzed in
game-theoretic terms. Meaning game is proposed to formalize the core of
intended communication in which the sender sends a message and the receiver
attempts to infer its meaning intended by the sender. Basic issues involved in
the game of natural language communication are discussed, such as salience,
grammaticality, common sense, and common belief, together with some
demonstration of the feasibility of game-theoretic account of language.


title: The ray attack, an inefficient trial to break RSA cryptosystems

abstract:
  The basic properties of RSA cryptosystems and some classical attacks on them
are described. Derived from geometric properties of the Euler functions, the
Euler function rays, a new ansatz to attack RSA cryptosystems is presented. A
resulting, albeit inefficient, algorithm is given. It essentially consists of a
loop with starting value determined by the Euler function ray and with step
width given by a function $\omega_e(n)$ being a multiple of the order
$\mathrm{ord}_n(e)$, where $e$ denotes the public key exponent and $n$ the RSA
modulus. For $n=pq$ and an estimate $r<\sqrt{pq}$ for the smaller prime factor
$p$, the running time is given by $T(e,n,r) = O((r-p)\ln e \ln n \ln r).$


title: Parsing and Generation with Tabulation and Compilation

abstract:
  The standard tabulation techniques for logic programming presuppose fixed
order of computation. Some data-driven control should be introduced in order to
deal with diverse contexts. The present paper describes a data-driven method of
constraint transformation with a sort of compilation which subsumes
accessibility check and last-call optimization, which characterize standard
natural-language parsing techniques, semantic-head-driven generation, etc.


title:
Automatic Classification using Self-Organising Neural Networks in
  Astrophysical Experiments

abstract:
  Self-Organising Maps (SOMs) are effective tools in classification problems,
and in recent years the even more powerful Dynamic Growing Neural Networks, a
variant of SOMs, have been developed. Automatic Classification (also called
clustering) is an important and difficult problem in many Astrophysical
experiments, for instance, Gamma Ray Burst classification, or gamma-hadron
separation. After a brief introduction to classification problem, we discuss
Self-Organising Maps in section 2. Section 3 discusses with various models of
growing neural networks and finally in section 4 we discuss the research
perspectives in growing neural networks for efficient classification in
astrophysical problems.


title: Data Management and Mining in Astrophysical Databases

abstract:
  We analyse the issues involved in the management and mining of astrophysical
data. The traditional approach to data management in the astrophysical field is
not able to keep up with the increasing size of the data gathered by modern
detectors. An essential role in the astrophysical research will be assumed by
automatic tools for information extraction from large datasets, i.e. data
mining techniques, such as clustering and classification algorithms. This asks
for an approach to data management based on data warehousing, emphasizing the
efficiency and simplicity of data access; efficiency is obtained using
multidimensional access methods and simplicity is achieved by properly handling
metadata. Clustering and classification techniques, on large datasets, pose
additional requirements: computational and memory scalability with respect to
the data size, interpretability and objectivity of clustering or classification
results. In this study we address some possible solutions.


title: Excellence in Computer Simulation

abstract:
  Excellent computer simulations are done for a purpose. The most valid
purposes are to explore uncharted territory, to resolve a well-posed scientific
or technical question, or to make a design choice. Stand-alone modeling can
serve the first purpose. The other two goals need a full integration of the
modeling effort into a scientific or engineering program.
  Some excellent work, much of it related to the Department of Energy
Laboratories, is reviewed. Some less happy stories are recounted.
  In the past, some of the most impressive work has involved complexity and
chaos. Prediction in a complex world requires a first principles understanding
based upon the intersection of theory, experiment and simulation.


title: Range Mode and Range Median Queries on Lists and Trees

abstract:
  We consider algorithms for preprocessing labelled lists and trees so that,
for any two nodes u and v we can answer queries of the form: What is the mode
or median label in the sequence of labels on the path from u to v.


title:
Adaptive Domain Model: Dealing With Multiple Attributes of Self-Managing
  Distributed Object Systems

abstract:
  Self-managing software has emerged as modern systems have become more
complex. Some of the distributed object systems may contain thousands of
objects deployed on tens or even hundreds hosts. Development and support of
such systems often costs a lot. To solve this issue the systems, which are
capable supporting multiple self-managing attributes, should be created. In the
paper, the Adaptive domain concept is introduced as an extension to the basic
domain concept to support a generic adaptation environment for building
distributed object systems with multiple self-managing attributes.


title: Small-World File-Sharing Communities

abstract:
  Web caches, content distribution networks, peer-to-peer file sharing
networks, distributed file systems, and data grids all have in common that they
involve a community of users who generate requests for shared data. In each
case, overall system performance can be improved significantly if we can first
identify and then exploit interesting structure within a community's access
patterns. To this end, we propose a novel perspective on file sharing based on
the study of the relationships that form among users based on the files in
which they are interested.
  We propose a new structure that captures common user interests in data--the
data-sharing graph-- and justify its utility with studies on three
data-distribution systems: a high-energy physics collaboration, the Web, and
the Kazaa peer-to-peer network. We find small-world patterns in the
data-sharing graphs of all three communities. We analyze these graphs and
propose some probable causes for these emergent small-world patterns. The
significance of small-world patterns is twofold: it provides a rigorous support
to intuition and, perhaps most importantly, it suggests ways to design
mechanisms that exploit these naturally emerging patterns.


title: Supporting Dynamic Ad hoc Collaboration Capabilities

abstract:
  Modern HENP experiments such as CMS and Atlas involve as many as 2000
collaborators around the world. Collaborations this large will be unable to
meet often enough to support working closely together. Many of the tools
currently available for collaboration focus on heavy-weight applications such
as videoconferencing tools. While these are important, there is a more basic
need for tools that support connecting physicists to work together on an ad hoc
or continuous basis. Tools that support the day-to-day connectivity and
underlying needs of a group of collaborators are important for providing
light-weight, non-intrusive, and flexible ways to work collaboratively. Some
example tools include messaging, file-sharing, and shared plot viewers. An
important component of the environment is a scalable underlying communication
framework. In this paper we will describe our current progress on building a
dynamic and ad hoc collaboration environment and our vision for its evolution
into a HENP collaboration environment.


title: Manifold Learning with Geodesic Minimal Spanning Trees

abstract:
  In the manifold learning problem one seeks to discover a smooth low
dimensional surface, i.e., a manifold embedded in a higher dimensional linear
vector space, based on a set of measured sample points on the surface. In this
paper we consider the closely related problem of estimating the manifold's
intrinsic dimension and the intrinsic entropy of the sample points.
Specifically, we view the sample points as realizations of an unknown
multivariate density supported on an unknown smooth manifold. We present a
novel geometrical probability approach, called the
geodesic-minimal-spanning-tree (GMST), to obtaining asymptotically consistent
estimates of the manifold dimension and the R\'{e}nyi $\alpha$-entropy of the
sample density on the manifold. The GMST approach is striking in its simplicity
and does not require reconstructing the manifold or estimating the multivariate
density of the samples. The GMST method simply constructs a minimal spanning
tree (MST) sequence using a geodesic edge matrix and uses the overall lengths
of the MSTs to simultaneously estimate manifold dimension and entropy. We
illustrate the GMST approach for dimension and entropy estimation of a human
face dataset.


title: Modeling Business

abstract:
  Business concepts are studied using a metamodel-based approach, using UML
2.0. The Notation Independent Business concepts metamodel is introduced. The
approach offers a mapping between different business modeling notations which
could be used for bridging BM tools and boosting the MDA approach.


title:
Bridging the gap between modal temporal logics and constraint-based QSR
  as an ALC(D) spatio-temporalisation with weakly cyclic TBoxes

abstract:
  The aim of this work is to provide a family of qualitative theories for
spatial change in general, and for motion of spatial scenes in particular. To
achieve this, we consider a spatio-temporalisation MTALC(D_x), of the
well-known ALC(D) family of Description Logics (DLs) with a concrete domainan.
In particular, the concrete domain D_x is generated by a qualitative spatial
Relation Algebra (RA) x. We show the important result that satisfiability of an
MTALC(D_x) concept with respect to a weakly cyclic TBox is decidable in
nondeterministic exponential time, by reducing it to the emptiness problem of a
weak alternating automaton augmented with spatial constraints, which we show to
remain decidable, although the accepting condition of a run involves,
additionally to the standard case, consistency of a CSP (Constraint
Satisfaction Problem) potentially infinite. The result provides an effective
tableaux-like satisfiability procedure which is discussed.


title: High-density and Secure Data Transmission via Linear Combinations

abstract:
  Suppose that there are $n$ Senders and $n$ Receivers. Our goal is to send
long messages from Sender $i$ to Receiver $i$ such that no other receiver can
retrieve the message intended for Receiver $i$. The task can easily be
completed using $n$ private channels between the pairs. Solutions, using one
channel needs either encryption or switching elements for routing the messages
to their addressee.
  The main result of the present work is a description of a network in which
The Senders and the Receivers are connected with only $n^{o(1)}$ channels; the
encoding and de-coding is nothing else just very fast linear combinations of
the message-bits; and there are no switching or routing-elements in the
network, just linear combinations are computed, with fixed connections
(channels or wires).
  In the proofs we do not use {\em any} unproven cryptographical or complexity
theoretical assumptions.


title: A Note on Objects Built From Bricks without Corners

abstract:
  We report a small advance on a question raised by Robertson, Schweitzer, and
Wagon in [RSW02]. They constructed a genus-13 polyhedron built from bricks
without corners, and asked whether every genus-0 such polyhedron must have a
corner. A brick is a parallelopiped, and a corner is a brick of degree three or
less in the brick graph. We describe a genus-3 polyhedron built from bricks
with no corner, narrowing the genus gap.


title:
An Extension of the Lovasz Local Lemma, and its Applications to Integer
  Programming

abstract:
  The Lovasz Local Lemma due to Erdos and Lovasz is a powerful tool in proving
the existence of rare events. We present an extension of this lemma, which
works well when the event to be shown to exist is a conjunction of individual
events, each of which asserts that a random variable does not deviate much from
its mean. As applications, we consider two classes of NP-hard integer programs:
minimax and covering integer programs. A key technique, randomized rounding of
linear relaxations, was developed by Raghavan and Thompson to derive good
approximation algorithms for such problems. We use our extension of the Local
Lemma to prove that randomized rounding produces, with non-zero probability,
much better feasible solutions than known before, if the constraint matrices of
these integer programs are column-sparse (e.g., routing using short paths,
problems on hypergraphs with small dimension/degree). This complements certain
well-known results from discrepancy theory. We also generalize the method of
pessimistic estimators due to Raghavan, to obtain constructive (algorithmic)
versions of our results for covering integer programs.


title: The Linguistic DS: Linguisitic Description in MPEG-7

abstract:
  MPEG-7 (Moving Picture Experts Group Phase 7) is an XML-based international
standard on semantic description of multimedia content. This document discusses
the Linguistic DS and related tools. The linguistic DS is a tool, based on the
GDA tag set (http://i-content.org/GDA/tagset.html), for semantic annotation of
linguistic data in or associated with multimedia content. The current document
text reflects `Study of FPDAM - MPEG-7 MDS Extensions' issued in March 2003,
and not most part of MPEG-7 MDS, for which the readers are referred to the
first version of MPEG-7 MDS document available from ISO (http://www.iso.org).
Without that reference, however, this document should be mostly intelligible to
those who are familiar with XML and linguistic theories. Comments are welcome
and will be considered in the standardization process.


title:
Flexible Camera Calibration Using a New Analytical Radial Undistortion
  Formula with Application to Mobile Robot Localization

abstract:
  Most algorithms in 3D computer vision rely on the pinhole camera model
because of its simplicity, whereas virtually all imaging devices introduce
certain amount of nonlinear distortion, where the radial distortion is the most
severe part. Common approach to radial distortion is by the means of polynomial
approximation, which introduces distortion-specific parameters into the camera
model and requires estimation of these distortion parameters. The task of
estimating radial distortion is to find a radial distortion model that allows
easy undistortion as well as satisfactory accuracy. This paper presents a new
radial distortion model with an easy analytical undistortion formula, which
also belongs to the polynomial approximation category. Experimental results are
presented to show that with this radial distortion model, satisfactory accuracy
is achieved. An application of the new radial distortion model is non-iterative
yellow line alignment with a calibrated camera on ODIS, a robot built in our
CSOIS.


title: A New Analytical Radial Distortion Model for Camera Calibration

abstract:
  Common approach to radial distortion is by the means of polynomial
approximation, which introduces distortion-specific parameters into the camera
model and requires estimation of these distortion parameters. The task of
estimating radial distortion is to find a radial distortion model that allows
easy undistortion as well as satisfactory accuracy. This paper presents a new
radial distortion model with an easy analytical undistortion formula, which
also belongs to the polynomial approximation category. Experimental results are
presented to show that with this radial distortion model, satisfactory accuracy
is achieved.


title: Rational Radial Distortion Models with Analytical Undistortion Formulae

abstract:
  The common approach to radial distortion is by the means of polynomial
approximation, which introduces distortion-specific parameters into the camera
model and requires estimation of these distortion parameters. The task of
estimating radial distortion is to find a radial distortion model that allows
easy undistortion as well as satisfactory accuracy. This paper presents a new
class of rational radial distortion models with easy analytical undistortion
formulae. Experimental results are presented to show that with this class of
rational radial distortion models, satisfactory and comparable accuracy is
achieved.


title:
Integrating cardinal direction relations and other orientation relations
  in Qualitative Spatial Reasoning

abstract:
  We propose a calculus integrating two calculi well-known in Qualitative
Spatial Reasoning (QSR): Frank's projection-based cardinal direction calculus,
and a coarser version of Freksa's relative orientation calculus. An original
constraint propagation procedure is presented, which implements the interaction
between the two integrated calculi. The importance of taking into account the
interaction is shown with a real example providing an inconsistent knowledge
base, whose inconsistency (a) cannot be detected by reasoning separately about
each of the two components of the knowledge, just because, taken separately,
each is consistent, but (b) is detected by the proposed algorithm, thanks to
the interaction knowledge propagated from each of the two compnents to the
other.


title: Limit groups and groups acting freely on $\bbR^n$-trees

abstract:
  We give a simple proof of the finite presentation of Sela's limit groups by
using free actions on $\bbR^n$-trees. We first prove that Sela's limit groups
do have a free action on an $\bbR^n$-tree. We then prove that a finitely
generated group having a free action on an $\bbR^n$-tree can be obtained from
free abelian groups and surface groups by a finite sequence of free products
and amalgamations over cyclic groups. As a corollary, such a group is finitely
presented, has a finite classifying space, its abelian subgroups are finitely
generated and contains only finitely many conjugacy classes of non-cyclic
maximal abelian subgroups.


title: A ternary Relation Algebra of directed lines

abstract:
  We define a ternary Relation Algebra (RA) of relative position relations on
two-dimensional directed lines (d-lines for short). A d-line has two degrees of
freedom (DFs): a rotational DF (RDF), and a translational DF (TDF). The
representation of the RDF of a d-line will be handled by an RA of 2D
orientations, CYC_t, known in the literature. A second algebra, TA_t, which
will handle the TDF of a d-line, will be defined. The two algebras, CYC_t and
TA_t, will constitute, respectively, the translational and the rotational
components of the RA, PA_t, of relative position relations on d-lines: the PA_t
atoms will consist of those pairs <t,r> of a TA_t atom and a CYC_t atom that
are compatible. We present in detail the RA PA_t, with its converse table, its
rotation table and its composition tables. We show that a (polynomial)
constraint propagation algorithm, known in the literature, is complete for a
subset of PA_t relations including almost all of the atomic relations. We will
discuss the application scope of the RA, which includes incidence geometry, GIS
(Geographic Information Systems), shape representation, localisation in
(multi-)robot navigation, and the representation of motion prepositions in NLP
(Natural Language Processing). We then compare the RA to existing ones, such as
an algebra for reasoning about rectangles parallel to the axes of an
(orthogonal) coordinate system, a ``spatial Odyssey'' of Allen's interval
algebra, and an algebra for reasoning about 2D segments.


title:
An Analytical Piecewise Radial Distortion Model for Precision Camera
  Calibration

abstract:
  The common approach to radial distortion is by the means of polynomial
approximation, which introduces distortion-specific parameters into the camera
model and requires estimation of these distortion parameters. The task of
estimating radial distortion is to find a radial distortion model that allows
easy undistortion as well as satisfactory accuracy. This paper presents a new
piecewise radial distortion model with easy analytical undistortion formula.
The motivation for seeking a piecewise radial distortion model is that, when a
camera is resulted in a low quality during manufacturing, the nonlinear radial
distortion can be complex. Using low order polynomials to approximate the
radial distortion might not be precise enough. On the other hand, higher order
polynomials suffer from the inverse problem. With the new piecewise radial
distortion function, more flexibility is obtained and the radial undistortion
can be performed analytically. Experimental results are presented to show that
with this new piecewise radial distortion model, better performance is achieved
than that using the single function. Furthermore, a comparable performance with
the conventional polynomial model using 2 coefficients can also be
accomplished.


title:
Gridscape: A Tool for the Creation of Interactive and Dynamic Grid
  Testbed Web Portals

abstract:
  The notion of grid computing has gained an increasing popularity recently as
a realistic solution to many of our large-scale data storage and processing
needs. It enables the sharing, selection and aggregation of resources
geographically distributed across collaborative organisations. Now more and
more people are beginning to embrace grid computing and thus are seeing the
need to set up their own grids and grid testbeds. With this comes the need to
have some means to enable them to view and monitor the status of the resources
in these testbeds (eg. Web based Grid portal). Generally developers invest a
substantial amount of time and effort developing custom monitoring software. To
overcome this limitation, this paper proposes Gridscape ? a tool that enables
the rapid creation of interactive and dynamic testbed portals (without any
programming effort). Gridscape primarily aims to provide a solution for those
users who need to be able to create a grid testbed portal but don?t necessarily
have the time or resources to build a system of their own from scratch.


title:
Hamevol1.0: a C++ code for differential equations based on Runge-Kutta
  algorithm. An application to matter enhanced neutrino oscillation

abstract:
  We present a C++ implementation of a fifth order semi-implicit Runge-Kutta
algorithm for solving Ordinary Differential Equations. This algorithm can be
used for studying many different problems and in particular it can be applied
for computing the evolution of any system whose Hamiltonian is known. We
consider in particular the problem of calculating the neutrino oscillation
probabilities in presence of matter interactions. The time performance and the
accuracy of this implementation is competitive with respect to the other
analytical and numerical techniques used in literature. The algorithm design
and the salient features of the code are presented and discussed and some
explicit examples of code application are given.


title:
Contributions to the Development and Improvement of a Regulatory and
  Pre-Regulatory Digitally System for the Tools within Flexible Fabrication
  Systems

abstract:
  The paper reports the obtained results for the projection and realization of
a digitally system aiming to assist the equipment for a regulatory and
pre-regulatory tools and holding tools within the flexible fabrication systems
(FFS). Moreover, based on the present results, the same methodology can be
applied for assisting tools from the point of view of their integrity and to
wear compensation in the FFS framework.


title: Learning Analogies and Semantic Relations

abstract:
  We present an algorithm for learning from unlabeled text, based on the Vector
Space Model (VSM) of information retrieval, that can solve verbal analogy
questions of the kind found in the Scholastic Aptitude Test (SAT). A verbal
analogy has the form A:B::C:D, meaning "A is to B as C is to D"; for example,
mason:stone::carpenter:wood. SAT analogy questions provide a word pair, A:B,
and the problem is to select the most analogous word pair, C:D, from a set of
five choices. The VSM algorithm correctly answers 47% of a collection of 374
college-level analogy questions (random guessing would yield 20% correct). We
motivate this research by relating it to work in cognitive science and
linguistics, and by applying it to a difficult problem in natural language
processing, determining semantic relations in noun-modifier pairs. The problem
is to classify a noun-modifier pair, such as "laser printer", according to the
semantic relation between the noun (printer) and the modifier (laser). We use a
supervised nearest-neighbour algorithm that assigns a class to a given
noun-modifier pair by finding the most analogous noun-modifier pair in the
training data. With 30 classes of semantic relations, on a collection of 600
labeled noun-modifier pairs, the learning algorithm attains an F value of 26.5%
(random guessing: 3.3%). With 5 classes of semantic relations, the F value is
43.2% (random: 20%). The performance is state-of-the-art for these challenging
problems.


title: From Statistical Knowledge Bases to Degrees of Belief

abstract:
  An intelligent agent will often be uncertain about various properties of its
environment, and when acting in that environment it will frequently need to
quantify its uncertainty. For example, if the agent wishes to employ the
expected-utility paradigm of decision theory to guide its actions, it will need
to assign degrees of belief (subjective probabilities) to various assertions.
Of course, these degrees of belief should not be arbitrary, but rather should
be based on the information available to the agent. This paper describes one
approach for inducing degrees of belief from very rich knowledge bases, that
can include information about particular individuals, statistical correlations,
physical laws, and default rules. We call our approach the random-worlds
method. The method is based on the principle of indifference: it treats all of
the worlds the agent considers possible as being equally likely. It is able to
integrate qualitative default reasoning with quantitative probabilistic
reasoning by providing a language in which both types of information can be
easily expressed. Our results show that a number of desiderata that arise in
direct inference (reasoning from statistical information to conclusions about
individuals) and default reasoning follow directly {from} the semantics of
random worlds. For example, random worlds captures important patterns of
reasoning such as specificity, inheritance, indifference to irrelevant
information, and default assumptions of independence. Furthermore, the
expressive power of the language used and the intuitive semantics of random
worlds allow the method to deal with problems that are beyond the scope of many
other non-deductive reasoning systems.


title: Secrecy in Multiagent Systems

abstract:
  We introduce a general framework for reasoning about secrecy and privacy
requirements in multiagent systems. Our definitions extend earlier definitions
of secrecy and nondeducibility given by Shannon and Sutherland. Roughly
speaking, one agent maintains secrecy with respect to another if the second
agent cannot rule out any possibilities for the behavior or state of the first
agent. We show that the framework can handle probability and nondeterminism in
a clean way, is useful for reasoning about asynchronous systems as well as
synchronous systems, and suggests generalizations of secrecy that may be useful
for dealing with issues such as resource-bounded reasoning. We also show that a
number of well-known attempts to characterize the absence of information flow
are special cases of our definitions of secrecy.


title: Efficient Instrumentation for Performance Profiling

abstract:
  Performance profiling consists of tracing a software system during execution
and then analyzing the obtained traces. However, traces themselves affect the
performance of the system distorting its execution. Therefore, there is a need
to minimize the effect of the tracing on the underlying system's performance.
To achieve this, the trace set needs to be optimized according to the
performance profiling problem being solved. Our position is that such
minimization can be achieved only by adding the software trace design and
implementation to the overall software development process. In such a process,
the performance analyst supplies the knowledge of performance measurement
requirements, while the software developer supplies the knowledge of the
software. Both of these are needed for an optimal trace placement.


title: Group Authentication Using The Naccache-Stern Public-Key Cryptosystem

abstract:
  A group authentication protocol authenticates pre-defined groups of
individuals such that:
  - No individual is identified
  - No knowledge of which groups can be successfully authenticated is known to
the verifier
  - No sensitive data is exposed
  The paper presents a group authentication protocol based on splitting the
private keys of the Naccache-Stern public-key cryptosystem in such a way that
the Boolean expression defining the authenticable groups is implicit in the
split.


title: Neural realisation of the SP theory: cell assemblies revisited

abstract:
  This paper describes how the elements of the SP theory (Wolff, 2003a) may be
realised with neural structures and processes. To the extent that this is
successful, the insights that have been achieved in the SP theory - the
integration and simplification of a range of phenomena in perception and
cognition - may be incorporated in a neural view of brain function.
  These proposals may be seen as a development of Hebb's (1949) concept of a
'cell assembly'. By contrast with that concept and variants of it, the version
described in this paper proposes that any one neuron can belong in one assembly
and only one assembly. A distinctive feature of the present proposals is that
any neuron or cluster of neurons within a cell assembly may serve as a proxy or
reference for another cell assembly or class of cell assemblies. This device
provides solutions to many of the problems associated with cell assemblies, it
allows information to be stored in a compressed form, and it provides a robust
mechanism by which assemblies may be connected to form hierarchies, grammars
and other kinds of knowledge structure.
  Drawing on insights derived from the SP theory, the paper also describes how
unsupervised learning may be achieved with neural structures and processes.
This theory of learning overcomes weaknesses in the Hebbian concept of learning
and it is, at the same time, compatible with the observations that Hebb's
theory was designed to explain.


title: Boundary knot method for Laplace and biharmonic problems

abstract:
  The boundary knot method (BKM) [1] is a meshless boundary-type radial basis
function (RBF) collocation scheme, where the nonsingular general solution is
used instead of fundamental solution to evaluate the homogeneous solution,
while the dual reciprocity method (DRM) is employed to approximation of
particular solution. Despite the fact that there are not nonsingular RBF
general solutions available for Laplace and biharmonic problems, this study
shows that the method can be successfully applied to these problems. The
high-order general and fundamental solutions of Burger and Winkler equations
are also first presented here.


title: Euclidean algorithms are Gaussian

abstract:
  This study provides new results about the probabilistic behaviour of a class
of Euclidean algorithms: the asymptotic distribution of a whole class of
cost-parameters associated to these algorithms is normal. For the cost
corresponding to the number of steps Hensley already has proved a Local Limit
Theorem; we give a new proof, and extend his result to other euclidean
algorithms and to a large class of digit costs, obtaining a faster, optimal,
rate of convergence. The paper is based on the dynamical systems methodology,
and the main tool is the transfer operator. In particular, we use recent
results of Dolgopyat.


title:
An Alternative to RDF-Based Languages for the Representation and
  Processing of Ontologies in the Semantic Web

abstract:
  This paper describes an approach to the representation and processing of
ontologies in the Semantic Web, based on the ICMAUS theory of computation and
AI. This approach has strengths that complement those of languages based on the
Resource Description Framework (RDF) such as RDF Schema and DAML+OIL. The main
benefits of the ICMAUS approach are simplicity and comprehensibility in the
representation of ontologies, an ability to cope with errors and uncertainties
in knowledge, and a versatile reasoning system with capabilities in the kinds
of probabilistic reasoning that seem to be required in the Semantic Web.


title: Implementing an Agent Trade Server

abstract:
  An experimental server for stock trading autonomous agents is presented and
made available, together with an agent shell for swift development. The server,
written in Java, was implemented as proof-of-concept for an agent trade server
for a real financial exchange.


title:
Application of interactive parallel visualization for commodity-based
  clusters using visualization APIs

abstract:
  We present an efficient and inexpensive to develop application for
interactive high-performance parallel visualization. We extend popular APIs
such as Open Inventor and VTK to support commodity-based cluster visualization.
Our implementation follows a standard master/slave concept: the general idea is
to have a ``Master'' node, which will intercept a sequential graphical user
interface (GUI) and broadcast it to the ``Slave'' nodes. The interactions
between the nodes are implemented using MPI. The parallel remote rendering uses
Chromium. This paper is mainly the report of our implementation experiences. We
present in detail the proposed model and key aspects of its implementation.
Also, we present performance measurements, we benchmark and quantitatively
demonstrate the dependence of the visualization speed on the data size and the
network bandwidth, and we identify the singularities and draw conclusions on
Chromium's sort-first rendering architecture. The most original part of this
work is the combined use of Open Inventor and Chromium.


title:
Augernome & XtremWeb: Monte Carlos computation on a global computing
  platform

abstract:
  In this paper, we present XtremWeb, a Global Computing platform used to
generate monte carlos showers in Auger, an HEP experiment to study the highest
energy cosmic rays at Mallargue-Mendoza, Argentina.
  XtremWeb main goal, as a Global Computing platform, is to compute distributed
applications using idle time of widely interconnected machines. It is
especially dedicated to -but not limited to- multi-parameters applications such
as monte carlos computations; its security mechanisms ensuring not only hosts
integrity but also results certification and its fault tolerant features,
encouraged us to test it and, finally, to deploy it as to support our CPU needs
to simulate showers.
  We first introduce Auger computing needs and how Global Computing could help.
We then detail XtremWeb architecture and goals. The fourth and last part
presents the profits we have gained to choose this platform. We conclude on
what could be done next.


title: Sound search in a denotational semantics for first order logic

abstract:
  In this paper we adapt the definitions and results from Apt and Vermeulen on
`First order logic as a constraint programming language' (in: Proceedings of
LPAR2001, Baaz and Voronkov (eds.), Springer LNAI 2514) to include important
ideas about search and choice into the system. We give motivating examples.
Then we set up denotational semantics for first order logic as follows: the
semantic universe includes states that consist of two components: a
substitution, which can be seen as the computed answer; and a constraint
satisfaction problem, which can be seen as the residue of the original problem,
yet to be handled by constraint programming. The interaction between these
components is regulated by an operator called: infer. In this paper we regard
infer as an operator on sets of states to enable us to analyze ideas about
search among states and choice between states.
  The precise adaptations of definitions and results are able to deal with the
examples and we show that, given several reasonable conditions, the new
definitions ensure soundness of the system with respect to the standard
interpretation of first order logic. In this way the `reasonable conditions'
can be read as conditions for sound search.
  We indicate briefly how to investigate efficiency of search in future
research.


title: Web Access to Cultural Heritage for the Disabled

abstract:
  Physical disabled access is something that most cultural institutions such as
museums consider very seriously. Indeed, there are normally legal requirements
to do so. However, online disabled access is still a relatively novel and
developing field. Many cultural organizations have not yet considered the
issues in depth and web developers are not necessarily experts either. The
interface for websites is normally tested with major browsers, but not with
specialist software like text to audio converters for the blind or against the
relevant accessibility and validation standards. We consider the current state
of the art in this area, especially with respect to aspects of particular
importance to the access of cultural heritage.


title: A logic for reasoning about upper probabilities

abstract:
  We present a propositional logic %which can be used to reason about the
uncertainty of events, where the uncertainty is modeled by a set of probability
measures assigning an interval of probability to each event. We give a sound
and complete axiomatization for the logic, and show that the satisfiability
problem is NP-complete, no harder than satisfiability for propositional logic.


title: Modeling Belief in Dynamic Systems, Part I: Foundations

abstract:
  Belief change is a fundamental problem in AI: Agents constantly have to
update their beliefs to accommodate new observations. In recent years, there
has been much work on axiomatic characterizations of belief change. We claim
that a better understanding of belief change can be gained from examining
appropriate semantic models. In this paper we propose a general framework in
which to model belief change. We begin by defining belief in terms of knowledge
and plausibility: an agent believes p if he knows that p is more plausible than
its negation. We then consider some properties defining the interaction between
knowledge and plausibility, and show how these properties affect the properties
of belief. In particular, we show that by assuming two of the most natural
properties, belief becomes a KD45 operator. Finally, we add time to the
picture. This gives us a framework in which we can talk about knowledge,
plausibility (and hence belief), and time, which extends the framework of
Halpern and Fagin for modeling knowledge in multi-agent systems. We then
examine the problem of ``minimal change''. This notion can be captured by using
prior plausibilities, an analogue to prior probabilities, which can be updated
by ``conditioning''. We show by example that conditioning on a plausibility
measure can capture many scenarios of interest. In a companion paper, we show
how the two best-studied scenarios of belief change, belief revisionand belief
update, fit into our framework.


title: Modeling Belief in Dynamic Systems, Part II: Revisions and Update

abstract:
  The study of belief change has been an active area in philosophy and AI. In
recent years two special cases of belief change, belief revision and belief
update, have been studied in detail. In a companion paper, we introduce a new
framework to model belief change. This framework combines temporal and
epistemic modalities with a notion of plausibility, allowing us to examine the
change of beliefs over time. In this paper, we show how belief revision and
belief update can be captured in our framework. This allows us to compare the
assumptions made by each method, and to better understand the principles
underlying them. In particular, it shows that Katsuno and Mendelzon's notion of
belief update depends on several strong assumptions that may limit its
applicability in artificial intelligence. Finally, our analysis allow us to
identify a notion of minimal change that underlies a broad range of belief
change operations including revision and update.


title: Camera Calibration: a USU Implementation

abstract:
  The task of camera calibration is to estimate the intrinsic and extrinsic
parameters of a camera model. Though there are some restricted techniques to
infer the 3-D information about the scene from uncalibrated cameras, effective
camera calibration procedures will open up the possibility of using a wide
range of existing algorithms for 3-D reconstruction and recognition.
  The applications of camera calibration include vision-based metrology, robust
visual platooning and visual docking of mobile robots where the depth
information is important.


title: Search and Navigation in Relational Databases

abstract:
  We present a new application for keyword search within relational databases,
which uses a novel algorithm to solve the join discovery problem by finding
Memex-like trails through the graph of foreign key dependencies. It differs
from previous efforts in the algorithms used, in the presentation mechanism and
in the use of primary-key only database queries at query-time to maintain a
fast response for users. We present examples using the DBLP data set.


title:
Two- versus three-dimensional connectivity testing of first-order
  queries to semi-algebraic sets

abstract:
  This paper addresses the question whether one can determine the connectivity
of a semi-algebraic set in three dimensions by testing the connectivity of a
finite number of two-dimensional ``samples'' of the set, where these samples
are defined by first-order queries. The question is answered negatively for two
classes of first-order queries: cartesian-product-free, and positive one-pass.


title: Quantifying and Visualizing Attribute Interactions

abstract:
  Interactions are patterns between several attributes in data that cannot be
inferred from any subset of these attributes. While mutual information is a
well-established approach to evaluating the interactions between two
attributes, we surveyed its generalizations as to quantify interactions between
several attributes. We have chosen McGill's interaction information, which has
been independently rediscovered a number of times under various names in
various disciplines, because of its many intuitively appealing properties. We
apply interaction information to visually present the most important
interactions of the data. Visualization of interactions has provided insight
into the structure of data on a number of domains, identifying redundant
attributes and opportunities for constructing new features, discovering
unexpected regularities in data, and have helped during construction of
predictive models; we illustrate the methods on numerous examples. A machine
learning method that disregards interactions may get caught in two traps:
myopia is caused by learning algorithms assuming independence in spite of
interactions, whereas fragmentation arises from assuming an interaction in
spite of independence.


title:
A Family of Simplified Geometric Distortion Models for Camera
  Calibration

abstract:
  The commonly used radial distortion model for camera calibration is in fact
an assumption or a restriction. In practice, camera distortion could happen in
a general geometrical manner that is not limited to the radial sense. This
paper proposes a simplified geometrical distortion modeling method by using two
different radial distortion functions in the two image axes. A family of
simplified geometric distortion models is proposed, which are either simple
polynomials or the rational functions of polynomials. Analytical geometric
undistortion is possible using two of the distortion functions discussed in
this paper and their performance can be improved by applying a piecewise
fitting idea. Our experimental results show that the geometrical distortion
models always perform better than their radial distortion counterparts.
Furthermore, the proposed geometric modeling method is more appropriate for
cameras whose distortion is not perfectly radially symmetric around the center
of distortion.


title: DPG: A Cache-Efficient Accelerator for Sorting and for Join Operators

abstract:
  We present a new algorithm for fast record retrieval,
distribute-probe-gather, or DPG. DPG has important applications both in sorting
and in joins. Current main memory sorting algorithms split their work into
three phases: extraction of key-pointer pairs; sorting of the key-pointer
pairs; and copying of the original records into the destination array according
the sorted key-pointer pairs. The copying in the last phase dominates today's
sorting time. Hence, the use of DPG in the third phase provides an accelerator
for existing sorting algorithms.
  DPG also provides two new join methods for foreign key joins: DPG-move join
and DPG-sort join. The resulting join methods with DPG are faster because DPG
join is cache-efficient and at the same time DPG join avoids the need for
sorting or for hashing. The ideas presented for foreign key join can also be
extended to faster record pair retrieval for spatial and temporal databases.


title: Disabled Access for Museum Websites

abstract:
  Physical disabled access is something that most museums consider very
seriously. Indeed, there are normally legal requirements to do so. However,
online disabled access is still a relatively novel field. Most museums have not
yet considered the issues in depth. The Human-Computer Interface for their
websites is normally tested with major browsers, but not with specialist
browsers or against the relevant accessibility and validation standards. We
consider the current state of the art in this area and mention an accessibility
survey of some museum websites.


title: Higher-Dimensional Packing with Order Constraints

abstract:
  We present a first exact study on higher-dimensional packing problems with
order constraints. Problems of this type occur naturally in applications such
as logistics or computer architecture and can be interpreted as
higher-dimensional generalizations of scheduling problems. Using
graph-theoretic structures to describe feasible solutions, we develop a novel
exact branch-and-bound algorithm. This extends previous work by Fekete and
Schepers; a key tool is a new order-theoretic characterization of feasible
extensions of a partial order to a given complementarity graph that is
tailor-made for use in a branch-and-bound environment. The usefulness of our
approach is validated by computational results.


title: On Applying Or-Parallelism and Tabling to Logic Programs

abstract:
  The past years have seen widening efforts at increasing Prolog's
declarativeness and expressiveness. Tabling has proved to be a viable technique
to efficiently overcome SLD's susceptibility to infinite loops and redundant
subcomputations. Our research demonstrates that implicit or-parallelism is a
natural fit for logic programs with tabling. To substantiate this belief, we
have designed and implemented an or-parallel tabling engine -- OPTYap -- and we
used a shared-memory parallel machine to evaluate its performance. To the best
of our knowledge, OPTYap is the first implementation of a parallel tabling
engine for logic programming systems. OPTYap builds on Yap's efficient
sequential Prolog engine. Its execution model is based on the SLG-WAM for
tabling, and on the environment copying for or-parallelism.
  Preliminary results indicate that the mechanisms proposed to parallelize
search in the context of SLD resolution can indeed be effectively and naturally
generalized to parallelize tabled computations, and that the resulting systems
can achieve good performance on shared-memory parallel machines. More
importantly, it emphasizes our belief that through applying or-parallelism and
tabling to logic programs the range of applications for Logic Programming can
be increased.


title: A Grid Based Architecture for High-Performance NLP

abstract:
  We describe the design and early implementation of an extensible,
component-based software architecture for natural language engineering
applications which interfaces with high performance distributed computing
services. The architecture leverages existing linguistic resource description
and discovery mechanisms based on metadata descriptions, combining these in a
compatible fashion with other software definition abstractions. Within this
architecture, application design is highly flexible, allowing disparate
components to be combined to suit the overall application functionality, and
formally described independently of processing concerns. An application
specification language provides abstraction from the programming environment
and allows ease of interface with high performance computational grids via a
broker.


title:
The Generalized Riemann or Henstock Integral Underpinning Multivariate
  Data Analysis: Application to Faint Structure Finding in Price Processes

abstract:
  Practical data analysis involves many implicit or explicit assumptions about
the good behavior of the data, and excludes consideration of various
potentially pathological or limit cases. In this work, we present a new general
theory of data, and of data processing, to bypass some of these assumptions.
The new framework presented is focused on integration, and has direct
applicability to expectation, distance, correlation, and aggregation. In a case
study, we seek to reveal faint structure in financial data. Our new foundation
for data encoding and handling offers increased justification for our
conclusions.


title: On the probabilistic approach to the random satisfiability problem

abstract:
  In this note I will review some of the recent results that have been obtained
in the probabilistic approach to the random satisfiability problem. At the
present moment the results are only heuristic. In the case of the random
3-satisfiability problem a phase transition from the satisfiable to the
unsatisfiable phase is found at $\alpha=4.267$. There are other values of
$\alpha$ that separates different regimes and they will be described in
details. In this context the properties of the survey decimation algorithm will
also be discussed.


title: Short Cycles Connectivity

abstract:
  Short cycles connectivity is a generalization of ordinary connectivity.
Instead by a path (sequence of edges), two vertices have to be connected by a
sequence of short cycles, in which two adjacent cycles have at least one common
vertex. If all adjacent cycles in the sequence share at least one edge, we talk
about edge short cycles connectivity.
  It is shown that the short cycles connectivity is an equivalence relation on
the set of vertices, while the edge short cycles connectivity components
determine an equivalence relation on the set of edges. Efficient algorithms for
determining equivalence classes are presented.
  Short cycles connectivity can be extended to directed graphs (cyclic and
transitive connectivity). For further generalization we can also consider
connectivity by small cliques or other families of graphs.


title:
Constant-Depth Frege Systems with Counting Axioms Polynomially Simulate
  Nullstellensatz Refutations

abstract:
  We show that constant-depth Frege systems with counting axioms modulo $m$
polynomially simulate Nullstellensatz refutations modulo $m$. Central to this
is a new definition of reducibility from formulas to systems of polynomials
with the property that, for most previously studied translations of formulas to
systems of polynomials, a formula reduces to its translation. When combined
with a previous result of the authors, this establishes the first size
separation between Nullstellensatz and polynomial calculus refutations. We also
obtain new, small refutations for certain CNFs by constant-depth Frege systems
with counting axioms.


title:
A Robust and Computational Characterisation of Peer-to-Peer Database
  Systems

abstract:
  In this paper we give a robust logical and computational characterisation of
peer-to-peer database systems. We first define a pre- cise model-theoretic
semantics of a peer-to-peer system, which allows for local inconsistency
handling. We then characterise the general computa- tional properties for the
problem of answering queries to such a peer-to- peer system. Finally, we devise
tight complexity bounds and distributed procedures for the problem of answering
queries in few relevant special cases.


title: On the expressive power of semijoin queries

abstract:
  The semijoin algebra is the variant of the relational algebra obtained by
replacing the join operator by the semijoin operator. We provide an
Ehrenfeucht-Fraiss\'{e} game, characterizing the discerning power of the
semijoin algebra. This game gives a method for showing that queries are not
expressible in the semijoin algebra.


title: Rethinking OpenPGP PKI and OpenPGP Public Keyserver

abstract:
  OpenPGP, an IETF Proposed Standard based on PGP application, has its own
Public Key Infrastructure (PKI) architecture which is different from the one
based on X.509, another standard from ITU. This paper describes the OpenPGP
PKI; the historical perspective as well as its current use. The current OpenPGP
PKI issues include the capability of a PGP keyserver and its performance. PGP
keyservers have been developed and operated by volunteers since the 1990s. The
keyservers distribute, merge, and expire the OpenPGP public keys. Major
keyserver managers from several countries have built the globally distributed
network of PGP keyservers. However, the current PGP Public Keyserver (pksd) has
some limitations. It does not support fully the OpenPGP format so that it is
neither expandable nor flexible, without any cluster technology. Finally we
introduce the project on the next generation OpenPGP public keyserver called
the OpenPKSD, lead by Hironobu Suzuki, one of the authors, and funded by
Japanese Information-technology Promotion Agency(IPA).


title: Collaborative Creation of Digital Content in Indian Languages

abstract:
  The world is passing through a major revolution called the information
revolution, in which information and knowledge is becoming available to people
in unprecedented amounts wherever and whenever they need it. Those societies
which fail to take advantage of the new technology will be left behind, just
like in the industrial revolution.
  The information revolution is based on two major technologies: computers and
communication. These technologies have to be delivered in a COST EFFECTIVE
manner, and in LANGUAGES accessible to people.
  One way to deliver them in cost effective manner is to make suitable
technology choices, and to allow people to access through shared resources.
This could be done throuch street corner shops (for computer usage, e-mail
etc.), schools, community centres and local library centres.


title: Information Revolution

abstract:
  The world is passing through a major revolution called the information
revolution, in which information and knowledge is becoming available to people
in unprecedented amounts wherever and whenever they need it. Those societies
which fail to take advantage of the new technology will be left behind, just
like in the industrial revolution.
  The information revolution is based on two major technologies: computers and
communication. These technologies have to be delivered in a COST EFFECTIVE
manner, and in LANGUAGES accessible to people.
  One way to deliver them in cost effective manner is to make suitable
technology choices (discussed later), and to allow people to access through
shared resources. This could be done throuch street corner shops (for computer
usage, e-mail etc.), schools, community centers and local library centres.


title: Anusaaraka: Overcoming the Language Barrier in India

abstract:
  The anusaaraka system makes text in one Indian language accessible in another
Indian language. In the anusaaraka approach, the load is so divided between man
and computer that the language load is taken by the machine, and the
interpretation of the text is left to the man. The machine presents an image of
the source text in a language close to the target language.In the image, some
constructions of the source language (which do not have equivalents) spill over
to the output. Some special notation is also devised. The user after some
training learns to read and understand the output. Because the Indian languages
are close, the learning time of the output language is short, and is expected
to be around 2 weeks.
  The output can also be post-edited by a trained user to make it grammatically
correct in the target language. Style can also be changed, if necessary. Thus,
in this scenario, it can function as a human assisted translation system.
  Currently, anusaarakas are being built from Telugu, Kannada, Marathi, Bengali
and Punjabi to Hindi. They can be built for all Indian languages in the near
future. Everybody must pitch in to build such systems connecting all Indian
languages, using the free software model.


title: Language Access: An Information Based Approach

abstract:
  The anusaaraka system (a kind of machine translation system) makes text in
one Indian language accessible through another Indian language. The machine
presents an image of the source text in a language close to the target
language. In the image, some constructions of the source language (which do not
have equivalents in the target language) spill over to the output. Some special
notation is also devised.
  Anusaarakas have been built from five pairs of languages: Telugu,Kannada,
Marathi, Bengali and Punjabi to Hindi. They are available for use through Email
servers.
  Anusaarkas follows the principle of substitutibility and reversibility of
strings produced. This implies preservation of information while going from a
source language to a target language.
  For narrow subject areas, specialized modules can be built by putting subject
domain knowledge into the system, which produce good quality grammatical
output. However, it should be remembered, that such modules will work only in
narrow areas, and will sometimes go wrong. In such a situation, anusaaraka
output will still remain useful.


title: LERIL : Collaborative Effort for Creating Lexical Resources

abstract:
  The paper reports on efforts taken to create lexical resources pertaining to
Indian languages, using the collaborative model. The lexical resources being
developed are: (1) Transfer lexicon and grammar from English to several Indian
languages. (2) Dependencey tree bank of annotated corpora for several Indian
languages. The dependency trees are based on the Paninian model. (3) Bilingual
dictionary of 'core meanings'.


title:
A Bernstein-Bezier Sufficient Condition for Invertibility of Polynomial
  Mapping Functions

abstract:
  We propose a sufficient condition for invertibility of a polynomial mapping
function defined on a cube or simplex. This condition is applicable to finite
element analysis using curved meshes. The sufficient condition is based on an
analysis of the Bernstein-B\'ezier form of the columns of the derivative.


title:
Extending Dublin Core Metadata to Support the Description and Discovery
  of Language Resources

abstract:
  As language data and associated technologies proliferate and as the language
resources community expands, it is becoming increasingly difficult to locate
and reuse existing resources. Are there any lexical resources for such-and-such
a language? What tool works with transcripts in this particular format? What is
a good format to use for linguistic data of this type? Questions like these
dominate many mailing lists, since web search engines are an unreliable way to
find language resources. This paper reports on a new digital infrastructure for
discovering language resources being developed by the Open Language Archives
Community (OLAC). At the core of OLAC is its metadata format, which is designed
to facilitate description and discovery of all kinds of language resources,
including data, tools, or advice. The paper describes OLAC metadata, its
relationship to Dublin Core metadata, and its dissemination using the metadata
harvesting protocol of the Open Archives Initiative.


title: On the complexity of curve fitting algorithms

abstract:
  We study a popular algorithm for fitting polynomial curves to scattered data
based on the least squares with gradient weights. We show that sometimes this
algorithm admits a substantial reduction of complexity, and, furthermore, find
precise conditions under which this is possible. It turns out that this is,
indeed, possible when one fits circles but not ellipses or hyperbolas.


title: Relational Grid Monitoring Architecture (R-GMA)

abstract:
  We describe R-GMA (Relational Grid Monitoring Architecture) which has been
developed within the European DataGrid Project as a Grid Information and
Monitoring System. Is is based on the GMA from GGF, which is a simple
Consumer-Producer model. The special strength of this implementation comes from
the power of the relational model. We offer a global view of the information as
if each Virtual Organisation had one large relational database. We provide a
number of different Producer types with different characteristics; for example
some support streaming of information. We also provide combined
Consumer/Producers, which are able to combine information and republish it. At
the heart of the system is the mediator, which for any query is able to find
and connect to the best Producers for the job. We have developed components to
allow a measure of inter-working between MDS and R-GMA. We have used it both
for information about the grid (primarily to find out about what services are
available at any one time) and for application monitoring. R-GMA has been
deployed in various testbeds; we describe some preliminary results and
experiences of this deployment.


title:
Controlled hierarchical filtering: Model of neocortical sensory
  processing

abstract:
  A model of sensory information processing is presented. The model assumes
that learning of internal (hidden) generative models, which can predict the
future and evaluate the precision of that prediction, is of central importance
for information extraction. Furthermore, the model makes a bridge to
goal-oriented systems and builds upon the structural similarity between the
architecture of a robust controller and that of the hippocampal entorhinal
loop. This generative control architecture is mapped to the neocortex and to
the hippocampal entorhinal loop. Implicit memory phenomena; priming and
prototype learning are emerging features of the model. Mathematical theorems
ensure stability and attractive learning properties of the architecture.
Connections to reinforcement learning are also established: both the control
network, and the network with a hidden model converge to (near) optimal policy
under suitable conditions. Falsifying predictions, including the role of the
feedback connections between neocortical areas are made.


title: Improvements to time bracketed authentication

abstract:
  We describe a collection of techniques whereby audiovisual or other
recordings of significant events can be made in a way that hinders
falsification, pre-dating, or post-dating by interested parties, even by the
makers and operators of the recording equipment. A central feature of these
techniques is the interplay between private information, which by its nature is
untrustworthy and susceptible to suppression or manipulation by interested
parties, and public information, which is too widely known to be manipulated by
anyone. While authenticated recordings may be infeasible to falsify, they can
be abused in other ways, such as being used for blackmail or harassment; but
susceptibility to these abuses can be reduced by encryption and secret sharing.


title: A Comparison of Secret Sharing Schemes Based on Latin Squares and RSA

abstract:
  In recent years there has been a great deal of work done on secret sharing
scehemes. Secret Sharing Schemes allow for the division of keys so that an
authorised set of users may access information. In this paper we wish to
present a critical comparison of two of these schemes based on Latin Squares,
[Cooper et., al.] and RSA [Shoup]. These two protocols will be examined in
terms of their positive and negative aspects of their secuirty.


title: Finding Traitors in Secure Networks Using Byzantine Agreements

abstract:
  Secure networks rely upon players to maintain security and reliability.
However not every player can be assumed to have total loyalty and one must use
methods to uncover traitors in such networks. We use the original concept of
the Byzantine Generals Problem by Lamport, and the more formal Byzantine
Agreement describe by Linial, to nd traitors in secure networks. By applying
general fault-tolerance methods to develop a more formal design of secure
networks we are able to uncover traitors amongst a group of players. We also
propose methods to integrate this system with insecure channels. This new
resiliency can be applied to broadcast and peer-to-peer secure communication
systems where agents may be traitors or become unreliable due to faults.


title:
On Decidability of Expressive Description Logics with Composition of
  Roles in Number Restrictions

abstract:
  Description Logics are knowledge representation formalisms which have been
used in a wide range of application domains. Owing to their appealing
expressiveness, we consider in this paper extensions of the well-known concept
language ALC allowing for number restrictions on complex role expressions.
These have been first introduced by Baader and Sattler as ALCN(M) languages,
with the adoption of role constructors M subset-of {o,-,And,Or}. In particular,
they showed in 1999 that, although ALCN(o) is decidable, the addition of other
operators may easily lead to undecidability: in fact, ALCN(o,And) and
ALCN(o,-,Or) were proved undecidable.
  In this work, we further investigate the computational properties of the ALCN
family, aiming at narrowing the decidability gap left open by Baader and
Sattler's results. In particular, we will show that ALCN(o) extended with
inverse roles both in number and in value restrictions becomes undecidable,
whereas it can be safely extended with qualified number restrictions without
losing decidability.


title:
Learning in Multiagent Systems: An Introduction from a Game-Theoretic
  Perspective

abstract:
  We introduce the topic of learning in multiagent systems. We first provide a
quick introduction to the field of game theory, focusing on the equilibrium
concepts of iterated dominance, and Nash equilibrium. We show some of the most
relevant findings in the theory of learning in games, including theorems on
fictitious play, replicator dynamics, and evolutionary stable strategies. The
CLRI theory and n-level learning agents are introduced as attempts to apply
some of these findings to the problem of engineering multiagent systems with
learning agents. Finally, we summarize some of the remaining challenges in the
field of learning in multiagent systems.


title: Artificial Neural Networks for Beginners

abstract:
  The scope of this teaching package is to make a brief induction to Artificial
Neural Networks (ANNs) for people who have no previous knowledge of them. We
first make a brief introduction to models of networks, for then describing in
general terms ANNs. As an application, we explain the backpropagation
algorithm, since it is widely used and many other algorithms are derived from
it. The user should know algebra and the handling of functions and vectors.
Differential calculus is recommendable, but not necessary. The contents of this
package should be understood by people with high school education. It would be
useful for people who are just curious about what are ANNs, or for people who
want to become familiar with them, so when they study them more fully, they
will already have clear notions of ANNs. Also, people who only want to apply
the backpropagation algorithm without a detailed and formal explanation of it
will find this material useful. This work should not be seen as "Nets for
dummies", but of course it is not a treatise. Much of the formality is skipped
for the sake of simplicity. Detailed explanations and demonstrations can be
found in the referred readings. The included exercises complement the
understanding of the theory. The on-line resources are highly recommended for
extending this brief induction.


title:
Evaluation of text data mining for database curation: lessons learned
  from the KDD Challenge Cup

abstract:
  MOTIVATION: The biological literature is a major repository of knowledge.
Many biological databases draw much of their content from a careful curation of
this literature. However, as the volume of literature increases, the burden of
curation increases. Text mining may provide useful tools to assist in the
curation process. To date, the lack of standards has made it impossible to
determine whether text mining techniques are sufficiently mature to be useful.
  RESULTS: We report on a Challenge Evaluation task that we created for the
Knowledge Discovery and Data Mining (KDD) Challenge Cup. We provided a training
corpus of 862 articles consisting of journal articles curated in FlyBase, along
with the associated lists of genes and gene products, as well as the relevant
data fields from FlyBase. For the test, we provided a corpus of 213 new
(`blind') articles; the 18 participating groups provided systems that flagged
articles for curation, based on whether the article contained experimental
evidence for gene expression products. We report on the the evaluation results
and describe the techniques used by the top performing groups.
  CONTACT: asy@mitre.org
  KEYWORDS: text mining, evaluation, curation, genomics, data management


title: Coherent Keyphrase Extraction via Web Mining

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. A limitation of previous keyphrase
extraction algorithms is that the selected keyphrases are occasionally
incoherent. That is, the majority of the output keyphrases may fit together
well, but there may be a minority that appear to be outliers, with no clear
semantic relation to the majority or to each other. This paper presents
enhancements to the Kea keyphrase extraction algorithm that are designed to
increase the coherence of the extracted keyphrases. The approach is to use the
degree of statistical association among candidate keyphrases as evidence that
they may be semantically related. The statistical association is measured using
web mining. Experiments demonstrate that the enhancements improve the quality
of the extracted keyphrases. Furthermore, the enhancements are not
domain-specific: the algorithm generalizes well when it is trained on one
domain (computer science documents) and tested on another (physics documents).


title: Fingerprint based bio-starter and bio-access

abstract:
  In the paper will be presented a safety and security system based on
fingerprint technology. The results suggest a new scenario where the new cars
can use a fingerprint sensor integrated in car handle to allow access and in
the dashboard as starter button.


title: IS (Iris Security)

abstract:
  In the paper will be presented a safety system based on iridology. The
results suggest a new scenario where the security problem in supervised and
unsupervised areas can be treat with the present system and the iris image
recognition.


title: The Rich-Club Phenomenon In The Internet Topology

abstract:
  We show that the Internet topology at the Autonomous System (AS) level has a
rich--club phenomenon. The rich nodes, which are a small number of nodes with
large numbers of links, are very well connected to each other. The rich--club
is a core tier that we measured using the rich--club connectivity and the
node--node link distribution. We obtained this core tier without any heuristic
assumption between the ASes. The rich--club phenomenon is a simple qualitative
way to differentiate between power law topologies and provides a criterion for
new network models. To show this, we compared the measured rich--club of the AS
graph with networks obtained using the Barab\'asi--Albert (BA) scale--free
network model, the Fitness BA model and the Inet--3.0 model.


title: Distributed and Parallel Net Imaging

abstract:
  A very complex vision system is developed to detect luminosity variations
connected with the discovery of new planets in the Universe. The traditional
imaging system can not manage a so large load. A private net is implemented to
perform an automatic vision and decision architecture. It lets to carry out an
on-line discrimination of interesting events by using two levels of triggers.
This system can even manage many Tbytes of data per day. The architecture
avails itself of a distributed parallel network system based on a maximum of
256 standard workstations with Microsoft Window as OS.


title: Image Analysis in Astronomy for very large vision machine

abstract:
  It is developed a very complex system (hardware/software) to detect
luminosity variations connected with the discovery of new planets outside the
Solar System. Traditional imaging approaches are very demanding in terms of
computing time; then, the implementation of an automatic vision and decision
software architecture is presented. It allows to perform an on-line
discrimination of interesting events by using two levels of triggers. A
fundamental challenge was to work with very large CCD camera (even 16k*16k
pixels) in line with very large telescopes. Then, the architecture can use a
distributed parallel network system based on a maximum of 256 standard
workstations.


title:
A new approach to relevancy in Internet searching - the "Vox Populi
  Algorithm"

abstract:
  In this paper we will derive a new algorithm for Internet searching. The main
idea of this algorithm is to extend the existing algorithms by a component,
which reflects the interests of the users more than existing methods. The "Vox
Populi Algorithm" (VPA) creates a feedback from the users to the content of the
search index. The information derived from the users query analysis is used to
modify the existing crawling algorithms. The VPA controls the distribution of
the resources of the crawler. Finally, we also discuss methods of suppressing
unwanted content (spam).


title: Open source software and peer review

abstract:
  We compare the open source model of software development to peer review in
academia.


title:
Static Data Structure for Discrete Advance Bandwidth Reservations on the
  Internet

abstract:
  In this paper we present a discrete data structure for reservations of
limited resources. A reservation is defined as a tuple consisting of the time
interval of when the resource should be reserved, $I_R$, and the amount of the
resource that is reserved, $B_R$, formally $R=\{I_R,B_R\}$.
  The data structure is similar to a segment tree. The maximum spanning
interval of the data structure is fixed and defined in advance. The granularity
and thereby the size of the intervals of the leaves is also defined in advance.
The data structure is built only once. Neither nodes nor leaves are ever
inserted, deleted or moved. Hence, the running time of the operations does not
depend on the number of reservations previously made. The running time does not
depend on the size of the interval of the reservation either. Let $n$ be the
number of leaves in the data structure. In the worst case, the number of
touched (i.e. traversed) nodes is in any operation $O(\log n)$, hence the
running time of any operation is also $O(\log n)$.


title:
Centralized reward system gives rise to fast and efficient work sharing
  for intelligent Internet agents lacking direct communication

abstract:
  WWW has a scale-free structure where novel information is often difficult to
locate. Moreover, Intelligent agents easily get trapped in this structure. Here
a novel method is put forth, which turns these traps into information
repositories, supplies: We populated an Internet environment with intelligent
news foragers. Foraging has its associated cost whereas foragers are rewarded
if they detect not yet discovered novel information. The intelligent news
foragers crawl by using the estimated long-term cumulated reward, and also have
a finite sized memory: the list of most promising supplies. Foragers form an
artificial life community: the most successful ones are allowed to multiply,
while unsuccessful ones die out. The specific property of this community is
that there is no direct communication amongst foragers but the centralized
rewarding system. Still, fast division of work is achieved.


title: Note on Needle in a Haystack

abstract:
  Introduced below is a quantum database method, not only for retrieval but
also for creation. It uses a particular structure of true's and false's in a
state vector of n qubits, permitting up to 2**2**n words, vastly more than for
classical bits. Several copies are produced so that later they can be
destructively observed and a word determined with high probability. Grover's
algorithm is proposed below to read out, nondestructively the unknown contents
of a given stored state vector using only one state vector.


title: EqRank: A Self-Consistent Equivalence Relation on Graph Vertexes

abstract:
  A new method of hierarchical clustering of graph vertexes is suggested. In
the method, the graph partition is determined with an equivalence relation
satisfying a recursive definition stating that vertexes are equivalent if the
vertexes they point to (or vertexes pointing to them) are equivalent. Iterative
application of the partitioning yields a hierarchical clustering of graph
vertexes. The method is applied to the citation graph of hep-th. The outcome is
a two-level classification scheme for the subject field presented in hep-th,
and indexing of the papers from hep-th in this scheme. A number of tests show
that the classification obtained is adequate.


title: Media Affordances of a Mobile Push-To-Talk Communication Service

abstract:
  This paper presents an exploratory study of college-age students using
two-way, push-to-talk cellular radios. We describe the observed and reported
use of cellular radio by the participants, the activities and purposes for
which they adopted it, and their responses. We then examine these empirical
results using mediated communication theory. Cellular radios have a unique
combination of affordances relative to other media used by this age group,
including instant messaging (IM) and mobile phones; the results of our analysis
do suggest explanations for some observed phenomena but also highlight the
counter-intuitive nature of other phenomena. For example, although the radios
have many important dissimilarities with IM from the viewpoint of mediated
communication theory, the observed use patterns resembled those of IM to a
surprising degree.


title: El informe NERA analizado

abstract:
  This is a review of the article "Government Preferences for Promoting
Open-Source Software: A Solution in Search of A Problem" by David Evans and
Bernard J. Reddy. This report was paid for by Microsoft and put together at its
request. Now Microsoft is using it as part of their lobbying campaign in Europe
against governments' promotion of Open Source Software. As expected, this
article is strongly biased and most of the conclusions are based upon false
hypotheses and evidence.


title: Model Checking Linear Logic Specifications

abstract:
  The overall goal of this paper is to investigate the theoretical foundations
of algorithmic verification techniques for first order linear logic
specifications. The fragment of linear logic we consider in this paper is based
on the linear logic programming language called LO enriched with universally
quantified goal formulas. Although LO was originally introduced as a
theoretical foundation for extensions of logic programming languages, it can
also be viewed as a very general language to specify a wide range of
infinite-state concurrent systems.
  Our approach is based on the relation between backward reachability and
provability highlighted in our previous work on propositional LO programs.
Following this line of research, we define here a general framework for the
bottom-up evaluation of first order linear logic specifications. The evaluation
procedure is based on an effective fixpoint operator working on a symbolic
representation of infinite collections of first order linear logic formulas.
The theory of well quasi-orderings can be used to provide sufficient conditions
for the termination of the evaluation of non trivial fragments of first order
linear logic.


title: The Structure of Information

abstract:
  A formal model of the structure of information is presented in five axioms
which define identity, containment, and joins of infons. Joins are shown to be
commutative, associative, provide inverses of infons, and, potentially, have
many identity elements, two of which are multiplicative and additive. Those two
types of join are distributive. The other identity elements are for operators
on entwined states. Multiplicative joins correspond to adding or removing new
bits to a system while additive joins correspond to a change of state. The
order or size of an infon is defined. This groundwork is intended to be used to
model continuous and discreet information structures through time, especially
in closed systems.


title:
Indexing Schemes for Similarity Search In Datasets of Short Protein
  Fragments

abstract:
  We propose a family of very efficient hierarchical indexing schemes for
ungapped, score matrix-based similarity search in large datasets of short (4-12
amino acid) protein fragments. This type of similarity search has importance in
both providing a building block to more complex algorithms and for possible use
in direct biological investigations where datasets are of the order of 60
million objects. Our scheme is based on the internal geometry of the amino acid
alphabet and performs exceptionally well, for example outputting 100 nearest
neighbours to any possible fragment of length 10 after scanning on average less
than one per cent of the entire dataset.


title:
The KR-Benes Network: A Control-Optimal Rearrangeable Permutation
  Network

abstract:
  The Benes network has been used as a rearrangeable network for over 40 years,
yet the uniform $N(2 \log N-1)$ control complexity of the $N \times N$ Benes is
not optimal for many permutations. In this paper, we present a novel $O(\log
N)$ depth rearrangeable network called KR-Benes that is {\it
permutation-specific control-optimal}. The KR-Benes routes {\it every}
permutation with the minimal control complexity {\it specific} to that
permutation and its worst-case complexity for arbitrary permutations is bounded
by the Benes; thus it replaces the Benes when considering control
complexity/latency. We design the KR-Benes by first constructing a restricted
$2 \log K +2$ depth rearrangeable network called $K$-Benes for routing
$K$-bounded permutations with control $2N \log K$, $0 \leq K \leq N/4$. We then
show that the $N \times N$ Benes network itself (with one additional stage)
contains every $K$-Benes network as a subgraph and use this property to
construct the KR-Benes network. With regard to the control-optimality of the
KR-Benes, we show that any optimal network for rearrangeably routing
$K$-bounded permutations must have depth $2 \log K + 2$, and therefore the
$K$-Benes (and hence the KR-Benes) is optimal.


title:
ROC Curves Within the Framework of Neural Network Assembly Memory Model:
  Some Analytic Results

abstract:
  On the basis of convolutional (Hamming) version of recent Neural Network
Assembly Memory Model (NNAMM) for intact two-layer autoassociative Hopfield
network optimal receiver operating characteristics (ROCs) have been derived
analytically. A method of taking into account explicitly a priori probabilities
of alternative hypotheses on the structure of information initiating memory
trace retrieval and modified ROCs (mROCs, a posteriori probabilities of correct
recall vs. false alarm probability) are introduced. The comparison of empirical
and calculated ROCs (or mROCs) demonstrates that they coincide quantitatively
and in this way intensities of cues used in appropriate experiments may be
estimated. It has been found that basic ROC properties which are one of
experimental findings underpinning dual-process models of recognition memory
can be explained within our one-factor NNAMM.


title:
Digital Version of Green`s Theorem and its Application to The Coverage
  Problem in Formal Verification

abstract:
  We present a novel scheme to the coverage problem, introducing a quantitative
way to estimate the interaction between a block and its enviroment.This is
achieved by setting a discrete version of Green`s theorem, specially adapted
for Model Checking based verification of integrated circuits.This method is
best suited for the coverage problem since it enables one to quantify the
incompleteness or, on the other hand, the redundancy of a set of rules,
describing the model under verification.Moreover this can be done continuously
throughout the verification process, thus enabling the user to pinpoint the
stages at which incompleteness/redundancy occurs. Although the method is
presented locally on a small hardware example, we additionally show its
possibility to provide precise coverage estimation also for large scale
systems. We compare this method to others by checking it on the same
test-cases.


title:
What Is Working Memory and Mental Imagery? A Robot that Learns to
  Perform Mental Computations

abstract:
  This paper goes back to Turing (1936) and treats his machine as a cognitive
model (W,D,B), where W is an "external world" represented by memory device (the
tape divided into squares), and (D,B) is a simple robot that consists of the
sensory-motor devices, D, and the brain, B. The robot's sensory-motor devices
(the "eye", the "hand", and the "organ of speech") allow the robot to simulate
the work of any Turing machine. The robot simulates the internal states of a
Turing machine by "talking to itself." At the stage of training, the teacher
forces the robot (by acting directly on its motor centers) to perform several
examples of an algorithm with different input data presented on tape. Two
effects are achieved: 1) The robot learns to perform the shown algorithm with
any input data using the tape. 2) The robot learns to perform the algorithm
"mentally" using an "imaginary tape." The model illustrates the simplest
concept of a universal learning neurocomputer, demonstrates universality of
associative learning as the mechanism of programming, and provides a
simplified, but nontrivial neurobiologically plausible explanation of the
phenomena of working memory and mental imagery. The model is implemented as a
user-friendly program for Windows called EROBOT. The program is available at
www.brain0.com/software.html.


title: Homomorphic public-key cryptosystems over groups and rings

abstract:
  We propose a new homomorphic public-key cryptosystem over arbitrary
nonidentity finite group based on the difficulty of the membership problem for
groups of integer matrices. Besides, a homomorphic cryptosystem is designed for
the first time over finite commutative rings.


title: Indexing of Tables Referencing Complex Structures

abstract:
  We introduce indexing of tables referencing complex structures such as
digraphs and spatial objects, appearing in genetics and other data intensive
analysis. The indexing is achieved by extracting dimension schemas from the
referenced structures. The schemas and their dimensionality are determined by
proper coloring algorithms and the duality between all such schemas and all
such possible proper colorings is established. This duality, in turn, provides
us with an extensive library of solutions when addressing indexing questions.
It is illustrated how to use the schemas, in connection with additional
relational database technologies, to optimize queries conditioned on the
structural information being referenced. Comparisons using bitmap indexing in
the Oracle 9.2i database, on the one hand, and multidimensional clustering in
DB2 8.1.2, on the other hand, are used to illustrate the applicability of the
indexing to different technology settings. Finally, we illustrate how the
indexing can be used to extract low dimensional schemas from a binary interval
tree in order to resolve efficiently interval and stabbing queries.


title: Exploration of RNA Editing and Design of Robust Genetic Algorithms

abstract:
  This paper presents our computational methodology using Genetic Algorithms
(GA) for exploring the nature of RNA editing. These models are constructed
using several genetic editing characteristics that are gleaned from the RNA
editing system as observed in several organisms. We have expanded the
traditional Genetic Algorithm with artificial editing mechanisms as proposed by
(Rocha, 1997). The incorporation of editing mechanisms provides a means for
artificial agents with genetic descriptions to gain greater phenotypic
plasticity, which may be environmentally regulated. Our first implementations
of these ideas have shed some light into the evolutionary implications of RNA
editing. Based on these understandings, we demonstrate how to select proper RNA
editors for designing more robust GAs, and the results will show promising
applications to real-world problems. We expect that the framework proposed will
both facilitate determining the evolutionary role of RNA editing in biology,
and advance the current state of research in Genetic Algorithms.


title:
Semi-metric Behavior in Document Networks and its Application to
  Recommendation Systems

abstract:
  Recommendation systems for different Document Networks (DN) such as the World
Wide Web (WWW) and Digital Libraries, often use distance functions extracted
from relationships among documents and keywords. For instance, documents in the
WWW are related via a hyperlink network, while documents in bibliographic
databases are related by citation and collaboration networks. Furthermore,
documents are related to keyterms. The distance functions computed from these
relations establish associative networks among items of the DN, referred to as
Distance Graphs, which allow recommendation systems to identify relevant
associations for individual users. However, modern recommendation systems need
to integrate associative data from multiple sources such as different
databases, web sites, and even other users. Thus, we are presented with a
problem of combining evidence (about associations between items) from different
sources characterized by distance functions. In this paper we describe our work
on (1) inferring relevant associations from, as well as characterizing,
semi-metric distance graphs and (2) combining evidence from different distance
graphs in a recommendation system. Regarding (1), we present the idea of
semi-metric distance graphs, and introduce ratios to measure semi-metric
behavior. We compute these ratios for several DN such as digital libraries and
web sites and show that they are useful to identify implicit associations.
Regarding (2), we describe an algorithm to combine evidence from distance
graphs that uses Evidence Sets, a set structure based on Interval Valued Fuzzy
Sets and Dempster-Shafer Theory of Evidence. This algorithm has been developed
for a recommendation system named TalkMine.

categories: cs.IR cond-mat.dis-nn cond-mat.stat-mech cs.AI cs.DL cs.HC cs.MA


title: Optimal Covering Tours with Turn Costs

abstract:
  We give the first algorithmic study of a class of ``covering tour'' problems
related to the geometric Traveling Salesman Problem: Find a polygonal tour for
a cutter so that it sweeps out a specified region (``pocket''), in order to
minimize a cost that depends mainly on the number of em turns. These problems
arise naturally in manufacturing applications of computational geometry to
automatic tool path generation and automatic inspection systems, as well as arc
routing (``postman'') problems with turn penalties. We prove the
NP-completeness of minimum-turn milling and give efficient approximation
algorithms for several natural versions of the problem, including a
polynomial-time approximation scheme based on a novel adaptation of the
m-guillotine method.