title: HEP@Home - A distributed computing system based on BOINC

abstract:
  Project SETI@HOME has proven to be one of the biggest successes of
distributed computing during the last years. With a quite simple approach SETI
manages to process large volumes of data using a vast amount of distributed
computer power.
  To extend the generic usage of this kind of distributed computing tools,
BOINC is being developed. In this paper we propose HEP@HOME, a BOINC version
tailored to the specific requirements of the High Energy Physics (HEP)
community.
  The HEP@HOME will be able to process large amounts of data using virtually
unlimited computing power, as BOINC does, and it should be able to work
according to HEP specifications. In HEP the amounts of data to be analyzed or
reconstructed are of central importance. Therefore, one of the design
principles of this tool is to avoid data transfer. This will allow scientists
to run their analysis applications and taking advantage of a large number of
CPUs. This tool also satisfies other important requirements in HEP, namely,
security, fault-tolerance and monitoring.


title:
Automated Pattern Detection--An Algorithm for Constructing Optimally
  Synchronizing Multi-Regular Language Filters

abstract:
  In the computational-mechanics structural analysis of one-dimensional
cellular automata the following automata-theoretic analogue of the
\emph{change-point problem} from time series analysis arises: \emph{Given a
string $\sigma$ and a collection $\{\mc{D}_i\}$ of finite automata, identify
the regions of $\sigma$ that belong to each $\mc{D}_i$ and, in particular, the
boundaries separating them.} We present two methods for solving this
\emph{multi-regular language filtering problem}. The first, although providing
the ideal solution, requires a stack, has a worst-case compute time that grows
quadratically in $\sigma$'s length and conditions its output at any point on
arbitrarily long windows of future input. The second method is to
algorithmically construct a transducer that approximates the first algorithm.
In contrast to the stack-based algorithm, however, the transducer requires only
a finite amount of memory, runs in linear time, and gives immediate output for
each letter read; it is, moreover, the best possible finite-state approximation
with these three features.

categories: cs.CV cond-mat.stat-mech cs.CL cs.DS cs.IR cs.LG nlin.AO nlin.CG nlin.PS physics.comp-ph q-bio.GN


title: Utilitarian resource assignment

abstract:
  This paper studies a resource allocation problem introduced by Koutsoupias
and Papadimitriou. The scenario is modelled as a multiple-player game in which
each player selects one of a finite number of known resources. The cost to the
player is the total weight of all players who choose that resource, multiplied
by the ``delay'' of that resource. Recent papers have studied the Nash
equilibria and social optima of this game in terms of the $L_\infty$ cost
metric, in which the social cost is taken to be the maximum cost to any player.
We study the $L_1$ variant of this game, in which the social cost is taken to
be the sum of the costs to the individual players, rather than the maximum of
these costs. We give bounds on the size of the coordination ratio, which is the
ratio between the social cost incurred by selfish behavior and the optimal
social cost; we also study the algorithmic problem of finding optimal
(lowest-cost) assignments and Nash Equilibria. Additionally, we obtain bounds
on the ratio between alternative Nash equilibria for some special cases of the
problem.


title:
Finite-Length Scaling and Finite-Length Shift for Low-Density
  Parity-Check Codes

abstract:
  Consider communication over the binary erasure channel BEC using random
low-density parity-check codes with finite-blocklength n from `standard'
ensembles. We show that large error events is conveniently described within a
scaling theory, and explain how to estimate heuristically their effect. Among
other quantities, we consider the finite length threshold e(n), defined by
requiring a block error probability P_B = 1/2. For ensembles with minimum
variable degree larger than two, the following expression is argued to hold
e(n) = e -e_1 n^{-2/3} +\Theta(n^{-1}) with a calculable shift} parameter
e_1>0.


title: Adaptive Cluster Expansion (ACE): A Hierarchical Bayesian Network

abstract:
  Using the maximum entropy method, we derive the "adaptive cluster expansion"
(ACE), which can be trained to estimate probability density functions in high
dimensional spaces. The main advantage of ACE over other Bayesian networks is
its ability to capture high order statistics after short training times, which
it achieves by making use of a hierarchical vector quantisation of the input
data. We derive a scheme for representing the state of an ACE network as a
"probability image", which allows us to identify statistically anomalous
regions in an otherwise statistically homogeneous image, for instance. Finally,
we present some probability images that we obtained after training ACE on some
Brodatz texture images - these demonstrate the ability of ACE to detect subtle
textural anomalies.


title: Complexity Results in Graph Reconstruction

abstract:
  We investigate the relative complexity of the graph isomorphism problem (GI)
and problems related to the reconstruction of a graph from its vertex-deleted
or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate
deck (LD) problems). We show that these problems are closely related for all
amounts $c \geq 1$ of deletion:
  1) $GI \equiv^{l}_{iso} VDC_{c}$, $GI \equiv^{l}_{iso} EDC_{c}$, $GI
\leq^{l}_{m} LVD_c$, and $GI \equiv^{p}_{iso} LED_c$.
  2) For all $k \geq 2$, $GI \equiv^{p}_{iso} k-VDC_c$ and $GI \equiv^{p}_{iso}
k-EDC_c$.
  3) For all $k \geq 2$, $GI \leq^{l}_{m} k-LVD_c$.
  4)$GI \equiv^{p}_{iso} 2-LVC_c$.
  5) For all $k \geq 2$, $GI \equiv^{p}_{iso} k-LED_c$.
  For many of these results, even the $c = 1$ case was not previously known.
  Similar to the definition of reconstruction numbers $vrn_{\exists}(G)$ [HP85]
and $ern_{\exists}(G)$ (see page 120 of [LS03]), we introduce two new graph
parameters, $vrn_{\forall}(G)$ and $ern_{\forall}(G)$, and give an example of a
family $\{G_n\}_{n \geq 4}$ of graphs on $n$ vertices for which
$vrn_{\exists}(G_n) < vrn_{\forall}(G_n)$. For every $k \geq 2$ and $n \geq 1$,
we show that there exists a collection of $k$ graphs on $(2^{k-1}+1)n+k$
vertices with $2^{n}$ 1-vertex-preimages, i.e., one has families of graph
collections whose number of 1-vertex-preimages is huge relative to the size of
the graphs involved.


title:
RRL: A Rich Representation Language for the Description of Agent
  Behaviour in NECA

abstract:
  In this paper, we describe the Rich Representation Language (RRL) which is
used in the NECA system. The NECA system generates interactions between two or
more animated characters. The RRL is an XML compliant framework for
representing the information that is exchanged at the interfaces between the
various NECA system modules. The full XML Schemas for the RRL are available at
http://www.ai.univie.ac.at/NECA/RRL


title: All Superlinear Inverse Schemes are coNP-Hard

abstract:
  How hard is it to invert NP-problems? We show that all superlinearly
certified inverses of NP problems are coNP-hard. To do so, we develop a novel
proof technique that builds diagonalizations against certificates directly into
a circuit.


title:
The Key Authority - Secure Key Management in Hierarchical Public Key
  Infrastructures

abstract:
  We model a private key`s life cycle as a finite state machine. The states are
the key`s phases of life and the transition functions describe tasks to be done
with the key. Based on this we define and describe the key authority, a trust
center module, which potentiates the easy enforcement of secure management of
private keys in hierarchical public key infrastructures. This is done by
assembling all trust center tasks concerning the crucial handling of private
keys within one centralized module. As this module resides under full control
of the trust center`s carrier it can easily be protected by well-known
organizational and technical measures.


title: Outflanking and securely using the PIN/TAN-System

abstract:
  The PIN/TAN-system is an authentication and authorization scheme used in
e-business. Like other similar schemes it is successfully attacked by
criminals. After shortly classifying the various kinds of attacks we accomplish
malicious code attacks on real World Wide Web transaction systems. In doing so
we find that it is really easy to outflank these systems. This is even
supported by the users' behavior. We give a few simple behavior rules to
improve this situation. But their impact is limited. Also the providers support
the attacks by having implementation flaws in their installations. Finally we
show that the PIN/TAN-system is not suitable for usage in highly secure
applications.


title:
Lattice QCD Data and Metadata Archives at Fermilab and the International
  Lattice Data Grid

abstract:
  The lattice gauge theory community produces large volumes of data. Because
the data produced by completed computations form the basis for future work, the
maintenance of archives of existing data and metadata describing the
provenance, generation parameters, and derived characteristics of that data is
essential not only as a reference, but also as a basis for future work.
Development of these archives according to uniform standards both in the data
and metadata formats provided and in the software interfaces to the component
services could greatly simplify collaborations between institutions and enable
the dissemination of meaningful results.
  This paper describes the progress made in the development of a set of such
archives at the Fermilab lattice QCD facility. We are coordinating the
development of the interfaces to these facilities and the formats of the data
and metadata they provide with the efforts of the international lattice data
grid (ILDG) metadata and middleware working groups, whose goals are to develop
standard formats for lattice QCD data and metadata and a uniform interface to
archive facilities that store them. Services under development include those
commonly associate with data grids: a service registry, a metadata database, a
replica catalog, and an interface to a mass storage system. All services
provide GSI authenticated web service interfaces following modern standards,
including WSDL and SOAP, and accept and provide data and metadata following
recent XML based formats proposed by the ILDG metadata working group.


title: Detecting User Engagement in Everyday Conversations

abstract:
  This paper presents a novel application of speech emotion recognition:
estimation of the level of conversational engagement between users of a voice
communication system. We begin by using machine learning techniques, such as
the support vector machine (SVM), to classify users' emotions as expressed in
individual utterances. However, this alone fails to model the temporal and
interactive aspects of conversational engagement. We therefore propose the use
of a multilevel structure based on coupled hidden Markov models (HMM) to
estimate engagement levels in continuous natural speech. The first level is
comprised of SVM-based classifiers that recognize emotional states, which could
be (e.g.) discrete emotion types or arousal/valence levels. A high-level HMM
then uses these emotional states as input, estimating users' engagement in
conversation by decoding the internal states of the HMM. We report experimental
results obtained by applying our algorithms to the LDC Emotional Prosody and
CallFriend speech corpora.


