title:
Les repr\'{e}sentations g\'{e}n\'{e}tiques d'objets : simples analogies
  ou mod\`{e}les pertinents ? Le point de vue de l'
  "\'{e}volutique".
–––
Genetic representations of
  objects : simple analogies or efficient models ? The "evolutic" point of view

abstract:
  Depuis une trentaine d'ann\'{e}es, les ing\'{e}nieurs utilisent couramment
des analogies avec l'\'{e}volution naturelle pour optimiser des dispositifs
techniques. Le plus souvent, ces m\'{e}thodes "g\'{e}n\'{e}tiques" ou
"\'{e}volutionnaires" sont consid\'{e}r\'{e}es uniquement du point de vue
pratique, comme des m\'{e}thodes d'optimisation performantes, qu'on peut
utiliser \`{a} la place d'autres m\'{e}thodes (gradients, simplexes, ...). Dans
cet article, nous essayons de montrer que les sciences et les techniques, mais
aussi les organisations humaines, et g\'{e}n\'{e}ralement tous les syst\`{e}mes
complexes, ob\'{e}issent \`{a} des lois d'\'{e}volution dont la
g\'{e}n\'{e}tique est un bon mod\`{e}le repr\'{e}sentatif, m\^{e}me si
g\^{e}nes et chromosomes sont "virtuels" : ainsi loin d'\^{e}tre seulement un
outil ponctuel d'aide \`{a} la synth\`{e}se de solutions technologiques, la
repr\'{e}sentation g\'{e}n\'{e}tique est-elle un mod\`{e}le dynamique global de
l'\'{e}volution du monde fa\c{c}onn\'{e} par l'agitation
humaine.––––For thirty years, engineers commonly use
analogies with natural evolution to optimize technical devices. More often that
not, these "genetic" or "evolutionary" methods are only view as efficient
tools, which could replace other optimization techniques (gradient methods,
simplex, ...). In this paper, we try to show that sciences, techniques, human
organizations, and more generally all complex systems, obey to evolution rules,
whose the genetic is a good representative model, even if genes and chromosomes
are "virtual". Thus, the genetic representation is not only a specific tool
helping for the design of technological solutions, but also a global and
dynamic model for the action of the human agitation on our world.


title: Multi-Dimensional Hash Chains and Application to Micropayment Schemes

abstract:
  One-way hash chains have been used in many micropayment schemes due to their
simplicity and efficiency. In this paper we introduce the notion of
multi-dimensional hash chains, which is a new generalization of traditional
one-way hash chains. We show that this construction has storage-computational
complexity of O(logN) per chain element, which is comparable with the best
result reported in recent literature. Based on multi-dimensional hash chains,
we then propose two cash-like micropayment schemes, which have a number of
advantages in terms of efficiency and security. We also point out some possible
improvements to PayWord and similar schemes by using multi-dimensional hash
chains


title: Integrity Constraints in Trust Management

abstract:
  We introduce the use, monitoring, and enforcement of integrity constraints in
trust management-style authorization systems. We consider what portions of the
policy state must be monitored to detect violations of integrity constraints.
Then we address the fact that not all participants in a trust management system
can be trusted to assist in such monitoring, and show how many integrity
constraints can be monitored in a conservative manner so that trusted
participants detect and report if the system enters a policy state from which
evolution in unmonitored portions of the policy could lead to a constraint
violation.


title:
On the Complexity of Nonrecursive XQuery and Functional Query Languages
  on Complex Values

abstract:
  This paper studies the complexity of evaluating functional query languages
for complex values such as monad algebra and the recursion-free fragment of
XQuery.
  We show that monad algebra with equality restricted to atomic values is
complete for the class TA[2^{O(n)}, O(n)] of problems solvable in linear
exponential time with a linear number of alternations. The monotone fragment of
monad algebra with atomic value equality but without negation is complete for
nondeterministic exponential time. For monad algebra with deep equality, we
establish TA[2^{O(n)}, O(n)] lower and exponential-space upper bounds.
  Then we study a fragment of XQuery, Core XQuery, that seems to incorporate
all the features of a query language on complex values that are traditionally
deemed essential. A close connection between monad algebra on lists and Core
XQuery (with ``child'' as the only axis) is exhibited, and it is shown that
these languages are expressively equivalent up to representation issues. We
show that Core XQuery is just as hard as monad algebra w.r.t. combined
complexity, and that it is in TC0 if the query is assumed fixed.


title: Randomly Spread CDMA: Asymptotics via Statistical Physics

abstract:
  This paper studies randomly spread code-division multiple access (CDMA) and
multiuser detection in the large-system limit using the replica method
developed in statistical physics. Arbitrary input distributions and flat fading
are considered. A generic multiuser detector in the form of the posterior mean
estimator is applied before single-user decoding. The generic detector can be
particularized to the matched filter, decorrelator, linear MMSE detector, the
jointly or the individually optimal detector, and others. It is found that the
detection output for each user, although in general asymptotically non-Gaussian
conditioned on the transmitted symbol, converges as the number of users go to
infinity to a deterministic function of a "hidden" Gaussian statistic
independent of the interferers. Thus the multiuser channel can be decoupled:
Each user experiences an equivalent single-user Gaussian channel, whose
signal-to-noise ratio suffers a degradation due to the multiple-access
interference. The uncoded error performance (e.g., symbol-error-rate) and the
mutual information can then be fully characterized using the degradation
factor, also known as the multiuser efficiency, which can be obtained by
solving a pair of coupled fixed-point equations identified in this paper. Based
on a general linear vector channel model, the results are also applicable to
MIMO channels such as in multiantenna systems.


title: Minimum-Cost Multicast over Coded Packet Networks

abstract:
  We consider the problem of establishing minimum-cost multicast connections
over coded packet networks, i.e. packet networks where the contents of outgoing
packets are arbitrary, causal functions of the contents of received packets. We
consider both wireline and wireless packet networks as well as both static
multicast (where membership of the multicast group remains constant for the
duration of the connection) and dynamic multicast (where membership of the
multicast group changes in time, with nodes joining and leaving the group).
  For static multicast, we reduce the problem to a polynomial-time solvable
optimization problem, and we present decentralized algorithms for solving it.
These algorithms, when coupled with existing decentralized schemes for
constructing network codes, yield a fully decentralized approach for achieving
minimum-cost multicast. By contrast, establishing minimum-cost static multicast
connections over routed packet networks is a very difficult problem even using
centralized computation, except in the special cases of unicast and broadcast
connections.
  For dynamic multicast, we reduce the problem to a dynamic programming problem
and apply the theory of dynamic programming to suggest how it may be solved.


title: Data-Structure Rewriting

abstract:
  We tackle the problem of data-structure rewriting including pointer
redirections. We propose two basic rewrite steps: (i) Local Redirection and
Replacement steps the aim of which is redirecting specific pointers determined
by means of a pattern, as well as adding new information to an existing data ;
and (ii) Global Redirection steps which are aimed to redirect all pointers
targeting a node towards another one. We define these two rewriting steps
following the double pushout approach. We define first the category of graphs
we consider and then define rewrite rules as pairs of graph homomorphisms of
the form "L <- K ->R". Unfortunately, inverse pushouts (complement pushouts)
are not unique in our setting and pushouts do not always exist. Therefore, we
define rewriting steps so that a rewrite rule can always be performed once a
matching is found.


title:
A Practical Approach for Circuit Routing on Dynamic Reconfigurable
  Devices

abstract:
  Management of communication by on-line routing in new FPGAs with a large
amount of logic resources and partial reconfigurability is a new challenging
problem. A Network-on-Chip
  (NoC) typically uses packet routing mechanism, which has often unsafe data
transfers, and network interface overhead. In this paper, circuit routing for
such dynamic NoCs is investigated, and a practical 1-dimensional network with
an efficient routing algorithm is proposed and implemented. Also, this concept
has been extended to the 2-dimensional case. The implementation results show
the low area overhead and high performance of this network.


title: Contextual equivalence for higher-order pi-calculus revisited

abstract:
  The higher-order pi-calculus is an extension of the pi-calculus to allow
communication of abstractions of processes rather than names alone. It has been
studied intensively by Sangiorgi in his thesis where a characterisation of a
contextual equivalence for higher-order pi-calculus is provided using labelled
transition systems and normal bisimulations. Unfortunately the proof technique
used there requires a restriction of the language to only allow finite types.
We revisit this calculus and offer an alternative presentation of the labelled
transition system and a novel proof technique which allows us to provide a
fully abstract characterisation of contextual equivalence using labelled
transitions and bisimulations for higher-order pi-calculus with recursive types
also.


title: A Survey of Reverse Engineering and Program Comprehension

abstract:
  Reverse engineering has been a standard practice in the hardware community
for some time. It has only been within the last ten years that reverse
engineering, or "program comprehension", has grown into the current
sub-discipline of software engineering. Traditional software engineering is
primarily focused on the development and design of new software. However, most
programmers work on software that other people have designed and developed. Up
to 50% of a software maintainers time can be spent determining the intent of
source code. The growing demand to reevaluate and reimplement legacy software
systems, brought on by the proliferation of clientserver and World Wide Web
technologies, has underscored the need for reverse engineering tools and
techniques. This paper introduces the terminology of reverse engineering and
gives some of the obstacles that make reverse engineering difficult. Although
reverse engineering remains heavily dependent on the human component, a number
of automated tools are presented that aid the reverse engineer.


title: mod_oai: An Apache Module for Metadata Harvesting

abstract:
  We describe mod_oai, an Apache 2.0 module that implements the Open Archives
Initiative Protocol for Metadata Harvesting (OAI-PMH). OAIPMH is the de facto
standard for metadata exchange in digital libraries and allows repositories to
expose their contents in a structured, application-neutral format with
semantics optimized for accurate incremental harvesting. Current
implementations of OAI-PMH are either separate applications that access an
existing repository, or are built-in to repository software packages. mod_oai
is different in that it optimizes harvesting web content by building OAI-PMH
capability into the Apache server. We discuss the implications of adding
harvesting capability to an Apache server and describe our initial experimental
results accessing a departmental web site using both web crawling and OAIPMH
harvesting techniques.


title: Improved message passing for inference in densely connected systems

abstract:
  An improved inference method for densely connected systems is presented. The
approach is based on passing condensed messages between variables, representing
macroscopic averages of microscopic messages. We extend previous work that
showed promising results in cases where the solution space is contiguous to
cases where fragmentation occurs. We apply the method to the signal detection
problem of Code Division Multiple Access (CDMA) for demonstrating its
potential. A highly efficient practical algorithm is also derived on the basis
of insight gained from the analysis.


title:
Consistency in Models for Distributed Learning under Communication
  Constraints

abstract:
  Motivated by sensor networks and other distributed settings, several models
for distributed learning are presented. The models differ from classical works
in statistical pattern recognition by allocating observations of an independent
and identically distributed (i.i.d.) sampling process amongst members of a
network of simple learning agents. The agents are limited in their ability to
communicate to a central fusion center and thus, the amount of information
available for use in classification or regression is constrained. For several
basic communication models in both the binary classification and regression
frameworks, we question the existence of agent decision rules and fusion rules
that result in a universally consistent ensemble. The answers to this question
present new issues to consider with regard to universal consistency. Insofar as
these models present a useful picture of distributed scenarios, this paper
addresses the issue of whether or not the guarantees provided by Stone's
Theorem in centralized environments hold in distributed settings.


title: Distributed Learning in Wireless Sensor Networks

abstract:
  The problem of distributed or decentralized detection and estimation in
applications such as wireless sensor networks has often been considered in the
framework of parametric models, in which strong assumptions are made about a
statistical description of nature. In certain applications, such assumptions
are warranted and systems designed from these models show promise. However, in
other scenarios, prior knowledge is at best vague and translating such
knowledge into a statistical model is undesirable. Applications such as these
pave the way for a nonparametric study of distributed detection and estimation.
In this paper, we review recent work of the authors in which some elementary
models for distributed learning are considered. These models are in the spirit
of classical work in nonparametric statistics and are applicable to wireless
sensor networks.


title: Tensor manipulation in GPL Maxima

abstract:
  GPL Maxima is an open-source computer algebra system based on DOE-MACSYMA.
GPL Maxima included two tensor manipulation packages from DOE-MACSYMA, but
these were in various states of disrepair. One of the two packages, CTENSOR,
implemented component-based tensor manipulation; the other, ITENSOR, treated
tensor symbols as opaque, manipulating them based on their index properties.
The present paper describes the state in which these packages were found, the
steps that were needed to make the packages fully functional again, and the new
functionality that was implemented to make them more versatile. A third
package, ATENSOR, was also implemented; fully compatible with the identically
named package in the commercial version of MACSYMA, ATENSOR implements abstract
tensor algebras.


title: A File System Abstraction for Sense and Respond Systems

abstract:
  The heterogeneity and resource constraints of sense-and-respond systems pose
significant challenges to system and application development. In this paper, we
present a flexible, intuitive file system abstraction for organizing and
managing sense-and-respond systems based on the Plan 9 design principles. A key
feature of this abstraction is the ability to support multiple views of the
system via filesystem namespaces. Constructed logical views present an
application-specific representation of the network, thus enabling high-level
programming of the network. Concurrently, structural views of the network
enable resource-efficient planning and execution of tasks. We present and
motivate the design using several examples, outline research challenges and our
research plan to address them, and describe the current state of
implementation.


title:
Statistical Modelling of Information Sharing: Community, Membership and
  Content

abstract:
  File-sharing systems, like many online and traditional information sharing
communities (e.g. newsgroups, BBS, forums, interest clubs), are dynamical
systems in nature. As peers get in and out of the system, the information
content made available by the prevailing membership varies continually in
amount as well as composition, which in turn affects all peers' join/leave
decisions. As a result, the dynamics of membership and information content are
strongly coupled, suggesting interesting issues about growth, sustenance and
stability.
  In this paper, we propose to study such communities with a simple statistical
model of an information sharing club. Carrying their private payloads of
information goods as potential supply to the club, peers join or leave on the
basis of whether the information they demand is currently available.
Information goods are chunked and typed, as in a file sharing system where
peers contribute different files, or a forum where messages are grouped by
topics or threads. Peers' demand and supply are then characterized by
statistical distributions over the type domain.
  This model reveals interesting critical behaviour with multiple equilibria. A
sharp growth threshold is derived: the club may grow towards a sustainable
equilibrium only if the value of an order parameter is above the threshold, or
shrink to emptiness otherwise. The order parameter is composite and comprises
the peer population size, the level of their contributed supply, the club's
efficiency in information search, the spread of supply and demand over the type
domain, as well as the goodness of match between them.


title: Geometric Models of Rolling-Shutter Cameras

abstract:
  Cameras with rolling shutters are becoming more common as low-power, low-cost
CMOS sensors are being used more frequently in cameras. The rolling shutter
means that not all scanlines are exposed over the same time interval. The
effects of a rolling shutter are noticeable when either the camera or objects
in the scene are moving and can lead to systematic biases in projection
estimation. We develop a general projection equation for a rolling shutter
camera and show how it is affected by different types of camera motion. In the
case of fronto-parallel motion, we show how that camera can be modeled as an
X-slit camera. We also develop approximate projection equations for a non-zero
angular velocity about the optical axis and approximate the projection equation
for a constant velocity screw motion. We demonstrate how the rolling shutter
effects the projective geometry of the camera and in turn the
structure-from-motion.


title: Weighted Automata in Text and Speech Processing

abstract:
  Finite-state automata are a very effective tool in natural language
processing. However, in a variety of applications and especially in speech
precessing, it is necessary to consider more general machines in which arcs are
assigned weights or costs. We briefly describe some of the main theoretical and
algorithmic aspects of these machines. In particular, we describe an efficient
composition algorithm for weighted transducers, and give examples illustrating
the value of determinization and minimization algorithms for weighted automata.


title:
Obtaining Membership Functions from a Neuron Fuzzy System extended by
  Kohonen Network

abstract:
  This article presents the Neo-Fuzzy-Neuron Modified by Kohonen Network
(NFN-MK), an hybrid computational model that combines fuzzy system technique
and artificial neural networks. Its main task consists in the automatic
generation of membership functions, in particular, triangle forms, aiming a
dynamic modeling of a system. The model is tested by simulating real systems,
here represented by a nonlinear mathematical function. Comparison with the
results obtained by traditional neural networks, and correlated studies of
neurofuzzy systems applied in system identification area, shows that the NFN-MK
model has a similar performance, despite its greater simplicity.


title: Space-time databases modeling global semantic networks

abstract:
  This paper represents an approach to creating global knowledge systems, using
new philosophy and infrastructure of global distributed semantic network (frame
knowledge representation system) based on the space-time database construction.
The main idea of the space-time database environment introduced in the paper is
to bind a document (an information frame, a knowledge) to a special kind of
entity, that we call permanent entity, -- an object without history and
evolution, described by a "point" in the generalized, informational space-time
(not an evolving object in the real space having history). For documents
(information) it means that document content is unchangeable, and documents are
absolutely persistent. This approach leads to new knowledge representation and
retreival techniques. We discuss the way of applying the concept to a global
distributed scientific library and scientific workspace. Some practical aspects
of the work are elaborated by the open IT project at
http://sourceforge.net/projects/gil/.


title:
Enforcing Semantic Integrity on Untrusted Clients in Networked Virtual
  Environments

abstract:
  During the last years, large-scale simulations of realistic physical
environments which support the interaction of multiple participants over the
Internet have become increasingly available and economically significant, most
notably in the computer gaming industry. Such systems, commonly called
networked virtual environments (NVEs), are usually based on a client-server
architecture where for performance reasons and bandwidth restrictions, the
simulation is partially deferred to the clients. This inevitable architectural
choice renders the simulation vulnerable to attacks against the semantic
integrity of the simulation: malicious clients may attempt to compromise the
physical and logical laws governing the simulation, or to alter the causality
of events a posteriori. In this paper, we initiate the systematic study of
semantic integrity in NVEs from a security point of view. We argue that naive
policies to enforce semantic integrity involve intolerable network load, and
are therefore not practically feasible. We present a new semantic integrity
protocol based on cryptographic primitives which enables the server system to
audit the local computations of the clients on demand. Our approach facilitates
low network and CPU load, incurs reasonable engineering overhead, and maximally
decouples the auditing process from the soft real time constraints of the
simulation.


title: An Optimization Model for Outlier Detection in Categorical Data

abstract:
  The task of outlier detection is to find small groups of data objects that
are exceptional when compared with rest large amount of data. Detection of such
outliers is important for many applications such as fraud detection and
customer migration. Most existing methods are designed for numeric data. They
will encounter problems with real-life applications that contain categorical
data. In this paper, we formally define the problem of outlier detection in
categorical data as an optimization problem from a global viewpoint. Moreover,
we present a local-search heuristic based algorithm for efficiently finding
feasible solutions. Experimental results on real datasets and large synthetic
datasets demonstrate the superiority of our model and algorithm.


title:
Spines of Random Constraint Satisfaction Problems: Definition and
  Connection with Computational Complexity

abstract:
  We study the connection between the order of phase transitions in
combinatorial problems and the complexity of decision algorithms for such
problems. We rigorously show that, for a class of random constraint
satisfaction problems, a limited connection between the two phenomena indeed
exists. Specifically, we extend the definition of the spine order parameter of
Bollobas et al. to random constraint satisfaction problems, rigorously showing
that for such problems a discontinuity of the spine is associated with a
$2^{\Omega(n)}$ resolution complexity (and thus a $2^{\Omega(n)}$ complexity of
DPLL algorithms) on random instances. The two phenomena have a common
underlying cause: the emergence of ``large'' (linear size) minimally
unsatisfiable subformulas of a random formula at the satisfiability phase
transition.
  We present several further results that add weight to the intuition that
random constraint satisfaction problems with a sharp threshold and a continuous
spine are ``qualitatively similar to random 2-SAT''. Finally, we argue that it
is the spine rather than the backbone parameter whose continuity has
implications for the decision complexity of combinatorial problems, and we
provide experimental evidence that the two parameters can behave in a different
manner.


title: Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems

abstract:
  We study threshold properties of random constraint satisfaction problems
under a probabilistic model due to Molloy. We give a sufficient condition for
the existence of a sharp threshold that leads (for boolean constraints) to a
necessary and sufficient for the existence of a sharp threshold in the case
where constraint templates are applied with equal probability, solving thus an
open problem of Creignou and Daude.


title:
The Peculiarities of Nonstationary Formation of Inhomogeneous Structures
  of Charged Particles in the Electrodiffusion Processes

abstract:
  In this paper the distribution of charged particles is constructed under the
approximation of ambipolar diffusion. The results of mathematical modelling in
two-dimensional case taking into account the velocities of the system are
presented.


title: Dynamic Shannon Coding

abstract:
  We present a new algorithm for dynamic prefix-free coding, based on Shannon
coding. We give a simple analysis and prove a better upper bound on the length
of the encoding produced than the corresponding bound for dynamic Huffman
coding. We show how our algorithm can be modified for efficient
length-restricted coding, alphabetic coding and coding with unequal letter
costs.


title:
Segmentation of the Homogeneity of a Signal Using a Piecewise Linear
  Recognition Tool

abstract:
  In this paper a new method of detection of homogeneous zones and singularity
parts of a 1D signal is proposed. The entropy function is used to transform
signal in piecewise linear one. The multiple regression permits to detect lines
and project them in the Hough parameters space in order to easily recognise
homogeneous zone and abrupt changes of the signal. Two application examples are
analysed, the first is a classical fractal signal and the other is issued from
a dynamic mechanical study.


title: Dynamic Simulation of Construction Machinery: Towards an Operator Model

abstract:
  In dynamic simulation of complete wheel loaders, one interesting aspect,
specific for the working task, is the momentary power distribution between
drive train and hydraulics, which is balanced by the operator.
  This paper presents the initial results to a simulation model of a human
operator. Rather than letting the operator model follow a predefined path with
control inputs at given points, it follows a collection of general rules that
together describe the machine's working cycle in a generic way. The advantage
of this is that the working task description and the operator model itself are
independent of the machine's technical parameters. Complete sub-system
characteristics can thus be changed without compromising the relevance and
validity of the simulation. Ultimately, this can be used to assess a machine's
total performance, fuel efficiency and operability already in the concept phase
of the product development process.


title:
General non-asymptotic and asymptotic formulas in channel resolvability
  and identification capacity and their application to wire-tap channel

abstract:
  Several non-asymptotic formulas are established in channel resolvability and
identification capacity, and they are applied to wire-tap channel. By using
these formulas, the $\epsilon$ capacities of the above three problems are
considered in the most general setting, where no structural assumptions such as
the stationary memoryless property are made on a channel. As a result, we solve
an open problem proposed in Han & Verdu and Han. Moreover, we obtain lower
bounds of the exponents of error probability and the wire-tapper's information
in wire-tap channel.


title:
Second order asymptotics in fixed-length source coding and intrinsic
  randomness

abstract:
  Second order asymptotics of fixed-length source coding and intrinsic
randomness is discussed with a constant error constraint. There was a
difference between optimal rates of fixed-length source coding and intrinsic
randomness, which never occurred in the first order asymptotics. In addition,
the relation between uniform distribution and compressed data is discussed
based on this fact. These results are valid for general information sources as
well as independent and identical distributions. A universal code attaining the
second order optimal rate is also constructed.


title: Effects of variations of load distribution on network performance

abstract:
  This paper is concerned with the characterization of the relationship between
topology and traffic dynamics. We use a model of network generation that allows
the transition from random to scale free networks. Specifically, we consider
three different topological types of network: random, scale-free with \gamma =
3, scale-free with \gamma = 2. By using a novel LRD traffic generator, we
observe best performance, in terms of transmission rates and delivered packets,
in the case of random networks. We show that, even if scale-free networks are
characterized by shorter characteristic-path- length (the lower the exponent,
the lower the path-length), they show worst performances in terms of
communication. We conjecture this could be explained in terms of changes in the
load distribution, defined here as the number of shortest paths going through a
given vertex. In fact, that distribu- tion is characterized by (i) a decreasing
mean (ii) an increas- ing standard deviation, as the networks becomes
scale-free (especially scale-free networks with low exponents). The use of a
degree-independent server also discriminates against a scale-free structure. As
a result, since the model is un- controlled, most packets will go through the
same vertices, favoring the onset of congestion.


title: Resource Bounded Unprovability of Computational Lower Bounds

abstract:
  This paper introduces new notions of asymptotic proofs,
PT(polynomial-time)-extensions, PTM(polynomial-time Turing
machine)-omega-consistency, etc. on formal theories of arithmetic including PA
(Peano Arithmetic). This paper shows that P not= NP (more generally, any
super-polynomial-time lower bound in PSPACE) is unprovable in a
PTM-omega-consistent theory T, where T is a consistent PT-extension of PA. This
result gives a unified view to the existing two major negative results on
proving P not= NP, Natural Proofs and relativizable proofs, through the two
manners of characterization of PTM-omega-consistency. We also show that the
PTM-omega-consistency of T cannot be proven in any PTM-omega-consistent theory
S, where S is a consistent PT-extension of T.


title: Monotonic and Nonmonotonic Preference Revision

abstract:
  We study here preference revision, considering both the monotonic case where
the original preferences are preserved and the nonmonotonic case where the new
preferences may override the original ones. We use a relational framework in
which preferences are represented using binary relations (not necessarily
finite). We identify several classes of revisions that preserve order axioms,
for example the axioms of strict partial or weak orders. We consider
applications of our results to preference querying in relational databases.


title: Probabilistic and Team PFIN-type Learning: General Properties

abstract:
  We consider the probability hierarchy for Popperian FINite learning and study
the general properties of this hierarchy. We prove that the probability
hierarchy is decidable, i.e. there exists an algorithm that receives p_1 and
p_2 and answers whether PFIN-type learning with the probability of success p_1
is equivalent to PFIN-type learning with the probability of success p_2.
  To prove our result, we analyze the topological structure of the probability
hierarchy. We prove that it is well-ordered in descending ordering and
order-equivalent to ordinal epsilon_0. This shows that the structure of the
hierarchy is very complicated.
  Using similar methods, we also prove that, for PFIN-type learning, team
learning and probabilistic learning are of the same power.


title: On the Effect of Fading on Ad hoc Networking

abstract:
  Most MANET (Mobile Ad hoc NETwork) research assumes idealized propagation
models. Experimental results have shown significant divergence from simulation
results due to the effect of signal fading in realistic wireless communication
channels. In this paper, we characterize the impact of fading on protocol
performance. We first study the effect of fading on MAC performance and show
that its effect can be dominating. One of our important conclusions is that
eliminating RTS/CTS packets results in more effective operation under fading.
We also identify an unfairness problem that arises due to backoffs in the
presence of fading. Moreover, fading results in several subtle interactions
between the MAC and routing layers. We identify several of these problems and
make observations about effective approaches for addressing them. For example,
the criteria for determining the best path should not only consider the link
status but also the link order. In addition, because routing protocols rely on
MAC level transmission failure (when the retry limit is exceeded), route
failure errors are often generated unnecessarily. Finally, because MAC level
broadcasts are unreliable, they are especially vulnerable to fading. We analyze
these effects and outline preliminary solutions to them.


title: Multiple Description Quantization via Gram-Schmidt Orthogonalization

abstract:
  The multiple description (MD) problem has received considerable attention as
a model of information transmission over unreliable channels. A general
framework for designing efficient multiple description quantization schemes is
proposed in this paper. We provide a systematic treatment of the El Gamal-Cover
(EGC) achievable MD rate-distortion region, and show that any point in the EGC
region can be achieved via a successive quantization scheme along with
quantization splitting. For the quadratic Gaussian case, the proposed scheme
has an intrinsic connection with the Gram-Schmidt orthogonalization, which
implies that the whole Gaussian MD rate-distortion region is achievable with a
sequential dithered lattice-based quantization scheme as the dimension of the
(optimal) lattice quantizers becomes large. Moreover, this scheme is shown to
be universal for all i.i.d. smooth sources with performance no worse than that
for an i.i.d. Gaussian source with the same variance and asymptotically optimal
at high resolution. A class of low-complexity MD scalar quantizers in the
proposed general framework also is constructed and is illustrated
geometrically; the performance is analyzed in the high resolution regime, which
exhibits a noticeable improvement over the existing MD scalar quantization
schemes.


title: Statistical analysis of quality measures for mobile ad hoc networks

abstract:
  How can the quality of a mobile ad hoc network (MANET) be quantified? This
work aims at an answer based on the lower network layers, i.e. on connectivity
between the wireless nodes, using statistical methods. A number of different
quality measures are introduced and classified according to their scaling
behaviour. They are analysed in a statistical model of a 1-dimensional MANET
system (corresponding e.g. to cars on a road). Neglecting boundary effects, the
model turns out to be exactly solvable, so that explicit analytical results for
the quality levels can be obtained both at fixed system size and in the limit
of large systems. In particular, this improves estimates known in the
literature for the probability of connectedness of 1-dimensional MANETs.


title: Fast Codes for Large Alphabets

abstract:
  We address the problem of constructing a fast lossless code in the case when
the source alphabet is large. The main idea of the new scheme may be described
as follows. We group letters with small probabilities in subsets (acting as
super letters) and use time consuming coding for these subsets only, whereas
letters in the subsets have the same code length and therefore can be coded
fast. The described scheme can be applied to sources with known and unknown
statistics.


title: Using Information Theory Approach to Randomness Testing

abstract:
  We address the problem of detecting deviations of binary sequence from
randomness,which is very important for random number (RNG) and pseudorandom
number generators (PRNG). Namely, we consider a null hypothesis $H_0$ that a
given bit sequence is generated by Bernoulli source with equal probabilities of
0 and 1 and the alternative hypothesis $H_1$ that the sequence is generated by
a stationary and ergodic source which differs from the source under $H_0$. We
show that data compression methods can be used as a basis for such testing and
describe two new tests for randomness, which are based on ideas of universal
coding. Known statistical tests and suggested ones are applied for testing
PRNGs. Those experiments show that the power of the new tests is greater than
of many known algorithms.


title: The Bandwidth Exchange Architecture

abstract:
  New applications for the Internet such as video on demand, grid computing
etc. depend on the availability of high bandwidth connections with acceptable
Quality of Service (QoS). There appears to be, therefore, a requirement for a
market where bandwidth-related transactions can take place. For this market to
be effective, it must be efficient for both the provider (seller) and the user
(buyer) of the bandwidth. This implies that: (a) the buyer must have a wide
choice of providers that operate in a competitive environment, (b) the seller
must be assured that a QoS transaction will be paid by the customer, and (c)
the QoS transaction establishment must have low overheads so that it may be
used by individual customers without a significant burden to the provider.
  In order to satisfy these requirements, we propose a framework that allows
customers to purchase bandwidth using an open market where providers advertise
links and capacities and customers bid for these services. The model is close
to that of a commodities market that offers both advance bookings (futures) and
a spot market. We explore the mechanisms that can support such a model.


title: Super Object Oriented Programming

abstract: This submission has been withdrawn at the request of the author.


title:
Towards a Group Theoretic Quantum Encryption Scheme Based on Generalized
  Hidden Subgroup Problem

abstract:
  This paper introduces a completely new approach to encryption based on group
theoretic quantum framework. Quantum cryptography has essentially focused only
on key distribution and proceeded with classical encryption algorithm with the
generated key. Here, we present a first step towards a quantum encryption
scheme based on the solution for the hidden subgroup problem. The shared secret
key K from QKD evolves as a generator for a subgroup H of a group G, in
combination of the plain text data modeled as group elements. The key K helps
in regeneration of the plain data on the receiver's side based on subgroup
reconstruction. This paper models all quantum computations using group
representations. A non-constructive proof is attempted towards the security of
the encryption scheme. We also address the issues involved in a such a venture
into the realms of Quantum data encryption.


title: Reversible Fault-Tolerant Logic

abstract:
  It is now widely accepted that the CMOS technology implementing irreversible
logic will hit a scaling limit beyond 2016, and that the increased power
dissipation is a major limiting factor. Reversible computing can potentially
require arbitrarily small amounts of energy. Recently several nano-scale
devices which have the potential to scale, and which naturally perform
reversible logic, have emerged. This paper addresses several fundamental issues
that need to be addressed before any nano-scale reversible computing systems
can be realized, including reliability and performance trade-offs and
architecture optimization. Many nano-scale devices will be limited to only near
neighbor interactions, requiring careful optimization of circuits. We provide
efficient fault-tolerant (FT) circuits when restricted to both 2D and 1D.
Finally, we compute bounds on the entropy (and hence, heat) generated by our FT
circuits and provide quantitative estimates on how large can we make our
circuits before we lose any advantage over irreversible computing.


title: Average Coset Weight Distribution of Combined LDPC Matrix Ensemble

abstract:
  In this paper, the average coset weight distribution (ACWD) of structured
ensembles of LDPC (Low-density Parity-Check) matrix, which is called combined
ensembles, is discussed. A combined ensemble is composed of a set of simpler
ensembles such as a regular bipartite ensemble. Two classes of combined
ensembles have prime importance; a stacked ensemble and a concatenated
ensemble, which consists of set of stacked matrices and concatenated matrices,
respectively. The ACWD formulas of these ensembles is shown in this paper. Such
formulas are key tools to evaluate the ACWD of a complex combined ensemble.
  From the ACWD of an ensemble, we can obtain some detailed properties of a
code (e.g., weight of coset leaders) which is not available from an average
weight distribution. Moreover, it is shown that the analysis based on the ACWD
is indispensable to evaluate the average weight distribution of some classes of
combined ensembles.


title: Improving Spam Detection Based on Structural Similarity

abstract:
  We propose a new detection algorithm that uses structural relationships
between senders and recipients of email as the basis for the identification of
spam messages. Users and receivers are represented as vectors in their
reciprocal spaces. A measure of similarity between vectors is constructed and
used to group users into clusters. Knowledge of their classification as past
senders/receivers of spam or legitimate mail, comming from an auxiliary
detection algorithm, is then used to label these clusters probabilistically.
This knowledge comes from an auxiliary algorithm. The measure of similarity
between the sender and receiver sets of a new message to the center vector of
clusters is then used to asses the possibility of that message being legitimate
or spam. We show that the proposed algorithm is able to correct part of the
false positives (legitimate messages classified as spam) using a testbed of one
week smtp log.


title: Pseudocodewords of Tanner graphs

abstract:
  This papers presents a detailed analysis of pseudocodewords of Tanner graphs.
Pseudocodewords arising on the iterative decoder's computation tree are
distinguished from pseudocodewords arising on finite degree lifts. Lower bounds
on the minimum pseudocodeword weight are presented for the BEC, BSC, and AWGN
channel. Some structural properties of pseudocodewords are examined, and
pseudocodewords and graph properties that are potentially problematic with
min-sum iterative decoding are identified. An upper bound on the minimum degree
lift needed to realize a particular irreducible lift-realizable pseudocodeword
is given in terms of its maximal component, and it is shown that all
irreducible lift-realizable pseudocodewords have components upper bounded by a
finite value $t$ that is dependent on the graph structure. Examples and
different Tanner graph representations of individual codes are examined and the
resulting pseudocodeword distributions and iterative decoding performances are
analyzed. The results obtained provide some insights in relating the structure
of the Tanner graph to the pseudocodeword distribution and suggest ways of
designing Tanner graphs with good minimum pseudocodeword weight.


title: Network Information Flow with Correlated Sources

abstract:
  In this paper, we consider a network communications problem in which multiple
correlated sources must be delivered to a single data collector node, over a
network of noisy independent point-to-point channels. We prove that perfect
reconstruction of all the sources at the sink is possible if and only if, for
all partitions of the network nodes into two subsets S and S^c such that the
sink is always in S^c, we have that H(U_S|U_{S^c}) < \sum_{i\in S,j\in S^c}
C_{ij}. Our main finding is that in this setup a general source/channel
separation theorem holds, and that Shannon information behaves as a classical
network flow, identical in nature to the flow of water in pipes. At first
glance, it might seem surprising that separation holds in a fairly general
network situation like the one we study. A closer look, however, reveals that
the reason for this is that our model allows only for independent
point-to-point channels between pairs of nodes, and not multiple-access and/or
broadcast channels, for which separation is well known not to hold. This
``information as flow'' view provides an algorithmic interpretation for our
results, among which perhaps the most important one is the optimality of
implementing codes using a layered protocol stack.


title: Design of Block Transceivers with Decision Feedback Detection

abstract:
  This paper presents a method for jointly designing the transmitter-receiver
pair in a block-by-block communication system that employs (intra-block)
decision feedback detection. We provide closed-form expressions for
transmitter-receiver pairs that simultaneously minimize the arithmetic mean
squared error (MSE) at the decision point (assuming perfect feedback), the
geometric MSE, and the bit error rate of a uniformly bit-loaded system at
moderate-to-high signal-to-noise ratios. Separate expressions apply for the
``zero-forcing'' and ``minimum MSE'' (MMSE) decision feedback structures. In
the MMSE case, the proposed design also maximizes the Gaussian mutual
information and suggests that one can approach the capacity of the block
transmission system using (independent instances of) the same (Gaussian) code
for each element of the block. Our simulation studies indicate that the
proposed transceivers perform significantly better than standard transceivers,
and that they retain their performance advantages in the presence of error
propagation.


title: Shortened Array Codes of Large Girth

abstract:
  One approach to designing structured low-density parity-check (LDPC) codes
with large girth is to shorten codes with small girth in such a manner that the
deleted columns of the parity-check matrix contain all the variables involved
in short cycles. This approach is especially effective if the parity-check
matrix of a code is a matrix composed of blocks of circulant permutation
matrices, as is the case for the class of codes known as array codes. We show
how to shorten array codes by deleting certain columns of their parity-check
matrices so as to increase their girth. The shortening approach is based on the
observation that for array codes, and in fact for a slightly more general class
of LDPC codes, the cycles in the corresponding Tanner graph are governed by
certain homogeneous linear equations with integer coefficients. Consequently,
we can selectively eliminate cycles from an array code by only retaining those
columns from the parity-check matrix of the original code that are indexed by
integer sequences that do not contain solutions to the equations governing
those cycles. We provide Ramsey-theoretic estimates for the maximum number of
columns that can be retained from the original parity-check matrix with the
property that the sequence of their indices avoid solutions to various types of
cycle-governing equations. This translates to estimates of the rate penalty
incurred in shortening a code to eliminate cycles. Simulation results show that
for the codes considered, shortening them to increase the girth can lead to
significant gains in signal-to-noise ratio in the case of communication over an
additive white Gaussian noise channel.


title: A new SISO algorithm with application to turbo equalization

abstract:
  In this paper we propose a new soft-input soft-output equalization algorithm,
offering very good performance/complexity tradeoffs. It follows the structure
of the BCJR algorithm, but dynamically constructs a simplified trellis during
the forward recursion. In each trellis section, only the M states with the
strongest forward metric are preserved, similar to the M-BCJR algorithm. Unlike
the M-BCJR, however, the remaining states are not deleted, but rather merged
into the surviving states. The new algorithm compares favorably with the
reduced-state BCJR algorithm, offering better performance and more flexibility,
particularly for systems with higher order modulations.


title: A Rule-Based Logic for Quantum Information

abstract:
  In the present article, we explore a new approach for the study of
orthomodular lattices, where we replace the problematic conjunction by a binary
operator, called the Sasaki projection. We present a characterization of
orthomodular lattices based on the use of an algebraic version of the Sasaki
projection operator (together with orthocomplementation) rather than on the
conjunction. We then define of a new logic, which we call Sasaki Orthologic,
which is closely related to quantum logic, and provide a rule-based definition
of this logic.


title: Efficient Authenticated Encryption Schemes with Public Verifiability

abstract:
  An authenticated encryption scheme allows messages to be encrypted and
authenticated simultaneously. In 2003, Ma and Chen proposed such a scheme with
public verifiability. That is, in their scheme the receiver can efficiently
prove to a third party that a message is indeed originated from a specific
sender. In this paper, we first identify two security weaknesses in the Ma-Chen
authenticated encryption scheme. Then, based on the Schnorr signature, we
proposed an efficient and secure improved scheme such that all the desired
security requirements are satisfied.


title: The Viterbi Algorithm: A Personal History

abstract:
  The story of the Viterbi algorithm (VA) is told from a personal perspective.
Applications both within and beyond communications are discussed. In brief
summary, the VA has proved to be an extremely important algorithm in a
surprising variety of fields.


title: Near Perfect Decoding of LDPC Codes

abstract:
  Cooperative optimization is a new way for finding global optima of
complicated functions of many variables. It has some important properties not
possessed by any conventional optimization methods. It has been successfully
applied in solving many large scale optimization problems in image processing,
computer vision, and computational chemistry. This paper shows the application
of this optimization principle in decoding LDPC codes, which is another hard
combinatorial optimization problem. In our experiments, it significantly
out-performed the sum-product algorithm, the best known method for decoding
LDPC codes. Compared to the sum-product algorithm, our algorithm reduced the
error rate further by three fold, improved the speed by six times, and lowered
error floors dramatically in the decoding.


title:
A Matter of Opinion: Sentiment Analysis and Business Intelligence
  (position paper)

abstract:
  A general-audience introduction to the area of "sentiment analysis", the
computational treatment of subjective, opinion-oriented language (an example
application is determining whether a review is "thumbs up" or "thumbs down").
Some challenges, applications to business-intelligence tasks, and potential
future directions are described.


title: Correlation Clustering with a Fixed Number of Clusters

abstract:
  We continue the investigation of problems concerning correlation clustering
or clustering with qualitative information, which is a clustering formulation
that has been studied recently. The basic setup here is that we are given as
input a complete graph on n nodes (which correspond to nodes to be clustered)
whose edges are labeled + (for similar pairs of items) and - (for dissimilar
pairs of items). Thus we have only as input qualitative information on
similarity and no quantitative distance measure between items. The quality of a
clustering is measured in terms of its number of agreements, which is simply
the number of edges it correctly classifies, that is the sum of number of -
edges whose endpoints it places in different clusters plus the number of +
edges both of whose endpoints it places within the same cluster.
  In this paper, we study the problem of finding clusterings that maximize the
number of agreements, and the complementary minimization version where we seek
clusterings that minimize the number of disagreements. We focus on the
situation when the number of clusters is stipulated to be a small constant k.
Our main result is that for every k, there is a polynomial time approximation
scheme for both maximizing agreements and minimizing disagreements. (The
problems are NP-hard for every k >= 2.) The main technical work is for the
minimization version, as the PTAS for maximizing agreements follows along the
lines of the property tester for Max k-CUT.
  In contrast, when the number of clusters is not specified, the problem of
minimizing disagreements was shown to be APX-hard, even though the maximization
version admits a PTAS.


title: Constraint-Based Qualitative Simulation

abstract:
  We consider qualitative simulation involving a finite set of qualitative
relations in presence of complete knowledge about their interrelationship. We
show how it can be naturally captured by means of constraints expressed in
temporal logic and constraint satisfaction problems. The constraints relate at
each stage the 'past' of a simulation with its 'future'. The benefit of this
approach is that it readily leads to an implementation based on constraint
technology that can be used to generate simulations and to answer queries about
them.


title:
Incorporating LINQ, State Diagrams Templating and Package Extension Into
  Java

abstract: This submission has been withdrawn at the request of the author.


title: Searching Monotone Multi-dimensional Arrays

abstract:
  In this paper we investigate the problem of searching monotone
multi-dimensional arrays. We generalize Linial and Saks' search algorithm
\cite{LS1} for monotone 3-dimensional arrays to $d$-dimensions with $d\geq 4$.
Our new search algorithm is asymptotically optimal for $d=4$.


title: Linear Datalog and Bounded Path Duality of Relational Structures

abstract:
  In this paper we systematically investigate the connections between logics
with a finite number of variables, structures of bounded pathwidth, and linear
Datalog Programs. We prove that, in the context of Constraint Satisfaction
Problems, all these concepts correspond to different mathematical embodiments
of a unique robust notion that we call bounded path duality. We also study the
computational complexity implications of the notion of bounded path duality. We
show that every constraint satisfaction problem $\csp(\best)$ with bounded path
duality is solvable in NL and that this notion explains in a uniform way all
families of CSPs known to be in NL. Finally, we use the results developed in
the paper to identify new problems in NL.


title:
On Extrinsic Information of Good Codes Operating Over Discrete
  Memoryless Channels

abstract:
  We show that the Extrinsic Information about the coded bits of any good
(capacity achieving) code operating over a wide class of discrete memoryless
channels (DMC) is zero when channel capacity is below the code rate and
positive constant otherwise, that is, the Extrinsic Information Transfer (EXIT)
chart is a step function of channel quality, for any capacity achieving code.
It follows that, for a common class of iterative receivers where the error
correcting decoder must operate at first iteration at rate above capacity (such
as in turbo equalization, turbo channel estimation, parallel and serial
concatenated coding and the like), classical good codes which achieve capacity
over the DMC are not effective and should be replaced by different new ones.
Another meaning of the results is that a good code operating at rate above
channel capacity falls apart into its individual transmitted symbols in the
sense that all the information about a coded transmitted symbol is contained in
the corresponding received symbol and no information about it can be inferred
from the other received symbols. The binary input additive white Gaussian noise
channel is treated in part 1 of this report. Part 2 extends the results to the
symmetric binary channel and to the binary erasure channel and provides an
heuristic extension to wider class of channel models.


title: Fast Distributed Algorithms for Computing Separable Functions

abstract:
  The problem of computing functions of values at the nodes in a network in a
totally distributed manner, where nodes do not have unique identities and make
decisions based only on local information, has applications in sensor,
peer-to-peer, and ad-hoc networks. The task of computing separable functions,
which can be written as linear combinations of functions of individual
variables, is studied in this context. Known iterative algorithms for averaging
can be used to compute the normalized values of such functions, but these
algorithms do not extend in general to the computation of the actual values of
separable functions.
  The main contribution of this paper is the design of a distributed randomized
algorithm for computing separable functions. The running time of the algorithm
is shown to depend on the running time of a minimum computation algorithm used
as a subroutine. Using a randomized gossip mechanism for minimum computation as
the subroutine yields a complete totally distributed algorithm for computing
separable functions. For a class of graphs with small spectral gap, such as
grid graphs, the time used by the algorithm to compute averages is of a smaller
order than the time required by a known iterative averaging scheme.


title: Sufficient conditions for convergence of the Sum-Product Algorithm

abstract:
  We derive novel conditions that guarantee convergence of the Sum-Product
algorithm (also known as Loopy Belief Propagation or simply Belief Propagation)
to a unique fixed point, irrespective of the initial messages. The
computational complexity of the conditions is polynomial in the number of
variables. In contrast with previously existing conditions, our results are
directly applicable to arbitrary factor graphs (with discrete variables) and
are shown to be valid also in the case of factors containing zeros, under some
additional conditions. We compare our bounds with existing ones, numerically
and, if possible, analytically. For binary variables with pairwise
interactions, we derive sufficient conditions that take into account local
evidence (i.e., single variable factors) and the type of pair interactions
(attractive or repulsive). It is shown empirically that this bound outperforms
existing bounds.


title: Convexity Analysis of Snake Models Based on Hamiltonian Formulation

abstract:
  This paper presents a convexity analysis for the dynamic snake model based on
the Potential Energy functional and the Hamiltonian formulation of the
classical mechanics. First we see the snake model as a dynamical system whose
singular points are the borders we seek. Next we show that a necessary
condition for a singular point to be an attractor is that the energy functional
is strictly convex in a neighborhood of it, that means, if the singular point
is a local minimum of the potential energy. As a consequence of this analysis,
a local expression relating the dynamic parameters and the rate of convergence
arises. Such results link the convexity analysis of the potential energy and
the dynamic snake model and point forward to the necessity of a physical
quantity whose convexity analysis is related to the dynamic and which
incorporate the velocity space. Such a quantity is exactly the (conservative)
Hamiltonian of the system.


title: Critical Point for Maximum Likelihood Decoding of Linear Block Codes

abstract:
  In this letter, the SNR value at which the error performance curve of a soft
decision maximum likelihood decoder reaches the slope corresponding to the code
minimum distance is determined for a random code. Based on this value, referred
to as the critical point, new insight about soft bounded distance decoding of
random-like codes (and particularly Reed-Solomon codes) is provided.


title: Resource Management Services for a Grid Analysis Environment

abstract:
  Selecting optimal resources for submitting jobs on a computational Grid or
accessing data from a data grid is one of the most important tasks of any Grid
middleware. Most modern Grid software today satisfies this responsibility and
gives a best-effort performance to solve this problem. Almost all decisions
regarding scheduling and data access are made by the software automatically,
giving users little or no control over the entire process. To solve this
problem, a more interactive set of services and middleware is desired that
provides users more information about Grid weather, and gives them more control
over the decision making process. This paper presents a set of services that
have been developed to provide more interactive resource management
capabilities within the Grid Analysis Environment (GAE) being developed
collaboratively by Caltech, NUST and several other institutes. These include a
steering service, a job monitoring service and an estimator service that have
been designed and written using a common Grid-enabled Web Services framework
named Clarens. The paper also presents a performance analysis of the developed
services to show that they have indeed resulted in a more interactive and
powerful system for user-centric Grid-enabled physics analysis.


title:
Heterogeneous Relational Databases for a Grid-enabled Analysis
  Environment

abstract:
  Grid based systems require a database access mechanism that can provide
seamless homogeneous access to the requested data through a virtual data access
system, i.e. a system which can take care of tracking the data that is stored
in geographically distributed heterogeneous databases. This system should
provide an integrated view of the data that is stored in the different
repositories by using a virtual data access mechanism, i.e. a mechanism which
can hide the heterogeneity of the backend databases from the client
applications. This paper focuses on accessing data stored in disparate
relational databases through a web service interface, and exploits the features
of a Data Warehouse and Data Marts. We present a middleware that enables
applications to access data stored in geographically distributed relational
databases without being aware of their physical locations and underlying
schema. A web service interface is provided to enable applications to access
this middleware in a language and platform independent way. A prototype
implementation was created based on Clarens [4], Unity [7] and POOL [8]. This
ability to access the data stored in the distributed relational databases
transparently is likely to be a very powerful one for Grid users, especially
the scientific community wishing to collate and analyze data distributed over
the Grid.


title: Fitness Uniform Deletion: A Simple Way to Preserve Diversity

abstract:
  A commonly experienced problem with population based optimisation methods is
the gradual decline in population diversity that tends to occur over time. This
can slow a system's progress or even halt it completely if the population
converges on a local optimum from which it cannot escape. In this paper we
present the Fitness Uniform Deletion Scheme (FUDS), a simple but somewhat
unconventional approach to this problem. Under FUDS the deletion operation is
modified to only delete those individuals which are "common" in the sense that
there exist many other individuals of similar fitness in the population. This
makes it impossible for the population to collapse to a collection of highly
related individuals with similar fitness. Our experimental results on a range
of optimisation problems confirm this, in particular for deceptive optimisation
problems the performance is significantly more robust to variation in the
selection intensity.


title:
Scientific impact quantity and quality: Analysis of two sources of
  bibliographic data

abstract:
  Attempts to understand the consequence of any individual scientist's activity
within the long-term trajectory of science is one of the most difficult
questions within the philosophy of science. Because scientific publications
play such as central role in the modern enterprise of science, bibliometric
techniques which measure the ``impact'' of an individual publication as a
function of the number of citations it receives from subsequent authors have
provided some of the most useful empirical data on this question. Until
recently, Thompson/ISI has provided the only source of large-scale ``inverted''
bibliographic data of the sort required for impact analysis. In the end of
2004, Google introduced a new service, GoogleScholar, making much of this same
data available. Here we analyze 203 publications, collectively cited by more
than 4000 other publications. We show surprisingly good agreement between data
citation counts provided by the two services. Data quality across the systems
is analyzed, and potentially useful complementarities between are considered.
The additional robustness offered by multiple sources of such data promises to
increase the utility of these measurements as open citation protocols and open
access increase their impact on electronic scientific publication practices.


title:
Bayesian Restoration of Digital Images Employing Markov Chain Monte
  Carlo a Review

abstract:
  A review of Bayesian restoration of digital images based on Monte Carlo
techniques is presented. The topics covered include Likelihood, Prior and
Posterior distributions, Poisson, Binay symmetric channel, and Gaussian channel
models of Likelihood distribution,Ising and Potts spin models of Prior
distribution, restoration of an image through Posterior maximization,
statistical estimation of a true image from Posterior ensembles, Markov Chain
Monte Carlo methods and cluster algorithms.


title: On Approximating Restricted Cycle Covers

abstract:
  A cycle cover of a graph is a set of cycles such that every vertex is part of
exactly one cycle. An L-cycle cover is a cycle cover in which the length of
every cycle is in the set L. The weight of a cycle cover of an edge-weighted
graph is the sum of the weights of its edges.
  We come close to settling the complexity and approximability of computing
L-cycle covers. On the one hand, we show that for almost all L, computing
L-cycle covers of maximum weight in directed and undirected graphs is APX-hard
and NP-hard. Most of our hardness results hold even if the edge weights are
restricted to zero and one.
  On the other hand, we show that the problem of computing L-cycle covers of
maximum weight can be approximated within a factor of 2 for undirected graphs
and within a factor of 8/3 in the case of directed graphs. This holds for
arbitrary sets L.


title: TeXmacs-maxima interface

abstract:
  This tutorial presents features of the new and improved TeXmacs-maxima
interface. It is designed for running maxima-5.9.2 from TeXmacs-1.0.5 (or
later).


title: DTN Routing in a Mobility Pattern Space

abstract:
  Routing in Delay Tolerant Networks (DTNs) benefits considerably if one can
take advantage of knowledge concerning node mobility. The main contribution of
this paper is the definition of a generic routing scheme for DTNs using a
high-dimensional Euclidean space constructed upon nodes' mobility patterns. For
example, nodes are represented as points having as coordinates their
probability of being found in each possible location. We present simulation
results indicating that such a scheme can be beneficial in a scenario inspired
by studies done on real mobility traces. This work should open the way to
further use of the virtual space formalism in DTN routing.


title:
Learning Polynomial Networks for Classification of Clinical
  Electroencephalograms

abstract:
  We describe a polynomial network technique developed for learning to classify
clinical electroencephalograms (EEGs) presented by noisy features. Using an
evolutionary strategy implemented within Group Method of Data Handling, we
learn classification models which are comprehensively described by sets of
short-term polynomials. The polynomial models were learnt to classify the EEGs
recorded from Alzheimer and healthy patients and recognize the EEG artifacts.
Comparing the performances of our technique and some machine learning methods
we conclude that our technique can learn well-suited polynomial models which
experts can find easy-to-understand.


title: The Bayesian Decision Tree Technique with a Sweeping Strategy

abstract:
  The uncertainty of classification outcomes is of crucial importance for many
safety critical applications including, for example, medical diagnostics. In
such applications the uncertainty of classification can be reliably estimated
within a Bayesian model averaging technique that allows the use of prior
information. Decision Tree (DT) classification models used within such a
technique gives experts additional information by making this classification
scheme observable. The use of the Markov Chain Monte Carlo (MCMC) methodology
of stochastic sampling makes the Bayesian DT technique feasible to perform.
However, in practice, the MCMC technique may become stuck in a particular DT
which is far away from a region with a maximal posterior. Sampling such DTs
causes bias in the posterior estimates, and as a result the evaluation of
classification uncertainty may be incorrect. In a particular case, the negative
effect of such sampling may be reduced by giving additional prior information
on the shape of DTs. In this paper we describe a new approach based on sweeping
the DTs without additional priors on the favorite shape of DTs. The
performances of Bayesian DT techniques with the standard and sweeping
strategies are compared on a synthetic data as well as on real datasets.
Quantitatively evaluating the uncertainty in terms of entropy of class
posterior probabilities, we found that the sweeping strategy is superior to the
standard strategy.


title:
Experimental Comparison of Classification Uncertainty for Randomised and
  Bayesian Decision Tree Ensembles

abstract:
  In this paper we experimentally compare the classification uncertainty of the
randomised Decision Tree (DT) ensemble technique and the Bayesian DT technique
with a restarting strategy on a synthetic dataset as well as on some datasets
commonly used in the machine learning community. For quantitative evaluation of
classification uncertainty, we use an Uncertainty Envelope dealing with the
class posterior distribution and a given confidence probability. Counting the
classifier outcomes, this technique produces feasible evaluations of the
classification uncertainty. Using this technique in our experiments, we found
that the Bayesian DT technique is superior to the randomised DT ensemble
technique.


title:
JClarens: A Java Framework for Developing and Deploying Web Services for
  Grid Computing

abstract:
  High Energy Physics (HEP) and other scientific communities have adopted
Service Oriented Architectures (SOA) as part of a larger Grid computing effort.
This effort involves the integration of many legacy applications and
programming libraries into a SOA framework. The Grid Analysis Environment (GAE)
is such a service oriented architecture based on the Clarens Grid Services
Framework and is being developed as part of the Compact Muon Solenoid (CMS)
experiment at the Large Hadron Collider (LHC) at European Laboratory for
Particle Physics (CERN). Clarens provides a set of authorization, access
control, and discovery services, as well as XMLRPC and SOAP access to all
deployed services. Two implementations of the Clarens Web Services Framework
(Python and Java) offer integration possibilities for a wide range of
programming languages. This paper describes the Java implementation of the
Clarens Web Services Framework called JClarens. and several web services of
interest to the scientific and Grid community that have been deployed using
JClarens.


title: Analyzing Worms and Network Traffic using Compression

abstract:
  Internet worms have become a widespread threat to system and network
operations. In order to fight them more efficiently, it is necessary to analyze
newly discovered worms and attack patterns. This paper shows how techniques
based on Kolmogorov Complexity can help in the analysis of internet worms and
network traffic. Using compression, different species of worms can be clustered
by type. This allows us to determine whether an unknown worm binary could in
fact be a later version of an existing worm in an extremely simple, automated,
manner. This may become a useful tool in the initial analysis of malicious
binaries. Furthermore, compression can also be useful to distinguish different
types of network traffic and can thus help to detect traffic anomalies: Certain
anomalies may be detected by looking at the compressibility of a network
session alone. We furthermore show how to use compression to detect malicious
network sessions that are very similar to known intrusion attempts. This
technique could become a useful tool to detect new variations of an attack and
thus help to prevent IDS evasion. We provide two new plugins for Snort which
demonstrate both approaches.


title: On the Entropy Rate of Pattern Processes

abstract:
  We study the entropy rate of pattern sequences of stochastic processes, and
its relationship to the entropy rate of the original process. We give a
complete characterization of this relationship for i.i.d. processes over
arbitrary alphabets, stationary ergodic processes over discrete alphabets, and
a broad family of stationary ergodic processes over uncountable alphabets. For
cases where the entropy rate of the pattern process is infinite, we
characterize the possible growth rate of the block entropy.


title: Pushdown dimension

abstract:
  This paper develops the theory of pushdown dimension and explores its
relationship with finite-state dimension. Pushdown dimension is trivially
bounded above by finite-state dimension for all sequences, since a pushdown
gambler can simulate any finite-state gambler. We show that for every rational
0 < d < 1, there exists a sequence with finite-state dimension d whose pushdown
dimension is at most d/2. This establishes a quantitative analogue of the
well-known fact that pushdown automata decide strictly more languages than
finite automata.


title: Oracles Are Subtle But Not Malicious

abstract:
  Theoretical computer scientists have been debating the role of oracles since
the 1970's. This paper illustrates both that oracles can give us nontrivial
insights about the barrier problems in circuit complexity, and that they need
not prevent us from trying to solve those problems.
  First, we give an oracle relative to which PP has linear-sized circuits, by
proving a new lower bound for perceptrons and low- degree threshold
polynomials. This oracle settles a longstanding open question, and generalizes
earlier results due to Beigel and to Buhrman, Fortnow, and Thierauf. More
importantly, it implies the first nonrelativizing separation of "traditional"
complexity classes, as opposed to interactive proof classes such as MIP and
MA-EXP. For Vinodchandran showed, by a nonrelativizing argument, that PP does
not have circuits of size n^k for any fixed k. We present an alternative proof
of this fact, which shows that PP does not even have quantum circuits of size
n^k with quantum advice. To our knowledge, this is the first nontrivial lower
bound on quantum circuit size.
  Second, we study a beautiful algorithm of Bshouty et al. for learning Boolean
circuits in ZPP^NP. We show that the NP queries in this algorithm cannot be
parallelized by any relativizing technique, by giving an oracle relative to
which ZPP^||NP and even BPP^||NP have linear-size circuits. On the other hand,
we also show that the NP queries could be parallelized if P=NP. Thus, classes
such as ZPP^||NP inhabit a "twilight zone," where we need to distinguish
between relativizing and black-box techniques. Our results on this subject have
implications for computational learning theory as well as for the circuit
minimization problem.


title: Bounds on the Entropy of Patterns of I.I.D. Sequences

abstract:
  Bounds on the entropy of patterns of sequences generated by independently
identically distributed (i.i.d.) sources are derived. A pattern is a sequence
of indices that contains all consecutive integer indices in increasing order of
first occurrence. If the alphabet of a source that generated a sequence is
unknown, the inevitable cost of coding the unknown alphabet symbols can be
exploited to create the pattern of the sequence. This pattern can in turn be
compressed by itself. The bounds derived here are functions of the i.i.d.
source entropy, alphabet size, and letter probabilities. It is shown that for
large alphabets, the pattern entropy must decrease from the i.i.d. one. The
decrease is in many cases more significant than the universal coding redundancy
bounds derived in prior works. The pattern entropy is confined between two
bounds that depend on the arrangement of the letter probabilities in the
probability space. For very large alphabets whose size may be greater than the
coded pattern length, all low probability letters are packed into one symbol.
The pattern entropy is upper and lower bounded in terms of the i.i.d. entropy
of the new packed alphabet. Correction terms, which are usually negligible, are
provided for both upper and lower bounds.


title:
Mapping Fusion and Synchronized Hyperedge Replacement into Logic
  Programming

abstract:
  In this paper we compare three different formalisms that can be used in the
area of models for distributed, concurrent and mobile systems. In particular we
analyze the relationships between a process calculus, the Fusion Calculus,
graph transformations in the Synchronized Hyperedge Replacement with Hoare
synchronization (HSHR) approach and logic programming. We present a translation
from Fusion Calculus into HSHR (whereas Fusion Calculus uses Milner
synchronization) and prove a correspondence between the reduction semantics of
Fusion Calculus and HSHR transitions. We also present a mapping from HSHR into
a transactional version of logic programming and prove that there is a full
correspondence between the two formalisms. The resulting mapping from Fusion
Calculus to logic programming is interesting since it shows the tight analogies
between the two formalisms, in particular for handling name generation and
mobility. The intermediate step in terms of HSHR is convenient since graph
transformations allow for multiple, remote synchronizations, as required by
Fusion Calculus semantics.


title: A Scalable Stream-Oriented Framework for Cluster Applications

abstract:
  This paper presents a stream-oriented architecture for structuring cluster
applications. Clusters that run applications based on this architecture can
scale to tenths of thousands of nodes with significantly less performance loss
or reliability problems. Our architecture exploits the stream nature of the
data flow and reduces congestion through load balancing, hides latency behind
data pushes and transparently handles node failures. In our ongoing work, we
are developing an implementation for this architecture and we are able to run
simple data mining applications on a cluster simulator.


title: Learning Multi-Class Neural-Network Models from Electroencephalograms

abstract:
  We describe a new algorithm for learning multi-class neural-network models
from large-scale clinical electroencephalograms (EEGs). This algorithm trains
hidden neurons separately to classify all the pairs of classes. To find best
pairwise classifiers, our algorithm searches for input variables which are
relevant to the classification problem. Despite patient variability and heavily
overlapping classes, a 16-class model learnt from EEGs of 65 sleeping newborns
correctly classified 80.8% of the training and 80.1% of the testing examples.
Additionally, the neural-network model provides a probabilistic interpretation
of decisions.


title: A Neural-Network Technique for Recognition of Filaments in Solar Images

abstract:
  We describe a new neural-network technique developed for an automated
recognition of solar filaments visible in the hydrogen H-alpha line full disk
spectroheliograms. This technique allows neural networks learn from a few image
fragments labelled manually to recognize the single filaments depicted on a
local background. The trained network is able to recognize filaments depicted
on the backgrounds with variations in brightness caused by atmospherics
distortions. Despite the difference in backgrounds in our experiments the
neural network has properly recognized filaments in the testing image
fragments. Using a parabolic activation function we extend this technique to
recognize multiple solar filaments which may appear in one fragment.


title: Learning from Web: Review of Approaches

abstract:
  Knowledge discovery is defined as non-trivial extraction of implicit,
previously unknown and potentially useful information from given data.
Knowledge extraction from web documents deals with unstructured, free-format
documents whose number is enormous and rapidly growing. The artificial neural
networks are well suitable to solve a problem of knowledge discovery from web
documents because trained networks are able more accurately and easily to
classify the learning and testing examples those represent the text mining
domain. However, the neural networks that consist of large number of weighted
connections and activation units often generate the incomprehensible and
hard-to-understand models of text classification. This problem may be also
addressed to most powerful recurrent neural networks that employ the feedback
links from hidden or output units to their input units. Due to feedback links,
recurrent neural networks are able take into account of a context in document.
To be useful for data mining, self-organizing neural network techniques of
knowledge extraction have been explored and developed. Self-organization
principles were used to create an adequate neural-network structure and reduce
a dimensionality of features used to describe text documents. The use of these
principles seems interesting because ones are able to reduce a neural-network
redundancy and considerably facilitate the knowledge representation.


title: A Learning Algorithm for Evolving Cascade Neural Networks

abstract:
  A new learning algorithm for Evolving Cascade Neural Networks (ECNNs) is
described. An ECNN starts to learn with one input node and then adding new
inputs as well as new hidden neurons evolves it. The trained ECNN has a nearly
minimal number of input and hidden neurons as well as connections. The
algorithm was successfully applied to classify artifacts and normal segments in
clinical electroencephalograms (EEGs). The EEG segments were visually labeled
by EEG-viewer. The trained ECNN has correctly classified 96.69% of the testing
segments. It is slightly better than a standard fully connected neural network.


title: Self-Organizing Multilayered Neural Networks of Optimal Complexity

abstract:
  The principles of self-organizing the neural networks of optimal complexity
is considered under the unrepresentative learning set. The method of
self-organizing the multi-layered neural networks is offered and used to train
the logical neural networks which were applied to the medical diagnostics.


title: Diagnostic Rule Extraction Using Neural Networks

abstract:
  The neural networks have trained on incomplete sets that a doctor could
collect. Trained neural networks have correctly classified all the presented
instances. The number of intervals entered for encoding the quantitative
variables is equal two. The number of features as well as the number of neurons
and layers in trained neural networks was minimal. Trained neural networks are
adequately represented as a set of logical formulas that more comprehensible
and easy-to-understand. These formulas are as the syndrome-complexes, which may
be easily tabulated and represented as a diagnostic table that the doctors
usually use. Decision rules provide the evaluations of their confidence in
which interested a doctor. Conducted clinical researches have shown that
iagnostic decisions produced by symbolic rules have coincided with the doctor's
conclusions.


title: Polynomial Neural Networks Learnt to Classify EEG Signals

abstract:
  A neural network based technique is presented, which is able to successfully
extract polynomial classification rules from labeled electroencephalogram (EEG)
signals. To represent the classification rules in an analytical form, we use
the polynomial neural networks trained by a modified Group Method of Data
Handling (GMDH). The classification rules were extracted from clinical EEG data
that were recorded from an Alzheimer patient and the sudden death risk
patients. The third data is EEG recordings that include the normal and artifact
segments. These EEG data were visually identified by medical experts. The
extracted polynomial rules verified on the testing EEG data allow to correctly
classify 72% of the risk group patients and 96.5% of the segments. These rules
performs slightly better than standard feedforward neural networks.


title: A Neural Network Decision Tree for Learning Concepts from EEG Data

abstract:
  To learn the multi-class conceptions from the electroencephalogram (EEG) data
we developed a neural network decision tree (DT), that performs the linear
tests, and a new training algorithm. We found that the known methods fail
inducting the classification models when the data are presented by the features
some of them are irrelevant, and the classes are heavily overlapped. To train
the DT, our algorithm exploits a bottom up search of the features that provide
the best classification accuracy of the linear tests. We applied the developed
algorithm to induce the DT from the large EEG dataset consisted of 65 patients
belonging to 16 age groups. In these recordings each EEG segment was
represented by 72 calculated features. The DT correctly classified 80.8% of the
training and 80.1% of the testing examples. Correspondingly it correctly
classified 89.2% and 87.7% of the EEG recordings.


title: Universal Minimax Discrete Denoising under Channel Uncertainty

abstract:
  The goal of a denoising algorithm is to recover a signal from its
noise-corrupted observations. Perfect recovery is seldom possible and
performance is measured under a given single-letter fidelity criterion. For
discrete signals corrupted by a known discrete memoryless channel, the DUDE was
recently shown to perform this task asymptotically optimally, without knowledge
of the statistical properties of the source. In the present work we address the
scenario where, in addition to the lack of knowledge of the source statistics,
there is also uncertainty in the channel characteristics. We propose a family
of discrete denoisers and establish their asymptotic optimality under a minimax
performance criterion which we argue is appropriate for this setting. As we
show elsewhere, the proposed schemes can also be implemented computationally
efficiently.


title: Summarization from Medical Documents: A Survey

abstract:
  Objective:
  The aim of this paper is to survey the recent work in medical documents
summarization.
  Background:
  During the last decade, documents summarization got increasing attention by
the AI research community. More recently it also attracted the interest of the
medical research community as well, due to the enormous growth of information
that is available to the physicians and researchers in medicine, through the
large and growing number of published journals, conference proceedings, medical
sites and portals on the World Wide Web, electronic medical records, etc.
  Methodology:
  This survey gives first a general background on documents summarization,
presenting the factors that summarization depends upon, discussing evaluation
issues and describing briefly the various types of summarization techniques. It
then examines the characteristics of the medical domain through the different
types of medical documents. Finally, it presents and discusses the
summarization techniques used so far in the medical domain, referring to the
corresponding systems and their characteristics.
  Discussion and conclusions:
  The paper discusses thoroughly the promising paths for future research in
medical documents summarization. It mainly focuses on the issue of scaling to
large collections of documents in various languages and from different media,
on personalization issues, on portability to new sub-domains, and on the
integration of summarization technology in practical applications


title: Conditional Hardness for Approximate Coloring

abstract:
  We study the coloring problem: Given a graph G, decide whether $c(G) \leq q$
or $c(G) \ge Q$, where c(G) is the chromatic number of G. We derive conditional
hardness for this problem for any constant $3 \le q < Q$. For $q\ge 4$, our
result is based on Khot's 2-to-1 conjecture [Khot'02]. For $q=3$, we base our
hardness result on a certain `fish shaped' variant of his conjecture.
  We also prove that the problem almost coloring is hard for any constant
