title:
Cyborg Systems as Platforms for Computer-Vision Algorithm-Development
  for Astrobiology

abstract:
  Employing the allegorical imagery from the film "The Matrix", we motivate and
discuss our `Cyborg Astrobiologist' research program. In this research program,
we are using a wearable computer and video camcorder in order to test and train
a computer-vision system to be a field-geologist and field-astrobiologist.


title: About Unitary Rating Score Constructing

abstract:
  It is offered to pool test points of different subjects and different aspects
of the same subject together in order to get the unitary rating score, by the
way of nonlinear transformation of indicator points in accordance with Zipf's
distribution. It is proposed to use the well-studied distribution of
Intellectuality Quotient IQ as the reference distribution for latent variable
"progress in studies".


title:
Cluster computing performances using virtual processors and mathematical
  software

abstract:
  In this paper I describe some results on the use of virtual processors
technology for parallelize some SPMD computational programs in a cluster
environment. The tested technology is the INTEL Hyper Threading on real
processors, and the programs are MATLAB 6.5 Release 13 scripts for floating
points computation. By the use of this technology, I tested that a cluster can
run with benefit a number of concurrent processes double the amount of physical
processors. The conclusions of the work concern on the utility and limits of
the used approach. The main result is that using virtual processors is a good
technique for improving parallel programs not only for memory-based
computations, but in the case of massive disk-storage operations too.


title: Design of a Community-based Translation Center

abstract:
  Interfaces that support multi-lingual content can reach a broader community.
We wish to extend the reach of CITIDEL, a digital library for computing
education materials, to support multiple languages. By doing so, we hope that
it will increase the number of users, and in turn the number of resources. This
paper discusses three approaches to translation (automated translation,
developer-based, and community-based), and a brief evaluation of these
approaches. It proposes a design for an online community translation center
where volunteers help translate interface components and educational materials
available in CITIDEL.


title:
Algorithm xxx: Modified Bessel functions of imaginary order and positive
  argument

abstract:
  Fortran 77 programs for the computation of modified Bessel functions of
purely imaginary order are presented. The codes compute the functions
$K_{ia}(x)$, $L_{ia}(x)$ and their derivatives for real $a$ and positive $x$;
these functions are independent solutions of the differential equation $x^2 w''
+x w' +(a^2 -x^2)w=0$. The code also computes exponentially scaled functions.
The range of computation is $(x,a)\in (0,1500]\times [-1500,1500]$ when scaled
functions are considered and it is larger than $(0,500]\times [-400,400]$ for
standard IEEE double precision arithmetic. The relative accuracy is better than
$10^{-13}$ in the range $(0,200]\times [-200,200]$ and close to $10^{-12}$ in
$(0,1500]\times [-1500,1500]$.


title: Unifying Computing and Cognition: The SP Theory and its Applications

abstract:
  This book develops the conjecture that all kinds of information processing in
computers and in brains may usefully be understood as "information compression
by multiple alignment, unification and search". This "SP theory", which has
been under development since 1987, provides a unified view of such things as
the workings of a universal Turing machine, the nature of 'knowledge', the
interpretation and production of natural language, pattern recognition and
best-match information retrieval, several kinds of probabilistic reasoning,
planning and problem solving, unsupervised learning, and a range of concepts in
mathematics and logic. The theory also provides a basis for the design of an
'SP' computer with several potential advantages compared with traditional
digital computers.


title: On the Cost of Participating in a Peer-to-Peer Network

abstract:
  In this paper, we model the cost incurred by each peer participating in a
peer-to-peer network. Such a cost model allows to gauge potential disincentives
for peers to collaborate, and provides a measure of the ``total cost'' of a
network, which is a possible benchmark to distinguish between proposals. We
characterize the cost imposed on a node as a function of the experienced load
and the node connectivity, and show how our model applies to a few proposed
routing geometries for distributed hash tables (DHTs). We further outline a
number of open questions this research has raised.


title:
Heuristic average-case analysis of the backtrack resolution of random
  3-Satisfiability instances

abstract:
  An analysis of the average-case complexity of solving random 3-Satisfiability
(SAT) instances with backtrack algorithms is presented. We first interpret
previous rigorous works in a unifying framework based on the statistical
physics notions of dynamical trajectories, phase diagram and growth process. It
is argued that, under the action of the Davis--Putnam--Loveland--Logemann
(DPLL) algorithm, 3-SAT instances are turned into 2+p-SAT instances whose
characteristic parameters (ratio alpha of clauses per variable, fraction p of
3-clauses) can be followed during the operation, and define resolution
trajectories. Depending on the location of trajectories in the phase diagram of
the 2+p-SAT model, easy (polynomial) or hard (exponential) resolutions are
generated. Three regimes are identified, depending on the ratio alpha of the
3-SAT instance to be solved. Lower sat phase: for small ratios, DPLL almost
surely finds a solution in a time growing linearly with the number N of
variables. Upper sat phase: for intermediate ratios, instances are almost
surely satisfiable but finding a solution requires exponential time (2 ^ (N
omega) with omega>0) with high probability. Unsat phase: for large ratios,
there is almost always no solution and proofs of refutation are exponential. An
analysis of the growth of the search tree in both upper sat and unsat regimes
is presented, and allows us to estimate omega as a function of alpha. This
analysis is based on an exact relationship between the average size of the
search tree and the powers of the evolution operator encoding the elementary
steps of the search heuristic.


title: Algebraic Elimination of epsilon-transitions

abstract:
  We present here algebraic formulas associating a k-automaton to a
k-epsilon-automaton. The existence depends on the definition of the star of
matrices and of elements in the semiring k. For this reason, we present the
theorem which allows the transformation of k-epsilon-automata into k-automata.
The two automata have the same behaviour.


title: Verification of Process Rewrite Systems in normal form

abstract:
  We consider the problem of model--checking for Process Rewrite Systems (PRSs)
in normal form. In a PRS in normal form every rewrite rule either only deals
with procedure calls and procedure termination, possibly with value return,
(this kind of rules allows to capture Pushdown Processes), or only deals with
dynamic activation of processes and synchronization (this kind of rules allows
to capture Petri Nets). The model-checking problem for PRSs and action-based
linear temporal logic (ALTL) is undecidable. However, decidability of
model--checking for PRSs and some interesting fragment of ALTL remains an open
question. In this paper we state decidability results concerning generalized
acceptance properties about infinite derivations (infinite term rewritings) in
PRSs in normal form. As a consequence, we obtain decidability of the
model-checking (restricted to infinite runs) for PRSs in normal form and a
meaningful fragment of ALTL.


title: Nested Intervals with Farey Fractions

abstract:
  Relational Databases are universally conceived as an advance over their
predecessors Network and Hierarchical models. Superior in every querying
respect, they turned out to be surprisingly incomplete when modeling transitive
dependencies. Almost every couple of months a question how to model a tree in
the database surfaces at comp.database.theory newsgroup. This article completes
a series of articles exploring Nested Intervals Model. Previous articles
introduced tree encoding with Binary Rational Numbers. However, binary encoding
grows exponentially, both in breadth and in depth. In this article, we'll
leverage Farey fractions in order to overcome this problem. We'll also
demonstrate that our implementation scales to a tree with 1M nodes.


title: Query Answering in Peer-to-Peer Data Exchange Systems

abstract:
  The problem of answering queries posed to a peer who is a member of a
peer-to-peer data exchange system is studied. The answers have to be consistent
wrt to both the local semantic constraints and the data exchange constraints
with other peers; and must also respect certain trust relationships between
peers. A semantics for peer consistent answers under exchange constraints and
trust relationships is introduced and some techniques for obtaining those
answers are presented.


title: Generalized Strong Preservation by Abstract Interpretation

abstract:
  Standard abstract model checking relies on abstract Kripke structures which
approximate concrete models by gluing together indistinguishable states, namely
by a partition of the concrete state space. Strong preservation for a
specification language L encodes the equivalence of concrete and abstract model
checking of formulas in L. We show how abstract interpretation can be used to
design abstract models that are more general than abstract Kripke structures.
Accordingly, strong preservation is generalized to abstract
interpretation-based models and precisely related to the concept of
completeness in abstract interpretation. The problem of minimally refining an
abstract model in order to make it strongly preserving for some language L can
be formulated as a minimal domain refinement in abstract interpretation in
order to get completeness w.r.t. the logical/temporal operators of L. It turns
out that this refined strongly preserving abstract model always exists and can
be characterized as a greatest fixed point. As a consequence, some well-known
behavioural equivalences, like bisimulation, simulation and stuttering, and
their corresponding partition refinement algorithms can be elegantly
characterized in abstract interpretation as completeness properties and
refinements.


title: Better Foreground Segmentation Through Graph Cuts

abstract:
  For many tracking and surveillance applications, background subtraction
provides an effective means of segmenting objects moving in front of a static
background. Researchers have traditionally used combinations of morphological
operations to remove the noise inherent in the background-subtracted result.
Such techniques can effectively isolate foreground objects, but tend to lose
fidelity around the borders of the segmentation, especially for noisy input.
This paper explores the use of a minimum graph cut algorithm to segment the
foreground, resulting in qualitatively and quantitiatively cleaner
segmentations. Experiments on both artificial and real data show that the
graph-based method reduces the error around segmented foreground objects. A
MATLAB code implementation is available at
http://www.cs.smith.edu/~nhowe/research/code/#fgseg


title:
Factor Temporal Prognosis of Tick-Borne Encephalitis Foci Functioning on
  the South of Russian Far East

abstract:
  A method of temporal factor prognosis of TE (tick-borne encephalitis)
infection has been developed. The high precision of the prognosis results for a
number of geographical regions of Primorsky Krai has been achieved. The method
can be applied not only to epidemiological research but also to others.


title: Using biased coins as oracles

abstract:
  While it is well known that a Turing machine equipped with the ability to
flip a fair coin cannot compute more that a standard Turing machine, we show
that this is not true for a biased coin. Indeed, any oracle set $X$ may be
coded as a probability $p_{X}$ such that if a Turing machine is given a coin
which lands heads with probability $p_{X}$ it can compute any function
recursive in $X$ with arbitrarily high probability. We also show how the
assumption of a non-recursive bias can be weakened by using a sequence of
increasingly accurate recursive biases or by choosing the bias at random from a
distribution with a non-recursive mean. We conclude by briefly mentioning some
implications regarding the physical realisability of such methods.


title:
Presynaptic modulation as fast synaptic switching: state-dependent
  modulation of task performance

abstract:
  Neuromodulatory receptors in presynaptic position have the ability to
suppress synaptic transmission for seconds to minutes when fully engaged. This
effectively alters the synaptic strength of a connection. Much work on
neuromodulation has rested on the assumption that these effects are uniform at
every neuron. However, there is considerable evidence to suggest that
presynaptic regulation may be in effect synapse-specific. This would define a
second "weight modulation" matrix, which reflects presynaptic receptor efficacy
at a given site. Here we explore functional consequences of this hypothesis. By
analyzing and comparing the weight matrices of networks trained on different
aspects of a task, we identify the potential for a low complexity "modulation
matrix", which allows to switch between differently trained subtasks while
retaining general performance characteristics for the task. This means that a
given network can adapt itself to different task demands by regulating its
release of neuromodulators. Specifically, we suggest that (a) a network can
provide optimized responses for related classification tasks without the need
to train entirely separate networks and (b) a network can blend a "memory mode"
which aims at reproducing memorized patterns and a "novelty mode" which aims to
facilitate classification of new patterns. We relate this work to the known
effects of neuromodulators on brain-state dependent processing.


title:
A correct, precise and efficient integration of set-sharing, freeness
  and linearity for the analysis of finite and rational tree languages

abstract:
  It is well-known that freeness and linearity information positively interact
with aliasing information, allowing both the precision and the efficiency of
the sharing analysis of logic programs to be improved. In this paper we present
a novel combination of set-sharing with freeness and linearity information,
which is characterized by an improved abstract unification operator. We provide
a new abstraction function and prove the correctness of the analysis for both
the finite tree and the rational tree cases. Moreover, we show that the same
notion of redundant information as identified in (Bagnara et al. 2002;
Zaffanella et al. 2002) also applies to this abstract domain combination: this
allows for the implementation of an abstract unification operator running in
polynomial time and achieving the same precision on all the considered
observable properties.


title: Enhanced sharing analysis techniques: a comprehensive evaluation

abstract:
  Sharing, an abstract domain developed by D. Jacobs and A. Langen for the
analysis of logic programs, derives useful aliasing information. It is
well-known that a commonly used core of techniques, such as the integration of
Sharing with freeness and linearity information, can significantly improve the
precision of the analysis. However, a number of other proposals for refined
domain combinations have been circulating for years. One feature that is common
to these proposals is that they do not seem to have undergone a thorough
experimental evaluation even with respect to the expected precision gains. In
this paper we experimentally evaluate: helping Sharing with the definitely
ground variables found using Pos, the domain of positive Boolean formulas; the
incorporation of explicit structural information; a full implementation of the
reduced product of Sharing and Pos; the issue of reordering the bindings in the
computation of the abstract mgu; an original proposal for the addition of a new
mode recording the set of variables that are deemed to be ground or free; a
refined way of using linearity to improve the analysis; the recovery of hidden
information in the combination of Sharing with freeness information. Finally,
we discuss the issue of whether tracking compoundness allows the computation of
more sharing information.


title: Surface Triangulation -- The Metric Approach

abstract:
  We embark in a program of studying the problem of better approximating
surfaces by triangulations(triangular meshes) by considering the approximating
triangulations as finite metric spaces and the target smooth surface as their
Haussdorff-Gromov limit. This allows us to define in a more natural way the
relevant elements, constants and invariants s.a. principal directions and
principal values, Gaussian and Mean curvature, etc. By a "natural way" we mean
an intrinsic, discrete, metric definitions as opposed to approximating or
paraphrasing the differentiable notions. In this way we hope to circumvent
computational errors and, indeed, conceptual ones, that are often inherent to
the classical, "numerical" approach. In this first study we consider the
problem of determining the Gaussian curvature of a polyhedral surface, by using
the {\em embedding curvature} in the sense of Wald (and Menger). We present two
modalities of employing these definitions for the computation of Gaussian
curvature.


title: A system for reflection in C++

abstract:
  Object-oriented programming languages such as Java and Objective C have
become popular for implementing agent-based and other object-based simulations
since objects in those languages can {\em reflect} (i.e. make runtime queries
of an object's structure). This allows, for example, a fairly trivial {\em
serialisation} routine (conversion of an object into a binary representation
that can be stored or passed over a network) to be written. However C++ does
not offer this ability, as type information is thrown away at compile time. Yet
C++ is often a preferred development environment, whether for performance
reasons or for its expressive features such as operator overloading.
  In this paper, we present the {\em Classdesc} system which brings many of the
benefits of object reflection to C++.


title: Running C++ models undet the Swarm environment

abstract:
  Objective-C is still the language of choice if users want to run their
simulation efficiently under the Swarm environment since the Swarm environment
itself was written in Objective-C. The language is a fast, object-oriented and
easy to learn. However, the language is less well known than, less expressive
than, and lacks support for many important features of C++ (eg. OpenMP for high
performance computing application). In this paper, we present a methodology and
software tools that we have developed for auto generating an Objective-C object
template (and all the necessary interfacing functions) from a given C++ model,
utilising the Classdesc's object description technology, so that the C++ model
can both be run and accessed under the Objective-C and C++ environments. We
also present a methodology for modifying an existing Swarm application to make
part of the model (eg. the heatbug's step method) run under the C++
environment.


title: EcoLab: Agent Based Modeling for C++ programmers

abstract:
  \EcoLab{} is an agent based modeling system for C++ programmers, strongly
influenced by the design of Swarm. This paper is just a brief outline of
\EcoLab's features, more details can be found in other published articles,
documentation and source code from the \EcoLab{} website.


title: ClassdescMP: Easy MPI programming in C++

abstract:
  ClassdescMP is a distributed memory parallel programming system for use with
C++ and MPI. It uses the Classdesc reflection system to ease the task of
building complicated messages to be sent between processes. It doesn't hide the
underlying MPI API, so it is an augmentation of MPI capabilities. Users can
still call standard MPI function calls if needed for performance reasons.


title: Automated Resolution of Noisy Bibliographic References

abstract:
  We describe a system used by the NASA Astrophysics Data System to identify
bibliographic references obtained from scanned article pages by OCR methods
with records in a bibliographic database. We analyze the process generating the
noisy references and conclude that the three-step procedure of correcting the
OCR results, parsing the corrected string and matching it against the database
provides unsatisfactory results. Instead, we propose a method that allows a
controlled merging of correction, parsing and matching, inspired by dependency
grammars. We also report on the effectiveness of various heuristics that we
have employed to improve recall.


title:
Dynamic Linking of Smart Digital Objects Based on User Navigation
  Patterns

abstract:
  We discuss a methodology to dynamically generate links among digital objects
by means of an unsupervised learning mechanism which analyzes user link
traversal patterns. We performed an experiment with a test bed of 150 complex
data objects, referred to as buckets. Each bucket manages its own content,
provides methods to interact with users and individually maintains a set of
links to other buckets. We demonstrate that buckets were capable of dynamically
adjusting their links to other buckets according to user link selections,
thereby generating a meaningful network of bucket relations. Our results
indicate such adaptive networks of linked buckets approximate the collective
link preferences of a community of user


title: Pseudorandom number generation by $p$-adic ergodic transformations

abstract:
  The paper study counter-dependent pseudorandom generators; the latter are
generators such that their state transition function (and output function) is
being modified dynamically while working: For such a generator the recurrence
sequence of states satisfies a congruence $x_{i+1}\equiv f_i(x_i)\pmod{2^n}$,
while its output sequence is of the form $z_{i}=F_i(u_i)$. The paper introduces
techniques and constructions that enable one to compose generators that output
uniformly distributed sequences of a maximum period length and with high linear
and 2-adic spans. The corresponding stream chipher is provably strong against a
known plaintext attack (up to a plausible conjecture). Both state transition
function and output function could be key-dependent, so the only information
available to a cryptanalyst is that these functions belong to some
(exponentially large) class. These functions are compositions of standard
machine instructions (such as addition, multiplication, bitwise logical
operations, etc.) The compositions should satisfy rather loose conditions; so
the corresponding generators are flexible enough and could be easily
implemented as computer programs.


title: Mobile Re-Finding of Web Information Using a Voice Interface

abstract:
  Mobile access to information is a considerable problem for many users,
especially to information found on the Web. In this paper, we explore how a
voice-controlled service, accessible by telephone, could support mobile users'
needs for refinding specific information previously found on the Web. We
outline challenges in creating such a service and describe architectural and
user interfaces issues discovered in an exploratory prototype we built called
WebContext.
  We also present the results of a study, motivated by our experience with
WebContext, to explore what people remember about information that they are
trying to refind and how they express information refinding requests in a
collaborative conversation. As part of the study, we examine how
end-usercreated Web page annotations can be used to help support mobile
information re-finding. We observed the use of URLs, page titles, and
descriptions of page contents to help identify waypoints in the search process.
Furthermore, we observed that the annotations were utilized extensively,
indicating that explicitly added context by the user can play an important role
in re-finding.


title: Deciding Disjunctive Linear Arithmetic with SAT

abstract:
  Disjunctive Linear Arithmetic (DLA) is a major decidable theory that is
supported by almost all existing theorem provers. The theory consists of
Boolean combinations of predicates of the form $\Sigma_{j=1}^{n}a_j\cdot x_j
\le b$, where the coefficients $a_j$, the bound $b$ and the variables $x_1 >...
x_n$ are of type Real ($\mathbb{R}$). We show a reduction to propositional
logic from disjunctive linear arithmetic based on Fourier-Motzkin elimination.
While the complexity of this procedure is not better than competing techniques,
it has practical advantages in solving verification problems. It also promotes
the option of deciding a combination of theories by reducing them to this
logic. Results from experiments show that this method has a strong advantage
over existing techniques when there are many disjunctions in the formula.


title: Semantic Optimization of Preference Queries

abstract:
  The notion of preference is becoming more and more ubiquitous in present-day
information systems. Preferences are primarily used to filter and personalize
the information reaching the users of such systems. In database systems,
preferences are usually captured as preference relations that are used to build
preference queries. In our approach, preference queries are relational algebra
or SQL queries that contain occurrences of the winnow operator ("find the most
preferred tuples in a given relation").
  We present here a number of semantic optimization techniques applicable to
preference queries. The techniques make use of integrity constraints, and make
it possible to remove redundant occurrences of the winnow operator and to apply
a more efficient algorithm for the computation of winnow. We also study the
propagation of integrity constraints in the result of the winnow. We have
identified necessary and sufficient conditions for the applicability of our
techniques, and formulated those conditions as constraint satisfiability
problems.


title: Baptista-type chaotic cryptosystems: Problems and countermeasures

abstract:
  In 1998, M. S. Baptista proposed a chaotic cryptosystem, which has attracted
much attention from the chaotic cryptography community: some of its
modifications and also attacks have been reported in recent years. In [Phys.
Lett. A 307 (2003) 22], we suggested a method to enhance the security of
Baptista-type cryptosystem, which can successfully resist all proposed attacks.
However, the enhanced Baptista-type cryptosystem has a nontrivial defect, which
produces errors in the decrypted data with a generally small but nonzero
probability, and the consequent error propagation exists. In this Letter, we
analyze this defect and discuss how to rectify it. In addition, we point out
some newly-found problems existing in all Baptista-type cryptosystems and
consequently propose corresponding countermeasures.


title: Improved randomized selection

abstract:
  We show that several versions of Floyd and Rivest's improved algorithm Select
for finding the $k$th smallest of $n$ elements require at most
$n+\min\{k,n-k\}+O(n^{1/2}\ln^{1/2}n)$ comparisons on average and with high
probability. This rectifies the analysis of Floyd and Rivest, and extends it to
the case of nondistinct elements. Encouraging computational results on large
median-finding problems are reported.


title: MammoGrid: Large-Scale Distributed Mammogram Analysis

abstract:
  Breast cancer as a medical condition and mammograms as images exhibit many
dimensions of variability across the population. Similarly, the way diagnostic
systems are used and maintained by clinicians varies between imaging centres
and breast screening programmes, and so does the appearance of the mammograms
generated. A distributed database that reflects the spread of pathologies
across the population is an invaluable tool for the epidemiologist and the
understanding of the variation in image acquisition protocols is essential to a
radiologist in a screening programme. Exploiting emerging grid technology, the
aim of the MammoGrid [1] project is to develop a Europe-wide database of
mammograms that will be used to investigate a set of important healthcare
applications and to explore the potential of the grid to support effective
co-working between healthcare professionals.


title:
An Integrated Approach for Extraction of Objects from XML and
  Transformation to Heterogeneous Object Oriented Databases

abstract:
  CERN's (European Organization for Nuclear Research) WISDOM project uses XML
for the replication of data between different data repositories in a
heterogeneous operating system environment. For exchanging data from
Web-resident databases, the data needs to be transformed into XML and back to
the database format. Many different approaches are employed to do this
transformation. This paper addresses issues that make this job more efficient
and robust than existing approaches. It incorporates the World Wide Web
Consortium (W3C) XML Schema specification in the database-XML relationship.
Incorporation of the XML Schema exhibits significant improvements in XML
content usage and reduces the limitations of DTD-based database XML services.
Secondly the paper explores the possibility of database independent
transformation of data between XML and different databases. It proposes a
standard XML format that every serialized object should follow. This makes it
possible to use objects of heterogeneous database seamlessly using XML.


title:
A Use-Case Driven Approach in Requirements Engineering : The Mammogrid
  Project

abstract:
  We report on the application of the use-case modeling technique to identify
and specify the user requirements of the MammoGrid project in an incremental
and controlled iterative approach. Modeling has been carried out in close
collaboration with clinicians and radiologists with no prior experience of use
cases. The study reveals the advantages and limitations of applying this
technique to requirements specification in the domains of breast cancer
screening and mammography research, with implications for medical imaging more
generally. In addition, this research has shown a return on investment in
use-case modeling in shorter gaps between phases of the requirements
engineering process. The qualitative result of this analysis leads us to
propose that a use-case modeling approach may result in reducing the cycle of
the requirements engineering process for medical imaging.


title: Resolving Clinicians Queries Across a Grids Infrastructure

abstract:
  The past decade has witnessed order of magnitude increases in computing
power, data storage capacity and network speed, giving birth to applications
which may handle large data volumes of increased complexity, distributed over
the Internet. Grids computing promises to resolve many of the difficulties in
facilitating medical image analysis to allow radiologists to collaborate
without having to co-locate. The EU-funded MammoGrid project aims to
investigate the feasibility of developing a Grid-enabled European database of
mammograms and provide an information infrastructure which federates multiple
mammogram databases. This will enable clinicians to develop new common,
collaborative and co-operative approaches to the analysis of mammographic data.
This paper focuses on one of the key requirements for large-scale distributed
mammogram analysis: resolving queries across a grid-connected federation of
images.


title: Encapsulation for Practical Simplification Procedures

abstract:
  ACL2 was used to prove properties of two simplification procedures. The
procedures differ in complexity but solve the same programming problem that
arises in the context of a resolution/paramodulation theorem proving system.
Term rewriting is at the core of the two procedures, but details of the
rewriting procedure itself are irrelevant. The ACL2 encapsulate construct was
used to assert the existence of the rewriting function and to state some of its
properties. Termination, irreducibility, and soundness properties were
established for each procedure. The availability of the encapsulation mechanism
in ACL2 is considered essential to rapid and efficient verification of this
kind of algorithm.


title: Accurately modeling the Internet topology

abstract:
  Based on measurements of the Internet topology data, we found out that there
are two mechanisms which are necessary for the correct modeling of the Internet
topology at the Autonomous Systems (AS) level: the Interactive Growth of new
nodes and new internal links, and a nonlinear preferential attachment, where
the preference probability is described by a positive-feedback mechanism. Based
on the above mechanisms, we introduce the Positive-Feedback Preference (PFP)
model which accurately reproduces many topological properties of the AS-level
Internet, including: degree distribution, rich-club connectivity, the maximum
degree, shortest path length, short cycles, disassortative mixing and
betweenness centrality. The PFP model is a phenomenological model which
provides a novel insight into the evolutionary dynamics of real complex
networks.


title:
A Knowledge-Theoretic Analysis of Uniform Distributed Coordination and
  Failure Detectors

abstract:
  It is shown that, in a precise sense, if there is no bound on the number of
faulty processes in a system with unreliable but fair communication, Uniform
Distributed Coordination (UDC) can be attained if and only if a system has
perfect failure detectors. This result is generalized to the case where there
is a bound t on the number of faulty processes. It is shown that a certain type
of generalized failure detector is necessary and sufficient for achieving UDC
in a context with at most t faulty processes. Reasoning about processes'
knowledge as to which other processes are faulty plays a key role in the
analysis.


title:
Corollaries on the fixpoint completion: studying the stable semantics by
  means of the Clark completion

abstract:
  The fixpoint completion fix(P) of a normal logic program P is a program
transformation such that the stable models of P are exactly the models of the
Clark completion of fix(P). This is well-known and was studied by Dung and
Kanchanasut (1989). The correspondence, however, goes much further: The
Gelfond-Lifschitz operator of P coincides with the immediate consequence
operator of fix(P), as shown by Wendt (2002), and even carries over to standard
operators used for characterizing the well-founded and the Kripke-Kleene
semantics. We will apply this knowledge to the study of the stable semantics,
and this will allow us to almost effortlessly derive new results concerning
fixed-point and metric-based semantics, and neural-symbolic integration.


title:
Self-Organising Networks for Classification: developing Applications to
  Science Analysis for Astroparticle Physics

abstract:
  Physics analysis in astroparticle experiments requires the capability of
recognizing new phenomena; in order to establish what is new, it is important
to develop tools for automatic classification, able to compare the final result
with data from different detectors. A typical example is the problem of Gamma
Ray Burst detection, classification, and possible association to known sources:
for this task physicists will need in the next years tools to associate data
from optical databases, from satellite experiments (EGRET, GLAST), and from
Cherenkov telescopes (MAGIC, HESS, CANGAROO, VERITAS).


title:
A Preliminary Study for the development of an Early Method for the
  Measurement in Function Points of a Software Product

abstract:
  The Function Points Analysis (FPA) of A.J. Albrecht is a method to determine
the functional size of software products. The International Function Point
Users Group, (IFPUG), establishes the FPA like a standard in the software
functional size measurement. The IFPUG [3] [4] method follows the Albrecht's
method and incorporates in its succesive versions modifications to the rules
and hints with the intention of improving it [7]. The required documentation
level to apply the method is the functional specification which corresponds to
level I in the Rudolph's clasification [8]. This documentation is avalaible
with some difficulty for those companies which are dedicated to develop
software for third parties when they have to prepare the appropiate budget for
this development. Then, we face the need of developing an early method [6] [9]
for measuring the functional size of a software product that we will name to
abbreviate it Early Method or EFPM (Early Function Point Method). The required
documentation to apply the EFPM would be the User Requirements or some
analogous documentations. This is a part of a research work now in process in
Oviedo University. In this article we only show the following, results:
  From the measurements of a set of projects using the IFPUG method v. 4.1 we
obtain the linear correlation coefficients between the total number of Function
Points for each project and the counters of the ILFs number, ILFs+EIFs number
and EIs+EOs+EQs number.
  Using the preliminary results we compute the regression functions. This
results we will allow us to determine the factors to be considered in the
development of EFPM and to estimate the function points.


title: Perspects in astrophysical databases

abstract:
  Astrophysics has become a domain extremely rich of scientific data. Data
mining tools are needed for information extraction from such large datasets.
This asks for an approach to data management emphasizing the efficiency and
simplicity of data access; efficiency is obtained using multidimensional access
methods and simplicity is achieved by properly handling metadata. Moreover,
clustering and classification techniques on large datasets pose additional
requirements in terms of computation and memory scalability and
interpretability of results. In this study we review some possible solutions.


title:
Alchemi: A .NET-based Grid Computing Framework and its Integration into
  Global Grids

abstract:
  Computational grids that couple geographically distributed resources are
becoming the de-facto computing platform for solving large-scale problems in
science, engineering, and commerce. Software to enable grid computing has been
primarily written for Unix-class operating systems, thus severely limiting the
ability to effectively utilize the computing resources of the vast majority of
desktop computers i.e. those running variants of the Microsoft Windows
operating system. Addressing Windows-based grid computing is particularly
important from the software industry's viewpoint where interest in grids is
emerging rapidly. Microsoft's .NET Framework has become near-ubiquitous for
implementing commercial distributed systems for Windows-based platforms,
positioning it as the ideal platform for grid computing in this context. In
this paper we present Alchemi, a .NET-based grid computing framework that
provides the runtime machinery and programming environment required to
construct desktop grids and develop grid applications. It allows flexible
application composition by supporting an object-oriented grid application
programming model in addition to a grid job model. Cross-platform support is
provided via a web services interface and a flexible execution model supports
dedicated and non-dedicated (voluntary) execution by grid nodes.


title: P2P Networks for Content Sharing

abstract:
  Peer-to-peer (P2P) technologies have been widely used for content sharing,
popularly called "file-swapping" networks. This chapter gives a broad overview
of content sharing P2P technologies. It starts with the fundamental concept of
P2P computing followed by the analysis of network topologies used in
peer-to-peer systems. Next, three milestone peer-to-peer technologies: Napster,
Gnutella, and Fasttrack are explored in details, and they are finally concluded
with the comparison table in the last section.


title: The Munich Rent Advisor: A Success for Logic Programming on the Internet

abstract:
  Most cities in Germany regularly publish a booklet called the {\em
Mietspiegel}. It basically contains a verbal description of an expert system.
It allows the calculation of the estimated fair rent for a flat. By hand, one
may need a weekend to do so. With our computerized version, the {\em Munich
Rent Advisor}, the user just fills in a form in a few minutes and the rent is
calculated immediately. We also extended the functionality and applicability of
the {\em Mietspiegel} so that the user need not answer all questions on the
form. The key to computing with partial information using high-level
programming was to use constraint logic programming. We rely on the internet,
and more specifically the World Wide Web, to provide this service to a broad
user group. More than ten thousand people have used our service in the last
three years. This article describes the experiences in implementing and using
the {\em Munich Rent Advisor}. Our results suggests that logic programming with
constraints can be an important ingredient in intelligent internet systems.


title: Geometrical Complexity of Classification Problems

abstract:
  Despite encouraging recent progresses in ensemble approaches, classification
methods seem to have reached a plateau in development. Further advances depend
on a better understanding of geometrical and topological characteristics of
point sets in high-dimensional spaces, the preservation of such characteristics
under feature transformations and sampling processes, and their interaction
with geometrical models used in classifiers. We discuss an attempt to measure
such properties from data sets and relate them to classifier accuracies.


title: A Numerical Example on the Principles of Stochastic Discrimination

abstract:
  Studies on ensemble methods for classification suffer from the difficulty of
modeling the complementary strengths of the components. Kleinberg's theory of
stochastic discrimination (SD) addresses this rigorously via mathematical
notions of enrichment, uniformity, and projectability of an ensemble. We
explain these concepts via a very simple numerical example that captures the
basic principles of the SD theory and method. We focus on a fundamental
symmetry in point set covering that is the key observation leading to the
foundation of the theory. We believe a better understanding of the SD method
will lead to developments of better tools for analyzing other ensemble methods.


title:
Automatically Generating Interfaces for Personalized Interaction with
  Digital Libraries

abstract:
  We present an approach to automatically generate interfaces supporting
personalized interaction with digital libraries; these interfaces augment the
user-DL dialog by empowering the user to (optionally) supply out-of-turn
information during an interaction, flatten or restructure the dialog, and
enquire about dialog options. Interfaces generated using this approach for
CITIDEL are described.


title: A Service-Based Approach for Managing Mammography Data

abstract:
  Grid-based technologies are emerging as a potential open-source
standards-based solution for managing and collabo-rating distributed resources.
In view of these new computing solutions, the Mammogrid project is developing a
service-based and Grid-aware application which manages a Euro-pean-wide
database of mammograms. Medical conditions such as breast cancer, and
mammograms as images, are ex-tremely complex with many dimensions of
variability across the population. An effective solution for the management of
disparate mammogram data sources is a federation of autonomous multi-centre
sites which transcends national boundaries. The Mammogrid solution utilizes the
Grid tech-nologies to integrate geographically distributed data sets. The
Mammogrid application will explore the potential of the Grid to support
effective co-working among radiologists through-out the EU. This paper outlines
the Mammogrid service-based approach in managing a federation of grid-connected
mam-mography databases.


title: Pattern Reification as the Basis for Description-Driven Systems

abstract:
  One of the main factors driving object-oriented software development for
information systems is the requirement for systems to be tolerant to change. To
address this issue in designing systems, this paper proposes a pattern-based,
object-oriented, description-driven system (DDS) architecture as an extension
to the standard UML four-layer meta-model. A DDS architecture is proposed in
which aspects of both static and dynamic systems behavior can be captured via
descriptive models and meta-models. The proposed architecture embodies four
main elements - firstly, the adoption of a multi-layered meta-modeling
architecture and reflective meta-level architecture, secondly the
identification of four data modeling relationships that can be made explicit
such that they can be modified dynamically, thirdly the identification of five
design patterns which have emerged from practice and have proved essential in
providing reusable building blocks for data management, and fourthly the
encoding of the structural properties of the five design patterns by means of
one fundamental pattern, the Graph pattern. A practical example of this
philosophy, the CRISTAL project, is used to demonstrate the use of
description-driven data objects to handle system evolution.


title: A perspective on the Healthgrid initiative

abstract:
  This paper presents a perspective on the Healthgrid initiative which involves
European projects deploying pioneering applications of grid technology in the
health sector. In the last couple of years, several grid projects have been
funded on health related issues at national and European levels. A crucial
issue is to maximize their cross fertilization in the context of an environment
where data of medical interest can be stored and made easily available to the
different actors in healthcare, physicians, healthcare centres and
administrations, and of course the citizens. The Healthgrid initiative,
represented by the Healthgrid association (http://www.healthgrid.org), was
initiated to bring the necessary long term continuity, to reinforce and promote
awareness of the possibilities and advantages linked to the deployment of GRID
technologies in health. Technologies to address the specific requirements for
medical applications are under development. Results from the DataGrid and other
projects are given as examples of early applications.


title:
Redundancy and Robustness of the AS-level Internet topology and its
  models

abstract:
  A comparison between the topological properties of the measured Internet
topology, at the autonomous system level (AS graph), and the equivalent graphs
generated by two different power law topology generators is presented. Only one
of the synthetic generators reproduces the tier connectivity of the AS graph.


title:
Efficient and Scalable Barrier over Quadrics and Myrinet with a New
  NIC-Based Collective Message Passing Protocol

abstract:
  Modern interconnects often have programmable processors in the network
interface that can be utilized to offload communication processing from host
CPU. In this paper, we explore different schemes to support collective
operations at the network interface and propose a new collective protocol. With
barrier as an initial case study, we have demontrated that much of the
communication processing can be greatly simplified with this collective
protocol. Accordingly, %with our proposed collective processing scheme, we have
designed and implemented efficient and scalable NIC-based barrier operations
over two high performance interconnects, Quadrics and Myrinet.
  Our evaluation shows that, over a Quadrics cluster of 8 nodes with ELan3
Network, the NIC-based barrier operation achieves a barrier latency of only
5.60$\mu$s. This result is a 2.48 factor of improvement over the Elanlib
tree-based barrier operation. Over a Myrinet cluster of 8 nodes with LANai-XP
NIC cards, a barrier latency of 14.20$\mu$s over 8 nodes is achieved. This is a
2.64 factor of improvement over the host-based barrier algorithm. Furthermore,
an analytical model developed for the proposed scheme indicates that a
NIC-based barrier operation on a 1024-node cluster can be performed with only
22.13$\mu$s latency over Quadrics and with 38.94$\mu$s latency over Myrinet.
These results indicate the potential for developing high performance
communication subsystems for next generation clusters.


title: The lattice dimension of a graph

abstract:
  We describe a polynomial time algorithm for, given an undirected graph G,
finding the minimum dimension d such that G may be isometrically embedded into
the d-dimensional integer lattice Z^d.


title: Mapping Topics and Topic Bursts in PNAS

abstract:
  Scientific research is highly dynamic. New areas of science continually
evolve;others gain or lose importance, merge or split. Due to the steady
increase in the number of scientific publications it is hard to keep an
overview of the structure and dynamic development of one's own field of
science, much less all scientific domains. However, knowledge of hot topics,
emergent research frontiers, or change of focus in certain areas is a critical
component of resource allocation decisions in research labs, governmental
institutions, and corporations. This paper demonstrates the utilization of
Kleinberg's burst detection algorithm, co-word occurrence analysis, and graph
layout techniques to generate maps that support the identification of major
research topics and trends. The approach was applied to analyze and map the
complete set of papers published in the Proceedings of the National Academy of
Sciences (PNAS) in the years 1982-2001. Six domain experts examined and
commented on the resulting maps in an attempt to reconstruct the evolution of
major research areas covered by PNAS.


title:
Computational complexity and simulation of rare events of Ising spin
  glasses

abstract:
  We discuss the computational complexity of random 2D Ising spin glasses,
which represent an interesting class of constraint satisfaction problems for
black box optimization. Two extremal cases are considered: (1) the +/- J spin
glass, and (2) the Gaussian spin glass. We also study a smooth transition
between these two extremal cases. The computational complexity of all studied
spin glass systems is found to be dominated by rare events of extremely hard
spin glass samples. We show that complexity of all studied spin glass systems
is closely related to Frechet extremal value distribution. In a hybrid
algorithm that combines the hierarchical Bayesian optimization algorithm (hBOA)
with a deterministic bit-flip hill climber, the number of steps performed by
both the global searcher (hBOA) and the local searcher follow Frechet
distributions. Nonetheless, unlike in methods based purely on local search, the
parameters of these distributions confirm good scalability of hBOA with local
search. We further argue that standard performance measures for optimization
algorithms--such as the average number of evaluations until convergence--can be
misleading. Finally, our results indicate that for highly multimodal constraint
satisfaction problems, such as Ising spin glasses, recombination-based search
can provide qualitatively better results than mutation-based search.


title: Parameter-less hierarchical BOA

abstract:
  The parameter-less hierarchical Bayesian optimization algorithm (hBOA)
enables the use of hBOA without the need for tuning parameters for solving each
problem instance. There are three crucial parameters in hBOA: (1) the selection
pressure, (2) the window size for restricted tournaments, and (3) the
population size. Although both the selection pressure and the window size
influence hBOA performance, performance should remain low-order polynomial with
standard choices of these two parameters. However, there is no standard
population size that would work for all problems of interest and the population
size must thus be eliminated in a different way. To eliminate the population
size, the parameter-less hBOA adopts the population-sizing technique of the
parameter-less genetic algorithm. Based on the existing theory, the
parameter-less hBOA should be able to solve nearly decomposable and
hierarchical problems in quadratic or subquadratic number of function
evaluations without the need for setting any parameters whatsoever. A number of
experiments are presented to verify scalability of the parameter-less hBOA.


title: Fitness inheritance in the Bayesian optimization algorithm

abstract:
  This paper describes how fitness inheritance can be used to estimate fitness
for a proportion of newly sampled candidate solutions in the Bayesian
optimization algorithm (BOA). The goal of estimating fitness for some candidate
solutions is to reduce the number of fitness evaluations for problems where
fitness evaluation is expensive. Bayesian networks used in BOA to model
promising solutions and generate the new ones are extended to allow not only
for modeling and sampling candidate solutions, but also for estimating their
fitness. The results indicate that fitness inheritance is a promising concept
in BOA, because population-sizing requirements for building appropriate models
of promising solutions lead to good fitness estimates even if only a small
proportion of candidate solutions is evaluated using the actual fitness
function. This can lead to a reduction of the number of actual fitness
evaluations by a factor of 30 or more.


title: Recycling Computed Answers in Rewrite Systems for Abduction

abstract:
  In rule-based systems, goal-oriented computations correspond naturally to the
possible ways that an observation may be explained. In some applications, we
need to compute explanations for a series of observations with the same domain.
The question whether previously computed answers can be recycled arises. A yes
answer could result in substantial savings of repeated computations. For
systems based on classic logic, the answer is YES. For nonmonotonic systems
however, one tends to believe that the answer should be NO, since recycling is
a form of adding information. In this paper, we show that computed answers can
always be recycled, in a nontrivial way, for the class of rewrite procedures
that we proposed earlier for logic programs with negation. We present some
experimental results on an encoding of the logistics domain.


title: Kolmogorov complexity and symmetric relational structures

abstract:
  We study partitions of Fra\"{\i}ss\'{e} limits of classes of finite
relational structures where the partitions are encoded by infinite binary
sequences which are random in the sense of Kolmogorov, Chaitin and Solomonoff.
It is shown that partition by a random sequence of a Fra\"{\i}ss\'{e} limit
preserves the limit property of the object.


title: Memory As A Monadic Control Construct In Problem-Solving

abstract:
  Recent advances in programming languages study and design have established a
standard way of grounding computational systems representation in category
theory. These formal results led to a better understanding of issues of control
and side-effects in functional and imperative languages. This framework can be
successfully applied to the investigation of the performance of Artificial
Intelligence (AI) inference and cognitive systems. In this paper, we delineate
a categorical formalisation of memory as a control structure driving
performance in inference systems. Abstracting away control mechanisms from
three widely used representations of memory in cognitive systems (scripts,
production rules and clusters) we explain how categorical triples capture the
interaction between learning and problem-solving.


title:
Towards a Model-Based Framework for Integrating Usability and Software
  Engineering Life Cycles

abstract:
  In this position paper we propose a process model that provides a development
infrastructure in which the usability engineering and software engineering life
cycles co-exist in complementary roles. We describe the motivation, hurdles,
rationale, arguments, and implementation plan for the need, specification, and
the usefulness of such a model.


title: The pre-history of quantum computation

abstract:
  The main ideas behind developments in the theory and technology of quantum
computation were formulated in the late 1970s and early 1980s by two physicists
in the West and a mathematician in the former Soviet Union. It is not generally
known in the West that the subject has roots in the Russian technical
literature. The author hopes to present as impartial a synthesis as possible of
the early history of thought on this subject. The role of reversible and
irreversible computational processes is examined briefly as it relates to the
origins of quantum computing and the so-called Information Paradox in physics.


title: Towards a Mathematical Theory of the Delays of the Asynchronous Circuits

abstract:
  The inequations of the delays of the asynchronous circuits are written, by
making use of pseudo-Boolean differential calculus. We consider these efforts
to be a possible starting point in the semi-formalized reconstruction of the
digital electrical engineering (which is a non-formalized theory).


title: On the Inertia of the Asynchronous Circuits

abstract: We present the bounded delays, the absolute inertia and the relative inertia.


title: Defining the Delays of the Asynchronous Circuits

abstract:
  We define the delays of a circuit, as well as the properties of determinism,
order, time invariance, constancy, symmetry and the serial connection.


title: Examples of Models of the Asynchronous Circuits


title: Anonymity and Information Hiding in Multiagent Systems

abstract:
  We provide a framework for reasoning about information-hiding requirements in
multiagent systems and for reasoning about anonymity in particular. Our
framework employs the modal logic of knowledge within the context of the runs
and systems framework, much in the spirit of our earlier work on secrecy
[Halpern and O'Neill 2002]. We give several definitions of anonymity with
respect to agents, actions, and observers in multiagent systems, and we relate
our definitions of anonymity to other definitions of information hiding, such
as secrecy. We also give probabilistic definitions of anonymity that are able
to quantify an observer s uncertainty about the state of the system. Finally,
we relate our definitions of anonymity to other formalizations of anonymity and
information hiding, including definitions of anonymity in the process algebra
CSP and definitions of information hiding using function views.


title: The UPLNC Compiler: Design and Implementation

abstract:
  The implementation of the compiler of the UPLNC language is presented with a
full source code listing.


title:
A General Framework for Bounds for Higher-Dimensional Orthogonal Packing
  Problems

abstract:
  Higher-dimensional orthogonal packing problems have a wide range of practical
applications, including packing, cutting, and scheduling. In the context of a
branch-and-bound framework for solving these packing problems to optimality, it
is of crucial importance to have good and easy bounds for an optimal solution.
Previous efforts have produced a number of special classes of such bounds.
Unfortunately, some of these bounds are somewhat complicated and hard to
generalize. We present a new approach for obtaining classes of lower bounds for
higher-dimensional packing problems; our bounds improve and simplify several
well-known bounds from previous literature. In addition, our approach provides
an easy framework for proving correctness of new bounds.


title: The Freeze-Tag Problem: How to Wake Up a Swarm of Robots

abstract:
  An optimization problem that naturally arises in the study of swarm robotics
is the Freeze-Tag Problem (FTP) of how to awaken a set of ``asleep'' robots, by
having an awakened robot move to their locations. Once a robot is awake, it can
assist in awakening other slumbering robots.The objective is to have all robots
awake as early as possible. While the FTP bears some resemblance to problems
from areas in combinatorial optimization such as routing, broadcasting,
scheduling, and covering, its algorithmic characteristics are surprisingly
different. We consider both scenarios on graphs and in geometric
environments.In graphs, robots sleep at vertices and there is a length function
on the edges. Awake robots travel along edges, with time depending on edge
length. For most scenarios, we consider the offline version of the problem, in
which each awake robot knows the position of all other robots. We prove that
the problem is NP-hard, even for the special case of star graphs. We also
establish hardness of approximation, showing that it is NP-hard to obtain an
approximation factor better than 5/3, even for graphs of bounded degree.These
lower bounds are complemented with several positive algorithmic results,
including: (1) We show that the natural greedy strategy on star graphs has a
tight worst-case performance of 7/3 and give a polynomial-time approximation
scheme (PTAS) for star graphs. (2) We give a simple O(log D)-competitive online
algorithm for graphs with maximum degree D and locally bounded edge weights.
(3) We give a PTAS, running in nearly linear time, for geometrically embedded
instances.


title: Spam filter analysis

abstract:
  Unsolicited bulk email (aka. spam) is a major problem on the Internet. To
counter spam, several techniques, ranging from spam filters to mail protocol
extensions like hashcash, have been proposed. In this paper we investigate the
effectiveness of several spam filtering techniques and technologies. Our
analysis was performed by simulating email traffic under different conditions.
We show that genetic algorithm based spam filters perform best at server level
and naive Bayesian filters are the most appropriate for filtering at user
level.


title:
Parameter-less Optimization with the Extended Compact Genetic Algorithm
  and Iterated Local Search

abstract:
  This paper presents a parameter-less optimization framework that uses the
extended compact genetic algorithm (ECGA) and iterated local search (ILS), but
is not restricted to these algorithms. The presented optimization algorithm
(ILS+ECGA) comes as an extension of the parameter-less genetic algorithm (GA),
where the parameters of a selecto-recombinative GA are eliminated. The approach
that we propose is tested on several well known problems. In the absence of
domain knowledge, it is shown that ILS+ECGA is a robust and easy-to-use
optimization method.


title: Transformation Rules for Locally Stratified Constraint Logic Programs

abstract:
  We propose a set of transformation rules for constraint logic programs with
negation. We assume that every program is locally stratified and, thus, it has
a unique perfect model. We give sufficient conditions which ensure that the
proposed set of transformation rules preserves the perfect model of the
programs. Our rules extend in some respects the rules for logic programs and
constraint logic programs already considered in the literature and, in
particular, they include a rule for unfolding a clause with respect to a
negative literal.


title:
An architecture for massive parallelization of the compact genetic
  algorithm

abstract:
  This paper presents an architecture which is suitable for a massive
parallelization of the compact genetic algorithm. The resulting scheme has
three major advantages. First, it has low synchronization costs. Second, it is
fault tolerant, and third, it is scalable.
  The paper argues that the benefits that can be obtained with the proposed
approach is potentially higher than those obtained with traditional parallel
genetic algorithms. In addition, the ideas suggested in the paper may also be
relevant towards parallelizing more complex probabilistic model building
genetic algorithms.


title:
A philosophical essay on life and its connections with genetic
  algorithms

abstract:
  This paper makes a number of connections between life and various facets of
genetic and evolutionary algorithms research. Specifically, it addresses the
topics of adaptation, multiobjective optimization, decision making, deception,
and search operators, among others. It argues that human life, from birth to
death, is an adaptive or dynamic optimization problem where people are
continuously searching for happiness. More important, the paper speculates that
genetic algorithms can be used as a source of inspiration for helping people
make decisions in their everyday life.


title: Nested Intervals Tree Encoding with Continued Fractions

abstract:
  We introduce a new variation of Tree Encoding with Nested Intervals, find
connections with Materialized Path, and suggest a method for moving parts of
the hierarchy.


title: Continued fractions and RSA with small secret exponent

abstract:
  Extending the classical Legendre's result, we describe all solutions of the
inequality |x - a/b| < c/b^2 in terms of convergents of continued fraction
expansion of x. Namely, we show that a/b = (rp_{m+1} +- sp_m) / (rq_{m+1} +-
sq_m) for some nonnegative integers m,r,s such that rs < 2c.
  As an application of this result, we describe a modification of Verheul and
van Tilborg variant of Wiener's attack on RSA cryptosystem with small secret
exponent.


title: The Complexity of Modified Instances

abstract:
  In this paper we study the complexity of solving a problem when a solution of
a similar instance is known. This problem is relevant whenever instances may
change from time to time, and known solutions may not remain valid after the
change. We consider two scenarios: in the first one, what is known is only a
solution of the problem before the change; in the second case, we assume that
some additional information, found during the search for this solution, is also
known. In the first setting, the techniques from the theory of NP-completeness
suffice to show complexity results. In the second case, negative results can
only be proved using the techniques of compilability, and are often related to
the size of considered changes.


title: On the Security of the Yi-Tan-Siew Chaos-Based Cipher

abstract:
  This paper presents a comprehensive analysis on the security of the
Yi-Tan-Siew chaotic cipher proposed in [IEEE TCAS-I 49(12):1826-1829 (2002)]. A
differential chosen-plaintext attack and a differential chosen-ciphertext
attack are suggested to break the sub-key K, under the assumption that the time
stamp can be altered by the attacker, which is reasonable in such attacks.
Also, some security Problems about the sub-keys $\alpha$ and $\beta$ are
clarified, from both theoretical and experimental points of view. Further
analysis shows that the security of this cipher is independent of the use of
the chaotic tent map, once the sub-key $K$ is removed via the proposed
suggested differential chosen-plaintext attack.


title:
Lexical Base as a Compressed Language Model of the World (on the
  material of the Ukrainian language)

abstract:
  In the article the fact is verified that the list of words selected by formal
statistical methods (frequency and functional genre unrestrictedness) is not a
conglomerate of non-related words. It creates a system of interrelated items
and it can be named "lexical base of language". This selected list of words
covers all the spheres of human activities. To verify this statement the
invariant synoptical scheme common for ideographic dictionaries of different
language was determined.


title:
Digital Signal Transmission with Chaotic Encryption: Design and
  Evaluation of a FPGA Realization

abstract:
  A discrete-time discrete-value pseudo-chaotic encoder/decoder system is
presented. The pseudo-chaotic module is a 3D discrete version of the well-known
Lorenz dynamical system. Scaling and biasing transformations as well as natural
number arithmetics are employed in order to simplify realizations on a small
size Field Programmable Gate Array (FPGA. The encryption ability is improved by
using only the least significant byte of one of the pseudo chaotic state
variables as the key to encrypt the plain text. The key is periodically
perturbed by another chaotic state variable. The statistical properties of the
pseudo chaotic cipher are compared with those of other pseudo-random generators
available in the literature. As an example of applicability of the technique, a
full duplex communication system is designed and constructed using FPGA's as
technological framework.


title: Integrating Defeasible Argumentation and Machine Learning Techniques

abstract:
  The field of machine learning (ML) is concerned with the question of how to
construct algorithms that automatically improve with experience. In recent
years many successful ML applications have been developed, such as datamining
programs, information-filtering systems, etc. Although ML algorithms allow the
detection and extraction of interesting patterns of data for several kinds of
problems, most of these algorithms are based on quantitative reasoning, as they
rely on training data in order to infer so-called target functions.
  In the last years defeasible argumentation has proven to be a sound setting
to formalize common-sense qualitative reasoning. This approach can be combined
with other inference techniques, such as those provided by machine learning
theory.
  In this paper we outline different alternatives for combining defeasible
argumentation and machine learning techniques. We suggest how different aspects
of a generic argument-based framework can be integrated with other ML-based
approaches.


title: A Tribute to Alain Colmerauer

abstract:
  The paper describes the contributions of Alain Colmerauer to the areas of
logic programs (LP) and constraint logic programs (CLP).


title: Light types for polynomial time computation in lambda-calculus

abstract:
  We propose a new type system for lambda-calculus ensuring that well-typed
programs can be executed in polynomial time: Dual light affine logic (DLAL).
  DLAL has a simple type language with a linear and an intuitionistic type
arrow, and one modality. It corresponds to a fragment of Light affine logic
(LAL). We show that contrarily to LAL, DLAL ensures good properties on
lambda-terms: subject reduction is satisfied and a well-typed term admits a
polynomial bound on the reduction by any strategy. We establish that as LAL,
DLAL allows to represent all polytime functions. Finally we give a type
inference procedure for propositional DLAL.


title:
Pseudorandom number generation by p-adic ergodic transformations: an
  addendum

abstract:
  The paper study counter-dependent pseudorandom number generators based on
$m$-variate ($m>1$) ergodic mappings of the space of 2-adic integers $\Z_2$.
The sequence of internal states of these generators is defined by the
recurrence law $\mathbf x_{i+1}= H^B_i(\mathbf x_i)\bmod{2^n}$, whereas their
output sequence is %while its output sequence is of the $\mathbf
z_{i}=F^B_i(\mathbf x_i)\mod 2^n$; here $\mathbf x_j, \mathbf z_j$ are
$m$-dimensional vectors over $\Z_2$. It is shown how the results obtained for a
univariate case could be extended to a multivariate case.


title: A Correlation-Based Distance

abstract:
  In this short technical report, we define on the sample space R^D a distance
between data points which depends on their correlation. We also derive an
expression for the center of mass of a set of points with respect to this
distance.


title: Evolving a Stigmergic Self-Organized Data-Mining

abstract:
  Self-organizing complex systems typically are comprised of a large number of
frequently similar components or events. Through their process, a pattern at
the global-level of a system emerges solely from numerous interactions among
the lower-level components of the system. Moreover, the rules specifying
interactions among the system's components are executed using only local
information, without reference to the global pattern, which, as in many
real-world problems is not easily accessible or possible to be found.
Stigmergy, a kind of indirect communication and learning by the environment
found in social insects is a well know example of self-organization, providing
not only vital clues in order to understand how the components can interact to
produce a complex pattern, as can pinpoint simple biological non-linear rules
and methods to achieve improved artificial intelligent adaptive categorization
systems, critical for Data-Mining. On the present work it is our intention to
show that a new type of Data-Mining can be designed based on Stigmergic
paradigms, taking profit of several natural features of this phenomenon. By
hybridizing bio-inspired Swarm Intelligence with Evolutionary Computation we
seek for an entire distributed, adaptive, collective and cooperative
self-organized Data-Mining. As a real-world, real-time test bed for our
proposal, World-Wide-Web Mining will be used. Having that purpose in mind, Web
usage Data was collected from the Monash University's Web site (Australia),
with over 7 million hits every week. Results are compared to other recent
systems, showing that the system presented is by far promising.


title: Epistemic Foundation of Stable Model Semantics

abstract:
  Stable model semantics has become a very popular approach for the management
of negation in logic programming. This approach relies mainly on the closed
world assumption to complete the available knowledge and its formulation has
its basis in the so-called Gelfond-Lifschitz transformation.
  The primary goal of this work is to present an alternative and
epistemic-based characterization of stable model semantics, to the
Gelfond-Lifschitz transformation. In particular, we show that stable model
semantics can be defined entirely as an extension of the Kripke-Kleene
semantics. Indeed, we show that the closed world assumption can be seen as an
additional source of `falsehood' to be added cumulatively to the Kripke-Kleene
semantics. Our approach is purely algebraic and can abstract from the
particular formalism of choice as it is based on monotone operators (under the
knowledge order) over bilattices only.