title: Life Above Threshold: From List Decoding to Area Theorem and MSE

abstract:
  We consider communication over memoryless channels using low-density
parity-check code ensembles above the iterative (belief propagation) threshold.
What is the computational complexity of decoding (i.e., of reconstructing all
the typical input codewords for a given channel output) in this regime? We
define an algorithm accomplishing this task and analyze its typical
performance. The behavior of the new algorithm can be expressed in purely
information-theoretical terms. Its analysis provides an alternative proof of
the area theorem for the binary erasure channel. Finally, we explain how the
area theorem is generalized to arbitrary memoryless channels. We note that the
recently discovered relation between mutual information and minimal square
error is an instance of the area theorem in the setting of Gaussian channels.


title: Nondeterministic Linear Logic

abstract:
  In this paper, we introduce Linear Logic with a nondeterministic facility,
which has a self-dual additive connective. In the system the proof net
technology is available in a natural way. The important point is that
nondeterminism in the system is expressed by the process of normalization, not
by proof search. Moreover we can incorporate the system into Light Linear Logic
and Elementary Linear Logic developed by J.-Y.Girard recently: Nondeterministic
Light Linear Logic and Nondeterministic Elementary Linear Logic are defined in
a very natural way.


title: Weak Typed Boehm Theorem on IMLL

abstract:
  In the Boehm theorem workshop on Crete island, Zoran Petric called Statman's
``Typical Ambiguity theorem'' typed Boehm theorem. Moreover, he gave a new
proof of the theorem based on set-theoretical models of the simply typed lambda
calculus. In this paper, we study the linear version of the typed Boehm theorem
on a fragment of Intuitionistic Linear Logic. We show that in the
multiplicative fragment of intuitionistic linear logic without the
multiplicative unit 1 (for short IMLL) weak typed Boehm theorem holds. The
system IMLL exactly corresponds to the linear lambda calculus without
exponentials, additives and logical constants. The system IMLL also exactly
corresponds to the free symmetric monoidal closed category without the unit
object. As far as we know, our separation result is the first one with regard
to these systems in a purely syntactical manner.


title: Similarity-Based Supervisory Control of Discrete Event Systems

abstract:
  Due to the appearance of uncontrollable events in discrete event systems, one
may wish to replace the behavior leading to the uncontrollability of
pre-specified language by some quite similar one. To capture this similarity,
we introduce metric to traditional supervisory control theory and generalize
the concept of original controllability to $\ld$-controllability, where $\ld$
indicates the similarity degree of two languages. A necessary and sufficient
condition for a language to be $\ld$-controllable is provided. We then examine
some properties of $\ld$-controllable languages and present an approach to
optimizing a realization.


title: The state complexity of L^2 and L^k

abstract:
  We show that if M is a DFA with n states over an arbitrary alphabet and L =
L(M), then the worst-case state complexity of L^2 is n*2^n - 2^{n-1}. If,
however, M is a DFA over a unary alphabet, then the worst-case state complexity
of L^k is kn-k+1 for all k >= 2.


title:
An In-Depth Look at Information Fusion Rules & the Unification of Fusion
  Theories

abstract:
  This paper may look like a glossary of the fusion rules and we also introduce
new ones presenting their formulas and examples: Conjunctive, Disjunctive,
Exclusive Disjunctive, Mixed Conjunctive-Disjunctive rules, Conditional rule,
Dempster's, Yager's, Smets' TBM rule, Dubois-Prade's, Dezert-Smarandache
classical and hybrid rules, Murphy's average rule,
Inagaki-Lefevre-Colot-Vannoorenberghe Unified Combination rules [and, as
particular cases: Iganaki's parameterized rule, Weighting Average Operator,
minC (M. Daniel), and newly Proportional Conflict Redistribution rules
(Smarandache-Dezert) among which PCR5 is the most exact way of redistribution
of the conflicting mass to non-empty sets following the path of the conjunctive
rule], Zhang's Center Combination rule, Convolutive x-Averaging, Consensus
Operator (Josang), Cautious Rule (Smets), ?-junctions rules (Smets), etc. and
three new T-norm & T-conorm rules adjusted from fuzzy and neutrosophic sets to
information fusion (Tchamova-Smarandache). Introducing the degree of union and
degree of inclusion with respect to the cardinal of sets not with the fuzzy set
point of view, besides that of intersection, many fusion rules can be improved.
There are corner cases where each rule might have difficulties working or may
not get an expected result.


title:
P-time Completeness of Light Linear Logic and its Nondeterministic
  Extension

abstract:
  In CSL'99 Roversi pointed out that the Turing machine encoding of Girard's
seminal paper "Light Linear Logic" has a flaw. Moreover he presented a working
version of the encoding in Light Affine Logic, but not in Light Linear Logic.
In this paper we present a working version of the encoding in Light Linear
Logic. The idea of the encoding is based on a remark of Girard's tutorial paper
on Linear Logic. The encoding is also an example which shows usefulness of
additive connectives. Moreover we also consider a nondeterministic extension of
Light Linear Logic. We show that the extended system is NP-complete in the same
meaning as P-completeness of Light Linear Logic.


title: Overhead-Free Computation, DCFLs, and CFLs

abstract:
  We study Turing machines that are allowed absolutely no space overhead. The
only work space the machines have, beyond the fixed amount of memory implicit
in their finite-state control, is that which they can create by cannibalizing
the input bits' own space. This model more closely reflects the fixed-sized
memory of real computers than does the standard complexity-theoretic model of
linear space.
  Though some context-sensitive languages cannot be accepted by such machines,
we show that all context-free languages can be accepted nondeterministically in
polynomial time with absolutely no space overhead, and that all deterministic
context-free languages can be accepted deterministically in polynomial time
with absolutely no space overhead.


title: Self-Organised Factorial Encoding of a Toroidal Manifold

abstract:
  It is shown analytically how a neural network can be used optimally to encode
input data that is derived from a toroidal manifold. The case of a 2-layer
network is considered, where the output is assumed to be a set of discrete
neural firing events. The network objective function measures the average
Euclidean error that occurs when the network attempts to reconstruct its input
from its output. This optimisation problem is solved analytically for a
toroidal input manifold, and two types of solution are obtained: a joint
encoder in which the network acts as a soft vector quantiser, and a factorial
encoder in which the network acts as a pair of soft vector quantisers (one for
each of the circular subspaces of the torus). The factorial encoder is favoured
for small network sizes when the number of observed firing events is large.
Such self-organised factorial encoding may be used to restrict the size of
network that is required to perform a given encoding task, and will decompose
an input manifold into its constituent submanifolds.


title: Hardware-Oriented Group Solutions for Hard Problems

abstract:
  Group and individual solutions are considered for hard problems such as
satisfiability problem. Time-space trade-off in a structured active memory
provides means to achieve lower time complexity for solutions of these
problems.


title: Frequent Knot Discovery

abstract:
  We explore the possibility of applying the framework of frequent pattern
mining to a class of continuous objects appearing in nature, namely knots. We
introduce the frequent knot mining problem and present a solution. The key
observation is that a database consisting of knots can be transformed into a
transactional database. This observation is based on the Prime Decomposition
Theorem of knots.


title:
Generating All Maximal Induced Subgraphs for Hereditary,
  Connected-Hereditary and Rooted-Hereditary Properties

abstract:
  The problem of computing all maximal induced subgraphs of a graph G that have
a graph property P, also called the maximal P-subgraphs problem, is considered.
This problem is studied for hereditary, connected-hereditary and
rooted-hereditary graph properties. The maximal P-subgraphs problem is reduced
to restricted versions of this problem by providing algorithms that solve the
general problem, assuming that an algorithm for a restricted version is given.
The complexity of the algorithms are analyzed in terms of total polynomial
time, incremental polynomial time and the complexity class P-enumerable. The
general results presented allow simple proofs that the maximal P-subgraphs
problem can be solved efficiently (in terms of the input and output) for many
different properties.


title:
Two Methods for Decreasing the Computational Complexity of the MIMO ML
  Decoder

abstract:
  We propose use of QR factorization with sort and Dijkstra's algorithm for
decreasing the computational complexity of the sphere decoder that is used for
ML detection of signals on the multi-antenna fading channel. QR factorization
with sort decreases the complexity of searching part of the decoder with small
increase in the complexity required for preprocessing part of the decoder.
Dijkstra's algorithm decreases the complexity of searching part of the decoder
with increase in the storage complexity. The computer simulation demonstrates
that the complexity of the decoder is reduced by the proposed methods
significantly.


title:
Maximum Mutual Information of Space-Time Block Codes with Symbolwise
  Decodability

abstract:
  In this paper, we analyze the performance of space-time block codes which
enable symbolwise maximum likelihood decoding. We derive an upper bound of
maximum mutual information (MMI) on space-time block codes that enable
symbolwise maximum likelihood decoding for a frequency non-selective
quasi-static fading channel. MMI is an upper bound on how much one can send
information with vanishing error probability by using the target code.


title: Neural Architectures for Robot Intelligence

abstract:
  We argue that the direct experimental approaches to elucidate the
architecture of higher brains may benefit from insights gained from exploring
the possibilities and limits of artificial control architectures for robot
systems. We present some of our recent work that has been motivated by that
view and that is centered around the study of various aspects of hand actions
since these are intimately linked with many higher cognitive abilities. As
examples, we report on the development of a modular system for the recognition
of continuous hand postures based on neural nets, the use of vision and tactile
sensing for guiding prehensile movements of a multifingered hand, and the
recognition and use of hand gestures for robot teaching.
  Regarding the issue of learning, we propose to view real-world learning from
the perspective of data mining and to focus more strongly on the imitation of
observed actions instead of purely reinforcement-based exploration. As a
concrete example of such an effort we report on the status of an ongoing
project in our lab in which a robot equipped with an attention system with a
neurally inspired architecture is taught actions by using hand gestures in
conjunction with speech commands. We point out some of the lessons learnt from
this system, and discuss how systems of this kind can contribute to the study
of issues at the junction between natural and artificial cognitive systems.


title: Strategy in Ulam's Game and Tree Code Give Error-Resistant Protocols

abstract:
  We present a new approach to construction of protocols which are proof
