title:
One-Chip Solution to Intelligent Robot Control: Implementing Hexapod
  Subsumption Architecture Using a Contemporary Microprocessor

abstract:
  This paper introduces a six-legged autonomous robot managed by a single
controller and a software core modeled on subsumption architecture. We begin by
discussing the features and capabilities of IsoPod, a new processor for
robotics which has enabled a streamlined implementation of our project. We
argue that this processor offers a unique set of hardware and software
features, making it a practical development platform for robotics in general
and for subsumption-based control architectures in particular. Next, we
summarize original ideas on subsumption architecture implementation for a
six-legged robot, as presented by its inventor Rodney Brooks in 1980s. A
comparison is then made to a more recent example of a hexapod control
architecture based on subsumption. The merits of both systems are analyzed and
a new subsumption architecture layout is formulated as a response. We conclude
with some remarks regarding the development of this project as a hint at new
potentials for intelligent robot design, opened by a recent development in
embedded controller market.


title: How to achieve various gait patterns from single nominal

abstract:
  In this paper is presented an approach to achieving on-line modification of
nominal biped gait without recomputing entire dynamics when steady motion is
performed. Straight, dynamically balanced walk was used as a nominal gait, and
applied modifications were speed-up and slow-down walk and turning left and
right. It is shown that the disturbances caused by these modifications
jeopardize dynamic stability, but they can be simply compensated to enable walk
continuation.


title: Clustering Categorical Data Streams

abstract:
  The data stream model has been defined for new classes of applications
involving massive data being generated at a fast pace. Web click stream
analysis and detection of network intrusions are two examples. Cluster analysis
on data streams becomes more difficult, because the data objects in a data
stream must be accessed in order and can be read only once or few times with
limited resources. Recently, a few clustering algorithms have been developed
for analyzing numeric data streams. However, to our knowledge to date, no
algorithm exists for clustering categorical data streams. In this paper, we
propose an efficient clustering algorithm for analyzing categorical data
streams. It has been proved that the proposed algorithm uses small memory
footprints. We provide empirical analysis on the performance of the algorithm
in clustering both synthetic and real data streams


title:
Vector Symbolic Architectures answer Jackendoff's challenges for
  cognitive neuroscience

abstract:
  Jackendoff (2002) posed four challenges that linguistic combinatoriality and
rules of language present to theories of brain function. The essence of these
problems is the question of how to neurally instantiate the rapid construction
and transformation of the compositional structures that are typically taken to
be the domain of symbolic processing. He contended that typical connectionist
approaches fail to meet these challenges and that the dialogue between
linguistic theory and cognitive neuroscience will be relatively unproductive
until the importance of these problems is widely recognised and the challenges
answered by some technical innovation in connectionist modelling. This paper
claims that a little-known family of connectionist models (Vector Symbolic
Architectures) are able to meet Jackendoff's challenges.


title: Monotonicity Results for Coherent MIMO Rician Channels

abstract:
  The dependence of the Gaussian input information rate on the line-of-sight
(LOS) matrix in multiple-input multiple-output coherent Rician fading channels
is explored. It is proved that the outage probability and the mutual
information induced by a multivariate circularly symmetric Gaussian input with
any covariance matrix are monotonic in the LOS matrix D, or more precisely,
monotonic in D'D in the sense of the Loewner partial order. Conversely, it is
also demonstrated that this ordering on the LOS matrices is a necessary
condition for the uniform monotonicity over all input covariance matrices. This
result is subsequently applied to prove the monotonicity of the isotropic
Gaussian input information rate and channel capacity in the singular values of
the LOS matrix. Extensions to multiple-access channels are also discussed.


title:
Free quasi-symmetric functions, product actions and quantum field theory
  of partitions

abstract:
  We examine two associative products over the ring of symmetric functions
related to the intransitive and Cartesian products of permutation groups. As an
application, we give an enumeration of some Feynman type diagrams arising in
Bender's QFT of partitions. We end by exploring possibilities to construct
noncommutative analogues.


title: Isomorphic Implication

abstract:
  We study the isomorphic implication problem for Boolean constraints. We show
that this is a natural analog of the subgraph isomorphism problem. We prove
that, depending on the set of constraints, this problem is in P, NP-complete,
or NP-hard, coNP-hard, and in parallel access to NP. We show how to extend the
NP-hardness and coNP-hardness to hardness for parallel access to NP for some
cases, and conjecture that this can be done in all cases.


title: Labelled transition systems as a Stone space

abstract:
  A fully abstract and universal domain model for modal transition systems and
refinement is shown to be a maximal-points space model for the bisimulation
quotient of labelled transition systems over a finite set of events. In this
domain model we prove that this quotient is a Stone space whose compact,
zero-dimensional, and ultra-metrizable Hausdorff topology measures the degree
of bisimilarity such that image-finite labelled transition systems are dense.
Using this compactness we show that the set of labelled transition systems that
refine a modal transition system, its ''set of implementations'', is compact
and derive a compactness theorem for Hennessy-Milner logic on such
implementation sets. These results extend to systems that also have partially
specified state propositions, unify existing denotational, operational, and
metric semantics on partial processes, render robust consistency measures for
modal transition systems, and yield an abstract interpretation of compact sets
of labelled transition systems as Scott-closed sets of modal transition
systems.


title:
Collective Intelligence Quanitifed for Computer-Mediated Group Problem
  Solving

abstract:
  Collective Intelligence (CI) is the ability of a group to exhibit greater
intelligence than its individual members. Expressed by the common saying that
"two minds are better than one," CI has been a topic of interest for social
psychology and the information sciences. Computer mediation adds a new element
in the form of distributed networks and group support systems. These facilitate
highly organized group activities that were all but impossible before computer
mediation. This paper presents experimental findings on group problem solving
where a distributed software system automatically integrates input from many
humans. In order to quantify Collective Intelligence, we compare the
performance of groups to individuals when solving a mathematically formalized
problem. This study shows that groups can outperform individuals on difficult
but not easy problems, though groups are slower to produce solutions. The
subjects are 57 university students. The task is the 8-Puzzle sliding tile
game.


title:
A Framework for Creating Natural Language User Interfaces for
  Action-Based Applications

abstract:
  In this paper we present a framework for creating natural language interfaces
to action-based applications. Our framework uses a number of reusable
application-independent components, in order to reduce the effort of creating a
natural language interface for a given application. Using a type-logical
grammar, we first translate natural language sentences into expressions in an
extended higher-order logic. These expressions can be seen as executable
specifications corresponding to the original sentences. The executable
specifications are then interpreted by invoking appropriate procedures provided
by the application for which a natural language interface is being created.


title:
From Feature Extraction to Classification: A multidisciplinary Approach
  applied to Portuguese Granites

abstract:
  The purpose of this paper is to present a complete methodology based on a
multidisciplinary approach, that goes from the extraction of features till the
classification of a set of different portuguese granites. The set of tools to
extract the features that characterise polished surfaces of the granites is
mainly based on mathematical morphology. The classification methodology is
based on a genetic algorithm capable of search the input feature space used by
the nearest neighbour rule classifier. Results show that is adequate to perform
feature reduction and simultaneous improve the recognition rate. Moreover, the
present methodology represents a robust strategy to understand the proper
nature of the images treated, and their discriminant features. KEYWORDS:
Portuguese grey granites, feature extraction, mathematical morphology, feature
reduction, genetic algorithms, nearest neighbour rule classifiers (k-NNR).


title:
Complete Characterization of the Equivalent MIMO Channel for
  Quasi-Orthogonal Space-Time Codes

abstract:
  Recently, a quasi-orthogonal space-time block code (QSTBC) capable of
achieving a significant fraction of the outage mutual information of a
multiple-input-multiple output (MIMO) wireless communication system for the
case of four transmit and one receive antennas was proposed. We generalize
these results to $n_T=2^n$ transmit and an arbitrary number of receive antennas
$n_R$. Furthermore, we completely characterize the structure of the equivalent
channel for the general case and show that for all $n_T=2^n$ and $n_R$ the
eigenvectors of the equivalent channel are fixed and independent from the
channel realization. Furthermore, the eigenvalues of the equivalent channel are
independent identically distributed random variables each following a
noncentral chi-square distribution with $4n_R$ degrees of freedom.
  Based on these important insights into the structure of the QSTBC, we derive
an analytical lower bound for the fraction of outage probability achieved with
QSTBC and show that this bound is tight for low signal-to-noise-ratios (SNR)
values and also for increasing number of receive antennas. We also present an
upper bound, which is tight for high SNR values and derive analytical
expressions for the case of four transmit antennas. Finally, by utilizing the
special structure of the QSTBC we propose a new transmit strategy, which
decouples the signals transmitted from different antennas in order to detect
the symbols separately with a linear ML-detector rather than joint detection,
an up to now only known advantage of orthogonal space-time block codes (OSTBC).


title:
ANTIDS: Self-Organized Ant-based Clustering Model for Intrusion
  Detection System

abstract:
  Security of computers and the networks that connect them is increasingly
becoming of great significance. Computer security is defined as the protection
of computing systems against threats to confidentiality, integrity, and
availability. There are two types of intruders: the external intruders who are
unauthorized users of the machines they attack, and internal intruders, who
have permission to access the system with some restrictions. Due to the fact
that it is more and more improbable to a system administrator to recognize and
manually intervene to stop an attack, there is an increasing recognition that
ID systems should have a lot to earn on following its basic principles on the
behavior of complex natural systems, namely in what refers to
self-organization, allowing for a real distributed and collective perception of
this phenomena. With that aim in mind, the present work presents a
self-organized ant colony based intrusion detection system (ANTIDS) to detect
intrusions in a network infrastructure. The performance is compared among
conventional soft computing paradigms like Decision Trees, Support Vector
Machines and Linear Genetic Programming to model fast, online and efficient
intrusion detection systems.


