title:
An Application of Rational Trees in a Logic Programming Interpreter for
  a Procedural Language

abstract:
  We describe here a simple application of rational trees to the implementation
of an interpreter for a procedural language written in a logic programming
language. This is possible in languages designed to support rational trees
(such as Prolog II and its descendants), but also in traditional Prolog, whose
data structures are initially based on Herbrand terms, but in which
implementations often omit the occurs check needed to avoid the creation of
infinite data structures. We provide code implementing two interpreters, one of
which needs non-occurs-check unification, which makes it faster (and more
economic). We provide experimental data supporting this, and we argue that
rational trees are interesting enough as to receive thorough support inside the
language.


title:
Characterization of the Burst Stabilization Protocol for the RR/RR CICQ
  Switch

abstract:
  Input buffered switches with Virtual Output Queueing (VOQ) can be unstable
when presented with unbalanced loads. Existing scheduling algorithms, including
iSLIP for Input Queued (IQ) switches and Round Robin (RR) for Combined Input
and Crossbar Queued (CICQ) switches, exhibit instability for some schedulable
loads. We investigate the use of a queue length threshold and bursting
mechanism to achieve stability without requiring internal speed-up. An
analytical model is developed to prove that the burst stabilization protocol
achieves stability and to predict the minimum burst value needed as a function
of offered load. The analytical model is shown to have very good agreement with
simulation results. These results show the advantage of the RR/RR CICQ switch
as a contender for the next generation of high-speed switches.


title:
Performance Evaluation of Packet-to-Cell Segmentation Schemes in Input
  Buffered Packet Switches

abstract:
  Most input buffered packet switches internally segment variable-length
packets into fixed-length cells. The last cell in a segmented packet will
contain overhead bytes if the packet length is not evenly divisible by the cell
length. Switch speed-up is used to compensate for this overhead. In this paper,
we develop an analytical model of a single-server queue where an input stream
of packets is segmented into cells for service. Analytical models are developed
for M/M/1, M/H2/1, and M/E2/1 queues with a discretized (or quantized) service
time. These models and simulation using real packet traces are used to evaluate
the effect of speed-up on mean queue length. We propose and evaluate a new
method of segmenting a packet trailer and subsequent packet header into a
single cell. This cell merging method reduces the required speed-up. No changes
to switch-matrix scheduling algorithms are needed. Simulation with a packet
trace shows a reduction in the needed speed-up for an iSLIP scheduled input
buffered switch.


title:
Concept of E-machine: How does a "dynamical" brain learn to process
  "symbolic" information? Part I

abstract:
  The human brain has many remarkable information processing characteristics
that deeply puzzle scientists and engineers. Among the most important and the
most intriguing of these characteristics are the brain's broad universality as
a learning system and its mysterious ability to dynamically change
(reconfigure) its behavior depending on a combinatorial number of different
contexts.
  This paper discusses a class of hypothetically brain-like dynamically
reconfigurable associative learning systems that shed light on the possible
nature of these brain's properties. The systems are arranged on the general
principle referred to as the concept of E-machine.
  The paper addresses the following questions:
  1. How can "dynamical" neural networks function as universal programmable
"symbolic" machines?
  2. What kind of a universal programmable symbolic machine can form
arbitrarily complex software in the process of programming similar to the
process of biological associative learning?
  3. How can a universal learning machine dynamically reconfigure its software
depending on a combinatorial number of possible contexts?


title: Where Fail-Safe Default Logics Fail

abstract:
  Reiter's original definition of default logic allows for the application of a
default that contradicts a previously applied one. We call failure this
condition. The possibility of generating failures has been in the past
considered as a semantical problem, and variants have been proposed to solve
it. We show that it is instead a computational feature that is needed to encode
some domains into default logic.


title:
Integrating design synthesis and assembly of structured objects in a
  visual design language

abstract:
  Computer Aided Design systems provide tools for building and manipulating
models of solid objects. Some also provide access to programming languages so
that parametrised designs can be expressed. There is a sharp distinction,
therefore, between building models, a concrete graphical editing activity, and
programming, an abstract, textual, algorithm-construction activity. The
recently proposed Language for Structured Design (LSD) was motivated by a
desire to combine the design and programming activities in one language. LSD
achieves this by extending a visual logic programming language to incorporate
the notions of solids and operations on solids. Here we investigate another
aspect of the LSD approach; namely, that by using visual logic programming as
the engine to drive the parametrised assembly of objects, we also gain the
powerful symbolic problem-solving capability that is the forte of logic
programming languages. This allows the designer/programmer to work at a higher
level, giving declarative specifications of a design in order to obtain the
design descriptions. Hence LSD integrates problem solving, design synthesis,
and prototype assembly in a single homogeneous programming/design environment.
We demonstrate this specification-to-final-assembly capability using the
masterkeying problem for designing systems of locks and keys.


title: Phantom Types and Subtyping

abstract:
  We investigate a technique from the literature, called the phantom-types
technique, that uses parametric polymorphism, type constraints, and unification
of polymorphic types to model a subtyping hierarchy. Hindley-Milner type
systems, such as the one found in Standard ML, can be used to enforce the
subtyping relation, at least for first-order values. We show that this
technique can be used to encode any finite subtyping hierarchy (including
hierarchies arising from multiple interface inheritance). We formally
demonstrate the suitability of the phantom-types technique for capturing
first-order subtyping by exhibiting a type-preserving translation from a simple
calculus with bounded polymorphism to a calculus embodying the type system of
SML.


title: Web pages search engine based on DNS

abstract:
  Search engine is main access to the largest information source in this world,
Internet. Now Internet is changing every aspect of our life. Information
retrieval service may be its most important services. But for common user,
internet search service is still far from our expectation, too many unrelated
search results, old information, etc. To solve these problems, a new system,
search engine based on DNS is proposed. The original idea, detailed content and
implementation of this system all are introduced in this paper.


title: Domain resource integration system

abstract:
  Domain Resource Integrated System (DRIS) is introduced in this paper. DRIS is
a hierarchical distributed Internet information retrieval system. This system
will solve some bottleneck problems such as long update interval, poor coverage
in current web search system. DRIS will build the information retrieval
infrastructure of Internet, but not a commercial search engine. The protocol
series of DRIS are also detailed in this paper.


title: Schedulers and Redundancy for a Class of Constraint Propagation Rules

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


title: Tournament versus Fitness Uniform Selection

abstract:
  In evolutionary algorithms a critical parameter that must be tuned is that of
selection pressure. If it is set too low then the rate of convergence towards
the optimum is likely to be slow. Alternatively if the selection pressure is
set too high the system is likely to become stuck in a local optimum due to a
loss of diversity in the population. The recent Fitness Uniform Selection
Scheme (FUSS) is a conceptually simple but somewhat radical approach to
addressing this problem - rather than biasing the selection towards higher
fitness, FUSS biases selection towards sparsely populated fitness levels. In
this paper we compare the relative performance of FUSS with the well known
tournament selection scheme on a range of problems.


title: A Flexible Rule Compiler for Speech Synthesis

abstract:
  We present a flexible rule compiler developed for a text-to-speech (TTS)
system. The compiler converts a set of rules into a finite-state transducer
(FST). The input and output of the FST are subject to parameterization, so that
the system can be applied to strings and sequences of feature-structures. The
resulting transducer is guaranteed to realize a function (as opposed to a
relation), and therefore can be implemented as a deterministic device (either a
deterministic FST or a bimachine).


title: Generating connected acyclic digraphs uniformly at random

abstract:
  We describe a simple algorithm based on a Markov chain process to generate
simply connected acyclic directed graphs over a fixed set of vertices. This
algorithm is an extension of a previous one, designed to generate acyclic
digraphs, non necessarily connected.


title: A Theory of Computation Based on Quantum Logic (I)

abstract:
  The (meta)logic underlying classical theory of computation is Boolean
(two-valued) logic. Quantum logic was proposed by Birkhoff and von Neumann as a
logic of quantum mechanics more than sixty years ago. The major difference
between Boolean logic and quantum logic is that the latter does not enjoy
distributivity in general. The rapid development of quantum computation in
recent years stimulates us to establish a theory of computation based on
quantum logic. The present paper is the first step toward such a new theory and
it focuses on the simplest models of computation, namely finite automata. It is
found that the universal validity of many properties of automata depend heavily
upon the distributivity of the underlying logic. This indicates that these
properties does not universally hold in the realm of quantum logic. On the
other hand, we show that a local validity of them can be recovered by imposing
a certain commutativity to the (atomic) statements about the automata under
consideration. This reveals an essential difference between the classical
theory of computation and the computation theory based on quantum logic.


title:
Protecting Public-Access Sites Against Distributed Denial-of-Service
  Attacks

abstract:
  A distributed denial-of-service (DDoS) attack can flood a victim site with
malicious traffic, causing service disruption or even complete failure.
Public-access sites like amazon or ebay are particularly vulnerable to such
attacks, because they have no way of a priori blocking unauthorized traffic.
  We present Active Internet Traffic Filtering (AITF), a mechanism that
protects public-access sites from highly distributed attacks by causing
undesired traffic to be blocked as close as possible to its sources. We
identify filters as a scarce resource and show that AITF protects a significant
amount of the victim's bandwidth, while requiring from each participating
router a number of filters that can be accommodated by today's routers. AITF is
incrementally deployable, because it offers a substantial benefit even to the
first sites that deploy it.


title: Stream cipher based on quasigroup string transformations in $Z_p^*$

abstract:
  In this paper we design a stream cipher that uses the algebraic structure of