against communication errors. The construction is based on a generalization of
the well known Ulam's game. We show equivalence between winning strategies in
this game and robust protocols for multi-party computation. We do not give any
complete theory. We want rather to describe a new fresh idea. We use a tree
code defined by Schulman. The tree code is the most important part of the
interactive version of Shannon's Coding Theorem proved by Schulman. He uses
probabilistic argument for the existence of a tree code without giving any
effective construction. We show another proof yielding a randomized
construction which in contrary to his proof almost surely gives a good code.
Moreover our construction uses much smaller alphabet.


title: An Example of Clifford Algebras Calculations with GiNaC

abstract:
  This example of Clifford algebras calculations uses GiNaC
(http://www.ginac.de/) library, which includes a support for generic Clifford
algebra starting from version~1.3.0. Both symbolic and numeric calculation are
possible and can be blended with other functions of GiNaC. This calculations
was made for the paper math.CV/0410399.
  Described features of GiNaC are already available at PyGiNaC
(http://sourceforge.net/projects/pyginac/) and due to course should propagate
into other software like GNU Octave (http://www.octave.org/), gTybalt
(http://www.fis.unipr.it/~stefanw/gtybalt.html), which use GiNaC library as
their back-end.


title:
Analysis of and workarounds for element reversal for a finite
  element-based algorithm for warping triangular and tetrahedral meshes

abstract:
  We consider an algorithm called FEMWARP for warping triangular and
tetrahedral finite element meshes that computes the warping using the finite
element method itself. The algorithm takes as input a two- or three-dimensional
domain defined by a boundary mesh (segments in one dimension or triangles in
two dimensions) that has a volume mesh (triangles in two dimensions or
tetrahedra in three dimensions) in its interior. It also takes as input a
prescribed movement of the boundary mesh. It computes as output updated
positions of the vertices of the volume mesh. The first step of the algorithm
is to determine from the initial mesh a set of local weights for each interior
vertex that describes each interior vertex in terms of the positions of its
neighbors. These weights are computed using a finite element stiffness matrix.
After a boundary transformation is applied, a linear system of equations based
upon the weights is solved to determine the final positions of the interior
vertices. The FEMWARP algorithm has been considered in the previous literature
(e.g., in a 2001 paper by Baker). FEMWARP has been succesful in computing
deformed meshes for certain applications. However, sometimes FEMWARP reverses
elements; this is our main concern in this paper. We analyze the causes for
this undesirable behavior and propose several techniques to make the method
more robust against reversals. The most successful of the proposed methods
includes combining FEMWARP with an optimization-based untangler.


title: A Note on Scheduling Equal-Length Jobs to Maximize Throughput

abstract:
  We study the problem of scheduling equal-length jobs with release times and
deadlines, where the objective is to maximize the number of completed jobs.
Preemptions are not allowed. In Graham's notation, the problem is described as
1|r_j;p_j=p|\sum U_j. We give the following results: (1) We show that the often
cited algorithm by Carlier from 1981 is not correct. (2) We give an algorithm
for this problem with running time O(n^5).


title: Simple Distributed Weighted Matchings

abstract:
  Wattenhofer [WW04] derive a complicated distributed algorithm to compute a
weighted matching of an arbitrary weighted graph, that is at most a factor 5
away from the maximum weighted matching of that graph. We show that a variant
of the obvious sequential greedy algorithm [Pre99], that computes a weighted
matching at most a factor 2 away from the maximum, is easily distributed. This
yields the best known distributed approximation algorithm for this problem so
far.


title: Worst-Case Optimal Tree Layout in External Memory

abstract:
  Consider laying out a fixed-topology tree of N nodes into external memory
with block size B so as to minimize the worst-case number of block memory
transfers required to traverse a path from the root to a node of depth D. We
prove that the optimal number of memory transfers is $$ \cases{
  \displaystyle
  \Theta\left( {D \over \lg (1{+}B)} \right)
  & when $D = O(\lg N)$, \cr
  \displaystyle
  \Theta\left( {\lg N \over \lg \left(1{+}{B \lg N \over D}\right)} \right)
  & when $D = \Omega(\lg N)$ and $D = O(B \lg N)$, \cr
  \displaystyle
  \Theta\left( {D \over B} \right)
  & when $D = \Omega(B \lg N)$.
  } $$


title: Intransitivity and Vagueness

abstract:
  There are many examples in the literature that suggest that
indistinguishability is intransitive, despite the fact that the
indistinguishability relation is typically taken to be an equivalence relation
(and thus transitive). It is shown that if the uncertainty perception and the
question of when an agent reports that two things are indistinguishable are
both carefully modeled, the problems disappear, and indistinguishability can
indeed be taken to be an equivalence relation. Moreover, this model also
suggests a logic of vagueness that seems to solve many of the problems related
to vagueness discussed in the philosophical literature. In particular, it is
shown here how the logic can handle the sorites paradox.


title:
Sleeping Beauty Reconsidered: Conditioning and Reflection in
  Asynchronous Systems

abstract:
  A careful analysis of conditioning in the Sleeping Beauty problem is done,
using the formal model for reasoning about knowledge and probability developed
by Halpern and Tuttle. While the Sleeping Beauty problem has been viewed as
revealing problems with conditioning in the presence of imperfect recall, the
analysis done here reveals that the problems are not so much due to imperfect
recall as to asynchrony. The implications of this analysis for van Fraassen's
Reflection Principle and Savage's Sure-Thing Principle are considered.


title: Turing Machine with Faults, Failures and Recovery

abstract:
  A Turing machine with faults, failures and recovery (TMF) is described. TMF
is (weakly) non-deterministic Turing machine consisting of five semi-infinite
tapes (Master Tape, Synchro Tape, Backup Tape, Backup Synchro Tape, User Tape)
and four controlling components (Program, Daemon, Apparatus, User).
Computational process consists of three phases (Program Phase, Failure Phase,
Repair Phase). C++ Simulator of a Turing machine with faults, failures and
recovery has been developed.


title: A 2-chain can interlock with a k-chain

abstract:
  One of the open problems posed in [3] is: what is the minimal number k such
that an open, flexible k-chain can interlock with a flexible 2-chain? In this
paper, we establish the assumption behind this problem, that there is indeed
some k that achieves interlocking. We prove that a flexible 2-chain can
interlock with a flexible, open 16-chain.


title:
An Extended Generalized Disjunctive Paraconsistent Data Model for
  Disjunctive Information

abstract:
  This paper presents an extension of generalized disjunctive paraconsistent
relational data model in which pure disjunctive positive and negative
information as well as mixed disjunctive positive and negative information can
be represented explicitly and manipulated. We consider explicit mixed
disjunctive information in the context of disjunctive databases as there is an
interesting interplay between these two types of information. Extended
generalized disjunctive paraconsistent relation is introduced as the main
structure in this model. The relational algebra is appropriately generalized to
work on extended generalized disjunctive paraconsistent relations and their
correctness is established.


title: Paraconsistent Intuitionistic Fuzzy Relational Data Model

abstract:
  In this paper, we present a generalization of the relational data model based
on paraconsistent intuitionistic fuzzy sets. Our data model is capable of
manipulating incomplete as well as inconsistent information. Fuzzy relation or
intuitionistic fuzzy relation can only handle incomplete information.
Associated with each relation are two membership functions one is called
truth-membership function $T$ which keeps track of the extent to which we
believe the tuple is in the relation, another is called false-membership
function which keeps track of the extent to which we believe that it is not in
the relation. A paraconsistent intuitionistic fuzzy relation is inconsistent if
there exists one tuple $a$ such that $T(a) + F(a) > 1$. In order to handle
inconsistent situation, we propose an operator called split to transform
inconsistent paraconsistent intuitionistic fuzzy relations into
pseudo-consistent paraconsistent intuitionistic fuzzy relations and do the
set-theoretic and relation-theoretic operations on them and finally use another
operator called combine to transform the result back to paraconsistent
intuitionistic fuzzy relation. For this model, we define algebraic operators
that are generalisations of the usual operators such as union, selection, join
on fuzzy relations. Our data model can underlie any database and knowledge-base
management system that deals with incomplete and inconsistent information.


title: Mathematical knowledge management is needed

abstract:
  In this lecture I discuss some aspects of MKM, Mathematical Knowledge
Management, with particuar emphasis on information storage and information
retrieval.


title: Interval Neutrosophic Logics: Theory and Applications

abstract:
  In this paper, we present the interval neutrosophic logics which generalizes
the fuzzy logic, paraconsistent logic, intuitionistic fuzzy logic and many
other non-classical and non-standard logics. We will give the formal definition
of interval neutrosophic propositional calculus and interval neutrosophic
predicate calculus. Then we give one application of interval neutrosophic
logics to do approximate reasoning.


title: Generalized Counters and Reversal Complexity

abstract:
  We generalize the definition of a counter and counter reversal complexity and
investigate the power of generalized deterministic counter automata in terms of
language recognition.


title: Robust Dialogue Understanding in HERALD

abstract:
  We tackle the problem of robust dialogue processing from the perspective of
language engineering. We propose an agent-oriented architecture that allows us
a flexible way of composing robust processors. Our approach is based on
Shoham's Agent Oriented Programming (AOP) paradigm. We will show how the AOP
agent model can be enriched with special features and components that allow us
to deal with classical problems of dialogue understanding.


title:
A knowledge-based approach to semi-automatic annotation of multimedia
  documents via user adaptation

abstract:
  Current approaches to the annotation process focus on annotation schemas,
languages for annotation, or are very application driven. In this paper it is
proposed that a more flexible architecture for annotation requires a knowledge
component to allow for flexible search and navigation of the annotated
material. In particular, it is claimed that a general approach must take into
account the needs, competencies, and goals of the producers, annotators, and
consumers of the annotated material. We propose that a user-model based
approach is, therefore, necessary.


title:
Semantic filtering by inference on domain knowledge in spoken dialogue
  systems

abstract:
  General natural dialogue processing requires large amounts of domain
knowledge as well as linguistic knowledge in order to ensure acceptable
coverage and understanding. There are several ways of integrating lexical
resources (e.g. dictionaries, thesauri) and knowledge bases or ontologies at
different levels of dialogue processing. We concentrate in this paper on how to
exploit domain knowledge for filtering interpretation hypotheses generated by a
robust semantic parser. We use domain knowledge to semantically constrain the
hypothesis space. Moreover, adding an inference mechanism allows us to complete
the interpretation when information is not explicitly available. Further, we
discuss briefly how this can be generalized towards a predictive natural
interactive system.


title: An argumentative annotation schema for meeting discussions

abstract:
  In this article, we are interested in the annotation of transcriptions of
human-human dialogue taken from meeting records. We first propose a meeting
content model where conversational acts are interpreted with respect to their
argumentative force and their role in building the argumentative structure of
the meeting discussion. Argumentation in dialogue describes the way
participants take part in the discussion and argue their standpoints. Then, we
propose an annotation scheme based on such an argumentative dialogue model as
well as the evaluation of its adequacy. The obtained higher-level semantic
annotations are exploited in the conceptual indexing of the information
contained in meeting discussions.


title:
Automatic Keyword Extraction from Spoken Text. A Comparison of two
  Lexical Resources: the EDR and WordNet

abstract:
  Lexical resources such as WordNet and the EDR electronic dictionary have been
used in several NLP tasks. Probably, partly due to the fact that the EDR is not
freely available, WordNet has been used far more often than the EDR. We have
used both resources on the same task in order to make a comparison possible.
The task is automatic assignment of keywords to multi-party dialogue episodes
(i.e. thematically coherent stretches of spoken text). We show that the use of
lexical resources in such a task results in slightly higher performances than
the use of a purely statistically based method.


title:
INSPIRE: Evaluation of a Smart-Home System for Infotainment Management
  and Device Control

abstract:
  This paper gives an overview of the assessment and evaluation methods which
have been used to determine the quality of the INSPIRE smart home system. The
system allows different home appliances to be controlled via speech, and
consists of speech and speaker recognition, speech understanding, dialogue
management, and speech output components. The performance of these components
is first assessed individually, and then the entire system is evaluated in an
interaction experiment with test users. Initial results of the assessment and
evaluation are given, in particular with respect to the transmission channel
impact on speech and speaker recognition, and the assessment of speech output
for different system metaphors.


title: Intelligent Computer Numerical Control unit for machine tools

abstract:
  The paper describes a new CNC control unit for machining centres with
learning ability and automatic intelligent generating of NC programs on the
bases of a neural network, which is built-in into a CNC unit as special device.
The device performs intelligent and completely automatically the NC part
programs only on the bases of 2D, 2,5D or 3D computer model of prismatic part.
Intervention of the operator is not needed. The neural network for milling,
drilling, reaming, threading and operations alike has learned to generate NC
programs in the learning module, which is a part of intelligent CAD/CAM system.


title: A Categorical View on Algebraic Lattices in Formal Concept Analysis

abstract:
  Formal concept analysis has grown from a new branch of the mathematical field
of lattice theory to a widely recognized tool in Computer Science and
elsewhere. In order to fully benefit from this theory, we believe that it can
be enriched with notions such as approximation by computation or
representability. The latter are commonly studied in denotational semantics and
domain theory and captured most prominently by the notion of algebraicity, e.g.
of lattices. In this paper, we explore the notion of algebraicity in formal
concept analysis from a category-theoretical perspective. To this end, we build
on the the notion of approximable concept with a suitable category and show
that the latter is equivalent to the category of algebraic lattices. At the
same time, the paper provides a relatively comprehensive account of the
representation theory of algebraic lattices in the framework of Stone duality,
relating well-known structures such as Scott information systems with further
formalisms from logic, topology, domains and lattice theory.


title: Fast Query Processing by Distributing an Index over CPU Caches

abstract:
  Data intensive applications on clusters often require requests quickly be
sent to the node managing the desired data. In many applications, one must look
through a sorted tree structure to determine the responsible node for accessing
or storing the data.
  Examples include object tracking in sensor networks, packet routing over the
internet, request processing in publish-subscribe middleware, and query
processing in database systems. When the tree structure is larger than the CPU
cache, the standard implementation potentially incurs many cache misses for
each lookup; one cache miss at each successive level of the tree. As the
CPU-RAM gap grows, this performance degradation will only become worse in the
future.
  We propose a solution that takes advantage of the growing speed of local area
networks for clusters. We split the sorted tree structure among the nodes of
the cluster. We assume that the structure will fit inside the aggregation of
the CPU caches of the entire cluster. We then send a word over the network (as
part of a larger packet containing other words) in order to examine the tree
structure in another node's CPU cache. We show that this is often faster than
the standard solution, which locally incurs multiple cache misses while
accessing each successive level of the tree.


title: Computational Unification: a Vision for Connecting Researchers

abstract:
  The extent to which the benefits of science can be fully realized depends
critically upon the quality of the connection between researchers themselves
and between researchers and members of the public. We believe that it is now
possible to improve these connections on a community-wide and even world-wide
basis through the use of an appropriate information management system. In this
paper we explore the concepts and challenges, and propose an architecture for
the implementation of such a system.
  "One of the greatest visions for science is a computational unification in
which every researcher can interact with all other researchers through use of
their own research system."
  "These features not only enable research collaboration on a scale never
previously envisaged, they also enable sharing and dissemination of scientific
knowledge to the public at large with a sophistication unparalleled in
history."


title:
Analyzing and Improving Performance of a Class of Anomaly-based
  Intrusion Detectors

abstract:
  Anomaly-based intrusion detection (AID) techniques are useful for detecting
novel intrusions into computing resources. One of the most successful AID
detectors proposed to date is stide, which is based on analysis of system call
sequences. In this paper, we present a detailed formal framework to analyze,
understand and improve the performance of stide and similar AID techniques.
Several important properties of stide-like detectors are established through
formal proofs, and validated by carefully conducted experiments using test
datasets. Finally, the framework is utilized to design two applications to
improve the cost and performance of stide-like detectors which are based on
sequence analysis. The first application reduces the cost of developing AID
detectors by identifying the critical sections in the training dataset, and the
second application identifies the intrusion context in the intrusive dataset,
that helps to fine-tune the detectors. Such fine-tuning in turn helps to
improve detection rate and reduce false alarm rate, thereby increasing the
effectiveness and efficiency of the intrusion detectors.


title: Selfish peering and routing in the Internet

abstract:
  The Internet is a loose amalgamation of independent service providers acting
in their own self-interest. We examine the implications of this economic
reality on peering relationships. Specifically, we consider how the incentives
of the providers might determine where they choose to interconnect with each
other. We consider a game where two selfish network providers must establish
peering points between their respective network graphs, given knowledge of
traffic conditions and a nearest-exit routing policy for out-going traffic, as
well as costs based on congestion and peering connectivity. We focus on the
pairwise stability equilibrium concept and use a stochastic procedure to solve
for the stochastically pairwise stable configurations. Stochastically stable
networks are selected for their robustness to deviations in strategy and are
therefore posited as the more likely networks to emerge in a dynamic setting.
We note a paucity of stochastically stable peering configurations under
asymmetric conditions, particularly to unequal interdomain traffic flow, with
adverse effects on system-wide efficiency. Under bilateral flow conditions, we
find that as the cost associated with the establishment of peering links
approaches zero, the variance in the number of peering links of stochastically
pairwise stable equilibria increases dramatically.


title: Using image partitions in 4th Dimension

abstract:
  I have plotted an image by using mathematical functions in the Database "4th
Dimension". I'm going to show an alternative method to: detect which sector has
been clicked; highlight it and combine it with other sectors already
highlighted; store the graph information in an efficient way; load and splat
image layers to reconstruct the stored graph.


title: The Cyborg Astrobiologist: First Field Experience

abstract:
  We present results from the first geological field tests of the `Cyborg
Astrobiologist', which is a wearable computer and video camcorder system that
we are using to test and train a computer-vision system towards having some of
the autonomous decision-making capabilities of a field-geologist and
field-astrobiologist. The Cyborg Astrobiologist platform has thus far been used
for testing and development of these algorithms and systems: robotic
acquisition of quasi-mosaics of images, real-time image segmentation, and
real-time determination of interesting points in the image mosaics. The
hardware and software systems function reliably, and the computer-vision
algorithms are adequate for the first field tests. In addition to the
proof-of-concept aspect of these field tests, the main result of these field
tests is the enumeration of those issues that we can improve in the future,
including: first, detection and accounting for shadows caused by 3D jagged
edges in the outcrop; second, reincorporation of more sophisticated
texture-analysis algorithms into the system; third, creation of hardware and
software capabilities to control the camera's zoom lens in an intelligent
manner; and fourth, development of algorithms for interpretation of complex
geological scenery. Nonetheless, despite these technical inadequacies, this
Cyborg Astrobiologist system, consisting of a camera-equipped wearable-computer
and its computer-vision algorithms, has demonstrated its ability of finding
genuinely interesting points in real-time in the geological scenery, and then
gathering more information about these interest points in an automated manner.

categories: cs.CV astro-ph cs.AI cs.CE cs.HC cs.RO cs.SE q-bio.NC


title: Temporal logic with predicate abstraction

abstract:
  A predicate linear temporal logic LTL_{\lambda,=} without quantifiers but
with predicate abstraction mechanism and equality is considered. The models of
LTL_{\lambda,=} can be naturally seen as the systems of pebbles (flexible
constants) moving over the elements of some (possibly infinite) domain. This
allows to use LTL_{\lambda,=} for the specification of dynamic systems using
some resources, such as processes using memory locations, mobile agents
occupying some sites, etc. On the other hand we show that LTL_{\lambda,=} is
not recursively axiomatizable and, therefore, fully automated verification of
LTL_{\lambda,=} specifications is not, in general, possible.


title: On Spatial Conjunction as Second-Order Logic

abstract:
  Spatial conjunction is a powerful construct for reasoning about dynamically
allocated data structures, as well as concurrent, distributed and mobile
computation. While researchers have identified many uses of spatial
conjunction, its precise expressive power compared to traditional logical
constructs was not previously known. In this paper we establish the expressive
power of spatial conjunction. We construct an embedding from first-order logic
with spatial conjunction into second-order logic, and more surprisingly, an
embedding from full second order logic into first-order logic with spatial
conjunction. These embeddings show that the satisfiability of formulas in
first-order logic with spatial conjunction is equivalent to the satisfiability
of formulas in second-order logic. These results explain the great expressive
power of spatial conjunction and can be used to show that adding unrestricted
spatial conjunction to a decidable logic leads to an undecidable logic. As one
example, we show that adding unrestricted spatial conjunction to two-variable
logic leads to undecidability. On the side of decidability, the embedding into
second-order logic immediately implies the decidability of first-order logic
with a form of spatial conjunction over trees. The embedding into spatial
conjunction also has useful consequences: because a restricted form of spatial
conjunction in two-variable logic preserves decidability, we obtain that a
correspondingly restricted form of second-order quantification in two-variable
logic is decidable. The resulting language generalizes the first-order theory
of boolean algebra over sets and is useful in reasoning about the contents of
data structures in object-oriented languages.


title: ReCord: A Distributed Hash Table with Recursive Structure

abstract:
  We propose a simple distributed hash table called ReCord, which is a
generalized version of Randomized-Chord and offers improved tradeoffs in
performance and topology maintenance over existing P2P systems. ReCord is
scalable and can be easily implemented as an overlay network, and offers a good
tradeoff between the node degree and query latency. For instance, an $n$-node
ReCord with $O(\log n)$ node degree has an expected latency of $\Theta(\log n)$
hops. Alternatively, it can also offer $\Theta(\frac{\log n}{\log \log n})$
hops latency at a higher cost of $O(\frac{\log^2 n}{\log
  \log n})$ node degree. Meanwhile, simulations of the dynamic behaviors of
ReCord are studied.


title: Some first thoughts on the stability of the asynchronous systems

abstract:
  The (non-initialized, non-deterministic) asynchronous systems (in the
input-output sense) are multi-valued functions from m-dimensional signals to
sets of n-dimensional signals, the concept being inspired by the modeling of
the asynchronous circuits. Our purpose is to state the problem of the their
stability.


title: Synchronization from a Categorical Perspective

abstract:
  We introduce a notion of synchronization for higher-dimensional automata,
based on coskeletons of cubical sets. Categorification transports this notion
to the setting of categorical transition systems. We apply the results to study
the semantics of an imperative programming language with message-passing.


title:
Fibonacci-Like Polynomials Produced by m-ary Huffman Codes for
  Absolutely Ordered Sequences

abstract:
  Fibonacci-like polynomials produced by m-ary Huffman codes for absolutely
ordered sequences have been described.


title: Applications of LDPC Codes to the Wiretap Channel

abstract:
  With the advent of quantum key distribution (QKD) systems, perfect (i.e.
information-theoretic) security can now be achieved for distribution of a
cryptographic key. QKD systems and similar protocols use classical
error-correcting codes for both error correction (for the honest parties to
correct errors) and privacy amplification (to make an eavesdropper fully
ignorant). From a coding perspective, a good model that corresponds to such a
setting is the wire tap channel introduced by Wyner in 1975. In this paper, we
study fundamental limits and coding methods for wire tap channels. We provide
an alternative view of the proof for secrecy capacity of wire tap channels and
show how capacity achieving codes can be used to achieve the secrecy capacity
for any wiretap channel. We also consider binary erasure channel and binary
symmetric channel special cases for the wiretap channel and propose specific
practical codes. In some cases our designs achieve the secrecy capacity and in
others the codes provide security at rates below secrecy capacity. For the
special case of a noiseless main channel and binary erasure channel, we
consider encoder and decoder design for codes achieving secrecy on the wiretap
channel; we show that it is possible to construct linear-time decodable secrecy
codes based on LDPC codes that achieve secrecy.


title: Computational Aspects of a Numerical Model for Combustion Flow

abstract:
  A computational method for numeric resolution of a PDEs system, based on a
Finite Differences schema integrated by interpolations of partial results, and
an estimate of the error of its solution respect to the normal FD solution.


title: A Directed Threshold - Signature Scheme

abstract:
  Directed signature is the solution of such problems when the signed message
contains information sensitive to the signature receiver. Generally, in many
application of directed signature, the signer is generally a single person. But
when the message is on behalf of an organization, a valid sensitive message may
require the approval of several people. Threshold signature schemes are used to
solve these problems. This paper presents a threshold directed signature
scheme.


title:
Capacity Achieving Code Constructions for Two Classes of (d,k)
  Constraints

abstract:
  In this paper, we present two low complexity algorithms that achieve capacity
for the noiseless (d,k) constrained channel when k=2d+1, or when k-d+1 is not
prime. The first algorithm, called symbol sliding, is a generalized version of
the bit flipping algorithm introduced by Aviran et al. [1]. In addition to
achieving capacity for (d,2d+1) constraints, it comes close to capacity in
other cases. The second algorithm is based on interleaving, and is a
generalized version of the bit stuffing algorithm introduced by Bender and Wolf
[2]. This method uses fewer than k-d biased bit streams to achieve capacity for
(d,k) constraints with k-d+1 not prime. In particular, the encoder for
(d,d+2^m-1) constraints, 1\le m<\infty, requires only m biased bit streams.


title: Basic properties for sand automata

abstract:
  We prove several results about the relations between injectivity and
surjectivity for sand automata. Moreover, we begin the exploration of the
dynamical behavior of sand automata proving that the property of nilpotency is
undecidable. We believe that the proof technique used for this last result
might reveal useful for many other results in this context.


title: Intuitionistic computability logic

abstract:
  Computability logic (CL) is a systematic formal theory of computational tasks
and resources, which, in a sense, can be seen as a semantics-based alternative
to (the syntactically introduced) linear logic. With its expressive and
flexible language, where formulas represent computational problems and "truth"
is understood as algorithmic solvability, CL potentially offers a comprehensive
logical basis for constructive applied theories and computing systems
inherently requiring constructive and computationally meaningful underlying
logics.
  Among the best known constructivistic logics is Heyting's intuitionistic
calculus INT, whose language can be seen as a special fragment of that of CL.
The constructivistic philosophy of INT, however, has never really found an
intuitively convincing and mathematically strict semantical justification. CL
has good claims to provide such a justification and hence a materialization of
Kolmogorov's known thesis "INT = logic of problems". The present paper contains
a soundness proof for INT with respect to the CL semantics. A comprehensive
online source on CL is available at http://www.cis.upenn.edu/~giorgi/cl.html


title: The equations of the ideal latches

abstract:
  The latches are simple circuits with feedback from the digital electrical
engineering. We have included in our work the C element of Muller, the RS
latch, the clocked RS latch, the D latch and also circuits containing two
interconnected latches: the edge triggered RS flip-flop, the D flip-flop, the
JK flip-flop, the T flip-flop. The purpose of this study is to model with
equations the previous circuits, considered to be ideal, i.e. non-inertial. The
technique of analysis is the pseudoboolean differential calculus.


title: A Trace Logic for Local Security Properties

abstract:
  We propose a new simple \emph{trace} logic that can be used to specify
\emph{local security properties}, i.e. security properties that refer to a
single participant of the protocol specification. Our technique allows a
protocol designer to provide a formal specification of the desired security
properties, and integrate it naturally into the design process of cryptographic
protocols. Furthermore, the logic can be used for formal verification. We
illustrate the utility of our technique by exposing new attacks on the well
studied protocol TMN.


title:
Capacity Analysis for Continuous Alphabet Channels with Side
  Information, Part I: A General Framework

abstract:
  Capacity analysis for channels with side information at the receiver has been
an active area of interest. This problem is well investigated for the case of
finite alphabet channels. However, the results are not easily generalizable to
the case of continuous alphabet channels due to analytic difficulties inherent
with continuous alphabets. In the first part of this two-part paper, we address
an analytical framework for capacity analysis of continuous alphabet channels
with side information at the receiver. For this purpose, we establish novel
necessary and sufficient conditions for weak* continuity and strict concavity
of the mutual information. These conditions are used in investigating the
existence and uniqueness of the capacity-achieving measures. Furthermore, we
derive necessary and sufficient conditions that characterize the capacity value
and the capacity-achieving measure for continuous alphabet channels with side
information at the receiver.


title:
Capacity Analysis for Continuous Alphabet Channels with Side
  Information, Part II: MIMO Channels

abstract:
  In this part, we consider the capacity analysis for wireless mobile systems
with multiple antenna architectures. We apply the results of the first part to
a commonly known baseband, discrete-time multiple antenna system where both the
transmitter and receiver know the channel's statistical law. We analyze the
capacity for additive white Gaussian noise (AWGN) channels, fading channels
with full channel state information (CSI) at the receiver, fading channels with
no CSI, and fading channels with partial CSI at the receiver. For each type of
channels, we study the capacity value as well as issues such as the existence,
uniqueness, and characterization of the capacity-achieving measures for
different types of moment constraints. The results are applicable to both
Rayleigh and Rician fading channels in the presence of arbitrary line-of-sight
and correlation profiles.


title: Efficient Algorithms for Large-Scale Topology Discovery

abstract:
  There is a growing interest in discovery of internet topology at the
interface level. A new generation of highly distributed measurement systems is
currently being deployed. Unfortunately, the research community has not
examined the problem of how to perform such measurements efficiently and in a
network-friendly manner. In this paper we make two contributions toward that
end. First, we show that standard topology discovery methods (e.g., skitter)
are quite inefficient, repeatedly probing the same interfaces. This is a
concern, because when scaled up, such methods will generate so much traffic
that they will begin to resemble DDoS attacks. We measure two kinds of
redundancy in probing (intra- and inter-monitor) and show that both kinds are
important. We show that straightforward approaches to addressing these two
kinds of redundancy must take opposite tacks, and are thus fundamentally in
conflict. Our second contribution is to propose and evaluate Doubletree, an
algorithm that reduces both types of redundancy simultaneously on routers and
end systems. The key ideas are to exploit the tree-like structure of routes to
and from a single point in order to guide when to stop probing, and to probe
each path by starting near its midpoint. Our results show that Doubletree can
reduce both types of measurement load on the network dramatically, while
permitting discovery of nearly the same set of nodes and links. We then show
how to enable efficient communication between monitors through the use of Bloom
filters.


title:
Rate Distortion and Denoising of Individual Data Using Kolmogorov
  complexity

abstract:
  We examine the structure of families of distortion balls from the perspective
of Kolmogorov complexity. Special attention is paid to the canonical
rate-distortion function of a source word which returns the minimal Kolmogorov
complexity of all distortion balls containing that word subject to a bound on
their cardinality. This canonical rate-distortion function is related to the
more standard algorithmic rate-distortion function for the given distortion
measure. Examples are given of list distortion, Hamming distortion, and
Euclidean distortion. The algorithmic rate-distortion function can behave
differently from Shannon's rate-distortion function. To this end, we show that
the canonical rate-distortion function can and does assume a wide class of
shapes (unlike Shannon's); we relate low algorithmic mutual information to low
Kolmogorov complexity (and consequently suggest that certain aspects of the
mutual information formulation of Shannon's rate-distortion function behave
differently than would an analogous formulation using algorithmic mutual
information); we explore the notion that low Kolmogorov complexity distortion
balls containing a given word capture the interesting properties of that word
(which is hard to formalize in Shannon's theory) and this suggests an approach
to denoising; and, finally, we show that the different behavior of the
rate-distortion curves of individual source words to some extent disappears
after averaging over the source words.


title: Bounded Input Bounded Predefined Control Bounded Output

abstract:
  The paper is an attempt to generalize a methodology, which is similar to the
bounded-input bounded-output method currently widely used for the system
stability studies. The presented earlier methodology allows decomposition of
input space into bounded subspaces and defining for each subspace its bounding
surface. It also defines a corresponding predefined control, which maps any
point of a bounded input into a desired bounded output subspace. This
methodology was improved by providing a mechanism for the fast defining a
bounded surface. This paper presents enhanced bounded-input
bounded-predefined-control bounded-output approach, which provides adaptability
feature to the control and allows transferring of a controlled system along a
suboptimal trajectory.


title:
Intelligent search strategies based on adaptive Constraint Handling
  Rules

abstract:
  The most advanced implementation of adaptive constraint processing with
Constraint Handling Rules (CHR) allows the application of intelligent search
strategies to solve Constraint Satisfaction Problems (CSP). This presentation
compares an improved version of conflict-directed backjumping and two variants
of dynamic backtracking with respect to chronological backtracking on some of
the AIM instances which are a benchmark set of random 3-SAT problems. A CHR
implementation of a Boolean constraint solver combined with these different
search strategies in Java is thus being compared with a CHR implementation of
the same Boolean constraint solver combined with chronological backtracking in
SICStus Prolog. This comparison shows that the addition of ``intelligence'' to
the search process may reduce the number of search steps dramatically.
Furthermore, the runtime of their Java implementations is in most cases faster
than the implementations of chronological backtracking. More specifically,
conflict-directed backjumping is even faster than the SICStus Prolog
implementation of chronological backtracking, although our Java implementation
of CHR lacks the optimisations made in the SICStus Prolog system. To appear in
Theory and Practice of Logic Programming (TPLP).


title: Analysis of 802.11b MAC: A QoS, Fairness, and Performance Perspective

abstract:
  Wireless LANs have achieved a tremendous amount of growth in recent years.
Among various wireless LAN technologies, the IEEE 802.11b based wireless LAN
technology can be cited as the most prominent technology today. Despite being
widely deployed, 802.11b cannot be termed as a well matured technology.
Although 802.11b is adequate for basic connectivity and packet switching, It is
evident that there is ample scope for its improvement in areas like quality of
service, fairness, performance, security, etc. In this survey report, we
identify and argue that the Medium Access Controller for 802.11b networks is
the prime area for these improvements. To enunciate our claims we highlight
some of the quality of service, fairness, and performance issues related to
802.11b MAC. We also describe and analyze some of the current research aimed at
addressing these issues. We then propose a novel scheme called the Intelligent
Collision Avoidance, seeking to enhance the MAC to address some of the
performance issues in 802.11b and similar networks.


title:
Artificial Intelligence and Systems Theory: Applied to Cooperative
  Robots

abstract:
  This paper describes an approach to the design of a population of cooperative
robots based on concepts borrowed from Systems Theory and Artificial
Intelligence. The research has been developed under the SocRob project, carried
out by the Intelligent Systems Laboratory at the Institute for Systems and
Robotics - Instituto Superior Tecnico (ISR/IST) in Lisbon. The acronym of the
project stands both for "Society of Robots" and "Soccer Robots", the case study
where we are testing our population of robots. Designing soccer robots is a
very challenging problem, where the robots must act not only to shoot a ball
towards the goal, but also to detect and avoid static (walls, stopped robots)
and dynamic (moving robots) obstacles. Furthermore, they must cooperate to
defeat an opposing team. Our past and current research in soccer robotics
includes cooperative sensor fusion for world modeling, object recognition and
tracking, robot navigation, multi-robot distributed task planning and
coordination, including cooperative reinforcement learning in cooperative and
adversarial environments, and behavior-based architectures for real time task
execution of cooperating robot teams.


title: Programmable Ethernet Switches and Their Applications

abstract:
  Modern Ethernet switches support many advanced features beyond route learning
and packet forwarding such as VLAN tagging, IGMP snooping, rate limiting, and
status monitoring, which can be controlled through a programmatic interface.
Traditionally, these features are mostly used to statically configure a
network. This paper proposes to apply them as dynamic control mechanisms to
maximize physical network link resources, to minimize failure recovery time, to
enforce QoS requirements, and to support link-layer multicast without
broadcasting. With these advanced programmable control mechanisms, standard
Ethernet switches can be used as effective building blocks for
metropolitan-area Ethernet networks (MEN), storage-area networks (SAN), and
computation cluster interconnects. We demonstrate the usefulness of this new
level of control over Ethernet switches with a MEN architecture that features
multi-fold throughput gains and sub-second failure recovery time.


title: Dynamic Modelling and Adaptive Traction Control for Mobile Robots

abstract:
  Mobile robots have received a great deal of research in recent years. A
significant amount of research has been published in many aspects related to
mobile robots. Most of the research is devoted to design and develop some
control techniques for robot motion and path planning. A large number of
researchers have used kinematic models to develop motion control strategy for
mobile robots. Their argument and assumption that these models are valid if the
robot has low speed, low acceleration and light load. However, dynamic
modelling of mobile robots is very important as they are designed to travel at
higher speed and perform heavy duty work. This paper presents and discusses a
new approach to develop a dynamic model and control strategy for wheeled mobile
robot which I modelled as a rigid body that roles on two wheels and a castor.
The motion control strategy consists of two levels. The first level is dealing
with the dynamic of the system and denoted as Low level controller. The second
level is developed to take care of path planning and trajectory generation.


title: Coevolution Based Adaptive Monte Carlo Localization (CEAMCL)

abstract:
  An adaptive Monte Carlo localization algorithm based on coevolution mechanism
of ecological species is proposed. Samples are clustered into species, each of
which represents a hypothesis of the robots pose. Since the coevolution between
the species ensures that the multiple distinct hypotheses can be tracked
stably, the problem of premature convergence when using MCL in highly symmetric
environments can be solved. And the sample size can be adjusted adaptively over
time according to the uncertainty of the robots pose by using the population
growth model. In addition, by using the crossover and mutation operators in
evolutionary computation, intra-species evolution can drive the samples move
towards the regions where the desired posterior density is large. So a small
size of samples can represent the desired density well enough to make precise
localization. The new algorithm is termed coevolution based adaptive Monte
Carlo localization (CEAMCL). Experiments have been carried out to prove the
efficiency of the new localization algorithm.


title: Topological Navigation of Simulated Robots using Occupancy Grid

abstract:
  Formerly I presented a metric navigation method in the Webots mobile robot
simulator. The navigating Khepera-like robot builds an occupancy grid of the
environment and explores the square-shaped room around with a value iteration
algorithm. Now I created a topological navigation procedure based on the
occupancy grid process. The extension by a skeletonization algorithm results a
graph of important places and the connecting routes among them. I also show the
significant time profit gained during the process.


title:
Design and Implementation of a General Decision-making Model in RoboCup
  Simulation

abstract:
  The study of the collaboration, coordination and negotiation among different
agents in a multi-agent system (MAS) has always been the most challenging yet
popular in the research of distributed artificial intelligence. In this paper,
we will suggest for RoboCup simulation, a typical MAS, a general
decision-making model, rather than define a different algorithm for each tactic
(e.g. ball handling, pass, shoot and interception, etc.) in soccer games as
most RoboCup simulation teams did. The general decision-making model is based
on two critical factors in soccer games: the vertical distance to the goal line
and the visual angle for the goalpost. We have used these two parameters to
formalize the defensive and offensive decisions in RoboCup simulation and the
results mentioned above had been applied in NOVAURO, original name is UJDB, a
RoboCup simulation team of Jiangsu University, whose decision-making model,
compared with that of Tsinghua University, the world champion team in 2001, is
a universal model and easier to be implemented.


title: Space Robotics Part 2: Space-based Manipulators

abstract:
  In this second of three short papers, I introduce some of the basic concepts
of space robotics with an emphasis on some specific challenging areas of
research that are peculiar to the application of robotics to space
infrastructure development. The style of these short papers is pedagogical and
the concepts in this paper are developed from fundamental manipulator robotics.
This second paper considers the application of space manipulators to on-orbit
servicing (OOS), an application which has considerable commercial application.
I provide some background to the notion of robotic on-orbit servicing and
explore how manipulator control algorithms may be modified to accommodate space
manipulators which operate in the micro-gravity of space.


title: Bionic Humans Using EAP as Artificial Muscles Reality and Challenges

abstract:
  For many years, the idea of a human with bionic muscles immediately conjures
up science fiction images of a TV series superhuman character that was
implanted with bionic muscles and portrayed with strength and speed far
superior to any normal human. As fantastic as this idea may seem, recent
developments in electroactive polymers (EAP) may one day make such bionics
possible. Polymers that exhibit large displacement in response to stimulation
that is other than electrical signal were known for many years. Initially, EAP
received relatively little attention due to their limited actuation capability.
However, in the recent years, the view of the EAP materials has changed due to
the introduction of effective new materials that significantly surpassed the
capability of the widely used piezoelectric polymer, PVDF. As this technology
continues to evolve, novel mechanisms that are biologically inspired are
expected to emerge. EAP materials can potentially provide actuation with
lifelike response and more flexible configurations. While further improvements
in performance and robustness are still needed, there already have been several
reported successes. In recognition of the need for cooperation in this
multidisciplinary field, the author initiated and organized a series of
international forums that are leading to a growing number of research and
development projects and to great advances in the field. In 1999, he challenged
the worldwide science and engineering community of EAP experts to develop a
robotic arm that is actuated by artificial muscles to win a wrestling match
against a human opponent. In this paper, the field of EAP as artificial muscles
will be reviewed covering the state of the art, the challenges and the vision
for the progress in future years.


title: A Search Relevancy Tuning Method Using Expert Results Content Evaluation

abstract:
  The article presents an online relevancy tuning method using explicit user
feedback. The author developed and tested a method of words' weights
modification based on search result evaluation by user. User decides whether
the result is useful or not after inspecting the full result content. The
experiment proved that the constantly accumulated words weights base leads to
better search quality in a specified data domain. The author also suggested
future improvements of the method.


title:
Extremal Properties of Three Dimensional Sensor Networks with
  Applications

abstract:
  In this paper, we analyze various critical transmitting/sensing ranges for
connectivity and coverage in three-dimensional sensor networks. As in other
large-scale complex systems, many global parameters of sensor networks undergo
phase transitions: For a given property of the network, there is a critical
threshold, corresponding to the minimum amount of the communication effort or
power expenditure by individual nodes, above (resp. below) which the property
exists with high (resp. a low) probability. For sensor networks, properties of
interest include simple and multiple degrees of connectivity/coverage. First,
we investigate the network topology according to the region of deployment, the
number of deployed sensors and their transmitting/sensing ranges. More
specifically, we consider the following problems: Assume that $n$ nodes, each
capable of sensing events within a radius of $r$, are randomly and uniformly
distributed in a 3-dimensional region $\mathcal{R}$ of volume $V$, how large
must the sensing range be to ensure a given degree of coverage of the region to
monitor? For a given transmission range, what is the minimum (resp. maximum)
degree of the network? What is then the typical hop-diameter of the underlying
network? Next, we show how these results affect algorithmic aspects of the
network by designing specific distributed protocols for sensor networks.


title:
A machine-independent port of the SR language run-time system to the
  NetBSD operating system

abstract:
  SR (synchronizing resources) is a PASCAL - style language enhanced with
constructs for concurrent programming developed at the University of Arizona in
the late 1980s. MPD (presented in Gregory Andrews' book about Foundations of
Multithreaded, Parallel, and Distributed Programming) is its successor,
providing the same language primitives with a different syntax. The run-time
system (in theory, identical) of both languages provides the illusion of a
multiprocessor machine on a single single- or multi- CPU Unix-like system or a
(local area) network of Unix-like machines. Chair V of the Computer Science
Department of the University of Bonn is operating a laboratory for a practical
course in parallel programming consisting of computing nodes running
NetBSD/arm, normally used via PVM, MPI etc. We are considering to offer SR and
MPD for this, too. As the original language distributions are only targeted at
a few commercial Unix systems, some porting effort is needed, outlined in the
SR porting guide. The integrated POSIX threads support of NetBSD-2.0 should
allow us to use library primitives provided for NetBSD's phtread system to
implement the primitives needed by the SR run-time system, thus implementing 13
target CPUs at once and automatically making use of SMP on VAX, Alpha, PowerPC,
Sparc, 32-bit Intel and 64 bit AMD CPUs.
  This paper describes work in progress.


title: Modules and Logic Programming

abstract:
  We study conditions for a concurrent construction of proof-nets in the
framework developed by Andreoli in recent papers. We define specific
correctness criteria for that purpose. We first study closed modules (i.e.
validity of the execution of a logic program), then extend the criterion to
open modules (i.e. validity during the execution) distinguishing criteria for
acyclicity and connectability in order to allow incremental verification.


title: Security of public key cryptosystems based on Chebyshev Polynomials

abstract:
  Chebyshev polynomials have been recently proposed for designing public-key
systems. Indeed, they enjoy some nice chaotic properties, which seem to be
suitable for use in Cryptography. Moreover, they satisfy a semi-group property,
which makes possible implementing a trapdoor mechanism. In this paper we study
a public key cryptosystem based on such polynomials, which provides both
encryption and digital signature. The cryptosystem works on real numbers and is
quite efficient. Unfortunately, from our analysis it comes up that it is not
secure. We describe an attack which permits to recover the corresponding
plaintext from a given ciphertext. The same attack can be applied to produce
forgeries if the cryptosystem is used for signing messages. Then, we point out
that also other primitives, a Diffie-Hellman like key agreement scheme and an
authentication scheme, designed along the same lines of the cryptosystem, are
not secure due to the aforementioned attack. We close the paper by discussing
the issues and the possibilities of constructing public key cryptosystems on
real numbers.


title:
Complexity of the Two-Variable Fragment with (Binary-Coded) Counting
  Quantifiers

abstract:
  We show that the satisfiability and finite satisfiability problems for the
two-variable fragment of first-order logic with counting quantifiers are both
in NEXPTIME, even when counting quantifiers are coded succinctly.


title: Logic Column 10: Specifying Confidentiality

abstract:
  This article illustrates the use of a logical specification language to
capture various forms of confidentiality properties used in the security
literature.


title: On Invariance and Convergence in Time Complexity theory

abstract:
  This article introduces three invariance principles under which P is
different from NP. In the second part a theorem of convergence is proven. This
theorem states that for any language L there exists an infinite sequence of
languages from O(n) that converges to L.


title:
Generating Conditional Probabilities for Bayesian Networks: Easing the
  Knowledge Acquisition Problem

abstract:
  The number of probability distributions required to populate a conditional
probability table (CPT) in a Bayesian network, grows exponentially with the
number of parent-nodes associated with that table. If the table is to be
populated through knowledge elicited from a domain expert then the sheer
magnitude of the task forms a considerable cognitive barrier. In this paper we
devise an algorithm to populate the CPT while easing the extent of knowledge
acquisition. The input to the algorithm consists of a set of weights that
quantify the relative strengths of the influences of the parent-nodes on the
child-node, and a set of probability distributions the number of which grows
only linearly with the number of associated parent-nodes. These are elicited
from the domain expert. The set of probabilities are obtained by taking into
consideration the heuristics that experts use while arriving at probabilistic
estimations. The algorithm is used to populate the CPT by computing appropriate
weighted sums of the elicited distributions. We invoke the methods of
information geometry to demonstrate how these weighted sums capture the
expert's judgemental strategy.


title:
A FP-Tree Based Approach for Mining All Strongly Correlated Pairs
  without Candidate Generation

abstract:
  Given a user-specified minimum correlation threshold and a transaction
database, the problem of mining all-strong correlated pairs is to find all item
pairs with Pearson's correlation coefficients above the threshold . Despite the
use of upper bound based pruning technique in the Taper algorithm [1], when the
number of items and transactions are very large, candidate pair generation and
test is still costly. To avoid the costly test of a large number of candidate
pairs, in this paper, we propose an efficient algorithm, called Tcp, based on
the well-known FP-tree data structure, for mining the complete set of
all-strong correlated item pairs. Our experimental results on both synthetic
and real world datasets show that, Tcp's performance is significantly better
than that of the previously developed Taper algorithm over practical ranges of
correlation threshold specifications.


title: Feedback Capacity of the First-Order Moving Average Gaussian Channel

abstract:
  The feedback capacity of the stationary Gaussian additive noise channel has
been open, except for the case where the noise is white. Here we find the
feedback capacity of the stationary first-order moving average additive
Gaussian noise channel in closed form. Specifically, the channel is given by
$Y_i = X_i + Z_i,$ $i = 1, 2, ...,$ where the input $\{X_i\}$ satisfies a power
constraint and the noise $\{Z_i\}$ is a first-order moving average Gaussian
process defined by $Z_i = \alpha U_{i-1} + U_i,$ $|\alpha| \le 1,$ with white
Gaussian innovations $U_i,$ $i = 0,1,....$
  We show that the feedback capacity of this channel is $-\log x_0,$ where
$x_0$ is the unique positive root of the equation $ \rho x^2 = (1-x^2) (1 -
|\alpha|x)^2,$ and $\rho$ is the ratio of the average input power per
transmission to the variance of the noise innovation $U_i$. The optimal coding
scheme parallels the simple linear signalling scheme by Schalkwijk and Kailath
for the additive white Gaussian noise channel -- the transmitter sends a
real-valued information-bearing signal at the beginning of communication and
subsequently refines the receiver's error by processing the feedback noise
signal through a linear stationary first-order autoregressive filter. The
resulting error probability of the maximum likelihood decoding decays
doubly-exponentially in the duration of the communication. This feedback
capacity of the first-order moving average Gaussian channel is very similar in
form to the best known achievable rate for the first-order
\emph{autoregressive} Gaussian noise channel studied by Butman, Wolfowitz, and
Tiernan, although the optimality of the latter is yet to be established.


title: A Note on Bulk Quantum Turing Machine

abstract:
  Recently, among experiments for realization of quantum computers, NMR quantum
computers have achieved the most impressive succession. There is a model of the
NMR quantum computation,namely Atsumi and Nishino's bulk quantum Turing
Machine. It assumes, however, an unnatural assumption with quantum mechanics.
We, then, define a more natural and quantum mechanically realizable modified
bulk quantum Turing Machine, and show its computational ability by comparing
complexity classes with quantum Turing Machine's counter part.


title: Impact of IT on Higher education Through Continuing Education

abstract:
  Information Technology is emerging to be the technology of 21st century. The
paradigm shift from industrial society to information society had already
become a reality! It is indeed high time to think about integrating IT in all
facets of education -- may it be in secondary level, or be it in reskilling the
employed ones. This paper discusses various issues in incorporating IT in
various levels of education, and the need to think about a task force to
counter the so-called slow down and recession in IT industry. The opportunities
for aspiring IT professionals were also discussed. The importance of reskilling
as a continuing education programme to make the people aware of the changing
trends in IT was also discussed.


title:
Using Wireless Sensor Networks to Narrow the Gap between Low-Level
  Information and Context-Awareness

abstract:
  Wireless sensor networks are finally becoming a reality. In this paper, we
present a scalable architecture for using wireless sensor networks in
combination with wireless Ethernet networks to provide a complete end-to-end
solution to narrow the gap between the low-level information and context
awareness. We developed and implemented a complete proximity detector in order
to give a wearable computer, such as a PDA, location context. Since location is
only one element of contextawareness, we pursued utilizing photo sensors and
temperature sensors in learning as much as possible about the environment. We
used the TinyOS RF Motes as our test bed WSN (Wireless Sensor Network), 802.11
compatible hardware as our wireless Ethernet network, and conventional PCs and
wired 802.3 networks to build the upper levels of the architecture.


title:
Efficient Even Distribution of Power Consumption in Wireless Sensor
  Networks

abstract:
  One of the limitations of wireless sensor nodes is their inherent limited
energy resource. Besides maximizing the lifetime of the sensor node, it is
preferable to distribute the energy dissipated throughout the wireless sensor
network in order to minimize maintenance and maximize overall system
performance. We investigate a new routing algorithm that uses diffusion in
order to achieve relatively even power dissipation throughout a wireless sensor
network by making good local decisions. We leverage from concepts of
peer-to-peer networks in which the system acts completely decentralized and all
nodes in the network are equal peers. Our algorithm utilizes the node load,
power levels, and spatial information in order to make the optimal routing
decision. According to our preliminary experimental results, our proposed
algorithm performs well according to its goals.


title: Content Based Image Retrieval with Mobile Agents and Steganography

abstract:
  In this paper we present an image retrieval system based on Gabor texture
features, steganography, and mobile agents.. By employing the information
hiding technique, the image attributes can be hidden in an image without
degrading the image quality. Thus the image retrieval process becomes simple.
Java based mobile agents manage the query phase of the system. Based on the
simulation results, the proposed system not only shows the efficiency in hiding
the attributes but also provides other advantages such as: (1) fast
transmission of the retrieval image to the receiver, (2) searching made easy.


title: An Empirical Analysis of Internet Protocol Version 6 (IPv6)

abstract:
  Although the current Internet Protocol known as IPv4 has served its purpose
for over 20 years, its days are numbered. With IPv6 reaching a mature enough
level, there is a need to evaluate the performance benefits or drawbacks that
the new IPv6 protocol will have in comparison to the well established IPv4
protocol. Theoretically, the overhead between the two different protocols
should be directly proportional to the difference in the packet's header size,
however according to our findings, the empirical performance difference between
IPv4 and IPv6, especially when the transition mechanisms are taken into
consideration, is much larger than anticipated. We first examine the
performance of each protocol independently. We then examined two transition
mechanisms which perform the encapsulation at various points in the network:
host-to-host and router-to-router (tunneling). Our experiments were conducted
using two dual stack (IPv4/IPv6) routers using end nodes running both Windows
2000 and Solaris 8.0 in order to compare two different IPv6 implementations
side by side. Our tests were written in C++ and utilized metrics such as
latency, throughput, CPU utilization, socket creation time, socket connection
time, web server simulation, and a video client/server application for TCP/UDP
in IPv4/IPv6 under both Windows 2000 and Solaris 8.0. Our empirical evaluation
proved that IPv6 is not yet a mature enough technology and that it is still
years away from having consistent and good enough implementations, as the
performance of IPv6 in many cases proved to be significantly worse than IPv4.


title: e3D: An Energy-Efficient Routing Algorithm for Wireless Sensor Networks

abstract:
  One of the limitations of wireless sensor nodes is their inherent limited
energy resource. Besides maximizing the lifetime of the sensor node, it is
preferable to distribute the energy dissipated throughout the wireless sensor
network in order to minimize maintenance and maximize overall system
performance. Any communication protocol that involves synchronization of peer
nodes incurs some overhead for setting up the communication. We introduce a new
algorithm, e3D (energy-efficient Distributed Dynamic Diffusion routing
algorithm), and compare it to two other algorithms, namely directed, and random
clustering communication. We take into account the setup costs and analyze the
energy-efficiency and the useful lifetime of the system. In order to better
understand the characteristics of each algorithm and how well e3D really
performs, we also compare e3D with its optimum counterpart and an optimum
clustering algorithm. The benefit of introducing these ideal algorithms is to
show the upper bound on performance at the cost of an astronomical prohibitive
synchronization costs. We compare the algorithms in terms of system lifetime,
power dissipation distribution, cost of synchronization, and simplicity of the
algorithm. Our simulation results show that e3D performs comparable to its
optimal counterpart while having significantly less overhead.


title: Routing Algorithms for Wireless Sensor Networks

abstract:
  Our contribution in this paper is e3D, a diffusion based routing protocol
that prolongs the system lifetime, evenly distributes the power dissipation
throughout the network, and incurs minimal overhead for synchronizing
communication. We compare e3D with other algorithms in terms of system
lifetime, power dissipation distribution, cost of synchronization, and
simplicity of the algorithm.


title: Usage Policy-based CPU Sharing in VOs

abstract:
  Resource sharing within Grid collaborations usually implies specific sharing
mechanisms at participating sites. Challenging policy issues can arise within
virtual organizations (VOs) that integrate participants and resources spanning
multiple physical institutions. Resource owners may wish to grant to one or
more VOs the right to use certain resources subject to local policy and service
level agreements, and each VO may then wish to use those resources subject to
VO policy. Thus, we must address the question of what usage policies (UPs)
should be considered for resource sharing in VOs. As a first step in addressing
this question, we develop and evaluate different UP scenarios within a
specialized context that mimics scientific Grids within which the resources to
be shared are computers. We also present a UP architecture and define roles and
functions for scheduling resources in such grid environments while satisfying
resource owner policies.


title:
Balanced Overlay Networks (BON): Decentralized Load Balancing via
  Self-Organized Random Networks

abstract:
  We present a novel framework, called balanced overlay networks (BON), that
provides scalable, decentralized load balancing for distributed computing using
large-scale pools of heterogeneous computers. Fundamentally, BON encodes the
information about each node's available computational resources in the
structure of the links connecting the nodes in the network. This distributed
encoding is self-organized, with each node managing its in-degree and local
connectivity via random-walk sampling. Assignment of incoming jobs to nodes
with the most free resources is also accomplished by sampling the nodes via
short random walks. Extensive simulations show that the resulting highly
dynamic and self-organized graph structure can efficiently balance
computational load throughout large-scale networks. These simulations cover a
wide spectrum of cases, including significant heterogeneity in available
computing resources and high burstiness in incoming load. We provide analytical
results that prove BON's scalability for truly large-scale networks: in
particular we show that under certain ideal conditions, the network structure
converges to Erdos-Renyi (ER) random graphs; our simulation results, however,
show that the algorithm does much better, and the structures seem to approach
the ideal case of d-regular random graphs. We also make a connection between
highly-loaded BONs and the well-known ball-bin randomized load balancing
framework.


title:
Numerical Solutions of 2-D Steady Incompressible Driven Cavity Flow at
  High Reynolds Numbers

abstract:
  Numerical calculations of the 2-D steady incompressible driven cavity flow
are presented. The Navier-Stokes equations in streamfunction and vorticity
formulation are solved numerically using a fine uniform grid mesh of 601x601.
The steady driven cavity solutions are computed for Re<21,000 with a maximum
absolute residuals of the governing equations that were less than 10-10. A new
quaternary vortex at the bottom left corner and a new tertiary vortex at the
top left corner of the cavity are observed in the flow field as the Reynolds
number increases. Detailed results are presented and comparisons are made with
benchmark solutions found in the literature.

categories: cs.NA math.NA physics.comp-ph physics.flu-dyn


title: Discussions on Driven Cavity Flow

abstract:
  The widely studied benchmark problem, 2-D driven cavity flow problem is
discussed in details in terms of physical and mathematical and also numerical
aspects. A very brief literature survey on studies on the driven cavity flow is
given. Based on the several numerical and experimental studies, the fact of the
matter is, above moderate Reynolds numbers physically the flow in a driven
cavity is not two-dimensional. However there exist numerical solutions for 2-D
driven cavity flow at high Reynolds numbers.


title:
Fourth Order Compact Formulation of Navier-Stokes Equations and Driven
  Cavity Flow at High Reynolds Numbers

abstract:
  A new fourth order compact formulation for the steady 2-D incompressible
Navier-Stokes equations is presented. The formulation is in the same form of
the Navier-Stokes equations such that any numerical method that solve the
Navier-Stokes equations can also be applied to this fourth order compact
formulation. In particular in this work the formulation is solved with an
efficient numerical method that requires the solution of tridiagonal systems
using a fine grid mesh of 601x601. Using this formulation, the steady 2-D
incompressible flow in a driven cavity is solved up to Reynolds number of
20,000 with fourth order spatial accuracy. Detailed solutions are presented.


title: Utilizing Reconfigurable Hardware Processors via Grid Services

abstract:
  Computational grids typically consist of nodes utilizing ordinary processors
such as the Intel Pentium. Field Programmable Gate Arrays (FPGAs) are able to
perform certain compute-intensive tasks very well due to their inherent
parallel architecture, often resulting in orders of magnitude speedups. This
paper explores how FPGAs can be transparently exposed for remote use via grid
services, by integrating the Proteus Software Platform with the Globus Toolkit
3.0.


title: Describing and Simulating Internet Routes

abstract:
  This paper introduces relevant statistics for the description of routes in
the internet, seen as a graph at the interface level. Based on the observed
properties, we propose and evaluate methods for generating artificial routes
suitable for simulation purposes. The work in this paper is based upon a study
of over seven million route traces produced by CAIDA's skitter infrastructure.