$\eps>0$, assuming Khot's Unique Games conjecture. This is the problem of
deciding for a given graph, between the case where one can 3-color all but a
$\eps$ fraction of the vertices without monochromatic edges, and the case where
the graph contains no independent set of relative size at least $\eps$.
  Our result is based on bounding various generalized noise-stability
quantities using the invariance principle of Mossel et al [MOO'05].


title: Selection in Scale-Free Small World

abstract:
  In this paper we compare the performance characteristics of our selection
based learning algorithm for Web crawlers with the characteristics of the
reinforcement learning algorithm. The task of the crawlers is to find new
information on the Web. The selection algorithm, called weblog update, modifies
the starting URL lists of our crawlers based on the found URLs containing new
information. The reinforcement learning algorithm modifies the URL orderings of
the crawlers based on the received reinforcements for submitted documents. We
performed simulations based on data collected from the Web. The collected
portion of the Web is typical and exhibits scale-free small world (SFSW)
structure. We have found that on this SFSW, the weblog update algorithm
performs better than the reinforcement learning algorithm. It finds the new
information faster than the reinforcement learning algorithm and has better new
information/all submitted documents ratio. We believe that the advantages of
the selection algorithm over reinforcement learning algorithm is due to the
small world property of the Web.


title:
Neural-Network Techniques for Visual Mining Clinical
  Electroencephalograms

abstract:
  In this chapter we describe new neural-network techniques developed for
visual mining clinical electroencephalograms (EEGs), the weak electrical
potentials invoked by brain activity. These techniques exploit fruitful ideas
of Group Method of Data Handling (GMDH). Section 2 briefly describes the
standard neural-network techniques which are able to learn well-suited
classification modes from data presented by relevant features. Section 3
introduces an evolving cascade neural network technique which adds new input
nodes as well as new neurons to the network while the training error decreases.
This algorithm is applied to recognize artifacts in the clinical EEGs. Section
4 presents the GMDH-type polynomial networks learnt from data. We applied this
technique to distinguish the EEGs recorded from an Alzheimer and a healthy
patient as well as recognize EEG artifacts. Section 5 describes the new
neural-network technique developed to induce multi-class concepts from data. We
used this technique for inducing a 16-class concept from the large-scale
clinical EEG data. Finally we discuss perspectives of applying the
neural-network techniques to clinical EEGs.


title:
Estimating Classification Uncertainty of Bayesian Decision Tree
  Technique on Financial Data

abstract:
  Bayesian averaging over classification models allows the uncertainty of
classification outcomes to be evaluated, which is of crucial importance for
making reliable decisions in applications such as financial in which risks have
to be estimated. The uncertainty of classification is determined by a trade-off
between the amount of data available for training, the diversity of a
classifier ensemble and the required performance. The interpretability of
classification models can also give useful information for experts responsible
for making reliable classifications. For this reason Decision Trees (DTs) seem
to be attractive classification models. The required diversity of the DT
ensemble can be achieved by using the Bayesian model averaging all possible
DTs. In practice, the Bayesian approach can be implemented on the base of a
Markov Chain Monte Carlo (MCMC) technique of random sampling from the posterior
distribution. For sampling large DTs, the MCMC method is extended by Reversible
Jump technique which allows inducing DTs under given priors. For the case when
the prior information on the DT size is unavailable, the sweeping technique
defining the prior implicitly reveals a better performance. Within this Chapter
we explore the classification uncertainty of the Bayesian MCMC techniques on
some datasets from the StatLog Repository and real financial data. The
classification uncertainty is compared within an Uncertainty Envelope technique
dealing with the class posterior distribution and a given confidence
probability. This technique provides realistic estimates of the classification
uncertainty which can be easily interpreted in statistical terms with the aim
of risk evaluation.


title:
Comparison of the Bayesian and Randomised Decision Tree Ensembles within
  an Uncertainty Envelope Technique

abstract:
  Multiple Classifier Systems (MCSs) allow evaluation of the uncertainty of
classification outcomes that is of crucial importance for safety critical
applications. The uncertainty of classification is determined by a trade-off
between the amount of data available for training, the classifier diversity and
the required performance. The interpretability of MCSs can also give useful
information for experts responsible for making reliable classifications. For
this reason Decision Trees (DTs) seem to be attractive classification models
for experts. The required diversity of MCSs exploiting such classification
models can be achieved by using two techniques, the Bayesian model averaging
and the randomised DT ensemble. Both techniques have revealed promising results
when applied to real-world problems. In this paper we experimentally compare
the classification uncertainty of the Bayesian model averaging with a
restarting strategy and the randomised DT ensemble on a synthetic dataset and
some domain problems commonly used in the machine learning community. To make
the Bayesian DT averaging feasible, we use a Markov Chain Monte Carlo
technique. The classification uncertainty is evaluated within an Uncertainty
Envelope technique dealing with the class posterior distribution and a given
confidence probability. Exploring a full posterior distribution, this technique
produces realistic estimates which can be easily interpreted in statistical
terms. In our experiments we found out that the Bayesian DTs are superior to
the randomised DT ensembles within the Uncertainty Envelope technique.


title:
An Evolving Cascade Neural Network Technique for Cleaning Sleep
  Electroencephalograms

abstract:
  Evolving Cascade Neural Networks (ECNNs) and a new training algorithm capable
of selecting informative features are described. The ECNN initially learns with
one input node and then evolves by adding new inputs as well as new hidden
neurons. The resultant ECNN has a near minimal number of hidden neurons and
inputs. The algorithm is successfully used for training ECNN to recognise
artefacts in sleep electroencephalograms (EEGs) which were visually labelled by
EEG-viewers. In our experiments, the ECNN outperforms the standard
neural-network as well as evolutionary techniques.


title: Self-Organization of the Neuron Collective of Optimal Complexity

abstract:
  The optimal complexity of neural networks is achieved when the
self-organization principles is used to eliminate the contradictions existing
in accordance with the K. Godel theorem about incompleteness of the systems
based on axiomatics. The principle of S. Beer exterior addition the Heuristic
Group Method of Data Handling by A. Ivakhnenko realized is used.