the multiplicative group $\bbbz_p^*$ (where p is a big prime number used in
ElGamal algorithm), by defining a quasigroup of order $p-1$ and by doing
quasigroup string transformations. The cryptographical strength of the proposed
stream cipher is based on the fact that breaking it would be at least as hard
as solving systems of multivariate polynomial equations modulo big prime number
$p$ which is NP-hard problem and there are no known fast randomized or
deterministic algorithms for solving it. Unlikely the speed of known ciphers
that work in $\bbbz_p^*$ for big prime numbers $p$, the speed of this stream
cipher both in encryption and decryption phase is comparable with the fastest
symmetric-key stream ciphers.


title: Scalable Probabilistic Models for 802.11 Protocol Verification

abstract:
  The IEEE 802.11 protocol is a popular standard for wireless local area
networks. Its medium access control layer (MAC) is a carrier sense multiple
access with collision avoidance (CSMA/CA) design and includes an exponential
backoff mechanism that makes it a possible target for probabilistic model
checking. In this work, we identify ways to increase the scope of application
of probabilistic model checking to the 802.11 MAC. Current techniques do not
scale to networks of even moderate size. To work around this problem, we
identify properties of the protocol that can be used to simplify the models and
make verification feasible. Using these observations, we directly optimize the
probabilistic timed automata models while preserving probabilistic reachability
measures. We substantiate our claims of significant reduction by our results
from using the probabilistic model checker PRISM.


title:
On the Practicality of Intrinsic Reconfiguration As a Fault Recovery
  Method in Analog Systems

abstract:
  Evolvable hardware combines the powerful search capability of evolutionary
algorithms with the flexibility of reprogrammable devices, thereby providing a
natural framework for reconfiguration. This framework has generated an interest
in using evolvable hardware for fault-tolerant systems because reconfiguration
can effectively deal with hardware faults whenever it is impossible to provide
spares. But systems cannot tolerate faults indefinitely, which means
reconfiguration does have a deadline. The focus of previous evolvable hardware
research relating to fault-tolerance has been primarily restricted to restoring
functionality, with no real consideration of time constraints. In this paper we
are concerned with evolvable hardware performing reconfiguration under deadline
constraints. In particular, we investigate reconfigurable hardware that
undergoes intrinsic evolution. We show that fault recovery done by intrinsic
reconfiguration has some restrictions, which designers cannot ignore.


title: Mathematical Analysis of Multi-Agent Systems

abstract:
  We review existing approaches to mathematical modeling and analysis of
multi-agent systems in which complex collective behavior arises out of local
interactions between many simple agents. Though the behavior of an individual
agent can be considered to be stochastic and unpredictable, the collective
behavior of such systems can have a simple probabilistic description. We show
that a class of mathematical models that describe the dynamics of collective
behavior of multi-agent systems can be written down from the details of the
individual agent controller. The models are valid for Markov or memoryless
agents, in which each agents future state depends only on its present state and
not any of the past states. We illustrate the approach by analyzing in detail
applications from the robotics domain: collaboration and foraging in groups of
robots.


title: Enhancing the expressive power of the U-Datalog language

abstract:
  U-Datalog has been developed with the aim of providing a set-oriented logical
update language, guaranteeing update parallelism in the context of a
Datalog-like language. In U-Datalog, updates are expressed by introducing
constraints (+p(X), to denote insertion, and [minus sign]p(X), to denote
deletion) inside Datalog rules. A U-Datalog program can be interpreted as a CLP
program. In this framework, a set of updates (constraints) is satisfiable if it
does not represent an inconsistent theory, that is, it does not require the
insertion and the deletion of the same fact. This approach resembles a very
simple form of negation. However, on the other hand, U-Datalog does not provide
any mechanism to explicitly deal with negative information, resulting in a
language with limited expressive power. In this paper, we provide a semantics,
based on stratification, handling the use of negated atoms in U-Datalog
programs, and we show which problems arise in defining a compositional
semantics.


title: Dealing With Curious Players in Secure Networks

abstract:
  In secure communications networks there are a great number of user
behavioural problems, which need to be dealt with. Curious players pose a very
real and serious threat to the integrity of such a network. By traversing a
network a Curious player could uncover secret information, which that user has
no need to know, by simply posing as a loyalty check. Loyalty checks are done
simply to gauge the integrity of the network with respect to players who act in
a malicious manner. We wish to propose a method, which can deal with Curious
players trying to obtain "Need to Know" information using a combined
Fault-tolerant, Cryptographic and Game Theoretic Approach.


title: Government mandated blocking of foreign Web content

abstract:
  Blocking of foreign Web content by Internet access providers has been a hot
topic for the last 18 months in Germany. Since fall 2001 the state of
North-Rhine-Westphalia very actively tries to mandate such blocking. This paper
will take a technical view on the problems imposed by the blocking orders and
blocking content at access or network provider level in general. It will also
give some empirical data on the effects of the blocking orders to help in the
legal assessment of the orders.


title:
Delimited continuations in natural language: quantification and polarity
  sensitivity

abstract:
  Making a linguistic theory is like making a programming language: one
typically devises a type system to delineate the acceptable utterances and a
denotational semantics to explain observations on their behavior. Via this
connection, the programming language concept of delimited continuations can
help analyze natural language phenomena such as quantification and polarity
sensitivity. Using a logical metalanguage whose syntax includes control
operators and whose semantics involves evaluation order, these analyses can be
expressed in direct style rather than continuation-passing style, and these
phenomena can be thought of as computational side effects.


title: Polarity sensitivity and evaluation order in type-logical grammar

abstract:
  We present a novel, type-logical analysis of_polarity sensitivity_: how
negative polarity items (like "any" and "ever") or positive ones (like "some")
are licensed or prohibited. It takes not just scopal relations but also linear
order into account, using the programming-language notions of delimited
continuations and evaluation order, respectively. It thus achieves greater
empirical coverage than previous proposals.


title: Efficient dot product over word-size finite fields

abstract:
  We want to achieve efficiency for the exact computation of the dot product of
two vectors over word-size finite fields. We therefore compare the practical
behaviors of a wide range of implementation techniques using different
representations. The techniques used include oating point representations,
discrete logarithms, tabulations, Montgomery reduction, delayed modulus.


title: Tabular Parsing

abstract:
  This is a tutorial on tabular parsing, on the basis of tabulation of
nondeterministic push-down automata. Discussed are Earley's algorithm, the
Cocke-Kasami-Younger algorithm, tabular LR parsing, the construction of parse
trees, and further issues.


title: On the universality of rank distributions of website popularity

abstract:
  We present an extensive analysis of long-term statistics of the queries to
websites using logs collected on several web caches in Russian academic
networks and on US IRCache caches. We check the sensitivity of the statistics
to several parameters: (1) duration of data collection, (2) geographical
location of the cache server collecting data, and (3) the year of data
collection. We propose a two-parameter modification of the Zipf law and
interpret the parameters. We find that the rank distribution of websites is
stable when approximated by the modified Zipf law. We suggest that website
popularity may be a universal property of Internet.


title: Parametric external predicates for the DLV System

abstract:
  This document describes syntax, semantics and implementation guidelines in
order to enrich the DLV system with the possibility to make external C function
calls. This feature is realized by the introduction of parametric external
predicates, whose extension is not specified through a logic program but
implicitly computed through external code.


title:
Toward the Implementation of Functions in the DLV System (Preliminary
  Technical Report)

abstract:
  This document describes the functions as they are treated in the DLV system.
We give first the language, then specify the main implementation issues.


title: Tycoon: A Distributed Market-based Resource Allocation System

abstract:
  P2P clusters like the Grid and PlanetLab enable in principle the same
statistical multiplexing efficiency gains for computing as the Internet
provides for networking. The key unsolved problem is resource allocation.
Existing solutions are not economically efficient and require high latency to
acquire resources. We designed and implemented Tycoon, a market based
distributed resource allocation system based on an Auction Share scheduling
algorithm. Preliminary results show that Tycoon achieves low latency and high
fairness while providing incentives for truth-telling on the part of strategic
users.


title: A Modular and Fault-Tolerant Data Transport Framework

abstract:
  The High Level Trigger (HLT) of the future ALICE heavy-ion experiment has to
reduce its input data rate of up to 25 GB/s to at most 1.25 GB/s for output
before the data is written to permanent storage. To cope with these data rates
a large PC cluster system is being designed to scale to several 1000 nodes,
connected by a fast network. For the software that will run on these nodes a
flexible data transport and distribution software framework, described in this
thesis, has been developed. The framework consists of a set of separate
components, that can be connected via a common interface. This allows to
construct different configurations for the HLT, that are even changeable at
runtime. To ensure a fault-tolerant operation of the HLT, the framework
includes a basic fail-over mechanism that allows to replace whole nodes after a
failure. The mechanism will be further expanded in the future, utilizing the
runtime reconnection feature of the framework's component interface. To connect
cluster nodes a communication class library is used that abstracts from the
actual network technology and protocol used to retain flexibility in the
hardware choice. It contains already two working prototype versions for the TCP
protocol as well as SCI network adapters. Extensions can be added to the
library without modifications to other parts of the framework. Extensive tests
and measurements have been performed with the framework. Their results as well
as conclusions drawn from them are also presented in this thesis. Performance
tests show very promising results for the system, indicating that it can
fulfill ALICE's requirements concerning the data transport.


title:
The study of distributed computing algorithms by multithread
  applications

abstract:
  The material in this note is used as an introduction to distributed
algorithms in a four year course on software and automatic control system in
the computer technology department of the Komsomolsk-on-Amur state technical
university. All our the program examples are written in Borland C/C++ 5.02 for
Windows 95/98/2000/NT/XP, and hence suit to compile and execute by Visual
C/C++. We consider the following approaches of the distributed computing: the
conversion of recursive algorithms to multithread applications, a realization
of the pairing algorithm, the building of wave systems by Petri nets and object
oriented programming.