title: Swarming around Shellfish Larvae

abstract:
  The collection of wild larvae seed as a source of raw material is a major sub
industry of shellfish aquaculture. To predict when, where and in what
quantities wild seed will be available, it is necessary to track the appearance
and growth of planktonic larvae. One of the most difficult groups to identify,
particularly at the species level are the Bivalvia. This difficulty arises from
the fact that fundamentally all bivalve larvae have a similar shape and colour.
Identification based on gross morphological appearance is limited by the
time-consuming nature of the microscopic examination and by the limited
availability of expertise in this field. Molecular and immunological methods
are also being studied. We describe the application of computational pattern
recognition methods to the automated identification and size analysis of
scallop larvae. For identification, the shape features used are binary
invariant moments; that is, the features are invariant to shift (position
within the image), scale (induced either by growth or differential image
magnification) and rotation. Images of a sample of scallop and non-scallop
larvae covering a range of maturities have been analysed. In order to overcome
the automatic identification, as well as to allow the system to receive new
unknown samples at any moment, a self-organized and unsupervised ant-like
clustering algorithm based on Swarm Intelligence is proposed, followed by
simple k-NNR nearest neighbour classification on the final map. Results achieve
a full recognition rate of 100% under several situations (k =1 or 3).


title: Less is More - Genetic Optimisation of Nearest Neighbour Classifiers

abstract:
  The present paper deals with optimisation of Nearest Neighbour rule
Classifiers via Genetic Algorithms. The methodology consists on implement a
Genetic Algorithm capable of search the input feature space used by the NNR
classifier. Results show that is adequate to perform feature reduction and
simultaneous improve the Recognition Rate. Some practical examples prove that
is possible to Recognise Portuguese Granites in 100%, with only 3 morphological
features (from an original set of 117 features), which is well suited for real
time applications. Moreover, the present method represents a robust strategy to
understand the proper nature of the images treated, and their discriminant
features. KEYWORDS: Feature Reduction, Genetic Algorithms, Nearest Neighbour
Rule Classifiers (k-NNR).


title:
Web Usage Mining Using Artificial Ant Colony Clustering and Genetic
  Programming

abstract:
  The rapid e-commerce growth has made both business community and customers
face a new situation. Due to intense competition on one hand and the customer's
option to choose from several alternatives business community has realized the
necessity of intelligent marketing strategies and relationship management. Web
usage mining attempts to discover useful knowledge from the secondary data
obtained from the interactions of the users with the Web. Web usage mining has
become very critical for effective Web site management, creating adaptive Web
sites, business and support services, personalization, network traffic flow
analysis and so on. The study of ant colonies behavior and their
self-organizing capabilities is of interest to knowledge retrieval/management
and decision support systems sciences, because it provides models of
distributed adaptive organization, which are useful to solve difficult
optimization, classification, and distributed control problems, among others.
In this paper, we propose an ant clustering algorithm to discover Web usage
patterns (data clusters) and a linear genetic programming approach to analyze
the visitor trends. Empirical results clearly shows that ant colony clustering
performs well when compared to a self-organizing map (for clustering Web usage
patterns) even though the performance accuracy is not that efficient when
comparared to evolutionary-fuzzy clustering (i-miner) approach. KEYWORDS: Web
Usage Mining, Swarm Intelligence, Ant Systems, Stigmergy, Data-Mining, Linear
Genetic Programming.


title: Swarms on Continuous Data

abstract:
  While being it extremely important, many Exploratory Data Analysis (EDA)
systems have the inhability to perform classification and visualization in a
continuous basis or to self-organize new data-items into the older ones
(evenmore into new labels if necessary), which can be crucial in KDD -
Knowledge Discovery, Retrieval and Data Mining Systems (interactive and online
forms of Web Applications are just one example). This disadvantge is also
present in more recent approaches using Self-Organizing Maps. On the present
work, and exploiting past sucesses in recently proposed Stigmergic Ant Systems
a robust online classifier is presented, which produces class decisions on a
continuous stream data, allowing for continuous mappings. Results show that
increasingly better results are achieved, as demonstraded by other authors in
different areas. KEYWORDS: Swarm Intelligence, Ant Systems, Stigmergy,
Data-Mining, Exploratory Data Analysis, Image Retrieval, Continuous
Classification.


title:
Self-Organizing the Abstract: Canvas as a Swarm Habitat for Collective
  Memory, Perception and Cooperative Distributed Creativity

abstract:
  Past experiences under the designation of "Swarm Paintings" conducted in
2001, not only confirmed the possibility of realizing an artificial art (thus
non-human), as introduced into the process the questioning of creative
migration, specifically from the computer monitors to the canvas via a robotic
harm. In more recent self-organized based research we seek to develop and
profound the initial ideas by using a swarm of autonomous robots (ARTsBOT
project 2002-03), that "live" avoiding the purpose of being merely a simple
perpetrator of order streams coming from an external computer, but instead,
that actually co-evolve within the canvas space, acting (that is, laying ink)
according to simple inner threshold stimulus response functions, reacting
simultaneously to the chromatic stimulus present in the canvas environment done
by the passage of their team-mates, as well as by the distributed feedback,
affecting their future collective behaviour. In parallel, and in what respects
to certain types of collective systems, we seek to confirm, in a physically
embedded way, that the emergence of order (even as a concept) seems to be found
at a lower level of complexity, based on simple and basic interchange of
information, and on the local dynamic of parts, who, by self-organizing
mechanisms tend to form an lived whole, innovative and adapting, allowing for
emergent open-ended creative and distributed production. KEYWORDS: ArtSBots
Project, Swarm Intelligence, Stigmergy, UnManned Art, Symbiotic Art, Swarm
Paintings, Robot Paintings, Non-Human Art, Painting Emergence and Cooperation,
Art and Complexity, ArtBots: The Robot Talent Show.


title:
Threats of Human Error in a High-Performance Storage System: Problem
  Statement and Case Study

abstract:
  System administration is a difficult, often tedious, job requiring many
skilled laborers. The data that is protected by system administrators is often
valued at or above the value of the institution maintaining that data. A number
of ethnographic studies have confirmed the skill of these operators, and the
difficulty of providing adequate tools. In an effort to minimize the
maintenance costs, an increasing portion of system administration is subject to
automation - particularly simple, routine tasks such as data backup. While such
tools reduce the risk of errors from carelessness, the same tools may result in
reduced skill and system familiarity in experienced workers. Care should be
taken to ensure that operators maintain system awareness without placing the
operator in a passive, monitoring role.


title:
Self-Organized Stigmergic Document Maps: Environment as a Mechanism for
  Context Learning

abstract:
  Social insect societies and more specifically ant colonies, are distributed
systems that, in spite of the simplicity of their individuals, present a highly
structured social organization. As a result of this organization, ant colonies
can accomplish complex tasks that in some cases exceed the individual
capabilities of a single ant. The study of ant colonies behavior and of their
self-organizing capabilities is of interest to knowledge retrieval/management
and decision support systems sciences, because it provides models of
distributed adaptive organization which are useful to solve difficult
optimization, classification, and distributed control problems, among others.
In the present work we overview some models derived from the observation of
real ants, emphasizing the role played by stigmergy as distributed
communication paradigm, and we present a novel strategy to tackle unsupervised
clustering as well as data retrieval problems. The present ant clustering
system (ACLUSTER) avoids not only short-term memory based strategies, as well
as the use of several artificial ant types (using different speeds), present in
some recent approaches. Moreover and according to our knowledge, this is also
the first application of ant systems into textual document clustering.
KEYWORDS: Swarm Intelligence, Ant Systems, Unsupervised Clustering, Data
Retrieval, Data Mining, Distributed Computing, Document Maps, Textual Document
Clustering.


title: Clustering Techniques for Marbles Classification

abstract:
  Automatic marbles classification based on their visual appearance is an
important industrial issue. However, there is no definitive solution to the
problem mainly due to the presence of randomly distributed high number of
different colours and its subjective evaluation by the human expert. In this
paper we present a study of segmentation techniques, we evaluate they overall
performance using a training set and standard quality measures and finally we
apply different clustering techniques to automatically classify the marbles.
KEYWORDS: Segmentation, Clustering, Quadtrees, Learning Vector Quantization
(LVQ), Simulated Annealing (SA).


title:
On the Implicit and on the Artificial - Morphogenesis and Emergent
  Aesthetics in Autonomous Collective Systems

abstract:
  Imagine a "machine" where there is no pre-commitment to any particular
representational scheme: the desired behaviour is distributed and roughly
specified simultaneously among many parts, but there is minimal specification
of the mechanism required to generate that behaviour, i.e. the global behaviour
evolves from the many relations of multiple simple behaviours. A machine that
lives to and from/with Synergy. An artificial super-organism that avoids
specific constraints and emerges within multiple low-level implicit
bio-inspired mechanisms. KEYWORDS: Complex Science, ArtSBots Project, Swarm
Intelligence, Stigmergy, UnManned Art, Symbiotic Art, Swarm Paintings, Robot
Paintings, Non-Human Art, Painting Emergence and Cooperation, Art and
Complexity, ArtBots: The Robot Talent Show.


title: The vertex-transitive TLF-planar graphs

abstract:
  We consider the class of the topologically locally finite (in short TLF)
planar vertex-transitive graphs, a class containing in particular all the
one-ended planar Cayley graphs and the normal transitive tilings. We
characterize these graphs with a finite local representation and a special kind
of finite state automaton named labeling scheme. As a result, we are able to
enumerate and describe all TLF-planar vertex-transitive graphs of any given
degree. Also, we are able decide to whether any TLF-planar transitive graph is
Cayley or not.


title:
The MC2 Project [Machines of Collective Conscience]: A possible walk, up
  to Life-like Complexity and Behaviour, from bottom, basic and simple
  bio-inspired heuristics - a walk, up into the morphogenesis of information