title: Genetic Algorithms and Quantum Computation

abstract:
  Recently, researchers have applied genetic algorithms (GAs) to address some
problems in quantum computation. Also, there has been some works in the
designing of genetic algorithms based on quantum theoretical concepts and
techniques. The so called Quantum Evolutionary Programming has two major
sub-areas: Quantum Inspired Genetic Algorithms (QIGAs) and Quantum Genetic
Algorithms (QGAs). The former adopts qubit chromosomes as representations and
employs quantum gates for the search of the best solution. The later tries to
solve a key question in this field: what GAs will look like as an
implementation on quantum hardware? As we shall see, there is not a complete
answer for this question. An important point for QGAs is to build a quantum
algorithm that takes advantage of both the GA and quantum computing parallelism
as well as true randomness provided by quantum computers. In the first part of
this paper we present a survey of the main works in GAs plus quantum computing
including also our works in this area. Henceforth, we review some basic
concepts in quantum computation and GAs and emphasize their inherent
parallelism. Next, we review the application of GAs for learning quantum
operators and circuit design. Then, quantum evolutionary programming is
considered. Finally, we present our current research in this field and some
perspectives.


title:
New Visualization of Surfaces in Parallel Coordinates - Eliminating
  Ambiguity and Some "Over-Plotting"