title: Parrondo's games with chaotic switching

abstract:
  This paper investigates the different effects of chaotic switching on
Parrondo's games, as compared to random and periodic switching. The rate of
winning of Parrondo's games with chaotic switching depends on coefficient(s)
defining the chaotic generator, initial conditions of the chaotic sequence and
the proportion of Game A played. Maximum rate of winning can be obtained with
all the above mentioned factors properly set, and this occurs when chaotic
switching approaches periodic behavior.


title:
Exploring tradeoffs in pleiotropy and redundancy using evolutionary
  computing

abstract:
  Evolutionary computation algorithms are increasingly being used to solve
optimization problems as they have many advantages over traditional
optimization algorithms. In this paper we use evolutionary computation to study
the trade-off between pleiotropy and redundancy in a client-server based
network. Pleiotropy is a term used to describe components that perform multiple
tasks, while redundancy refers to multiple components performing one same task.
Pleiotropy reduces cost but lacks robustness, while redundancy increases
network reliability but is more costly, as together, pleiotropy and redundancy
build flexibility and robustness into systems. Therefore it is desirable to
have a network that contains a balance between pleiotropy and redundancy. We
explore how factors such as link failure probability, repair rates, and the
size of the network influence the design choices that we explore using genetic
algorithms.


title: NLML--a Markup Language to Describe the Unlimited English Grammar

abstract:
  In this paper we present NLML (Natural Language Markup Language), a markup
language to describe the syntactic and semantic structure of any grammatically
correct English expression. At first the related works are analyzed to
demonstrate the necessity of the NLML: simple form, easy management and direct
storage. Then the description of the English grammar with NLML is introduced in
details in three levels: sentences (with different complexities, voices, moods,
and tenses), clause (relative clause and noun clause) and phrase (noun phrase,
verb phrase, prepositional phrase, adjective phrase, adverb phrase and
predicate phrase). At last the application fields of the NLML in NLP are shown
with two typical examples: NLOJM (Natural Language Object Modal in Java) and
NLDB (Natural Language Database).


title: Optimizing genetic algorithm strategies for evolving networks

abstract:
  This paper explores the use of genetic algorithms for the design of networks,
where the demands on the network fluctuate in time. For varying network
constraints, we find the best network using the standard genetic algorithm
operators such as inversion, mutation and crossover. We also examine how the
choice of genetic algorithm operators affects the quality of the best network
found. Such networks typically contain redundancy in servers, where several
servers perform the same task and pleiotropy, where servers perform multiple
tasks. We explore this trade-off between pleiotropy versus redundancy on the
cost versus reliability as a measure of the quality of the network.


title: A treatment of higher-order features in logic programming

abstract:
  The logic programming paradigm provides the basis for a new intensional view
of higher-order notions. This view is realized primarily by employing the terms
of a typed lambda calculus as representational devices and by using a richer
form of unification for probing their structures. These additions have
important meta-programming applications but they also pose non-trivial
implementation problems. One issue concerns the machine representation of
lambda terms suitable to their intended use: an adequate encoding must
facilitate comparison operations over terms in addition to supporting the usual
reduction computation. Another aspect relates to the treatment of a unification
operation that has a branching character and that sometimes calls for the
delaying of the solution of unification problems. A final issue concerns the
execution of goals whose structures become apparent only in the course of
computation. These various problems are exposed in this paper and solutions to
them are described. A satisfactory representation for lambda terms is developed
by exploiting the nameless notation of de Bruijn as well as explicit encodings
of substitutions. Special mechanisms are molded into the structure of
traditional Prolog implementations to support branching in unification and
carrying of unification problems over other computation steps; a premium is
placed in this context on exploiting determinism and on emulating usual
first-order behaviour. An extended compilation model is presented that treats
higher-order unification and also handles dynamically emergent goals. The ideas
described here have been employed in the Teyjus implementation of the Lambda
Prolog language, a fact that is used to obtain a preliminary assessment of
their efficacy.


title: Decidability and Universality in Symbolic Dynamical Systems

abstract:
  Many different definitions of computational universality for various types of
dynamical systems have flourished since Turing's work. We propose a general
definition of universality that applies to arbitrary discrete time symbolic
dynamical systems. Universality of a system is defined as undecidability of a
model-checking problem. For Turing machines, counter machines and tag systems,
our definition coincides with the classical one. It yields, however, a new
definition for cellular automata and subshifts. Our definition is robust with
respect to initial condition, which is a desirable feature for physical
realizability.
  We derive necessary conditions for undecidability and universality. For