abstract:
  Synergy (from the Greek word synergos), broadly defined, refers to combined
or co-operative effects produced by two or more elements (parts or
individuals). The definition is often associated with the holistic conviction
quote that "the whole is greater than the sum of its parts" (Aristotle, in
Metaphysics), or the whole cannot exceed the sum of the energies invested in
each of its parts (e.g. first law of thermodynamics) even if it is more
accurate to say that the functional effects produced by wholes are different
from what the parts can produce alone. Synergy is a ubiquitous phenomena in
nature and human societies alike. One well know example is provided by the
emergence of self-organization in social insects, via direct or indirect
interactions. The latter types are more subtle and defined as stigmergy to
explain task coordination and regulation in the context of nest reconstruction
in termites. An example, could be provided by two individuals, who interact
indirectly when one of them modifies the environment and the other responds to
the new environment at a later time. In other words, stigmergy could be defined
as a particular case of environmental or spatial synergy. The system is purely
holistic, and their properties are intrinsically emergent and autocatalytic. On
the present work we present a "machine" where there is no precommitment to any
particular representational scheme: the desired behaviour is distributed and
roughly specified simultaneously among many parts, but there is minimal
specification of the mechanism required to generate that behaviour, i.e. the
global behaviour evolves from the many relations of multiple simple behaviours.


title:
The Biological Concept of Neoteny in Evolutionary Colour Image
  Segmentation - Simple Experiments in Simple Non-Memetic Genetic Algorithms

abstract:
  Neoteny, also spelled Paedomorphosis, can be defined in biological terms as
the retention by an organism of juvenile or even larval traits into later life.
In some species, all morphological development is retarded; the organism is
juvenilized but sexually mature. Such shifts of reproductive capability would
appear to have adaptive significance to organisms that exhibit it. In terms of
evolutionary theory, the process of paedomorphosis suggests that larval stages
and developmental phases of existing organisms may give rise, under certain
circumstances, to wholly new organisms. Although the present work does not
pretend to model or simulate the biological details of such a concept in any
way, these ideas were incorporated by a rather simple abstract computational
strategy, in order to allow (if possible) for faster convergence into simple
non-memetic Genetic Algorithms, i.e. without using local improvement procedures
(e.g. via Baldwin or Lamarckian learning). As a case-study, the Genetic
Algorithm was used for colour image segmentation purposes by using K-mean
unsupervised clustering methods, namely for guiding the evolutionary algorithm
in his search for finding the optimal or sub-optimal data partition. Average
results suggest that the use of neotonic strategies by employing juvenile
genotypes into the later generations and the use of linear-dynamic mutation
rates instead of constant, can increase fitness values by 58% comparing to
classical Genetic Algorithms, independently from the starting population
characteristics on the search space. KEYWORDS: Genetic Algorithms, Artificial
Neoteny, Dynamic Mutation Rates, Faster Convergence, Colour Image Segmentation,
Classification, Clustering.


title: Artificial Neoteny in Evolutionary Image Segmentation


title: Line and Word Matching in Old Documents

abstract:
  This paper is concerned with the problem of establishing an index based on
word matching. It is assumed that the book was digitised as better as possible
and some pre-processing techniques were already applied as line orientation
correction and some noise removal. However two main factor are responsible for
being not possible to apply ordinary optical character recognition techniques
(OCR): the presence of antique fonts and the degraded state of many characters
due to unrecoverable original time degradation. In this paper we make a short
introduction to word segmentation that involves finding the lines that
characterise a word. After we discuss different approaches for word matching
and how they can be combined to obtain an ordered list for candidate words for
the matching. This discussion will be illustrated by examples.


title: Map Segmentation by Colour Cube Genetic K-Mean Clustering

abstract:
  Segmentation of a colour image composed of different kinds of texture regions
can be a hard problem, namely to compute for an exact texture fields and a
decision of the optimum number of segmentation areas in an image when it
contains similar and/or unstationary texture fields. In this work, a method is
described for evolving adaptive procedures for these problems. In many real
world applications data clustering constitutes a fundamental issue whenever
behavioural or feature domains can be mapped into topological domains. We
formulate the segmentation problem upon such images as an optimisation problem
and adopt evolutionary strategy of Genetic Algorithms for the clustering of
small regions in colour feature space. The present approach uses k-Means
unsupervised clustering methods into Genetic Algorithms, namely for guiding
this last Evolutionary Algorithm in his search for finding the optimal or
sub-optimal data partition, task that as we know, requires a non-trivial search
because of its NP-complete nature. To solve this task, the appropriate genetic
coding is also discussed, since this is a key aspect in the implementation. Our
purpose is to demonstrate the efficiency of Genetic Algorithms to automatic and
unsupervised texture segmentation. Some examples in Colour Maps are presented
and overall results discussed. KEYWORDS: Genetic Algorithms, Artificial
Neoteny, Dynamic Mutation Rates, Faster Convergence, Colour Image Segmentation,
Classification, Clustering.


title: A class of one-dimensional MDS convolutional codes

abstract:
  A class of one-dimensional convolutional codes will be presented. They are
all MDS codes, i. e., have the largest distance among all one-dimensional codes
of the same length n and overall constraint length delta. Furthermore, their
extended row distances are computed, and they increase with slope n-delta. In
certain cases of the algebraic parameters, we will also derive parity check
matrices of Vandermonde type for these codes. Finally, cyclicity in the
convolutional sense will be discussed for our class of codes. It will turn out
that they are cyclic if and only if the field element used in the generator
matrix has order n. This can be regarded as a generalization of the block code
case.


title:
Artificial Ant Colonies in Digital Image Habitats - A Mass Behaviour
  Effect Study on Pattern Recognition

abstract:
  Some recent studies have pointed that, the self-organization of neurons into
brain-like structures, and the self-organization of ants into a swarm are
similar in many respects. If possible to implement, these features could lead
to important developments in pattern recognition systems, where perceptive
capabilities can emerge and evolve from the interaction of many simple local
rules. The principle of the method is inspired by the work of Chialvo and
Millonas who developed the first numerical simulation in which swarm cognitive
map formation could be explained. From this point, an extended model is
presented in order to deal with digital image habitats, in which artificial
ants could be able to react to the environment and perceive it. Evolution of
pheromone fields point that artificial ant colonies could react and adapt
appropriately to any type of digital habitat. KEYWORDS: Swarm Intelligence,
Self-Organization, Stigmergy, Artificial Ant Systems, Pattern Recognition and
Perception, Image Segmentation, Gestalt Perception Theory, Distributed
Computation.


title: Image Colour Segmentation by Genetic Algorithms

abstract:
  Segmentation of a colour image composed of different kinds of texture regions
can be a hard problem, namely to compute for an exact texture fields and a
decision of the optimum number of segmentation areas in an image when it
contains similar and/or unstationary texture fields. In this work, a method is
described for evolving adaptive procedures for these problems. In many real
world applications data clustering constitutes a fundamental issue whenever
behavioural or feature domains can be mapped into topological domains. We
formulate the segmentation problem upon such images as an optimisation problem
and adopt evolutionary strategy of Genetic Algorithms for the clustering of
small regions in colour feature space. The present approach uses k-Means
unsupervised clustering methods into Genetic Algorithms, namely for guiding
this last Evolutionary Algorithm in his search for finding the optimal or
sub-optimal data partition, task that as we know, requires a non-trivial search
because of its intrinsic NP-complete nature. To solve this task, the
appropriate genetic coding is also discussed, since this is a key aspect in the
implementation. Our purpose is to demonstrate the efficiency of Genetic
Algorithms to automatic and unsupervised texture segmentation. Some examples in
Colour Maps, Ornamental Stones and in Human Skin Mark segmentation are
presented and overall results discussed. KEYWORDS: Genetic Algorithms, Colour
Image Segmentation, Classification, Clustering.


title: On Image Filtering, Noise and Morphological Size Intensity Diagrams

abstract:
  In the absence of a pure noise-free image it is hard to define what noise is,
in any original noisy image, and as a consequence also where it is, and in what
amount. In fact, the definition of noise depends largely on our own aim in the
whole image analysis process, and (perhaps more important) in our
self-perception of noise. For instance, when we perceive noise as disconnected
and small it is normal to use MM-ASF filters to treat it. There is two
evidences of this. First, in many instances there is no ideal and pure
noise-free image to compare our filtering process (nothing but our
self-perception of its pure image); second, and related with this first point,
MM transformations that we chose are only based on our self - and perhaps -
fuzzy notion. The present proposal combines the results of two MM filtering
transformations (FT1, FT2) and makes use of some measures and quantitative
relations on their Size/Intensity Diagrams to find the most appropriate noise
removal process. Results can also be used for finding the most appropriate stop
criteria, and the right sequence of MM operators combination on Alternating
Sequential Filters (ASF), if these measures are applied, for instance, on a
Genetic Algorithm's target function.


title:
Evolving Categories: Consistent Framework for Representation of Data and
  Algorithms

abstract:
  A concept of "evolving categories" is suggested to build a simple, scalable,
mathematically consistent framework for representing in uniform way both data
and algorithms. A state machine for executing algorithms becomes clear, rich
and powerful semantics, based on category theory, and still allows easy
implementation. Moreover, it gives an original insight into the nature and
semantics of algorithms.


title: Real Time Models of the Asynchronous Circuits: The Delay Theory

abstract:
  The chapter from the book introduces the delay theory, whose purpose is the
modeling of the asynchronous circuits from digital electrical engineering with
ordinary and differential pseudo-boolean equations.


title:
The Combination of Paradoxical, Uncertain, and Imprecise Sources of
  Information based on DSmT and Neutro-Fuzzy Inference

abstract:
  The management and combination of uncertain, imprecise, fuzzy and even