abstract:
  $\cal{A}$ point $P \in \Real^n$ is represented in Parallel Coordinates by a
polygonal line $\bar{P}$ (see \cite{Insel99a} for a recent survey). Earlier
\cite{inselberg85plane}, a surface $\sigma$ was represented as the {\em
envelope} of the polygonal lines representing it's points. This is ambiguous in
the sense that {\em different} surfaces can provide the {\em same} envelopes.
Here the ambiguity is eliminated by considering the surface $\sigma$ as the
envelope of it's {\em tangent planes} and in turn, representing each of these
planes by $n$-1 points \cite{Insel99a}. This, with some future extension, can
yield a new and unambiguous representation, $\bar{\sigma}$, of the surface
consisting of $n$-1 planar regions whose properties correspond lead to the {\em
recognition} of the surfaces' properties i.e. developable, ruled etc.
\cite{hung92smooth}) and {\em classification} criteria.
  It is further shown that the image (i.e. representation) of an algebraic
surface of degree 2 in $\Real^n$ is a region whose boundary is also an
algebraic curve of degree 2. This includes some {\em non-convex} surfaces which
with the previous ambiguous representation could not be treated. An efficient
construction algorithm for the representation of the quadratic surfaces (given
either by {\em explicit} or {\em implicit} equation) is provided. The results
obtained are suitable for applications, to be presented in a future paper, and
in particular for the approximation of complex surfaces based on their {\em
planar} images. An additional benefit is the elimination of the
``over-plotting'' problem i.e. the ``bunching'' of polygonal lines which often
obscure part of the parallel-coordinate display.