instance, a universal system must have a sensitive point and a proper
subsystem. We conjecture that universal systems have infinite number of
subsystems. We also discuss the thesis according to which computation should
occur at the `edge of chaos' and we exhibit a universal chaotic system.


title: An Algorithm for Transforming Color Images into Tactile Graphics

abstract:
  This paper presents an algorithm that transforms color visual images, like
photographs or paintings, into tactile graphics. In the algorithm, the edges of
objects are detected and colors of the objects are estimated. Then, the edges
and the colors are encoded into lines and textures in the output tactile image.
Design of the method is substantiated by various qualities of haptic
recognizing of images. Also, means of presentation of the tactile images in
printouts are discussed. Example translated images are shown.


title: Propositional computability logic I

abstract:
  In the same sense as classical logic is a formal theory of truth, the
recently initiated approach called computability logic is a formal theory of
computability. It understands (interactive) computational problems as games
played by a machine against the environment, their computability as existence
of a machine that always wins the game, logical operators as operations on
computational problems, and validity of a logical formula as being a scheme of
"always computable" problems. The present contribution gives a detailed
exposition of a soundness and completeness proof for an axiomatization of one
of the most basic fragments of computability logic. The logical vocabulary of
this fragment contains operators for the so called parallel and choice
operations, and its atoms represent elementary problems, i.e. predicates in the
standard sense. This article is self-contained as it explains all relevant
concepts. While not technically necessary, however, familiarity with the
foundational paper "Introduction to computability logic" [Annals of Pure and
Applied Logic 123 (2003), pp.1-99] would greatly help the reader in
understanding the philosophy, underlying motivations, potential and utility of
computability logic, -- the context that determines the value of the present
results. Online introduction to the subject is available at
http://www.cis.upenn.edu/~giorgi/cl.html and
http://www.csc.villanova.edu/~japaridz/CL/gsoll.html .


title: Computability Logic: a formal theory of interaction

abstract:
  Computability logic is a formal theory of (interactive) computability in the
same sense as classical logic is a formal theory of truth. This approach was
initiated very recently in "Introduction to computability logic" (Annals of
Pure and Applied Logic 123 (2003), pp.1-99). The present paper reintroduces
computability logic in a more compact and less technical way. It is written in
a semitutorial style with a general computer science, logic or mathematics
audience in mind. An Internet source on the subject is available at
http://www.cis.upenn.edu/~giorgi/cl.html, and additional material at
http://www.csc.villanova.edu/~japaridz/CL/gsoll.html .


title:
Test Collections for Patent-to-Patent Retrieval and Patent Map
  Generation in NTCIR-4 Workshop

abstract:
  This paper describes the Patent Retrieval Task in the Fourth NTCIR Workshop,
and the test collections produced in this task. We perform the invalidity
search task, in which each participant group searches a patent collection for
the patents that can invalidate the demand in an existing claim. We also
perform the automatic patent map generation task, in which the patents
associated with a specific topic are organized in a multi-dimensional matrix.


title: DAB Content Annotation and Receiver Hardware Control with XML

abstract:
  The Eureka-147 Digital Audio Broadcasting (DAB) standard defines the 'dynamic
labels' data field for holding information about the transmission content.
However, this information does not follow a well-defined structure since it is
designed to carry text for direct output to displays, for human interpretation.
This poses a problem when machine interpretation of DAB content information is
desired. Extensible Markup Language (XML) was developed to allow for the
well-defined, structured machine-to-machine exchange of data over computer
networks. This article proposes a novel technique of machine-interpretable DAB
content annotation and receiver hardware control, involving the utilisation of
XML as metadata in the transmitted DAB frames.


title:
The Gridbus Toolkit for Service Oriented Grid and Utility Computing: An
  Overview and Status Report

abstract:
  Grids aim at exploiting synergies that result from cooperation of autonomous
distributed entities. The synergies that result from grid cooperation include
the sharing, exchange, selection, and aggregation of geographically distributed
resources such as computers, data bases, software, and scientific instruments
for solving large-scale problems in science, engineering, and commerce. For
this cooperation to be sustainable, participants need to have economic
incentive. Therefore, "incentive" mechanisms should be considered as one of key
design parameters of Grid architectures. In this article, we present an
overview and status of an open source Grid toolkit, called Gridbus, whose
architecture is fundamentally driven by the requirements of Grid economy.
Gridbus technologies provide services for both computational and data grids
that power the emerging eScience and eBusiness applications.


title:
The Random Buffer Tree : A Randomized Technique for I/O-efficient
  Algorithms

abstract:
  In this paper, we present a probabilistic self-balancing dictionary data
structure for massive data sets, and prove expected amortized I/O-optimal
bounds on the dictionary operations. We show how to use the structure as an
I/O-optimal priority queue. The data structure, which we call as the random
buffer tree, abstracts the properties of the random treap and the buffer tree
and has the same expected I/O-bounds as the buffer tree.


title: The Effect of Faults on Network Expansion

abstract:
  In this paper we study the problem of how resilient networks are to node
faults. Specifically, we investigate the question of how many faults a network
can sustain so that it still contains a large (i.e. linear-sized) connected
component that still has approximately the same expansion as the original
fault-free network. For this we apply a pruning technique which culls away
parts of the faulty network which have poor expansion. This technique can be
applied to both adversarial faults and to random faults. For adversarial faults
we prove that for every network with expansion alpha, a large connected
component with basically the same expansion as the original network exists for
up to a constant times alpha n faults. This result is tight in the sense that
every graph G of size n and uniform expansion alpha(.), i.e. G has an expansion
of alpha(n) and every subgraph G' of size m of G has an expansion of
O(alpha(m)), can be broken into sublinear components with omega(alpha(n) n)
faults.
  For random faults we observe that the situation is significantly different,
because in this case the expansion of a graph only gives a very weak bound on
its resilience to random faults. More specifically, there are networks of
uniform expansion O(sqrt{n}) that are resilient against a constant fault
probability but there are also networks of uniform expansion Omega(1/log n)
that are not resilient against a O(1/log n) fault probability. Thus, a
different parameter is needed. For this we introduce the span of a graph which
allows us to determine the maximum fault probability in a much better way than
the expansion can. We use the span to show the first known results for the
effect of random faults on the expansion of d-dimensional meshes.


title: XML framework for concept description and knowledge representation

abstract:
  An XML framework for concept description is given, based upon the fact that
the tree structure of XML implies the logical structure of concepts as defined
by attributional calculus. Especially, the attribute-value representation is
implementable in the XML framework. Since the attribute-value representation is
an important way to represent knowledge in AI, the framework offers a further
and simpler way than the powerful RDF technology.


title: Characterisations of Intersection Graphs by Vertex Orderings

abstract:
  Characterisations of interval graphs, comparability graphs, co-comparability
graphs, permutation graphs, and split graphs in terms of linear orderings of
the vertex set are presented. As an application, it is proved that interval
graphs, co-comparability graphs, AT-free graphs, and split graphs have
bandwidth bounded by their maximum degree.


title:
When Do Differences Matter? On-Line Feature Extraction Through Cognitive
  Economy

abstract:
  For an intelligent agent to be truly autonomous, it must be able to adapt its
representation to the requirements of its task as it interacts with the world.
Most current approaches to on-line feature extraction are ad hoc; in contrast,
this paper presents an algorithm that bases judgments of state compatibility
and state-space abstraction on principled criteria derived from the
psychological principle of cognitive economy. The algorithm incorporates an
active form of Q-learning, and partitions continuous state-spaces by merging
and splitting Voronoi regions. The experiments illustrate a new methodology for
testing and comparing representations by means of learning curves. Results from
the puck-on-a-hill task demonstrate the algorithm's ability to learn effective
representations, superior to those produced by some other, well-known, methods.


title: The Persistent Buffer Tree : An I/O-efficient Index for Temporal Data

abstract:
  In a variety of applications, we need to keep track of the development of a
data set over time. For maintaining and querying this multi version data
I/O-efficiently, external memory data structures are required. In this paper,
we present a probabilistic self-balancing persistent data structure in external
memory called the persistent buffer tree, which supports insertions, updates
and deletions of data items at the present version and range queries for any
version, past or present. The persistent buffer tree is I/O-optimal in the
sense that the expected amortized I/O performance bounds are asymptotically the
same as the deterministic amortized bounds of the (single version) buffer tree
in the worst case.


title:
Propagation by Selective Initialization and Its Application to Numerical
  Constraint Satisfaction Problems

abstract:
  Numerical analysis has no satisfactory method for the more realistic
optimization models. However, with constraint programming one can compute a
cover for the solution set to arbitrarily close approximation. Because the use
of constraint propagation for composite arithmetic expressions is
computationally expensive, consistency is computed with interval arithmetic. In
this paper we present theorems that support, selective initialization, a simple
modification of constraint propagation that allows composite arithmetic
expressions to be handled efficiently.


title: Elements for Response Time Statistics in ERP Transaction Systems

abstract:
  We present some measurements and ideas for response time statistics in ERP
systems. It is shown that the response time distribution of a given transaction
in a given system is generically a log-normal distribution or, in some
situations, a sum of two or more log-normal distributions. We present some
arguments for this form of the distribution based on heuristic rules for
response times, and we show data from performance measurements in actual
systems to support the log-normal form. Deviations of the log-normal form can
often be traced back to performance problems in the system. Consequences for
the interpretation of response time data and for service level agreements are
discussed.


title: Online Searching with an Autonomous Robot

abstract:
  We discuss online strategies for visibility-based searching for an object
hidden behind a corner, using Kurt3D, a real autonomous mobile robot. This task
is closely related to a number of well-studied problems. Our robot uses a
three-dimensional laser scanner in a stop, scan, plan, go fashion for building
a virtual three-dimensional environment. Besides planning trajectories and
avoiding obstacles, Kurt3D is capable of identifying objects like a chair. We
derive a practically useful and asymptotically optimal strategy that guarantees
a competitive ratio of 2, which differs remarkably from the well-studied
scenario without the need of stopping for surveying the environment. Our
strategy is used by Kurt3D, documented in a separate video.


title:
Model-checking Driven Black-box Testing Algorithms for Systems with
  Unspecified Components

abstract:
  Component-based software development has posed a serious challenge to system
verification since externally-obtained components could be a new source of
system failures. This issue can not be completely solved by either
model-checking or traditional software testing techniques alone due to several
reasons:
  1) externally obtained components are usually unspecified/partially
specified; 2)it is generally difficult to establish an adequacy criteria for
testing a component; 3)components may be used to dynamically upgrade a system.
  This paper introduces a new approach (called {\em model-checking driven
black-box testing}) that combines model-checking with traditional black-box
software testing to tackle the problem in a complete, sound, and automatic way.
  The idea is to, with respect to some requirement (expressed in CTL or LTL)
about the system, use model-checking techniques to derive a condition
(expressed in communication graphs) for an unspecified component such that the
system satisfies the requirement iff the condition is satisfied by the
component, and which can be established by testing the component with test
cases generated from the condition on-the-fly. In this paper, we present
model-checking driven black-box testing algorithms to handle both CTL and LTL
requirements.
  We also illustrate the idea through some examples.


title: 2-Sat Sub-Clauses and the Hypernodal Structure of the 3-Sat Problem

abstract:
  Like simpler graphs, nested (hypernodal) graphs consist of two components: a
set of nodes and a set of edges, where each edge connects a pair of nodes. In
the hypernodal graph model, however, a node may contain other graphs, so that a
node may be contained in a graph that it contains. The inherently recursive
structure of the hypernodal graph model aptly characterizes both the structure
and dynamic of the 3-sat problem, a broadly applicable, though intractable,
computer science problem. In this paper I first discuss the structure of the
3-sat problem, analyzing the relation of 3-sat to 2-sat, a related, though
tractable problem. I then discuss sub-clauses and sub-clause thresholds and the
transformation of sub-clauses into implication graphs, demonstrating how
combinations of implication graphs are equivalent to hypernodal graphs. I
conclude with a brief discussion of the use of hypernodal graphs to model the
3-sat problem, illustrating how hypernodal graphs model both the conditions for
satisfiability and the process by which particular 3-sat assignments either
succeed or fail.


title:
Algorithms for Estimating Information Distance with Application to
  Bioinformatics and Linguistics

abstract:
  After reviewing unnormalized and normalized information distances based on
incomputable notions of Kolmogorov complexity, we discuss how Kolmogorov
complexity can be approximated by data compression algorithms. We argue that
optimal algorithms for data compression with side information can be
successfully used to approximate the normalized distance. Next, we discuss an
alternative information distance, which is based on relative entropy rate (also
known as Kullback-Leibler divergence), and compression-based algorithms for its
estimation. Based on available biological and linguistic data, we arrive to
unexpected conclusion that in Bioinformatics and Computational Linguistics this
alternative distance is more relevant and important than the ones based on
Kolmogorov complexity.


title: Near Rationality and Competitive Equilibria in Networked Systems

abstract:
  A growing body of literature in networked systems research relies on game
theory and mechanism design to model and address the potential lack of
cooperation between self-interested users. Most game-theoretic models applied
to system research only describe competitive equilibria in terms of pure Nash
equilibria, that is, a situation where the strategy of each user is
deterministic, and is her best response to the strategies of all the other
users. However, the assumptions necessary for a pure Nash equilibrium to hold
may be too stringent for practical systems. Using three case studies on
computer security, TCP congestion control, and network formation, we outline
the limits of game-theoretic models relying on Nash equilibria, and we argue
that considering competitive equilibria of a more general form may help
reconcile predictions from game-theoretic models with empirically observed
behavior.


title: NLOMJ--Natural Language Object Model in Java

abstract:
  In this paper we present NLOMJ--a natural language object model in Java with
English as the experiment language. This modal describes the grammar elements
of any permissible expression in a natural language and their complicated
relations with each other with the concept "Object" in OOP(Object Oriented
Programming). Directly mapped to the syntax and semantics of the natural
language, it can be used in information retrieval as a linguistic method.
Around the UML diagram of the NLOMJ the important classes(Sentence, Clause and
Phrase) and their sub classes are introduced and their syntactic and semantic
meanings are explained.


title:
Extraction of topological features from communication network
  topological patterns using self-organizing feature maps

abstract:
  Different classes of communication network topologies and their
representation in the form of adjacency matrix and its eigenvalues are
presented. A self-organizing feature map neural network is used to map
different classes of communication network topological patterns. The neural
network simulation results are reported.


title: Benchmarking Blunders and Things That Go Bump in the Night

abstract:
  Benchmarking; by which I mean any computer system that is driven by a
controlled workload, is the ultimate in performance testing and simulation.
Aside from being a form of institutionalized cheating, it also offer countless
opportunities for systematic mistakes in the way the workloads are applied and
the resulting measurements interpreted. Right test, wrong conclusion is a
ubiquitous mistake that happens because test engineers tend to treat data as
divine. Such reverence is not only misplaced, it's also a sure ticket to
production hell when the application finally goes live. I demonstrate how such
mistakes can be avoided by means of two war stories that are real WOPRs. (a)
How to resolve benchmark flaws over the psychic hotline and (b) How benchmarks
can go flat with too much Java juice. In each case I present simple performance
models and show how they can be applied to correctly assess benchmark data.


title: A note on dimensions of polynomial size circuits

abstract:
  In this paper, we use resource-bounded dimension theory to investigate
polynomial size circuits. We show that for every $i\geq 0$, $\Ppoly$ has $i$th
order scaled $\pthree$-strong dimension 0. We also show that $\Ppoly^\io$ has
$\pthree$-dimension 1/2, $\pthree$-strong dimension 1. Our results improve
previous measure results of Lutz (1992) and dimension results of Hitchcock and
Vinodchandran (2004).


title:
Speculation on graph computation architectures and computing via
  synchronization

abstract:
  A speculative overview of a future topic of research. The paper is a
collection of ideas concerning two related areas:
  1) Graph computation machines ("computing with graphs"). This is the class of
models of computation in which the state of the computation is represented as a
graph or network.
  2) Arc-based neural networks, which store information not as activation in
the nodes, but rather by adding and deleting arcs. Sometimes the arcs may be
interpreted as synchronization.
  Warnings to readers: this is not the sort of thing that one might submit to a
journal or conference. No proofs are presented. The presentation is informal,
and written at an introductory level. You'll probably want to wait for a more
concise presentation.


title:
Visualising the structure of architectural open spaces based on shape
  analysis

abstract:
  This paper proposes the application of some well known two-dimensional
geometrical shape descriptors for the visualisation of the structure of
architectural open spaces. The paper demonstrates the use of visibility
measures such as distance to obstacles and amount of visible space to calculate
shape descriptors such as convexity and skeleton of the open space. The aim of
the paper is to indicate a simple, objective and quantifiable approach to
understand the structure of open spaces otherwise impossible due to the complex
construction of built structures.


title: Using matrices in post-processing phase of CFD simulations

abstract:
  In this work I present a technique of construction and fast evaluation of a
family of cubic polynomials for analytic smoothing and graphical rendering of
particles trajectories for flows in a generic geometry. The principal result of
the work was implementation and test of a method for interpolating 3D points by
regular parametric curves and their fast and efficient evaluation for a good
resolution of rendering. For the purpose I have used a parallel environment
using a multiprocessor cluster architecture. The efficiency of the used method
is good, mainly reducing the number of floating-points computations by caching
the numerical values of some line-parameter's powers, and reducing the
necessity of communication among processes. This work has been developed for
the Research and Development Department of my company for planning advanced
customized models of industrial burners.


title: Incompleteness of States w.r.t. Traces in Model Checking

abstract:
  Cousot and Cousot introduced and studied a general past/future-time
specification language, called mu*-calculus, featuring a natural time-symmetric
trace-based semantics. The standard state-based semantics of the mu*-calculus
is an abstract interpretation of its trace-based semantics, which turns out to
be incomplete (i.e., trace-incomplete), even for finite systems. As a
consequence, standard state-based model checking of the mu*-calculus is
incomplete w.r.t. trace-based model checking. This paper shows that any
refinement or abstraction of the domain of sets of states induces a
corresponding semantics which is still trace-incomplete for any propositional
fragment of the mu*-calculus. This derives from a number of results, one for
each incomplete logical/temporal connective of the mu*-calculus, that
characterize the structure of models, i.e. transition systems, whose
corresponding state-based semantics of the mu*-calculus is trace-complete.


title:
Exploiting Cross-Document Relations for Multi-document Evolving
  Summarization

abstract:
  This paper presents a methodology for summarization from multiple documents
which are about a specific topic. It is based on the specification and
identification of the cross-document relations that occur among textual
elements within those documents. Our methodology involves the specification of
the topic-specific entities, the messages conveyed for the specific entities by
certain textual elements and the specification of the relations that can hold
among these messages. The above resources are necessary for setting up a
specific topic for our query-based summarization approach which uses these
resources to identify the query-specific messages within the documents and the
query-specific relations that connect these messages across documents.


title:
A General Framework For Lazy Functional Logic Programming With Algebraic
  Polymorphic Types

abstract:
  We propose a general framework for first-order functional logic programming,
supporting lazy functions, non-determinism and polymorphic datatypes whose data
constructors obey a set C of equational axioms. On top of a given C, we specify
a program as a set R of C-based conditional rewriting rules for defined
functions. We argue that equational logic does not supply the proper semantics
for such programs. Therefore, we present an alternative logic which includes
C-based rewriting calculi and a notion of model. We get soundness and
completeness for C-based rewriting w.r.t. models, existence of free models for
all programs, and type preservation results. As operational semantics, we
develop a sound and complete procedure for goal solving, which is based on the
combination of lazy narrowing with unification modulo C. Our framework is quite
expressive for many purposes, such as solving action and change problems, or
realizing the GAMMA computation model.


title: Knowledge And The Action Description Language A

abstract:
  We introduce Ak, an extension of the action description language A (Gelfond
and Lifschitz, 1993) to handle actions which affect knowledge. We use sensing
actions to increase an agent's knowledge of the world and non-deterministic
actions to remove knowledge. We include complex plans involving conditionals
and loops in our query language for hypothetical reasoning. We also present a
translation of Ak domain descriptions into epistemic logic programs.


title: Multi-Threading And Message Communication In Qu-Prolog

abstract:
  This paper presents the multi-threading and internet message communication
capabilities of Qu-Prolog. Message addresses are symbolic and the
communications package provides high-level support that completely hides
details of IP addresses and port numbers as well as the underlying TCP/IP
transport layer. The combination of the multi-threads and the high level
inter-thread message communications provide simple, powerful support for
implementing internet distributed intelligent applications.


title: Constraint Logic Programming with Hereditary Harrop Formula

abstract:
  Constraint Logic Programming (CLP) and Hereditary Harrop formulas (HH) are
two well known ways to enhance the expressivity of Horn clauses. In this paper,
we present a novel combination of these two approaches. We show how to enrich
the syntax and proof theory of HH with the help of a given constraint system,
in such a way that the key property of HH as a logic programming language
(namely, the existence of uniform proofs) is preserved. We also present a
procedure for goal solving, showing its soundness and completeness for
computing answer constraints. As a consequence of this result, we obtain a new
strong completeness theorem for CLP that avoids the need to build disjunctions
of computed answers, as well as a more abstract formulation of a known
completeness theorem for HH.


title: New Covert Channels in HTTP

abstract:
  This paper presents new methods enabling anonymous communication on the
Internet. We describe a new protocol that allows us to create an anonymous
overlay network by exploiting the web browsing activities of regular users. We
show that the overlay network provides an anonymity set greater than the set of
senders and receivers in a realistic threat model. In particular, the protocol
provides unobservability in our threat model.


title:
Finite-Tree Analysis for Constraint Logic-Based Languages: The Complete
  Unabridged Version

abstract:
  Logic languages based on the theory of rational, possibly infinite, trees
have much appeal in that rational trees allow for faster unification (due to
the safe omission of the occurs-check) and increased expressivity (cyclic terms
can provide very efficient representations of grammars and other useful
objects). Unfortunately, the use of infinite rational trees has problems. For
instance, many of the built-in and library predicates are ill-defined for such
trees and need to be supplemented by run-time checks whose cost may be
significant. Moreover, some widely-used program analysis and manipulation
techniques are correct only for those parts of programs working over finite
trees. It is thus important to obtain, automatically, a knowledge of the
program variables (the finite variables) that, at the program points of
interest, will always be bound to finite terms. For these reasons, we propose
here a new data-flow analysis, based on abstract interpretation, that captures
such information.


title: A lambda calculus for quantum computation with classical control

abstract:
  The objective of this paper is to develop a functional programming language
for quantum computers. We develop a lambda calculus for the classical control
model, following the first author's work on quantum flow-charts. We define a
call-by-value operational semantics, and we give a type system using affine
intuitionistic linear logic. The main results of this paper are the safety
properties of the language and the development of a type inference algorithm.


title: Convergence of Discrete MDL for Sequential Prediction

abstract:
  We study the properties of the Minimum Description Length principle for
sequence prediction, considering a two-part MDL estimator which is chosen from
a countable class of models. This applies in particular to the important case
of universal sequence prediction, where the model class corresponds to all
algorithms for some fixed universal Turing machine (this correspondence is by
enumerable semimeasures, hence the resulting models are stochastic). We prove
convergence theorems similar to Solomonoff's theorem of universal induction,
which also holds for general Bayes mixtures. The bound characterizing the
convergence speed for MDL predictions is exponentially larger as compared to
Bayes mixtures. We observe that there are at least three different ways of
using MDL for prediction. One of these has worse prediction properties, for
which predictions only converge if the MDL estimator stabilizes. We establish
sufficient conditions for this to occur. Finally, some immediate consequences
for complexity relations and randomness criteria are proven.


title: Efficient coroutine generation of constrained Gray sequences

abstract:
  We study an interesting family of cooperating coroutines, which is able to
generate all patterns of bits that satisfy certain fairly general ordering
constraints, changing only one bit at a time. (More precisely, the directed
graph of constraints is required to be cycle-free when it is regarded as an
undirected graph.) If the coroutines are implemented carefully, they yield an
algorithm that needs only a bounded amount of computation per bit change,
thereby solving an open problem in the field of combinatorial pattern
generation.


title:
Toward a New Policy for Scientific and Technical Communication: the Case
  of Kyrgyz Republic

abstract:
  The objective of this policy paper is to formulate a new policy in the field
of scientific and technical information (STI) in Kyrgyz Republic in the light
of emergence and rapid development of electronic scientific communication. The
major problem with communication in science in the Republic is lack of adequate
access to information by scientists. An equally serious problem is poor
visibility of research conducted in Kyrgyzstan and, as consequence, negligible
research impact on academic society globally. The paper proposes an integrated
approach to formulation of a new STI policy based on a number of policy
components: telecommunication networks, computerization, STI systems,
legislation & standards, and education & trainings. Two alternatives were
considered: electronic vs. paper-based scientific communication and development
of the national STI system vs. cross-national virtual collaboration. The study
results in suggesting a number of policy recommendations for identified
stakeholders.


title:
Splitting an operator: Algebraic modularity results for logics with
  fixpoint semantics

abstract:
  It is well known that, under certain conditions, it is possible to split
logic programs under stable model semantics, i.e. to divide such a program into
a number of different "levels", such that the models of the entire program can
be constructed by incrementally constructing models for each level. Similar
results exist for other non-monotonic formalisms, such as auto-epistemic logic
and default logic. In this work, we present a general, algebraicsplitting
theory for logics with a fixpoint semantics. Together with the framework of
approximation theory, a general fixpoint theory for arbitrary operators, this
gives us a uniform and powerful way of deriving splitting results for each
logic with a fixpoint semantics. We demonstrate the usefulness of these
results, by generalizing existing results for logic programming, auto-epistemic
logic and default logic.


title:
Model checking for Process Rewrite Systems and a class of action--based
  regular properties

abstract:
  We consider the model checking problem for Process Rewrite Systems (PRSs), an
infinite-state formalism (non Turing-powerful) which subsumes many common
models such as Pushdown Processes and Petri Nets. PRSs can be adopted as formal
models for programs with dynamic creation and synchronization of concurrent
processes, and with recursive procedures. The model-checking problem for PRSs
and action-based linear temporal logic (ALTL) is undecidable. However,
decidability for some interesting fragment of ALTL remains an open question. In
this paper we state decidability results concerning generalized acceptance
properties about infinite derivations (infinite term rewriting) in PRSs. As a
consequence, we obtain decidability of the model-checking (restricted to
infinite runs) for PRSs and a meaningful fragment of ALTL.


title: Quantum Computers

abstract:
  This research paper gives an overview of quantum computers - description of
their operation, differences between quantum and silicon computers, major
construction problems of a quantum computer and many other basic aspects. No
special scientific knowledge is necessary for the reader.


title: Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard

abstract:
  Maximum-likelihood decoding is one of the central algorithmic problems in
coding theory. It has been known for over 25 years that maximum-likelihood
decoding of general linear codes is NP-hard. Nevertheless, it was so far
unknown whether maximum- likelihood decoding remains hard for any specific
family of codes with nontrivial algebraic structure. In this paper, we prove
that maximum-likelihood decoding is NP-hard for the family of Reed-Solomon
codes. We moreover show that maximum-likelihood decoding of Reed-Solomon codes
remains hard even with unlimited preprocessing, thereby strengthening a result
of Bruck and Naor.


title: Bi-criteria Algorithm for Scheduling Jobs on Cluster Platforms

abstract:
  We describe in this paper a new method for building an efficient algorithm
for scheduling jobs in a cluster. Jobs are considered as parallel tasks (PT)
which can be scheduled on any number of processors. The main feature is to
consider two criteria that are optimized together. These criteria are the
makespan and the weighted minimal average completion time (minsum). They are
chosen for their complementarity, to be able to represent both user-oriented
objectives and system administrator objectives. We propose an algorithm based
on a batch policy with increasing batch sizes, with a smart selection of jobs
in each batch. This algorithm is assessed by intensive simulation results,
compared to a new lower bound (obtained by a relaxation of ILP) of the optimal
schedules for both criteria separately. It is currently implemented in an
actual real-size cluster platform.


title: "In vivo" spam filtering: A challenge problem for data mining

abstract:
  Spam, also known as Unsolicited Commercial Email (UCE), is the bane of email
communication. Many data mining researchers have addressed the problem of
detecting spam, generally by treating it as a static text classification
problem. True in vivo spam filtering has characteristics that make it a rich
and challenging domain for data mining. Indeed, real-world datasets with these
characteristics are typically difficult to acquire and to share. This paper
demonstrates some of these characteristics and argues that researchers should
pursue in vivo spam filtering as an accessible domain for investigating them.


title:
A Comparative Study of Fuzzy Classification Methods on Breast Cancer
  Data

abstract:
  In this paper, we examine the performance of four fuzzy rule generation
methods on Wisconsin breast cancer data. The first method generates fuzzy if
then rules using the mean and the standard deviation of attribute values. The
second approach generates fuzzy if then rules using the histogram of attributes
values. The third procedure generates fuzzy if then rules with certainty of
each attribute into homogeneous fuzzy sets. In the fourth approach, only
overlapping areas are partitioned. The first two approaches generate a single
fuzzy if then rule for each class by specifying the membership function of each
antecedent fuzzy set using the information about attribute values of training
patterns. The other two approaches are based on fuzzy grids with homogeneous
fuzzy partitions of each attribute. The performance of each approach is
evaluated on breast cancer data sets. Simulation results show that the Modified
grid approach has a high classification rate of 99.73 %.


title: Intelligent Systems: Architectures and Perspectives

abstract:
  The integration of different learning and adaptation techniques to overcome
individual limitations and to achieve synergetic effects through the
hybridization or fusion of these techniques has, in recent years, contributed
to a large number of new intelligent system designs. Computational intelligence
is an innovative framework for constructing intelligent hybrid architectures
involving Neural Networks (NN), Fuzzy Inference Systems (FIS), Probabilistic
Reasoning (PR) and derivative free optimization techniques such as Evolutionary
Computation (EC). Most of these hybridization approaches, however, follow an ad
hoc design methodology, justified by success in certain application domains.
Due to the lack of a common framework it often remains difficult to compare the
various hybrid systems conceptually and to evaluate their performance
comparatively. This chapter introduces the different generic architectures for
integrating intelligent systems. The designing aspects and perspectives of
different hybrid archirectures like NN-FIS, EC-FIS, EC-NN, FIS-PR and NN-FIS-EC
systems are presented. Some conclusions are also provided towards the end.


title: A Neuro-Fuzzy Approach for Modelling Electricity Demand in Victoria

abstract:
  Neuro-fuzzy systems have attracted growing interest of researchers in various
scientific and engineering areas due to the increasing need of intelligent
systems. This paper evaluates the use of two popular soft computing techniques
and conventional statistical approach based on Box--Jenkins autoregressive
integrated moving average (ARIMA) model to predict electricity demand in the
State of Victoria, Australia. The soft computing methods considered are an
evolving fuzzy neural network (EFuNN) and an artificial neural network (ANN)
trained using scaled conjugate gradient algorithm (CGA) and backpropagation
(BP) algorithm. The forecast accuracy is compared with the forecasts used by
Victorian Power Exchange (VPX) and the actual energy demand. To evaluate, we
considered load demand patterns for 10 consecutive months taken every 30 min
for training the different prediction models. Test results show that the
neuro-fuzzy system performed better than neural networks, ARIMA model and the
VPX forecasts.


title: Neuro Fuzzy Systems: Sate-of-the-Art Modeling Techniques

abstract:
  Fusion of Artificial Neural Networks (ANN) and Fuzzy Inference Systems (FIS)
have attracted the growing interest of researchers in various scientific and
engineering areas due to the growing need of adaptive intelligent systems to
solve the real world problems. ANN learns from scratch by adjusting the
interconnections between layers. FIS is a popular computing framework based on
the concept of fuzzy set theory, fuzzy if-then rules, and fuzzy reasoning. The
advantages of a combination of ANN and FIS are obvious. There are several
approaches to integrate ANN and FIS and very often it depends on the
application. We broadly classify the integration of ANN and FIS into three
categories namely concurrent model, cooperative model and fully fused model.
This paper starts with a discussion of the features of each model and
generalize the advantages and deficiencies of each model. We further focus the
review on the different types of fused neuro-fuzzy systems and citing the
advantages and disadvantages of each model.


title: Is Neural Network a Reliable Forecaster on Earth? A MARS Query!

abstract:
  Long-term rainfall prediction is a challenging task especially in the modern
world where we are facing the major environmental problem of global warming. In
general, climate and rainfall are highly non-linear phenomena in nature
exhibiting what is known as the butterfly effect. While some regions of the
world are noticing a systematic decrease in annual rainfall, others notice
increases in flooding and severe storms. The global nature of this phenomenon
is very complicated and requires sophisticated computer modeling and simulation
to predict accurately. In this paper, we report a performance analysis for
Multivariate Adaptive Regression Splines (MARS)and artificial neural networks
for one month ahead prediction of rainfall. To evaluate the prediction
efficiency, we made use of 87 years of rainfall data in Kerala state, the
southern part of the Indian peninsula situated at latitude -longitude pairs
(8o29'N - 76o57' E). We used an artificial neural network trained using the
scaled conjugate gradient algorithm. The neural network and MARS were trained
with 40 years of rainfall data. For performance evaluation, network predicted
outputs were compared with the actual rainfall data. Simulation results reveal
that MARS is a good forecasting tool and performed better than the considered
neural network.


title: DCT Based Texture Classification Using Soft Computing Approach

abstract:
  Classification of texture pattern is one of the most important problems in
pattern recognition. In this paper, we present a classification method based on
the Discrete Cosine Transform (DCT) coefficients of texture image. As DCT works
on gray level image, the color scheme of each image is transformed into gray
levels. For classifying the images using DCT we used two popular soft computing
techniques namely neurocomputing and neuro-fuzzy computing. We used a
feedforward neural network trained using the backpropagation learning and an
evolving fuzzy neural network to classify the textures. The soft computing
models were trained using 80% of the texture data and remaining was used for
testing and validation purposes. A performance comparison was made among the
soft computing models for the texture classification problem. We also analyzed
the effects of prolonged training of neural networks. It is observed that the
proposed neuro-fuzzy model performed better than neural network.


title: Estimating Genome Reversal Distance by Genetic Algorithm

abstract:
  Sorting by reversals is an important problem in inferring the evolutionary
relationship between two genomes. The problem of sorting unsigned permutation
has been proven to be NP-hard. The best guaranteed error bounded is the 3/2-
approximation algorithm. However, the problem of sorting signed permutation can
be solved easily. Fast algorithms have been developed both for finding the
sorting sequence and finding the reversal distance of signed permutation. In
this paper, we present a way to view the problem of sorting unsigned
permutation as signed permutation. And the problem can then be seen as
searching an optimal signed permutation in all n2 corresponding signed
permutations. We use genetic algorithm to conduct the search. Our experimental
result shows that the proposed method outperform the 3/2-approximation
algorithm.


title: A High-Level Reconfigurable Computing Platform Software Frameworks

abstract:
  Reconfigurable computing refers to the use of processors, such as Field
Programmable Gate Arrays (FPGAs), that can be modified at the hardware level to
take on different processing tasks. A reconfigurable computing platform
describes the hardware and software base on top of which modular extensions can
be created, depending on the desired application. Such reconfigurable computing
platforms can take on varied designs and implementations, according to the
constraints imposed and features desired by the scope of applications. This
paper introduces a PC-based reconfigurable computing platform software
frameworks that is flexible and extensible enough to abstract the different
hardware types and functionality that different PCs may have. The requirements
of the software platform, architectural issues addressed, rationale behind the
decisions made, and frameworks design implemented are discussed.


title: Intrusion Detection Systems Using Adaptive Regression Splines

abstract:
  Past few years have witnessed a growing recognition of intelligent techniques
for the construction of efficient and reliable intrusion detection systems. Due
to increasing incidents of cyber attacks, building effective intrusion
detection systems (IDS) are essential for protecting information systems
security, and yet it remains an elusive goal and a great challenge. In this
paper, we report a performance analysis between Multivariate Adaptive
Regression Splines (MARS), neural networks and support vector machines. The
MARS procedure builds flexible regression models by fitting separate splines to
distinct intervals of the predictor variables. A brief comparison of different
neural network learning algorithms is also given.


title: Data Mining Approach for Analyzing Call Center Performance

abstract:
  The aim of our research was to apply well-known data mining techniques (such
as linear neural networks, multi-layered perceptrons, probabilistic neural
networks, classification and regression trees, support vector machines and
finally a hybrid decision tree neural network approach) to the problem of
predicting the quality of service in call centers; based on the performance
data actually collected in a call center of a large insurance company. Our aim
was two-fold. First, to compare the performance of models built using the
above-mentioned techniques and, second, to analyze the characteristics of the
input sensitivity in order to better understand the relationship between the
perform-ance evaluation process and the actual performance and in this way help
improve the performance of call centers. In this paper we summarize our
findings.


title: Modeling Chaotic Behavior of Stock Indices Using Intelligent Paradigms

abstract:
  The use of intelligent systems for stock market predictions has been widely
established. In this paper, we investigate how the seemingly chaotic behavior
of stock markets could be well represented using several connectionist
paradigms and soft computing techniques. To demonstrate the different
techniques, we considered Nasdaq-100 index of Nasdaq Stock MarketS and the S&P
CNX NIFTY stock index. We analyzed 7 year's Nasdaq 100 main index values and 4
year's NIFTY index values. This paper investigates the development of a
reliable and efficient technique to model the seemingly chaotic behavior of
stock markets. We considered an artificial neural network trained using
Levenberg-Marquardt algorithm, Support Vector Machine (SVM), Takagi-Sugeno
neuro-fuzzy model and a Difference Boosting Neural Network (DBNN). This paper
briefly explains how the different connectionist paradigms could be formulated
using different learning methods and then investigates whether they can provide
the required level of performance, which are sufficiently good and robust so as
to provide a reliable forecast model for stock market indices. Experiment
results reveal that all the connectionist paradigms considered could represent
the stock indices behavior very accurately.


title:
Hybrid Fuzzy-Linear Programming Approach for Multi Criteria Decision
  Making Problems

abstract:
  The purpose of this paper is to point to the usefulness of applying a linear
mathematical formulation of fuzzy multiple criteria objective decision methods
in organising business activities. In this respect fuzzy parameters of linear
programming are modelled by preference-based membership functions. This paper
begins with an introduction and some related research followed by some
fundamentals of fuzzy set theory and technical concepts of fuzzy multiple
objective decision models. Further a real case study of a manufacturing plant
and the implementation of the proposed technique is presented. Empirical
results clearly show the superiority of the fuzzy technique in optimising
individual objective functions when compared to non-fuzzy approach.
Furthermore, for the problem considered, the optimal solution helps to infer
that by incorporating fuzziness in a linear programming model either in
constraints, or both in objective functions and constraints, provides a similar
(or even better) level of satisfaction for obtained results compared to
non-fuzzy linear programming.


title: A proof of Alon's second eigenvalue conjecture and related problems

abstract:
  In this paper we show the following conjecture of Noga Alon. Fix a positive
integer d>2 and real epsilon > 0; consider the probability that a random
d-regular graph on n vertices has the second eigenvalue of its adjacency matrix
greater than 2 sqrt(d-1) + epsilon; then this probability goes to zero as n
tends to infinity.
  We prove the conjecture for a number of notions of random d-regular graph,
including models for d odd. We also estimate the aforementioned probability
more precisely, showing in many cases and models (but not all) that it decays
like a polynomial in 1/n.


title: Computing Multi-Homogeneous Bezout Numbers is Hard

abstract:
  The multi-homogeneous Bezout number is a bound for the number of solutions of
a system of multi-homogeneous polynomial equations, in a suitable product of
projective spaces.
  Given an arbitrary, not necessarily multi-homogeneous system, one can ask for
the optimal multi-homogenization that would minimize the Bezout number.
  In this paper, it is proved that the problem of computing, or even estimating
the optimal multi-homogeneous Bezout number is actually NP-hard.
  In terms of approximation theory for combinatorial optimization, the problem
of computing the best multi-homogeneous structure does not belong to APX,
unless P = NP.
  Moreover, polynomial time algorithms for estimating the minimal
multi-homogeneous Bezout number up to a fixed factor cannot exist even in a
randomized setting, unless BPP contains NP.


title: Encryption Schemes using Finite Frames and Hadamard Arrays

abstract:
  We propose a cipher similar to the One Time Pad and McEliece cipher based on
a subband coding scheme. The encoding process is an approximation to the One
Time Pad encryption scheme. We present results of numerical experiments which
suggest that a brute force attack to the proposed scheme does not result in all
possible plaintexts, as the One Time Pad does, but still the brute force attack
does not compromise the system. However, we demonstrate that the cipher is
vulnerable to a chosen-plaintext attack.


title:
A Grid Service Broker for Scheduling Distributed Data-Oriented
  Applications on Global Grids

abstract:
  The next generation of scientific experiments and studies, popularly called
as e-Science, is carried out by large collaborations of researchers distributed
around the world engaged in analysis of huge collections of data generated by
scientific instruments. Grid computing has emerged as an enabler for e-Science
as it permits the creation of virtual organizations that bring together
communities with common objectives. Within a community, data collections are
stored or replicated on distributed resources to enhance storage capability or
efficiency of access. In such an environment, scientists need to have the
ability to carry out their studies by transparently accessing distributed data
and computational resources. In this paper, we propose and develop a Grid
broker that mediates access to distributed resources by (a) discovering
suitable data sources for a given analysis scenario, (b) suitable computational
resources, (c) optimally mapping analysis jobs to resources, (d) deploying and
monitoring job execution on selected resources, (e) accessing data from local
or remote data source during job execution and (f) collating and presenting
results. The broker supports a declarative and dynamic parametric programming
model for creating grid applications. We have used this model in grid-enabling
a high energy physics analysis application (Belle Analysis Software Framework).
The broker has been used in deploying Belle experiment data analysis jobs on a
grid testbed, called Belle Analysis Data Grid, having resources distributed
across Australia interconnected through GrangeNet.


title: Meta-Learning Evolutionary Artificial Neural Networks

abstract:
  In this paper, we present MLEANN (Meta-Learning Evolutionary Artificial
Neural Network), an automatic computational framework for the adaptive
optimization of artificial neural networks wherein the neural network
architecture, activation function, connection weights; learning algorithm and
its parameters are adapted according to the problem. We explored the
performance of MLEANN and conventionally designed artificial neural networks
for function approximation problems. To evaluate the comparative performance,
we used three different well-known chaotic time series. We also present the
state of the art popular neural network learning algorithms and some
experimentation results related to convergence speed and generalization
performance. We explored the performance of backpropagation algorithm;
conjugate gradient algorithm, quasi-Newton algorithm and Levenberg-Marquardt
algorithm for the three chaotic time series. Performances of the different
learning algorithms were evaluated when the activation functions and
architecture were changed. We further present the theoretical background,
algorithm, design strategy and further demonstrate how effective and inevitable
is the proposed MLEANN framework to design a neural network, which is smaller,
faster and with a better generalization performance.


title: The Largest Compatible Subset Problem for Phylogenetic Data

abstract:
  The phylogenetic tree construction is to infer the evolutionary relationship
between species from the experimental data. However, the experimental data are
often imperfect and conflicting each others. Therefore, it is important to
extract the motif from the imperfect data. The largest compatible subset
problem is that, given a set of experimental data, we want to discard the
minimum such that the remaining is compatible. The largest compatible subset
problem can be viewed as the vertex cover problem in the graph theory that has
been proven to be NP-hard. In this paper, we propose a hybrid Evolutionary
Computing (EC) method for this problem. The proposed method combines the EC
approach and the algorithmic approach for special structured graphs. As a
result, the complexity of the problem is dramatically reduced. Experiments were
performed on randomly generated graphs with different edge densities. The
vertex covers produced by the proposed method were then compared to the vertex
covers produced by a 2-approximation algorithm. The experimental results showed
that the proposed method consistently outperformed a classical 2- approximation
algorithm. Furthermore, a significant improvement was found when the graph
density was small.


title: A Concurrent Fuzzy-Neural Network Approach for Decision Support Systems

abstract:
  Decision-making is a process of choosing among alternative courses of action
for solving complicated problems where multi-criteria objectives are involved.
The past few years have witnessed a growing recognition of Soft Computing
technologies that underlie the conception, design and utilization of
intelligent systems. Several works have been done where engineers and
scientists have applied intelligent techniques and heuristics to obtain optimal
decisions from imprecise information. In this paper, we present a concurrent
fuzzy-neural network approach combining unsupervised and supervised learning
techniques to develop the Tactical Air Combat Decision Support System (TACDSS).
Experiment results clearly demonstrate the efficiency of the proposed
technique.


title: Evolution of a Subsumption Architecture Neurocontroller

abstract:
  An approach to robotics called layered evolution and merging features from
the subsumption architecture into evolutionary robotics is presented, and its
advantages are discussed. This approach is used to construct a layered
controller for a simulated robot that learns which light source to approach in
an environment with obstacles. The evolvability and performance of layered
evolution on this task is compared to (standard) monolithic evolution,
incremental and modularised evolution. To corroborate the hypothesis that a
layered controller performs at least as well as an integrated one, the evolved
layers are merged back into a single network. On the grounds of the test
results, it is argued that layered evolution provides a superior approach for
many tasks, and it is suggested that this approach may be the key to scaling up
evolutionary robotics.


title:
Analysis of Hybrid Soft and Hard Computing Techniques for Forex
  Monitoring Systems

abstract:
  In a universe with a single currency, there would be no foreign exchange
market, no foreign exchange rates, and no foreign exchange. Over the past
twenty-five years, the way the market has performed those tasks has changed
enormously. The need for intelligent monitoring systems has become a necessity
to keep track of the complex forex market. The vast currency market is a
foreign concept to the average individual. However, once it is broken down into
simple terms, the average individual can begin to understand the foreign
exchange market and use it as a financial instrument for future investing. In
this paper, we attempt to compare the performance of hybrid soft computing and
hard computing techniques to predict the average monthly forex rates one month
ahead. The soft computing models considered are a neural network trained by the
scaled conjugate gradient algorithm and a neuro-fuzzy model implementing a
Takagi-Sugeno fuzzy inference system. We also considered Multivariate Adaptive
Regression Splines (MARS), Classification and Regression Trees (CART) and a
hybrid CART-MARS technique. We considered the exchange rates of Australian
dollar with respect to US dollar, Singapore dollar, New Zealand dollar,
Japanese yen and United Kingdom pounds. The models were trained using 70% of
the data and remaining was used for testing and validation purposes. It is
observed that the proposed hybrid models could predict the forex rates more
accurately than all the techniques when applied individually. Empirical results
also reveal that the hybrid hard computing approach also improved some of our
previous work using a neuro-fuzzy approach.


title: A New Computational Framework For 2D Shape-Enclosing Contours

abstract:
  In this paper, a new framework for one-dimensional contour extraction from
discrete two-dimensional data sets is presented. Contour extraction is
important in many scientific fields such as digital image processing, computer
vision, pattern recognition, etc. This novel framework includes (but is not
limited to) algorithms for dilated contour extraction, contour displacement,
shape skeleton extraction, contour continuation, shape feature based contour
refinement and contour simplification. Many of the new techniques depend
strongly on the application of a Delaunay tessellation. In order to demonstrate
the versatility of this novel toolbox approach, the contour extraction
techniques presented here are applied to scientific problems in material
science, biology and heavy ion physics.


title: Business Intelligence from Web Usage Mining

abstract:
  The rapid e-commerce growth has made both business community and customers
face a new situation. Due to intense competition on one hand and the customer's
option to choose from several alternatives business community has realized the
necessity of intelligent marketing strategies and relationship management. Web
usage mining attempts to discover useful knowledge from the secondary data
obtained from the interactions of the users with the Web. Web usage mining has
become very critical for effective Web site management, creating adaptive Web
sites, business and support services, personalization, network traffic flow
analysis and so on. In this paper, we present the important concepts of Web
usage mining and its various practical applications. We further present a novel
approach 'intelligent-miner' (i-Miner) to optimize the concurrent architecture
of a fuzzy clustering algorithm (to discover web data clusters) and a fuzzy
inference system to analyze the Web site visitor trends. A hybrid evolutionary
fuzzy clustering algorithm is proposed in this paper to optimally segregate
similar user interests. The clustered data is then used to analyze the trends
using a Takagi-Sugeno fuzzy inference system learned using a combination of
evolutionary algorithm and neural network learning. Proposed approach is
compared with self-organizing maps (to discover patterns) and several function
approximation techniques like neural networks, linear genetic programming and
Takagi-Sugeno fuzzy inference system (to analyze the clusters). The results are
graphically illustrated and the practical significance is discussed in detail.
Empirical results clearly show that the proposed Web usage-mining framework is
efficient.


title:
Adaptation of Mamdani Fuzzy Inference System Using Neuro - Genetic
  Approach for Tactical Air Combat Decision Support System

abstract:
  Normally a decision support system is build to solve problem where
multi-criteria decisions are involved. The knowledge base is the vital part of
the decision support containing the information or data that is used in
decision-making process. This is the field where engineers and scientists have
applied several intelligent techniques and heuristics to obtain optimal
decisions from imprecise information. In this paper, we present a hybrid
neuro-genetic learning approach for the adaptation a Mamdani fuzzy inference
system for the Tactical Air Combat Decision Support System (TACDSS). Some
simulation results demonstrating the difference of the learning techniques and
are also provided.


title:
EvoNF: A Framework for Optimization of Fuzzy Inference Systems Using
  Neural Network Learning and Evolutionary Computation

abstract:
  Several adaptation techniques have been investigated to optimize fuzzy
inference systems. Neural network learning algorithms have been used to
determine the parameters of fuzzy inference system. Such models are often
called as integrated neuro-fuzzy models. In an integrated neuro-fuzzy model
there is no guarantee that the neural network learning algorithm converges and
the tuning of fuzzy inference system will be successful. Success of
evolutionary search procedures for optimization of fuzzy inference system is
well proven and established in many application areas. In this paper, we will
explore how the optimization of fuzzy inference systems could be further
improved using a meta-heuristic approach combining neural network learning and
evolutionary computation. The proposed technique could be considered as a
methodology to integrate neural networks, fuzzy inference systems and
evolutionary search procedures. We present the theoretical frameworks and some
experimental results to demonstrate the efficiency of the proposed technique.


title:
Optimization of Evolutionary Neural Networks Using Hybrid Learning
  Algorithms

abstract:
  Evolutionary artificial neural networks (EANNs) refer to a special class of
artificial neural networks (ANNs) in which evolution is another fundamental
form of adaptation in addition to learning. Evolutionary algorithms are used to
adapt the connection weights, network architecture and learning algorithms
according to the problem environment. Even though evolutionary algorithms are
well known as efficient global search algorithms, very often they miss the best
local solutions in the complex solution space. In this paper, we propose a
hybrid meta-heuristic learning approach combining evolutionary learning and
local search methods (using 1st and 2nd order error information) to improve the
learning and faster convergence obtained using a direct evolutionary approach.
The proposed technique is tested on three different chaotic time series and the
test results are compared with some popular neuro-fuzzy systems and a recently
developed cutting angle method of global optimization. Empirical results reveal
that the proposed technique is efficient in spite of the computational
complexity.


title: Computational Geometry Column 45

abstract:
  The algorithm of Edelsbrunner for surface reconstruction by ``wrapping'' a
set of points in R^3 is described.


title:
Security-Performance Tradeoffs of Inheritance based Key Predistribution
  for Wireless Sensor Networks

abstract:
  Key predistribution is a well-known technique for ensuring secure
communication via encryption among sensors deployed in an ad-hoc manner to form
a sensor network. In this paper, we propose a novel 2-Phase technique for key
predistribution based on a combination of inherited and random key assignments
from the given key pool to individual sensor nodes. We also develop an
analytical framework for measuring security-performance tradeoffs of different
key distribution schemes by providing metrics for measuring sensornet
connectivity and resiliency to enemy attacks. In particular, we show
analytically that the 2-Phase scheme provides better average connectivity and
superior $q$-composite connectivity than the random scheme. We then prove that
the invulnerability of a communication link under arbitrary number of node
captures by an adversary is higher under the 2-Phase scheme. The probability of
a communicating node pair having an exclusive key also scales better with
network size under the 2-Phase scheme. We also show analytically that the
vulnerability of an arbitrary communication link in the sensornet to single
node capture is lower under 2-Phase assuming both network-wide as well as
localized capture. Simulation results also show that the number of exclusive
keys shared between any two nodes is higher while the number of $q$-composite
links compromised when a given number of nodes are captured by the enemy is
smaller under the 2-Phase scheme as compared to the random one.