paradoxical or high conflicting sources of information has always been, and
still remains today, of primal importance for the development of reliable
modern information systems involving artificial reasoning. In this chapter, we
present a survey of our recent theory of plausible and paradoxical reasoning,
known as Dezert-Smarandache Theory (DSmT) in the literature, developed for
dealing with imprecise, uncertain and paradoxical sources of information. We
focus our presentation here rather on the foundations of DSmT, and on the two
important new rules of combination, than on browsing specific applications of
DSmT available in literature. Several simple examples are given throughout the
presentation to show the efficiency and the generality of this new approach.
The last part of this chapter concerns the presentation of the neutrosophic
logic, the neutro-fuzzy inference and its connection with DSmT. Fuzzy logic and
neutrosophic logic are useful tools in decision making after fusioning the
information using the DSm hybrid rule of combination of masses.


title: Mass Storage Management and the Grid

abstract:
  The University of Edinburgh has a significant interest in mass storage
systems as it is one of the core groups tasked with the roll out of storage
software for the UK's particle physics grid, GridPP. We present the results of
a development project to provide software interfaces between the SDSC Storage
Resource Broker, the EU DataGrid and the Storage Resource Manager. This project
was undertaken in association with the eDikt group at the National eScience
Centre, the Universities of Bristol and Glasgow, Rutherford Appleton Laboratory
and the San Diego Supercomputing Center.


title: ScotGrid: A Prototype Tier 2 Centre

abstract:
  ScotGrid is a prototype regional computing centre formed as a collaboration
between the universities of Durham, Edinburgh and Glasgow as part of the UK's
national particle physics grid, GridPP. We outline the resources available at
the three core sites and our optimisation efforts for our user communities. We
discuss the work which has been conducted in extending the centre to embrace
new projects both from particle physics and new user communities and explain
our methodology for doing this.


title:
Preemptive Multi-Machine Scheduling of Equal-Length Jobs to Minimize the
  Average Flow Time

abstract:
  We study the problem of preemptive scheduling of n equal-length jobs with
given release times on m identical parallel machines. The objective is to
minimize the average flow time. Recently, Brucker and Kravchenko proved that
the optimal schedule can be computed in polynomial time by solving a linear
program with O(n^3) variables and constraints, followed by some substantial
post-processing (where n is the number of jobs.) In this note we describe a
simple linear program with only O(mn) variables and constraints. Our linear
program produces directly the optimal schedule and does not require any
post-processing.


title:
Partitioning Regular Polygons into Circular Pieces II:Nonconvex
  Partitions

abstract:
  We explore optimal circular nonconvex partitions of regular k-gons. The
circularity of a polygon is measured by its aspect ratio: the ratio of the
radii of the smallest circumscribing circle to the largest inscribed disk. An
optimal circular partition minimizes the maximum ratio over all pieces in the
partition. We show that the equilateral triangle has an optimal 4-piece
nonconvex partition, the square an optimal 13-piece nonconvex partition, and
the pentagon has an optimal nonconvex partition with more than 20 thousand
pieces. For hexagons and beyond, we provide a general algorithm that approaches
optimality, but does not achieve it.


title: Complexity of Self-Assembled Shapes

abstract:
  The connection between self-assembly and computation suggests that a shape
can be considered the output of a self-assembly ``program,'' a set of tiles
that fit together to create a shape. It seems plausible that the size of the
smallest self-assembly program that builds a shape and the shape's
descriptional (Kolmogorov) complexity should be related. We show that when
using a notion of a shape that is independent of scale, this is indeed so: in
the Tile Assembly Model, the minimal number of distinct tile types necessary to
self-assemble a shape, at some scale, can be bounded both above and below in
terms of the shape's Kolmogorov complexity. As part of the proof of the main
result, we sketch a general method for converting a program outputting a shape
as a list of locations into a set of tile types that self-assembles into a
scaled up version of that shape. Our result implies, somewhat
counter-intuitively, that self-assembly of a scaled-up version of a shape often
requires fewer tile types. Furthermore, the independence of scale in
self-assembly theory appears to play the same crucial role as the independence
of running time in the theory of computability. This leads to an elegant
formulation of languages of shapes generated by self-assembly. Considering
functions from integers to shapes, we show that the running-time complexity,
with respect to Turing machines, is polynomially equivalent to the scale
complexity of the same function implemented via self-assembly by a finite set
of tile types. Our results also hold for shapes defined by Wang tiling -- where
there is no sense of a self-assembly process -- except that here time
complexity must be measured with respect to non-deterministic Turing machines.


title: The Computational Power of Benenson Automata

abstract:
  The development of autonomous molecular computers capable of making
independent decisions in vivo regarding local drug administration may
revolutionize medical science. Recently Benenson at el (2004) have envisioned
one form such a ``smart drug'' may take by implementing an in vitro scheme, in
which a long DNA state molecule is cut repeatedly by a restriction enzyme in a
manner dependent upon the presence of particular short DNA ``rule molecules.''
To analyze the potential of their scheme in terms of the kinds of computations
it can perform, we study an abstraction assuming that a certain class of
restriction enzymes is available and reactions occur without error. We also
discuss how our molecular algorithms could perform with known restriction
enzymes. By exhibiting a way to simulate arbitrary circuits, we show that these
``Benenson automata'' are capable of computing arbitrary Boolean functions.
Further, we show that they are able to compute efficiently exactly those
functions computable by log-depth circuits. Computationally, we formalize a new
variant of limited width branching programs with a molecular implementation.


title: The Google Similarity Distance

abstract:
  Words and phrases acquire meaning from the way they are used in society, from