title:
Algebraic Curves in Parallel Coordinates - Avoiding the "Over-Plotting"
  Problem

abstract:
  ${\cal U}$ntil now the representation (i.e. plotting) of curve in Parallel
Coordinates is constructed from the point $\leftrightarrow$ line duality. The
result is a ``line-curve'' which is seen as the envelope of it's tangents.
Usually this gives an unclear image and is at the heart of the
``over-plotting'' problem; a barrier in the effective use of Parallel
Coordinates. This problem is overcome by a transformation which provides
directly the ``point-curve'' representation of a curve. Earlier this was
applied to conics and their generalizations. Here the representation, also
called dual, is extended to all planar algebraic curves. Specifically, it is
shown that the dual of an algebraic curve of degree $n$ is an algebraic of
degree at most $n(n - 1)$ in the absence of singular points. The result that
conics map into conics follows as an easy special case. An algorithm, based on
algebraic geometry using resultants and homogeneous polynomials, is obtained
which constructs the dual image of the curve. This approach has potential
generalizations to multi-dimensional algebraic surfaces and their
approximation. The ``trade-off'' price then for obtaining {\em planar}
representation of multidimensional algebraic curves and hyper-surfaces is the
higher degree of the image's boundary which is also an algebraic curve in
$\|$-coords.