their relative semantics to other words and phrases. For computers the
equivalent of `society' is `database,' and the equivalent of `use' is `way to
search the database.' We present a new theory of similarity between words and
phrases based on information distance and Kolmogorov complexity. To fix
thoughts we use the world-wide-web as database, and Google as search engine.
The method is also applicable to other search engines and databases. This
theory is then applied to construct a method to automatically extract
similarity, the Google similarity distance, of words and phrases from the
world-wide-web using Google page counts. The world-wide-web is the largest
database on earth, and the context information entered by millions of
independent users averages out to provide automatic semantics of useful
quality. We give applications in hierarchical clustering, classification, and
language translation. We give examples to distinguish between colors and
numbers, cluster names of paintings by 17th century Dutch masters and names of
books by English novelists, the ability to understand emergencies, and primes,
and we demonstrate the ability to do a simple automatic English-Spanish
translation. Finally, we use the WordNet database as an objective baseline
against which to judge the performance of our method. We conduct a massive
randomized trial in binary classification using support vector machines to
learn categories based on our Google distance, resulting in an a mean agreement
of 87% with the expert crafted WordNet categories.


title: An unbreakable cryptosystem

abstract:
  The remarkably long-standing problem of cryptography is to generate
completely secure key. It is widely believed that the task cannot be achieved
within classical cryptography. However, there is no proof in support of this
belief. We present an incredibly simple classical cryptosystem which can
generate completely secure key.


title: Formal Test Purposes and The Validity of Test Cases

abstract:
  We give a formalization of the notion of test purpose based on (suitably
restricted) Message Sequence Charts. We define the validity of test cases with
respect to such a formal test purpose and provide a simple decision procedure
for validity.


title:
The Inverse Method Implements the Automata Approach for Modal
  Satisfiability

abstract:
  Tableaux-based decision procedures for satisfiability of modal and
description logics behave quite well in practice, but it is sometimes hard to
obtain exact worst-case complexity results using these approaches, especially
for EXPTIME-complete logics. In contrast, automata-based approaches often yield
algorithms for which optimal worst-case complexity can easily be proved.
However, the algorithms obtained this way are usually not only worst-case, but
also best-case exponential: they first construct an automaton that is always
exponential in the size of the input, and then apply the (polynomial) emptiness
test to this large automaton. To overcome this problem, one must try to
construct the automaton "on-the-fly" while performing the emptiness test.
  In this paper we will show that Voronkov's inverse method for the modal logic
K can be seen as an on-the-fly realization of the emptiness test done by the
automata approach for K. The benefits of this result are two-fold. First, it
shows that Voronkov's implementation of the inverse method, which behaves quite
well in practice, is an optimized on-the-fly implementation of the
automata-based satisfiability procedure for K. Second, it can be used to give a
simpler proof of the fact that Voronkov's optimizations do not destroy
completeness of the procedure. We will also show that the inverse method can
easily be extended to handle global axioms, and that the correspondence to the
automata approach still holds in this setting. In particular, the inverse
method yields an EXPTIME-algorithm for satisfiability in K w.r.t. global
axioms.


title: Quantum Interactive Proofs with Competing Provers

abstract:
  This paper studies quantum refereed games, which are quantum interactive
proof systems with two competing provers: one that tries to convince the
verifier to accept and the other that tries to convince the verifier to reject.
We prove that every language having an ordinary quantum interactive proof
system also has a quantum refereed game in which the verifier exchanges just
one round of messages with each prover. A key part of our proof is the fact
that there exists a single quantum measurement that reliably distinguishes
between mixed states chosen arbitrarily from disjoint convex sets having large
minimal trace distance from one another. We also show how to reduce the
probability of error for some classes of quantum refereed games.


title:
Chosen-Plaintext Cryptanalysis of a Clipped-Neural-Network-Based Chaotic
  Cipher

abstract:
  In ISNN'04, a novel symmetric cipher was proposed, by combining a chaotic
signal and a clipped neural network (CNN) for encryption. The present paper
analyzes the security of this chaotic cipher against chosen-plaintext attacks,
and points out that this cipher can be broken by a chosen-plaintext attack.
Experimental analyses are given to support the feasibility of the proposed
attack.


title: Negotiating over Bundles and Prices Using Aggregate Knowledge

abstract:
  Combining two or more items and selling them as one good, a practice called
bundling, can be a very effective strategy for reducing the costs of producing,
marketing, and selling goods. In this paper, we consider a form of multi-issue
negotiation where a shop negotiates both the contents and the price of bundles
of goods with his customers. We present some key insights about, as well as a
technique for, locating mutually beneficial alternatives to the bundle
currently under negotiation. The essence of our approach lies in combining
historical sales data, condensed into aggregate knowledge, with current data
about the ongoing negotiation process, to exploit these insights. In
particular, when negotiating a given bundle of goods with a customer, the shop
analyzes the sequence of the customer's offers to determine the progress in the
negotiation process. In addition, it uses aggregate knowledge concerning
customers' valuations of goods in general. We show how the shop can use these
two sources of data to locate promising alternatives to the current bundle.
When the current negotiation's progress slows down, the shop may suggest the
most promising of those alternatives and, depending on the customer's response,
continue negotiating about the alternative bundle, or propose another
alternative. Extensive computer simulation experiments show that our approach
increases the speed with which deals are reached, as well as the number and
quality of the deals reached, as compared to a benchmark. In addition, we show
that the performance of our system is robust to a variety of changes in the
negotiation strategies employed by the customers.


title: On the existence of stable models of non-stratified logic programs

abstract:
  This paper introduces a fundamental result, which is relevant for Answer Set
programming, and planning. For the first time since the definition of the
stable model semantics, the class of logic programs for which a stable model
exists is given a syntactic characterization. This condition may have a
practical importance both for defining new algorithms for checking consistency
and computing answer sets, and for improving the existing systems. The approach
of this paper is to introduce a new canonical form (to which any logic program
can be reduced to), to focus the attention on cyclic dependencies. The
technical result is then given in terms of programs in canonical form
(canonical programs), without loss of generality. The result is based on
identifying the cycles contained in the program, showing that stable models of
the overall program are composed of stable models of suitable sub-programs,
corresponding to the cycles, and on defining the Cycle Graph. Each vertex of
this graph corresponds to one cycle, and each edge corresponds to onehandle,
which is a literal containing an atom that, occurring in both cycles, actually
determines a connection between them. In fact, the truth value of the handle in
the cycle where it appears as the head of a rule, influences the truth value of
the atoms of the cycle(s) where it occurs in the body. We can therefore
introduce the concept of a handle path, connecting different cycles. If for
every odd cycle we can find a handle path with certain properties, then the
existence of stable model is guaranteed.


title:
Online Learning of Aggregate Knowledge about Non-linear Preferences
  Applied to Negotiating Prices and Bundles

abstract:
  In this paper, we consider a form of multi-issue negotiation where a shop
negotiates both the contents and the price of bundles of goods with his
customers. We present some key insights about, as well as a procedure for,
locating mutually beneficial alternatives to the bundle currently under
negotiation. The essence of our approach lies in combining aggregate
(anonymous) knowledge of customer preferences with current data about the
ongoing negotiation process. The developed procedure either works with already
obtained aggregate knowledge or, in the absence of such knowledge, learns the
relevant information online. We conduct computer experiments with simulated
customers that have_nonlinear_ preferences. We show how, for various types of
customers, with distinct negotiation heuristics, our procedure (with and
without the necessary aggregate knowledge) increases the speed with which deals
are reached, as well as the number and the Pareto efficiency of the deals
reached compared to a benchmark.


title: A Monte Carlo algorithm for efficient large matrix inversion

abstract:
  This paper introduces a new Monte Carlo algorithm to invert large matrices.
It is based on simultaneous coupled draws from two random vectors whose
covariance is the required inverse. It can be considered a generalization of a
previously reported algorithm for hermitian matrices inversion based in only
one draw. The use of two draws allows the inversion on non-hermitian matrices.
Both the conditions for convergence and the rate of convergence are similar to
the Gauss-Seidel algorithm. Results on two examples are presented, a real
non-symmetric matrix related to quantitative genetics and a complex
non-hermitian matrix relevant for physicists. Compared with other Monte Carlo
algorithms it reveals a large reduction of the processing time showing eight
times faster processing in the examples studied.


title: Mutual Information and Minimum Mean-square Error in Gaussian Channels

abstract:
  This paper deals with arbitrarily distributed finite-power input signals
observed through an additive Gaussian noise channel. It shows a new formula
that connects the input-output mutual information and the minimum mean-square
error (MMSE) achievable by optimal estimation of the input given the output.
That is, the derivative of the mutual information (nats) with respect to the
signal-to-noise ratio (SNR) is equal to half the MMSE, regardless of the input
statistics. This relationship holds for both scalar and vector signals, as well
as for discrete-time and continuous-time noncausal MMSE estimation. This
fundamental information-theoretic result has an unexpected consequence in
continuous-time nonlinear estimation: For any input signal with finite power,
the causal filtering MMSE achieved at SNR is equal to the average value of the
noncausal smoothing MMSE achieved with a channel whose signal-to-noise ratio is
chosen uniformly distributed between 0 and SNR.


title: Global minimization of a quadratic functional: neural network approach

abstract:
  The problem of finding out the global minimum of a multiextremal functional
is discussed. One frequently faces with such a functional in various
applications. We propose a procedure, which depends on the dimensionality of
the problem polynomially. In our approach we use the eigenvalues and
eigenvectors of the connection matrix.


title:
Q-valued neural network as a system of fast identification and pattern
  recognition

abstract:
  An effective neural network algorithm of the perceptron type is proposed. The
algorithm allows us to identify strongly distorted input vector reliably. It is
shown that its reliability and processing speed are orders of magnitude higher
than that of full connected neural networks. The processing speed of our
algorithm exceeds the one of the stack fast-access retrieval algorithm that is
modified for working when there are noises in the input channel.


title: On the asymptotic accuracy of the union bound

abstract:
  A new lower bound on the error probability of maximum likelihood decoding of
a binary code on a binary symmetric channel was proved in Barg and McGregor
(2004, cs.IT/0407011). It was observed in that paper that this bound leads to a
new region of code rates in which the random coding exponent is asymptotically
tight, giving a new region in which the reliability of the BSC is known
exactly. The present paper explains the relation of these results to the union
bound on the error probability.


title: Source Coding With Encoder Side Information

abstract:
  We introduce the idea of distortion side information, which does not directly
depend on the source but instead affects the distortion measure. We show that
such distortion side information is not only useful at the encoder, but that
under certain conditions, knowing it at only the encoder is as good as knowing
it at both encoder and decoder, and knowing it at only the decoder is useless.
Thus distortion side information is a natural complement to the signal side
information studied by Wyner and Ziv, which depends on the source but does not
involve the distortion measure. Furthermore, when both types of side
information are present, we characterize the penalty for deviating from the
configuration of encoder-only distortion side information and decoder-only
signal side information, which in many cases is as good as full side
information knowledge.


title: Source-Channel Diversity for Parallel Channels

abstract:
  We consider transmitting a source across a pair of independent, non-ergodic
channels with random states (e.g., slow fading channels) so as to minimize the
average distortion. The general problem is unsolved. Hence, we focus on
comparing two commonly used source and channel encoding systems which
correspond to exploiting diversity either at the physical layer through
parallel channel coding or at the application layer through multiple
description source coding.
  For on-off channel models, source coding diversity offers better performance.
For channels with a continuous range of reception quality, we show the reverse
is true. Specifically, we introduce a new figure of merit called the distortion
exponent which measures how fast the average distortion decays with SNR. For
continuous-state models such as additive white Gaussian noise channels with
multiplicative Rayleigh fading, optimal channel coding diversity at the
physical layer is more efficient than source coding diversity at the
application layer in that the former achieves a better distortion exponent.
  Finally, we consider a third decoding architecture: multiple description
encoding with a joint source-channel decoding. We show that this architecture
achieves the same distortion exponent as systems with optimal channel coding
diversity for continuous-state channels, and maintains the the advantages of
multiple description systems for on-off channels. Thus, the multiple
description system with joint decoding achieves the best performance, from
among the three architectures considered, on both continuous-state and on-off
channels.


title:
State of the Art, Evaluation and Recommendations regarding "Document
  Processing and Visualization Techniques"

abstract:
  Several Networks of Excellence have been set up in the framework of the
European FP5 research program. Among these Networks of Excellence, the NEMIS
project focuses on the field of Text Mining.
  Within this field, document processing and visualization was identified as
one of the key topics and the WG1 working group was created in the NEMIS
project, to carry out a detailed survey of techniques associated with the text
mining process and to identify the relevant research topics in related research
areas.
  In this document we present the results of this comprehensive survey. The
report includes a description of the current state-of-the-art and practice, a
roadmap for follow-up research in the identified areas, and recommendations for
anticipated technological development in the domain of text mining.


title:
Reductions in Distributed Computing Part I: Consensus and Atomic
  Commitment Tasks

abstract:
  We introduce several notions of reduction in distributed computing, and
investigate reduction properties of two fundamental agreement tasks, namely
Consensus and Atomic Commitment.
  We first propose the notion of reduction "a la Karp'', an analog for
distributed computing of the classical Karp reduction. We then define a weaker
reduction which is the analog of Cook reduction. These two reductions are
called K-reduction and C-reduction, respectively.
  We also introduce the notion of C*-reduction which has no counterpart in
classical (namely, non distributed) systems, and which naturally arises when
dealing with symmetric tasks.
  We establish various reducibility and irreducibility theorems with respect to
these three reductions. Our main result is an incomparability statement for
Consensus and Atomic Commitment tasks: we show that they are incomparable with
respect to the C-reduction, except when the resiliency degree is 1, in which
case Atomic Commitment is strictly harder than Consensus. A side consequence of
these results is that our notion of C-reduction is strictly weaker than the one
of K-reduction, even for unsolvable tasks.


title: Reductions in Distributed Computing Part II: k-Threshold Agreement Tasks

abstract:
  We extend the results of Part I by considering a new class of agreement
tasks, the so-called k-Threshold Agreement tasks (previously introduced by
Charron-Bost and Le Fessant). These tasks naturally interpolate between Atomic
Commitment and Consensus. Moreover, they constitute a valuable tool to derive
irreducibility results between Consensus tasks only. In particular, they allow
us to show that (A) for a fixed set of processes, the higher the resiliency
degree is, the harder the Consensus task is, and (B) for a fixed resiliency
degree, the smaller the set of processes is, the harder the Consensus task is.
  The proofs of these results lead us to consider new oracle-based reductions,
involving a weaker variant of the C-reduction introduced in Part I. We also
discuss the relationship between our results and previous ones relating
f-resiliency and wait-freedom.


title: Thematic Annotation: extracting concepts out of documents

abstract:
  Contrarily to standard approaches to topic annotation, the technique used in
this work does not centrally rely on some sort of -- possibly statistical --
keyword extraction. In fact, the proposed annotation algorithm uses a large
scale semantic database -- the EDR Electronic Dictionary -- that provides a
concept hierarchy based on hyponym and hypernym relations. This concept
hierarchy is used to generate a synthetic representation of the document by
aggregating the words present in topically homogeneous document segments into a
set of concepts best preserving the document's content.
  This new extraction technique uses an unexplored approach to topic selection.
Instead of using semantic similarity measures based on a semantic resource, the
later is processed to extract the part of the conceptual hierarchy relevant to
the document content. Then this conceptual hierarchy is searched to extract the
most relevant set of concepts to represent the topics discussed in the
document. Notice that this algorithm is able to extract generic concepts that
are not directly present in the document.


title: Power Aware Routing for Sensor Databases

abstract:
  Wireless sensor networks offer the potential to span and monitor large
geographical areas inexpensively. Sensor network databases like TinyDB are the
dominant architectures to extract and manage data in such networks. Since
sensors have significant power constraints (battery life), and high
communication costs, design of energy efficient communication algorithms is of
great importance. The data flow in a sensor database is very different from
data flow in an ordinary network and poses novel challenges in designing
efficient routing algorithms. In this work we explore the problem of energy
efficient routing for various different types of database queries and show that
in general, this problem is NP-complete. We give a constant factor
approximation algorithm for one class of query, and for other queries give
heuristic algorithms. We evaluate the efficiency of the proposed algorithms by
simulation and demonstrate their near optimal performance for various network
sizes.


title: CDTP Chain Distributed Transfer Protocol

abstract:
  The rapid growth of the internet in general and of bandwidth capacity at
internet clients in particular poses increasing computation and bandwidth
demands on internet servers. Internet access technologies like ADSL [DSL],
Cable Modem and Wireless modem allow internet clients to access the internet
with orders of magnitude more bandwidth than using traditional modems. We
present CDTP a distributed transfer protocol that allows clients to cooperate
and therefore remove the strain from the internet server thus achieving much
better performance than traditional transfer protocols (e.g. FTP [FTP]). The
CDTP server and client tools are presented also as well as results of
experiments. Finally a bandwidth measurement technique is presented. CDTP tools
use this technique to differentiate between slow and fast clients.


title:
An estimate of accuracy for interpolant numerical solutions of a PDE
  problem

abstract:
  In this paper we present an estimate of accuracy for a piecewise polynomial
approximation of a classical numerical solution to a non linear differential
problem. We suppose the numerical solution U is computed using a grid with a
small linear step and interval time Tu, while the polynomial approximation V is
an interpolation of the values of a numerical solution on a less fine grid and
interval time Tv << Tu. The estimate shows that the interpolant solution V can
be, under suitable hypotheses, a good approximation and in general its
computational cost is much lower of the cost of the fine numerical solution. We
present two possible applications to linear case and periodic case.


title: A Distributed Economics-based Infrastructure for Utility Computing

abstract:
  Existing attempts at utility computing revolve around two approaches. The
first consists of proprietary solutions involving renting time on dedicated
utility computing machines. The second requires the use of heavy, monolithic
applications that are difficult to deploy, maintain, and use.
  We propose a distributed, community-oriented approach to utility computing.
Our approach provides an infrastructure built on Web Services in which modular
components are combined to create a seemingly simple, yet powerful system. The
community-oriented nature generates an economic environment which results in
fair transactions between consumers and providers of computing cycles while
simultaneously encouraging improvements in the infrastructure of the
computational grid itself.


title: A Survey of Distributed Intrusion Detection Approaches

abstract:
  Distributed intrustion detection systems detect attacks on computer systems
by analyzing data aggregated from distributed sources. The distributed nature
of the data sources allows patterns in the data to be seen that might not be
detectable if each of the sources were examined individually. This paper
describes the various approaches that have been developed to share and analyze
data in such systems, and discusses some issues that must be addressed before
fully decentralized distributed intrusion detection systems can be made viable.


title:
A Survey of Fault-Tolerance and Fault-Recovery Techniques in Parallel
  Systems

abstract:
  Supercomputing systems today often come in the form of large numbers of
commodity systems linked together into a computing cluster. These systems, like
any distributed system, can have large numbers of independent hardware
components cooperating or collaborating on a computation. Unfortunately, any of
this vast number of components can fail at any time, resulting in potentially
erroneous output. In order to improve the robustness of supercomputing
applications in the presence of failures, many techniques have been developed
to provide resilience to these kinds of system faults. This survey provides an
overview of these various fault-tolerance techniques.


title: Implementation of Motzkin-Burger algorithm in Maple

abstract:
  Subject of this paper is an implementation of a well-known Motzkin-Burger
algorithm, which solves the problem of finding the full set of solutions of a
system of linear homogeneous inequalities. There exist a number of
implementations of this algorithm, but there was no one in Maple, to the best
of the author's knowledge.


title:
Advances towards a General-Purpose Societal-Scale Human-Collective
  Problem-Solving Engine

abstract:
  Human collective intelligence has proved itself as an important factor in a
society's ability to accomplish large-scale behavioral feats. As societies have
grown in population-size, individuals have seen a decrease in their ability to
activeily participate in the problem-solving processes of the group.
Representative decision-making structures have been used as a modern solution
to society's inadequate information-processing infrastructure. With computer
and network technologies being further embedded within the fabric of society,
the implementation of a general-purpose societal-scale human-collective
problem-solving engine is envisioned as a means of furthering the
collective-intelligence potential of society. This paper provides both a novel
framework for creating collective intelligence systems and a method for
implementing a representative and expertise system based on social-network
theory.


title: Portfolio selection using neural networks

abstract:
  In this paper we apply a heuristic method based on artificial neural networks
in order to trace out the efficient frontier associated to the portfolio
selection problem. We consider a generalization of the standard Markowitz
mean-variance model which includes cardinality and bounding constraints. These
constraints ensure the investment in a given number of different assets and
limit the amount of capital to be invested in each asset. We present some
experimental results obtained with the neural network heuristic and we compare
them to those obtained with three previous heuristic methods.


title:
Formal Languages and Algorithms for Similarity based Retrieval from
  Sequence Databases

abstract:
  The paper considers various formalisms based on Automata, Temporal Logic and
Regular Expressions for specifying queries over sequences. Unlike traditional
binary semantics, the paper presents a similarity based semantics for thse
formalisms. More specifically, a distance measure in the range [0,1] is
associated with a sequence, query pair denoting how closely the sequence
satisfies the query. These measures are defined using a spectrum of normed
vector distance measures. Various distance measures based on the syntax and the
traditional semantics of the query are presented. Efficient algorithms for
computing these distance measure are presented. These algorithms can be
employed for retrieval of sequence from a database that closely satisfy a
given.


title: A Time-Optimal Delaunay Refinement Algorithm in Two Dimensions

abstract:
  We propose a new refinement algorithm to generate size-optimal
quality-guaranteed Delaunay triangulations in the plane. The algorithm takes
$O(n \log n + m)$ time, where $n$ is the input size and $m$ is the output size.
This is the first time-optimal Delaunay refinement algorithm.


title: Multipartite Secret Correlations and Bound Information

abstract:
  We consider the problem of secret key extraction when $n$ honest parties and
an eavesdropper share correlated information. We present a family of
probability distributions and give the full characterization of its
distillation properties. This formalism allows us to design a rich variety of
cryptographic scenarios. In particular, we provide examples of multipartite
probability distributions containing non-distillable secret correlations, also
known as bound information.


title: On The Liniar Time Complexity of Finite Languages

abstract:
  The present paper presents and proves a proposition concerning the time
complexity of finite languages. It is shown herein, that for any finite
language (a language for which the set of words composing it is finite) there
is a Turing machine that computes the language in such a way that for any input
of length k the machine stops in, at most, k + 1 steps.


title: A Cryptographic Study of Some Digital Signature Schemes

abstract:
  In this thesis, we propose some directed signature schemes. In addition, we
have discussed their applications in different situations. In this thesis, we
would like to discuss the security aspects during the design process of the
proposed directed digital signature schemes. The security of the most digital
signature schemes widely use in practice is based on the two difficult
problems, viz; the problem of factoring integers (The RSA scheme) and the
problem of finding discrete logarithms over finite fields (The ElGamal scheme).
The proposed works in this thesis is divided into seven chapters.


title:
A simple algorithm for decoding Reed-Solomon codes and its relation to
  the Welch-Berlekamp algorithm

abstract:
  A simple and natural Gao algorithm for decoding algebraic codes is described.
Its relation to the Welch-Berlekamp and Euclidean algorithms is given.


title: Fedora: An Architecture for Complex Objects and their Relationships

abstract:
  The Fedora architecture is an extensible framework for the storage,
management, and dissemination of complex objects and the relationships among
them. Fedora accommodates the aggregation of local and distributed content into
digital objects and the association of services with objects. This al-lows an
object to have several accessible representations, some of them dy-namically
produced. The architecture includes a generic RDF-based relation-ship model
that represents relationships among objects and their components. Queries
against these relationships are supported by an RDF triple store. The
architecture is implemented as a web service, with all aspects of the complex
object architecture and related management functions exposed through REST and
SOAP interfaces. The implementation is available as open-source soft-ware,
providing the foundation for a variety of end-user applications for digital
libraries, archives, institutional repositories, and learning object systems.


title:
On the security of the Yen-Guo's domino signal encryption algorithm
  (DSEA)

abstract:
  Recently, a new domino signal encryption algorithm (DSEA) was proposed for
digital signal transmission, especially for digital images and videos. This
paper analyzes the security of DSEA, and points out the following weaknesses:
1) its security against the brute-force attack was overestimated; 2) it is not
sufficiently secure against ciphertext-only attacks, and only one ciphertext is
enough to get some information about the plaintext and to break the value of a
sub-key; 3) it is insecure against known/chosen-plaintext attacks, in the sense
that the secret key can be recovered from a number of continuous bytes of only
one known/chosen plaintext and the corresponding ciphertext. Experimental
results are given to show the performance of the proposed attacks, and some
countermeasures are discussed to improve DSEA.


title: On the Design of Perceptual MPEG-Video Encryption Algorithms

abstract:
  In this paper, some existing perceptual encryption algorithms of MPEG videos
are reviewed and some problems, especially security defects of two recently
proposed MPEG-video perceptual encryption schemes, are pointed out. Then, a
simpler and more effective design is suggested, which selectively encrypts
fixed-length codewords (FLC) in MPEG-video bitstreams under the control of
three perceptibility factors. The proposed design is actually an encryption
configuration that can work with any stream cipher or block cipher. Compared
with the previously-proposed schemes, the new design provides more useful
features, such as strict size-preservation, on-the-fly encryption and multiple
perceptibility, which make it possible to support more applications with
different requirements. In addition, four different measures are suggested to
provide better security against known/chosen-plaintext attacks.


title:
Application of Generating Functions and Partial Differential Equations
  in Coding Theory

abstract:
  In this work we have considered formal power series and partial differential
equations, and their relationship with Coding Theory. We have obtained the
nature of solutions for the partial differential equations for Cycle Poisson
Case. The coefficients for this case have been simulated, and the high tendency
of growth is shown. In the light of Complex Analysis, the Hadamard
Multiplication's Theorem is presented as a new approach to divide the power
sums relating to the error probability, each part of which can be analyzed
later.


title: On the weight distribution of convolutional codes

abstract:
  Detailed information about the weight distribution of a convolutional code is
given by the adjacency matrix of the state diagram associated with a controller
canonical form of the code. We will show that this matrix is an invariant of
the code. Moreover, it will be proven that codes with the same adjacency matrix
have the same dimension and the same Forney indices and finally that for
one-dimensional binary convolutional codes the adjacency matrix determines the
code uniquely up to monomial equivalence.


title: Public Key Cryptography based on Semigroup Actions

abstract:
  A generalization of the original Diffie-Hellman key exchange in $(\Z/p\Z)^*$
found a new depth when Miller and Koblitz suggested that such a protocol could
be used with the group over an elliptic curve. In this paper, we propose a
further vast generalization where abelian semigroups act on finite sets. We
define a Diffie-Hellman key exchange in this setting and we illustrate how to
build interesting semigroup actions using finite (simple) semirings. The
practicality of the proposed extensions rely on the orbit sizes of the
semigroup actions and at this point it is an open question how to compute the
sizes of these orbits in general and also if there exists a square root attack
in general. In Section 2 a concrete practical semigroup action built from
simple semirings is presented. It will require further research to analyse this
system.


title: Combining Independent Modules in Lexical Multiple-Choice Problems

abstract:
  Existing statistical approaches to natural language problems are very coarse
approximations to the true complexity of language processing. As such, no
single technique will be best for all problem instances. Many researchers are
examining ensemble methods that combine the output of multiple modules to
create more accurate solutions. This paper examines three merging rules for
combining probability distributions: the familiar mixture rule, the logarithmic
rule, and a novel product rule. These rules were applied with state-of-the-art
results to two problems used to assess human mastery of lexical semantics --
synonym questions and analogy questions. All three merging rules result in
ensembles that are more accurate than any of their component modules. The
differences among the three rules are not statistically significant, but it is
suggestive that the popular mixture rule is not the best rule for either of the
two problems.


title: Clustering SPIRES with EqRank

abstract:
  SPIRES is the largest database of scientific papers in the subject field of
high energy and nuclear physics. It contains information on the citation graph
of more than half a million of papers (vertexes of the citation graph). We
outline the EqRank algorithm designed to cluster vertexes of directed graphs,
and present the results of EqRank application to the SPIRES citation graph. The
hierarchical clustering of SPIRES yielded by EqRank is used to set up a web
service, which is also outlined.


title: Enhancing Histograms by Tree-Like Bucket Indices

abstract:
  Histograms are used to summarize the contents of relations into a number of
buckets for the estimation of query result sizes. Several techniques (e.g.,
MaxDiff and V-Optimal) have been proposed in the past for determining bucket
boundaries which provide accurate estimations. However, while search strategies
for optimal bucket boundaries are rather sophisticated, no much attention has
been paid for estimating queries inside buckets and all of the above techniques
adopt naive methods for such an estimation. This paper focuses on the problem
of improving the estimation inside a bucket once its boundaries have been
fixed. The proposed technique is based on the addition, to each bucket, of
32-bit additional information (organized into a 4-level tree index), storing
approximate cumulative frequencies at 7 internal intervals of the bucket. Both
theoretical analysis and experimental results show that, among a number of
alternative ways to organize the additional information, the 4-level tree index
provides the best frequency estimation inside a bucket. The index is later
added to two well-known histograms, MaxDiff and V-Optimal, obtaining the
non-obvious result that despite the spatial cost of 4LT which reduces the
number of allowed buckets once the storage space has been fixed, the original
methods are strongly improved in terms of accuracy.


title:
Large-scale lattice Boltzmann simulations of complex fluids: advances
  through the advent of computational grids

abstract:
  During the last two years the RealityGrid project has allowed us to be one of
the few scientific groups involved in the development of computational grids.
Since smoothly working production grids are not yet available, we have been
able to substantially influence the direction of software development and grid
deployment within the project. In this paper we review our results from large
scale three-dimensional lattice Boltzmann simulations performed over the last
two years. We describe how the proactive use of computational steering and
advanced job migration and visualization techniques enabled us to do our
scientific work more efficiently. The projects reported on in this paper are
studies of complex fluid flows under shear or in porous media, as well as
large-scale parameter searches, and studies of the self-organisation of liquid
cubic mesophases.
  Movies are available at
http://www.ica1.uni-stuttgart.de/~jens/pub/05/05-PhilTransReview.html

categories: cs.DC cond-mat.other cond-mat.soft physics.flu-dyn


title: Algebraic Properties for Selector Functions

abstract:
  The nondeterministic advice complexity of the P-selective sets is known to be
exactly linear. Regarding the deterministic advice complexity of the
P-selective sets--i.e., the amount of Karp--Lipton advice needed for
polynomial-time machines to recognize them in general--the best current upper
bound is quadratic [Ko, 1983] and the best current lower bound is linear
[Hemaspaandra and Torenvliet, 1996].
  We prove that every associatively P-selective set is commutatively,
associatively P-selective. Using this, we establish an algebraic sufficient
condition for the P-selective sets to have a linear upper bound (which thus
would match the existing lower bound) on their deterministic advice complexity:
If all P-selective sets are associatively P-selective then the deterministic
advice complexity of the P-selective sets is linear. The weakest previously
known sufficient condition was P=NP.
  We also establish related results for algebraic properties of, and advice
complexity of, the nondeterministically selective sets.


abstract:
  Existing quantum key distribution schemes need the support of classical
authentication scheme to ensure security. This is a conceptual drawback of
quantum cryptography. It is pointed out that quantum cryptosystem does not need
any support of classical cryptosystem to ensure security. No-cloning principal
can alone provide security in communication. Even no-cloning principle itself
can help to authenticate each bit of information. It implies that quantum
password need not to be a secret password.


title: Effectively Open Real Functions

abstract:
  A function f is continuous iff the PRE-image f^{-1}[V] of any open set V is
open again. Dual to this topological property, f is called OPEN iff the IMAGE
f[U] of any open set U is open again. Several classical Open Mapping Theorems
in Analysis provide a variety of sufficient conditions for openness.
  By the Main Theorem of Recursive Analysis, computable real functions are
necessarily continuous. In fact they admit a well-known characterization in
terms of the mapping V+->f^{-1}[V] being EFFECTIVE: Given a list of open
rational balls exhausting V, a Turing Machine can generate a corresponding list
for f^{-1}[V]. Analogously, EFFECTIVE OPENNESS requires the mapping U+->f[U] on
open real subsets to be effective.
  By effectivizing classical Open Mapping Theorems as well as from application
of Tarski's Quantifier Elimination, the present work reveals several rich
classes of functions to be effectively open.


title: A Logic for Non-Monotone Inductive Definitions

abstract:
  Well-known principles of induction include monotone induction and different
sorts of non-monotone induction such as inflationary induction, induction over
well-founded sets and iterated induction. In this work, we define a logic
formalizing induction over well-founded sets and monotone and iterated
induction. Just as the principle of positive induction has been formalized in
FO(LFP), and the principle of inflationary induction has been formalized in
FO(IFP), this paper formalizes the principle of iterated induction in a new
logic for Non-Monotone Inductive Definitions (ID-logic). The semantics of the
logic is strongly influenced by the well-founded semantics of logic
programming. Our main result concerns the modularity properties of inductive
definitions in ID-logic. Specifically, we formulate conditions under which a
simultaneous definition $\D$ of several relations is logically equivalent to a
conjunction of smaller definitions $\D_1 \land ... \land \D_n$ with disjoint
sets of defined predicates. The difficulty of the result comes from the fact
that predicates $P_i$ and $P_j$ defined in $\D_i$ and $\D_j$, respectively, may
be mutually connected by simultaneous induction. Since logic programming and
abductive logic programming under well-founded semantics are proper fragments
of our logic, our modularity results are applicable there as well.


title: On the Sensitivity of Cyclically-Invariant Boolean Functions

abstract:
  In this paper we construct a cyclically invariant Boolean function whose
sensitivity is $\Theta(n^{1/3})$. This result answers two previously published
questions. Tur\'an (1984) asked if any Boolean function, invariant under some
transitive group of permutations, has sensitivity $\Omega(\sqrt{n})$. Kenyon
and Kutin (2004) asked whether for a ``nice'' function the product of
0-sensitivity and 1-sensitivity is $\Omega(n)$. Our function answers both
questions in the negative.
  We also prove that for minterm-transitive functions (a natural class of
Boolean functions including our example) the sensitivity is $\Omega(n^{1/3})$.
Hence for this class of functions sensitivity and block sensitivity are
polynomially related.


title: Enforcing Bulk Mail Classification

abstract:
  Spam costs US corporations upwards of $8.9 billion a year, and comprises as
much as 40% of all email received. Solutions exist to reduce the amount of spam
seen by end users, but cannot withstand sophisticated attacks. Worse yet, many
will occasionally misclassify and silently drop legitimate email. Spammers take
advantage of the near-zero cost of sending email to flood the network, knowing
that success even a tiny fraction of the time means a profit. End users,
however, have proven unwilling to pay money to send email to friends and
family.
  We show that it is feasible to extend the existing mail system to reduce the
amount of unwanted email, without misclassifying email, and without charging
well-behaved users. We require that bulk email senders accurately classify each
email message they send as an advertisement with an area of interest or else be
charged a small negative incentive per message delivered. Recipients are able
to filter out email outside their scope of interest, while senders are able to
focus their sendings to the appropriate audience.


title:
An Empirical Study of MDL Model Selection with Infinite Parametric
  Complexity

abstract:
  Parametric complexity is a central concept in MDL model selection. In
practice it often turns out to be infinite, even for quite simple models such
as the Poisson and Geometric families. In such cases, MDL model selection as
based on NML and Bayesian inference based on Jeffreys' prior can not be used.
Several ways to resolve this problem have been proposed. We conduct experiments
to compare and evaluate their behaviour on small sample sizes.
  We find interestingly poor behaviour for the plug-in predictive code; a
restricted NML model performs quite well but it is questionable if the results
validate its theoretical motivation. The Bayesian model with the improper
Jeffreys' prior is the most dependable.


title:
Estimating Range Queries using Aggregate Data with Integrity
  Constraints: a Probabilistic Approach

abstract:
  The problem of recovering (count and sum) range queries over multidimensional
data only on the basis of aggregate information on such data is addressed. This
problem can be formalized as follows. Suppose that a transformation T producing
a summary from a multidimensional data set is used. Now, given a data set D, a
summary S=T(D) and a range query r on D, the problem consists of studying r by
modelling it as a random variable defined over the sample space of all the data
sets D' such that T(D) = S. The study of such a random variable, done by the
definition of its probability distribution and the computation of its mean
value and variance, represents a well-founded, theoretical probabilistic
approach for estimating the query only on the basis of the available
information (that is the summary S) without assumptions on original data.


title:
Generalized Laplace transformations and integration of hyperbolic
  systems of linear partial differential equations

abstract:
  We give a new procedure for generalized factorization and construction of the
complete solution of strictly hyperbolic linear partial differential equations
or strictly hyperbolic systems of such equations in the plane. This procedure
generalizes the classical theory of Laplace transformations of second-order
equations in the plane.


title: From truth to computability II

abstract:
  Computability logic is a formal theory of computational tasks and resources.
Formulas in it represent interactive computational problems, and "truth" is
understood as algorithmic solvability. Interactive computational problems, in
turn, are defined as a certain sort games between a machine and its
environment, with logical operators standing for operations on such games.
Within the ambitious program of finding axiomatizations for incrementally rich
fragments of this semantically introduced logic, the earlier article "From
truth to computability I" proved soundness and completeness for system CL3,
whose language has the so called parallel connectives (including negation),
choice connectives, choice quantifiers, and blind quantifiers. The present
paper extends that result to the significantly more expressive system CL4 with
the same collection of logical operators. What makes CL4 expressive is the
presence of two sorts of atoms in its language: elementary atoms, representing
elementary computational problems (i.e. predicates, i.e. problems of zero
degree of interactivity), and general atoms, representing arbitrary
computational problems. CL4 conservatively extends CL3, with the latter being
nothing but the general-atom-free fragment of the former. Removing the blind
(classical) group of quantifiers from the language of CL4 is shown to yield a
decidable logic despite the fact that the latter is still first-order. A
comprehensive online source on computability logic can be found at
http://www.cis.upenn.edu/~giorgi/cl.html


title: On Partially Additive Kleene Algebras

abstract:
  We define the notion of a partially additive Kleene algebra, which is a
Kleene algebra where the + operation need only be partially defined. These
structures formalize a number of examples that cannot be handled directly by
Kleene algebras. We relate partially additive Kleene algebras to existing
algebraic structures, by exhibiting categorical connections with Kleene
algebras, partially additive categories, and closed semirings.


title: Playful, streamlike computation

abstract:
  We offer a short tour into the interactive interpretation of sequential
programs. We emphasize streamlike computation -- that is, computation of
successive bits of information upon request. The core of the approach surveyed
here dates back to the work of Berry and the author on sequential algorithms on
concrete data structures in the late seventies, culminating in the design of
the programming language CDS, in which the semantics of programs of any type
can be explored interactively. Around one decade later, two major insights of
Cartwright and Felleisen on one hand, and of Lamarche on the other hand gave
new, decisive impulses to the study of sequentiality. Cartwright and Felleisen
observed that sequential algorithms give a direct semantics to control
operators like \"call-cc\" and proposed to include explicit errors both in the
syntax and in the semantics of the language PCF. Lamarche (unpublished)
connected sequential algorithms to linear logic and games. The successful
program of games semantics has spanned over the nineties until now, starting
with syntax-independent characterizations of the term model of PCF by Abramsky,
Jagadeesan, and Malacaria on one hand, and by Hyland and Ong on the other hand.


title: Symmetry and interactivity in Programming

abstract:
  We recall some of the early occurrences of the notions of interactivity and
symmetry in the operational and denotational semantics of programming
languages. We suggest some connections with ludics.


title: Introduction to linear logic and ludics, part I

abstract:
  This two-parts paper offers a survey of linear logic and ludics, which were
introduced by Girard in 1986 and 2001, respectively. Both theories revisit
mathematical logic from first principles, with inspiration from and
applications to computer science. The present part I covers an introduction to
the connectives and proof rules of linear logic, to its decidability
properties, and to its models. Part II will deal with proof nets, a graph-like
representation of proofs which is one of the major innovations of linear logic,
and will present an introduction to ludics.


title: Enabling Agents to Dynamically Select Protocols for Interactions

abstract:
  in this paper we describe a method which allows agents to dynamically select
protocols and roles when they need to execute collaborative tasks


title:
Oligopolistic Competition in an Evolutionary Environment: a Computer
  Simulation

abstract:
  The following notes contain a computer simulation concerning effective
competition in an evolutionary environment. The scope is to underline the
existence of a side effect pertaining to the competitive processes: the
tendency toward an excess of supply by producers which operate in a strongly
competitive situation. A set of four oligopolistic firms will be employed in
the formal reconstruction. The simulation will operate following the Edmond
Malinvaud "short side" approach, as far as the price adjustment is concerned,
and the sequential Hicksian "weeks" structure with regard of the temporal
characterization. The content of the present paper ought to be considered as a
development of the writing: Michele Tucci, Evolution and Gravitation: a
Computer Simulation of a Non-Walrasian Equilibrium Model, published with the
E-print Archives at arXiv.com (section: Computer Science, registration number:
cs.CY/0209017). In such a paper there can be found some preliminary
considerations regarding the comparison between the evolutionary and the
gravitational paradigms and the evaluation of approaches belonging to rival
schools of economic thought.


title:
Data Tastes Better Seasoned: Introducing the ASH Family of Hashing
  Algorithms

abstract:
  Over the recent months it has become clear that the current generation of
cryptographic hashing algorithms are insufficient to meet future needs. The ASH
family of algorithms provides modifications to the existing SHA-2 family. These
modifications are designed with two main goals: 1) Providing increased
collision resistance. 2) Increasing mitigation of security risks
post-collision. The unique public/private sections and salt/pepper design
elements provide increased flexibility for a broad range of applications. The
ASH family is a new generation of cryptographic hashing algorithms.


title: Introduction to linear logic and ludics, part II

abstract:
  This paper is the second part of an introduction to linear logic and ludics,
both due to Girard. It is devoted to proof nets, in the limited, yet central,
framework of multiplicative linear logic and to ludics, which has been recently
developped in an aim of further unveiling the fundamental interactive nature of
computation and logic. We hope to offer a few computer science insights into
this new theory.


title:
Split-2 Bisimilarity has a Finite Axiomatization over CCS with<br>
  Hennessy's Merge

abstract:
  This note shows that split-2 bisimulation equivalence (also known as timed
equivalence) affords a finite equational axiomatization over the process
algebra obtained by adding an auxiliary operation proposed by Hennessy in 1981
to the recursion, relabelling and restriction free fragment of Milner's
Calculus of Communicating Systems. Thus the addition of a single binary
operation, viz. Hennessy's merge, is sufficient for the finite equational
axiomatization of parallel composition modulo this non-interleaving
equivalence. This result is in sharp contrast to a theorem previously obtained
by the same authors to the effect that the same language is not finitely based
modulo bisimulation equivalence.