title: The role of behavior modifiers in representation development

abstract:
  We address the problem of the development of representations and their
relationship to the environment. We study a software agent which develops in a
network a representation of its simple environment which captures and
integrates the relationships between agent and environment through a closure
mechanism. The inclusion of a variable behavior modifier allows better
representation development. This can be confirmed with an internal description
of the closure mechanism, and with an external description of the properties of
the representation network.


title: End-User Effects of Microreboots in Three-Tiered Internet Systems

abstract:
  Microreboots restart fine-grained components of software systems "with a
clean slate," and only take a fraction of the time needed for full system
reboot. Microreboots provide an application-generic recovery technique for
Internet services, which can be supported entirely in middleware and requires
no changes to the applications or any a priori knowledge of application
semantics.
  This paper investigates the effect of microreboots on end-users of an
eBay-like online auction application; we find that microreboots are nearly as
effective as full reboots, but are significantly less disruptive in terms of
downtime and lost work. In our experiments, microreboots reduced the number of
failed user requests by 65% and the perceived downtime by 78% compared to a
server process restart. We also show how to replace user-visible transient
failures with transparent call-retry, at the cost of a slight increase in
end-user-visible latency during recovery. Due to their low cost, microreboots
can be used aggressively, even when their necessity is less than certain, hence
adding to the reduced recovery time a reduction in the fault detection time,
which further improves availability.


title:
Polynomial-time computing over quadratic maps I: sampling in real
  algebraic sets

abstract:
  Given a quadratic map Q : K^n -> K^k defined over a computable subring D of a
real closed field K, and a polynomial p(Y_1,...,Y_k) of degree d, we consider
the zero set Z=Z(p(Q(X)),K^n) of the polynomial p(Q(X_1,...,X_n)). We present a
procedure that computes, in (dn)^O(k) arithmetic operations in D, a set S of
(real univariate representations of) sampling points in K^n that intersects
nontrivially each connected component of Z. As soon as k=o(n), this is faster
than the standard methods that all have exponential dependence on n in the
complexity. In particular, our procedure is polynomial-time for constant k. In
contrast, the best previously known procedure (due to A.Barvinok) is only
capable of deciding in n^O(k^2) operations the nonemptiness (rather than
constructing sampling points) of the set Z in the case of p(Y)=sum_i Y_i^2 and
homogeneous Q.
  A by-product of our procedure is a bound (dn)^O(k) on the number of connected
components of Z.
  The procedure consists of exact symbolic computations in D and outputs
vectors of algebraic numbers. It involves extending K by infinitesimals and
subsequent limit computation by a novel procedure that utilizes knowledge of an
explicit isomorphism between real algebraic sets.


title: Demolishing Searle's Chinese Room

abstract:
  Searle's Chinese Room argument is refuted by showing that he has actually
given two different versions of the room, which fail for different reasons.
Hence, Searle does not achieve his stated goal of showing ``that a system could
have input and output capabilities that duplicated those of a native Chinese
speaker and still not understand Chinese''.


title: Polymorphic lemmas and definitions in Lambda Prolog and Twelf

abstract:
  Lambda Prolog is known to be well-suited for expressing and implementing
logics and inference systems. We show that lemmas and definitions in such
logics can be implemented with a great economy of expression. We encode a
higher-order logic using an encoding that maps both terms and types of the
object logic (higher-order logic) to terms of the metalanguage (Lambda Prolog).
We discuss both the Terzo and Teyjus implementations of Lambda Prolog. We also
encode the same logic in Twelf and compare the features of these two
metalanguages for our purposes.


title: Specialization of Functional Logic Programs Based on Needed Narrowing

abstract:
  Many functional logic languages are based on narrowing, a unification-based
goal-solving mechanism which subsumes the reduction mechanism of functional
languages and the resolution principle of logic languages. Needed narrowing is
an optimal evaluation strategy which constitutes the basis of modern
(narrowing-based) lazy functional logic languages. In this work, we present the
fundamentals of partial evaluation in such languages. We provide correctness
results for partial evaluation based on needed narrowing and show that the nice
properties of this strategy are essential for the specialization process. In
particular, the structure of the original program is preserved by partial
evaluation and, thus, the same evaluation strategy can be applied for the
execution of specialized programs. This is in contrast to other partial
evaluation schemes for lazy functional logic programs which may change the
program structure in a negative way. Recent proposals for the partial
evaluation of declarative multi-paradigm programs use (some form of) needed
narrowing to perform computations at partial evaluation time. Therefore, our
results constitute the basis for the correctness of such partial evaluators.


title: Distributed Control by Lagrangian Steepest Descent

abstract:
  Often adaptive, distributed control can be viewed as an iterated game between
independent players. The coupling between the players' mixed strategies,
arising as the system evolves from one instant to the next, is determined by
the system designer. Information theory tells us that the most likely joint
strategy of the players, given a value of the expectation of the overall
control objective function, is the minimizer of a Lagrangian function of the
joint strategy. So the goal of the system designer is to speed evolution of the
joint strategy to that Lagrangian minimizing point, lower the expectated value
of the control objective function, and repeat. Here we elaborate the theory of
algorithms that do this using local descent procedures, and that thereby
achieve efficient, adaptive, distributed control.


title: Predictable Software -- A Shortcut to Dependable Computing ?

abstract:
  Many dependability techniques expect certain behaviors from the underlying
subsystems and fail in chaotic ways if these expectations are not met. Under
expected circumstances, however, software tends to work quite well. This paper
suggests that, instead of fixing elusive bugs or rewriting software, we improve
the predictability of conditions faced by our programs. This approach might be
a cheaper and faster way to improve dependability of software. After
identifying some of the common triggers of unpredictability, the paper
describes three engineering principles that hold promise in combating
unpredictability, suggests a way to benchmark predictability, and outlines a
brief research agenda.


title: Search Efficiency in Indexing Structures for Similarity Searching

abstract:
  Similarity searching finds application in a wide variety of domains including
multilingual databases, computational biology, pattern recognition and text
retrieval. Similarity is measured in terms of a distance function, edit
distance, in general metric spaces, which is expensive to compute. Indexing
techniques can be used reduce the number of distance computations. We present
an analysis of various existing similarity indexing structures for the same.
The performance obtained using the index structures studied was found to be
unsatisfactory . We propose an indexing technique that combines the features of
clustering with M tree(MTB) and the results indicate that this gives better
performance.


title: Belle Computing System

abstract:
  We describe the present status of the computing system in the Belle
experiment at the KEKB $e^+e^-$ asymmetric-energy collider. So far, we have
logged more than 160 fb$^{-1}$ of data, corresponding to the world's largest
data sample of 170M $B\bar{B}$ pairs at the $\Upsilon(4S)$ energy region. A
large amount of event data has to be processed to produce an analysis event
sample in a timely fashion. In addition, Monte Carlo events have to be created
to control systematic errors accurately. This requires stable and efficient
usage of computing resources. Here we review our computing model and then
describe how we efficiently proceed DST/MC productions in our system.


title: A Comparative Study of Arithmetic Constraints on Integer Intervals

abstract:
  We propose here a number of approaches to implement constraint propagation
for arithmetic constraints on integer intervals. To this end we introduce
integer interval arithmetic. Each approach is explained using appropriate proof
rules that reduce the variable domains. We compare these approaches using a set
of benchmarks.


title:
Extending the SDSS Batch Query System to the National Virtual
  Observatory Grid

abstract:
  The Sloan Digital Sky Survey science database is approaching 2TB. While the
vast majority of queries normally execute in seconds or minutes, this
interactive execution time can be disproportionately increased by a small
fraction of queries that take hours or days to run; either because they require
non-index scans of the largest tables or because they request very large result
sets. In response to this, we added a multi-queue job submission and tracking
system. The transfer of very large result sets from queries over the network is
another serious problem. Statistics suggested that much of this data transfer
is unnecessary; users would prefer to store results locally in order to allow
further cross matching and filtering. To allow local analysis, we implemented a
system that gives users their own personal database (MyDB) at the portal site.
Users may transfer data to their MyDB, and then perform further analysis before
extracting it to their own machine.
  We intend to extend the MyDB and asynchronous query ideas to multiple NVO
nodes. This implies development, in a distributed manner, of several features,
which have been demonstrated for a single node in the SDSS Batch Query System
(CasJobs). The generalization of asynchronous queries necessitates some form of
MyDB storage as well as workflow tracking services on each node and
coordination strategies among nodes.


title: The World Wide Telescope: An Archetype for Online Science

abstract:
  Most scientific data will never be directly examined by scientists; rather it
will be put into online databases where it will be analyzed and summarized by
computer programs. Scientists increasingly see their instruments through online
scientific archives and analysis tools, rather than examining the raw data.
Today this analysis is primarily driven by scientists asking queries, but
scientific archives are becoming active databases that self-organize and
recognize interesting and anomalous facts as data arrives. In some fields, data
from many different archives can be cross-correlated to produce new insights.
Astronomy presents an excellent example of these trends; and, federating
Astronomy archives presents interesting challenges for computer scientists.


title: Distributed Computing Economics

abstract:
  Computing economics are changing. Today there is rough price parity between
(1) one database access, (2) ten bytes of network traffic, (3) 100,000
instructions, (4) 10 bytes of disk storage, and (5) a megabyte of disk
bandwidth. This has implications for how one structures Internet-scale
distributed computing: one puts computing as close to the data as possible in
order to avoid expensive network traffic.


title:
The Sloan Digital Sky Survey Science Archive: Migrating a Multi-Terabyte
  Astronomical Archive from Object to Relational DBMS

abstract:
  The Sloan Digital Sky Survey Science Archive is the first in a series of
multi-Terabyte digital archives in Astronomy and other data-intensive sciences.
To facilitate data mining in the SDSS archive, we adapted a commercial database
engine and built specialized tools on top of it. Originally we chose an
object-oriented database management system due to its data organization
capabilities, platform independence, query performance and conceptual fit to
the data. However, after using the object database for the first couple of
years of the project, it soon began to fall short in terms of its query support
and data mining performance. This was as much due to the inability of the
database vendor to respond our demands for features and bug fixes as it was due
to their failure to keep up with the rapid improvements in hardware
performance, particularly faster RAID disk systems. In the end, we were forced
to abandon the object database and migrate our data to a relational database.
We describe below the technical issues that we faced with the object database
and how and why we migrated to relational technology.


title: A Quick Look at SATA Disk Performance

abstract:
  We have been investigating the use of low-cost, commodity components for
multi-terabyte SQL Server databases. Dubbed storage bricks, these servers are
white box PCs containing the largest ATA drives, value-priced AMD or Intel
processors, and inexpensive ECC memory. One issue has been the wiring mess, air
flow problems, length restrictions, and connector failures created by seven or
more parallel ATA (PATA) ribbon cables and drives in]a tower or 3U rack-mount
chassis. Large capacity Serial ATA (SATA) drives have recently become widely
available for the PC environment at a reasonable price. In addition to being
faster, the SATA connectors seem more reliable, have a more reasonable length
restriction (1m) and allow better airflow. We tested two drive brands along
with two RAID controllers to evaluate SATA drive performance and reliablility.
This paper documents our results so far.


title: Fast Multipoint-Evaluation of Bivariate Polynomials

abstract:
  We generalize univariate multipoint evaluation of polynomials of degree n at
sublinear amortized cost per point. More precisely, it is shown how to evaluate
a bivariate polynomial p of maximum degree less than n, specified by its n^2
coefficients, simultaneously at n^2 given points using a total of O(n^{2.667})
arithmetic operations. In terms of the input size N being quadratic in n, this
amounts to an amortized cost of O(N^{0.334}) per point.


title: Secure Transmission of Sensitive data using multiple channels

abstract:
  A new scheme for transmitting sensitive data is proposed, the proposed scheme
depends on partitioning the output of a block encryption module using the
Chinese Remainder Theorem among a set of channels. The purpose of using the
Chinese Remainder Theorem is to hide the cipher text in order to increase the
difficulty of attacking the cipher. The theory, implementation and the security
of this scheme are described in this paper.


title:
Uniform Proofs of Order Independence for Various Strategy Elimination
  Procedures

abstract:
  We provide elementary and uniform proofs of order independence for various
strategy elimination procedures for finite strategic games, both for dominance
by pure and by mixed strategies. The proofs follow the same pattern and focus
on the structural properties of the dominance relations. They rely on Newman's
Lemma established in 1942 and related results on the abstract reduction
systems.


title: Distribution of Mutual Information from Complete and Incomplete Data

abstract:
  Mutual information is widely used, in a descriptive way, to measure the
stochastic dependence of categorical random variables. In order to address
questions such as the reliability of the descriptive value, one must consider
sample-to-population inferential approaches. This paper deals with the
posterior distribution of mutual information, as obtained in a Bayesian
framework by a second-order Dirichlet prior distribution. The exact analytical
expression for the mean, and analytical approximations for the variance,
skewness and kurtosis are derived. These approximations have a guaranteed
accuracy level of the order O(1/n^3), where n is the sample size. Leading order
approximations for the mean and the variance are derived in the case of
incomplete samples. The derived analytical expressions allow the distribution
of mutual information to be approximated reliably and quickly. In fact, the
derived expressions can be computed with the same order of complexity needed
for descriptive mutual information. This makes the distribution of mutual
information become a concrete alternative to descriptive mutual information in
many applications which would benefit from moving to the inductive side. Some
of these prospective applications are discussed, and one of them, namely
feature selection, is shown to perform significantly better when inductive
mutual information is used.

categories: cs.LG cs.AI cs.IT math.IT math.ST stat.TH


title:
What we should teach, but don't: Proposal for a cross pollinated HCI-SE
  curriculum

abstract:
  Software engineering (SE) and usability engineering (UE), as disciplines,
have reached substantial levels of maturity. Each of these two disciplines is
now well represented with respect to most computer science (CS) curricula. But,
the two disciplines are practiced almost independently - missing oppurtunities
to collaborate, coordinate and communicate about the overall design - and
thereby contributing to system failures. Today, a confluence of several
ingredients contribute to these failures: the increasing importance of the user
interface (UI) component in the overall system, the independent maturation of
the human computer interaction area, and the lack of a cohesive process model
to integrate the UI experts' UE development efforts with that of SE. This in
turn, we believe, is a result of a void in computing curricula: a lack of
education and training regarding the importance of communication, collaboration
and coordination between the SE and UE processes. In this paper we describe the
current approach to teaching SE and UE and its shortcomings. We identify and
analyze the barriers and issues involved in developing systems having
substantial interactive components. We then propose four major themes of
learning for a comprehensive computing curriculum integrating SE, UE, and
system architectures in a project environment.


title: An approach to membrane computing under inexactitude

abstract:
  In this paper we introduce a fuzzy version of symport/antiport membrane
systems. Our fuzzy membrane systems handle possibly inexact copies of reactives
and their rules are endowed with threshold functions that determine whether a
rule can be applied or not to a given set of objects, depending of the degree
of accuracy of these objects to the reactives specified in the rule. We prove
that these fuzzy membrane systems generate exactly the recursively enumerable
finite-valued fuzzy sets of natural numbers.