title:
Where's the "Party" in "Multi-Party"? Analyzing the Structure of
  Small-Group Sociable Talk

abstract:
  Spontaneous multi-party interaction - conversation among groups of three or
more participants - is part of daily life. While automated modeling of such
interactions has received increased attention in ubiquitous computing research,
there is little applied research on the organization of this highly dynamic and
spontaneous sociable interaction within small groups. We report here on an
applied conversation analytic study of small-group sociable talk, emphasizing
structural and temporal aspects that can inform computational models. In
particular, we examine the mechanics of multiple simultaneous conversational
floors - how participants initiate a new floor amidst an on-going floor, and
how they subsequently show their affiliation with one floor over another. We
also discuss the implications of these findings for the design of "smart"
multi-party applications.


title: The computational power of population protocols

abstract:
  We consider the model of population protocols introduced by Angluin et al.,
in which anonymous finite-state agents stably compute a predicate of the
multiset of their inputs via two-way interactions in the all-pairs family of
communication networks. We prove that all predicates stably computable in this
model (and certain generalizations of it) are semilinear, answering a central
open question about the power of the model. Removing the assumption of two-way
interaction, we also consider several variants of the model in which agents
communicate by anonymous message-passing where the recipient of each message is
chosen by an adversary and the sender is not identified to the recipient. These
one-way models are distinguished by whether messages are delivered immediately
or after a delay, whether a sender can record that it has sent a message, and
whether a recipient can queue incoming messages, refusing to accept new
messages until it has had a chance to send out messages of its own. We
characterize the classes of predicates stably computable in each of these
one-way models using natural subclasses of the semilinear predicates.


title:
A Quadratic Time-Space Tradeoff for Unrestricted Deterministic Decision
  Branching Programs

abstract:
  For a decision problem from coding theory, we prove a quadratic expected
time-space tradeoff of the form $\eT\eS=\Omega(\tfrac{n^2}{q})$ for $q$-way
deterministic decision branching programs, where $q\geq 2$. Here $\eT$ is the
expected computation time and $\eS$ is the expected space, when all inputs are
equally likely. This bound is to our knowledge, the first such to show an
exponential size requirement whenever $\eT = O(n^2)$. Previous exponential size
tradeoffs for Boolean decision branching programs were valid for
time-restricted models with $T=o(n\log_2{n})$. Proving quadratic time-space
tradeoffs for unrestricted time decision branching programs has been a major
goal of recent research -- this goal has already been achieved for
multiple-output branching programs two decades ago. We also show the first
quadratic time-space tradeoffs for Boolean decision branching programs
verifying circular convolution, matrix-vector multiplication and discrete
Fourier transform. Furthermore, we demonstrate a constructive Boolean decision
function which has a quadratic expected time-space tradeoff in the Boolean
deterministic decision branching program model. When $q$ is a constant the
tradeoff results derived here for decision functions verifying various
functions are order-comparable to previously known tradeoff bounds for
calculating the corresponding multiple-output functions.


title: Analog Codes on Graphs

abstract:
  We consider the problem of transmission of a sequence of real data produced
by a Nyquist sampled band-limited analog source over a band-limited analog
channel, which introduces an additive white Gaussian noise. An analog coding
scheme is described, which can achieve a mean-squared error distortion
proportional to $(1+SNR)^{-B}$ for a bandwidth expansion factor of $B/R$, where
$0 < R < 1$ is the rate of individual component binary codes used in the
construction and $B \geq 1$ is an integer. Thus, over a wide range of SNR
values, the proposed code performs much better than any single previously known
analog coding system.


title: On an Improvement over R\'enyi's Equivocation Bound

abstract:
  We consider the problem of estimating the probability of error in
multi-hypothesis testing when MAP criterion is used. This probability, which is
also known as the Bayes risk is an important measure in many communication and
information theory problems. In general, the exact Bayes risk can be difficult
to obtain. Many upper and lower bounds are known in literature. One such upper
bound is the equivocation bound due to R\'enyi which is of great philosophical
interest because it connects the Bayes risk to conditional entropy. Here we
give a simple derivation for an improved equivocation bound.
  We then give some typical examples of problems where these bounds can be of
use. We first consider a binary hypothesis testing problem for which the exact
Bayes risk is difficult to derive. In such problems bounds are of interest.
Furthermore using the bounds on Bayes risk derived in the paper and a random
coding argument, we prove a lower bound on equivocation valid for most random
codes over memoryless channels.


title: Radial Structure of the Internet

abstract:
  The structure of the Internet at the Autonomous System (AS) level has been
studied by both the Physics and Computer Science communities. We extend this
work to include features of the core and the periphery, taking a radial
perspective on AS network structure. New methods for plotting AS data are
described, and they are used to analyze data sets that have been extended to
contain edges missing from earlier collections. In particular, the average
distance from one vertex to the rest of the network is used as the baseline
metric for investigating radial structure. Common vertex-specific quantities
are plotted against this metric to reveal distinctive characteristics of
central and peripheral vertices. Two data sets are analyzed using these
measures as well as two common generative models (Barabasi-Albert and Inet). We
find a clear distinction between the highly connected core and a sparse
periphery. We also find that the periphery has a more complex structure than
that predicted by degree distribution or the two generative models.


title:
Wireless ad-hoc networks: Strategies and Scaling laws for the fixed SNR
  regime

abstract:
  This paper deals with throughput scaling laws for random ad-hoc wireless
networks in a rich scattering environment. We develop schemes to optimize the
ratio, $\rho(n)$ of achievable network sum capacity to the sum of the
point-to-point capacities of source-destinations pairs operating in isolation.
For fixed SNR networks, i.e., where the worst case SNR over the
source-destination pairs is fixed independent of $n$, we show that
collaborative strategies yield a scaling law of $\rho(n) = {\cal
O}(\frac{1}{n^{1/3}})$ in contrast to multi-hop strategies which yield a
scaling law of $\rho(n) = {\cal O}(\frac{1}{\sqrt{n}})$. While, networks where
worst case SNR goes to zero, do not preclude the possibility of collaboration,
multi-hop strategies achieve optimal throughput. The plausible reason is that
the gains due to collaboration cannot offset the effect of vanishing receive
SNR. This suggests that for fixed SNR networks, a network designer should look
for network protocols that exploit collaboration. The fact that most current
networks operate in a fixed SNR interference limited environment provides
further motivation for considering this regime.


title: A Condition Number Analysis of a Line-Surface Intersection Algorithm

abstract:
  We propose an algorithm based on Newton's method and subdivision for finding
all zeros of a polynomial system in a bounded region of the plane. This
algorithm can be used to find the intersections between a line and a surface,
which has applications in graphics and computer-aided geometric design. The
algorithm can operate on polynomials represented in any basis that satisfies a
few conditions. The power basis, the Bernstein basis, and the first-kind
Chebyshev basis are among those compatible with the algorithm. The main novelty
of our algorithm is an analysis showing that its running is bounded only in
terms of the condition number of the polynomial's zeros and a constant
depending on the polynomial basis.


title: On-line topological simplification of weighted graphs

abstract:
  We describe two efficient on-line algorithms to simplify weighted graphs by
eliminating degree-two vertices. Our algorithms are on-line in that they react
to updates on the data, keeping the simplification up-to-date. The supported
updates are insertions of vertices and edges; hence, our algorithms are
partially dynamic. We provide both analytical and empirical evaluations of the
efficiency of our approaches. Specifically, we prove an O(log n) upper bound on
the amortized time complexity of our maintenance algorithms, with n the number
of insertions.


title: Self-Stabilizing Byzantine Pulse Synchronization

abstract:
  The ``Pulse Synchronization'' problem can be loosely described as targeting
to invoke a recurring distributed event as simultaneously as possible at the
different nodes and with a frequency that is as regular as possible. This
target becomes surprisingly subtle and difficult to achieve when facing both
transient and permanent failures. In this paper we present an algorithm for
pulse synchronization that self-stabilizes while at the same time tolerating a
permanent presence of Byzantine faults. The Byzantine nodes might incessantly
try to de-synchronize the correct nodes. Transient failures might throw the
system into an arbitrary state in which correct nodes have no common notion
what-so-ever, such as time or round numbers, and can thus not infer anything
from their own local states upon the state of other correct nodes. The
presented algorithm grants nodes the ability to infer that eventually all
correct nodes will invoke their pulses within a very short time interval of
each other and will do so regularly.
  Pulse synchronization has previously been shown to be a powerful tool for
designing general self-stabilizing Byzantine algorithms and is hitherto the
only method that provides for the general design of efficient practical
protocols in the confluence of these two fault models. The difficulty, in
general, to design any algorithm in this fault model may be indicated by the
remarkably few algorithms resilient to both fault models. The few published
self-stabilizing Byzantine algorithms are typically complicated and sometimes
converge from an arbitrary initial state only after exponential or super
exponential time.


title:
Connection between continuous and digital n-manifolds and the Poincare
  conjecture

abstract:
  We introduce LCL covers of closed n-dimensional manifolds by n-dimensional
disks and study their properties. We show that any LCL cover of an
n-dimensional sphere can be converted to the minimal LCL cover, which consists
of 2n+2 disks. We prove that an LCL collection of n-disks is a cover of a
continuous n-sphere if and only if the intersection graph of this collection is
a digital n-sphere. Using a link between LCL covers of closed continuous
n-manifolds and digital n-manifolds, we find conditions where a continuous
closed three-dimensional manifold is the three-dimensional sphere. We discuss a
connection between the classification problems for closed continuous
three-dimensional manifolds and digital three-manifolds.


title: On Universality in Real Computation

abstract:
  Models of computation operating over the real numbers and computing a larger
class of functions compared to the class of general recursive functions
invariably introduce a non-finite element of infinite information encoded in an
arbitrary non-computable number or non-recursive function. In this paper we
show that Turing universality is only possible at every Turing degree but not
over all, in that sense universality at the first level is elegantly well
defined while universality at higher degrees is at least ambiguous. We propose
a concept of universal relativity and universal jump between levels in the
arithmetical and analytical hierarchy.


title: Stationary Algorithmic Probability

abstract:
  Kolmogorov complexity and algorithmic probability are defined only up to an
additive resp. multiplicative constant, since their actual values depend on the
choice of the universal reference computer. In this paper, we analyze a natural
approach to eliminate this machine-dependence.
  Our method is to assign algorithmic probabilities to the different computers
themselves, based on the idea that "unnatural" computers should be hard to
emulate. Therefore, we study the Markov process of universal computers randomly
emulating each other. The corresponding stationary distribution, if it existed,
would give a natural and machine-independent probability measure on the
computers, and also on the binary strings.
  Unfortunately, we show that no stationary distribution exists on the set of
all computers; thus, this method cannot eliminate machine-dependence. Moreover,
we show that the reason for failure has a clear and interesting physical
interpretation, suggesting that every other conceivable attempt to get rid of
those additive constants must fail in principle, too.
  However, we show that restricting to some subclass of computers might help to
get rid of some amount of machine-dependence in some situations, and the
resulting stationary computer and string probabilities have beautiful
properties.


title: Linear-time Self-stabilizing Byzantine Clock Synchronization

abstract:
  Clock synchronization is a very fundamental task in distributed system. It
thus makes sense to require an underlying clock synchronization mechanism to be
highly fault-tolerant. A self-stabilizing algorithm seeks to attain
synchronization once lost; a Byzantine algorithm assumes synchronization is
never lost and focuses on containing the influence of the permanent presence of
faulty nodes. There are efficient self-stabilizing solutions for clock
synchronization as well as efficient solutions that are resilient to Byzantine
faults. In contrast, to the best of our knowledge there is no practical
solution that is self-stabilizing while tolerating the permanent presence of
Byzantine nodes. We present the first linear-time self-stabilizing Byzantine
clock synchronization algorithm. Our deterministic clock synchronization
algorithm is based on the observation that all clock synchronization algorithms
require events for exchanging clock values and re-synchronizing the clocks to
within safe bounds. These events usually need to happen synchronously at the
different nodes. In classic Byzantine algorithms this is fulfilled or aided by
having the clocks initially close to each other and thus the actual clock
values can be used for synchronizing the events. This implies that clock values
cannot differ arbitrarily, which necessarily renders these solutions to be
non-stabilizing. Our scheme suggests using an underlying distributed pulse
synchronization module that is uncorrelated to the clock values.


title: A study of fuzzy and many-valued logics in cellular automata

abstract:
  In this paper we provide an analytical study of the theory of multi-valued
and fuzzy cellular automata where the fuzziness appears as the result of the
application of an underlying multi-valued or continuous logic as opposed to
standard logic as used conventionally. Using the disjunctive normal form of any
one of the 255 ECA's so defined, we modify the underlying logic structure and
redefine the ECA within the framework of this new logic. The idea here is to
show that the evolution of space-time diagrams of ECA's under even a
probabilistic logic can exhibit non-chaotic behavior. This is looked at
specifically for Probabilistic Rule 110, in contrast with Boolean Rule 110
which is known to be capable of universal computation.


title: Improved Content Based Image Watermarking

abstract:
  This paper presents a robust and transparent scheme of watermarking that
exploits the human visual systems' sensitivity to frequency, along with local
image characteristics obtained from the spatial domain. The underlying idea is
generating a visual mask based on the visual systems' perception of image
content. This mask is used to embed a decimal sequence while keeping its
amplitude below the distortion sensitivity of the image pixel. We consider
texture, luminance, corner and the edge information in the image to generate a
mask that makes the addition of the watermark imperceptible to the human eye.


title: Automated verification of weak equivalence within the SMODELS system

abstract:
  In answer set programming (ASP), a problem at hand is solved by (i) writing a
logic program whose answer sets correspond to the solutions of the problem, and
by (ii) computing the answer sets of the program using an answer set solver as
a search engine. Typically, a programmer creates a series of gradually
improving logic programs for a particular problem when optimizing program
length and execution time on a particular solver. This leads the programmer to
a meta-level problem of ensuring that the programs are equivalent, i.e., they
give rise to the same answer sets. To ease answer set programming at
methodological level, we propose a translation-based method for verifying the
equivalence of logic programs. The basic idea is to translate logic programs P
and Q under consideration into a single logic program EQT(P,Q) whose answer
sets (if such exist) yield counter-examples to the equivalence of P and Q. The
method is developed here in a slightly more general setting by taking the
visibility of atoms properly into account when comparing answer sets. The
translation-based approach presented in the paper has been implemented as a
translator called lpeq that enables the verification of weak equivalence within
the smodels system using the same search engine as for the search of models.
Our experiments with lpeq and smodels suggest that establishing the equivalence
of logic programs in this way is in certain cases much faster than naive
cross-checking of answer sets.


title: Similarity of Semantic Relations

abstract:
  There are at least two kinds of similarity. Relational similarity is
correspondence between relations, in contrast with attributional similarity,
which is correspondence between attributes. When two words have a high degree
of attributional similarity, we call them synonyms. When two pairs of words
have a high degree of relational similarity, we say that their relations are
analogous. For example, the word pair mason:stone is analogous to the pair
carpenter:wood. This paper introduces Latent Relational Analysis (LRA), a
method for measuring relational similarity. LRA has potential applications in
many areas, including information extraction, word sense disambiguation, and
information retrieval. Recently the Vector Space Model (VSM) of information
retrieval has been adapted to measuring relational similarity, achieving a
score of 47% on a collection of 374 college-level multiple-choice word analogy
questions. In the VSM approach, the relation between a pair of words is
characterized by a vector of frequencies of predefined patterns in a large
corpus. LRA extends the VSM approach in three ways: (1) the patterns are
derived automatically from the corpus, (2) the Singular Value Decomposition
(SVD) is used to smooth the frequency data, and (3) automatically generated
synonyms are used to explore variations of the word pairs. LRA achieves 56% on
the 374 analogy questions, statistically equivalent to the average human score
of 57%. On the related problem of classifying semantic relations, LRA achieves
similar gains over the VSM.


title: Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs

abstract:
  For digraphs $D$ and $H$, a mapping $f: V(D)\dom V(H)$ is a homomorphism of
$D$ to $H$ if $uv\in A(D)$ implies $f(u)f(v)\in A(H).$ If, moreover, each
vertex $u \in V(D)$ is associated with costs $c_i(u), i \in V(H)$, then the
cost of the homomorphism $f$ is $\sum_{u\in V(D)}c_{f(u)}(u)$. For each fixed
digraph $H$, we have the {\em minimum cost homomorphism problem for} $H$. The
problem is to decide, for an input graph $D$ with costs $c_i(u),$ $u \in V(D),
i\in V(H)$, whether there exists a homomorphism of $D$ to $H$ and, if one
exists, to find one of minimum cost. Minimum cost homomorphism problems
encompass (or are related to) many well studied optimization problems. We
describe a dichotomy of the minimum cost homomorphism problem for semicomplete
multipartite digraphs $H$. This solves an open problem from an earlier paper.
To obtain the dichotomy of this paper, we introduce and study a new notion, a
$k$-Min-Max ordering of digraphs.


title: Analysis of a Reputation System for Mobile Ad-Hoc Networks with Liars

abstract:
  The application of decentralized reputation systems is a promising approach
to ensure cooperation and fairness, as well as to address random failures and
malicious attacks in Mobile Ad-Hoc Networks. However, they are potentially
vulnerable to liars. With our work, we provide a first step to analyzing
robustness of a reputation system based on a deviation test. Using a mean-field
approach to our stochastic process model, we show that liars have no impact
unless their number exceeds a certain threshold (phase transition). We give
precise formulae for the critical values and thus provide guidelines for an
optimal choice of parameters.


title: Logic programs with monotone abstract constraint atoms

abstract:
  We introduce and study logic programs whose clauses are built out of monotone
constraint atoms. We show that the operational concept of the one-step
provability operator generalizes to programs with monotone constraint atoms,
but the generalization involves nondeterminism. Our main results demonstrate
that our formalism is a common generalization of (1) normal logic programming
with its semantics of models, supported models and stable models, (2) logic
programming with weight atoms (lparse programs) with the semantics of stable
models, as defined by Niemela, Simons and Soininen, and (3) of disjunctive
logic programming with the possible-model semantics of Sakama and Inoue.


title: Heap Reference Analysis Using Access Graphs

abstract:
  Despite significant progress in the theory and practice of program analysis,
analysing properties of heap data has not reached the same level of maturity as
the analysis of static and stack data. The spatial and temporal structure of
stack and static data is well understood while that of heap data seems
arbitrary and is unbounded. We devise bounded representations which summarize
properties of the heap data. This summarization is based on the structure of
the program which manipulates the heap. The resulting summary representations
are certain kinds of graphs called access graphs. The boundedness of these
representations and the monotonicity of the operations to manipulate them make
it possible to compute them through data flow analysis.
  An important application which benefits from heap reference analysis is
garbage collection, where currently liveness is conservatively approximated by
reachability from program variables. As a consequence, current garbage
collectors leave a lot of garbage uncollected, a fact which has been confirmed
by several empirical studies. We propose the first ever end-to-end static
analysis to distinguish live objects from reachable objects. We use this
information to make dead objects unreachable by modifying the program. This
application is interesting because it requires discovering data flow
information representing complex semantics. In particular, we discover four
properties of heap data: liveness, aliasing, availability, and anticipability.
Together, they cover all combinations of directions of analysis (i.e. forward
and backward) and confluence of information (i.e. union and intersection). Our
analysis can also be used for plugging memory leaks in C/C++ languages.


title:
Application Layer Definition and Analyses of Controller Area Network Bus
  for Wire Harness Assembly Machine

abstract:
  With the feature of multi-master bus access, nondestructive contention-based
arbitration and flexible configuration, Controller Area Network (CAN) bus is
applied into the control system of Wire Harness Assembly Machine (WHAM). To
accomplish desired goal, the specific features of the CAN bus is analyzed by
compared with other field buses and the functional performances in the CAN bus
system of WHAM is discussed. Then the application layer planning of CAN bus for
dynamic priority is presented. The critical issue for the use of CAN bus system
in WHAM is the data transfer rate between different nodes. So processing
efficient model is introduced to assist analyzing data transfer procedure.
Through the model, it is convenient to verify the real time feature of the CAN
bus system in WHAM.


title: Lp Computable Functions and Fourier Series

abstract:
  This paper studies how well computable functions can be approximated by their
Fourier series. To this end, we equip the space of Lp-computable functions
(computable Lebesgue integrable functions) with a size notion, by introducing
Lp-computable Baire categories.
  We show that Lp-computable Baire categories satisfy the following three basic
properties. Singleton sets {f} (where f is Lp-computable) are meager, suitable
infinite unions of meager sets are meager, and the whole space of Lp-computable
functions is not meager. We give an alternative characterization of meager sets
via Banach Mazur games.
  We study the convergence of Fourier series for Lp-computable functions and
show that whereas for every p>1, the Fourier series of every Lp-computable
function f converges to f in the Lp norm, the set of L1-computable functions
whose Fourier series does not diverge almost everywhere is meager.


title: The Haar Wavelet Transform of a Dendrogram

abstract:
  We describe a new wavelet transform, for use on hierarchies or binary rooted
trees. The theoretical framework of this approach to data analysis is
described. Case studies are used to further exemplify this approach. A first
set of application studies deals with data array smoothing, or filtering. A
second set of application studies relates to hierarchical tree condensation.
Finally, a third study explores the wavelet decomposition, and the
reproducibility of data sets such as text, including a new perspective on the
generation or computability of such data objects.


title: Spherical Indexing for Neighborhood Queries

abstract:
  This is an algorithm for finding neighbors when the objects can freely move
and have no predefined position. The query consists in finding neighbors for a
center location and a given radius. Space is discretized in cubic cells. This
algorithm introduces a direct spherical indexing that gives the list of all
cells making up the query sphere, for any radius and any center location. It
can additionally take in account both cyclic and non-cyclic regions of
interest. Finding only the K nearest neighbors naturally benefits from the
spherical indexing by minimally running through the sphere from center to edge,
and reducing the maximum distance when K neighbors have been found.


title:
Realistic Boundary Conditions for Ad Hoc Network Node Mobility Models
  and a New Approach to the Random Waypoint Model

abstract:
  In this paper, we examine the cause of the border effect observed in many
mobility models used to construct simulations of ad hoc networking protocol
performance. We specify conditions under which a node mobility model must
produce spatial mobile node distribution functions that obey the diffusion
equation. In particular demonstrate that these conditions are satisfied by the
random direction (RD) model. We show that it is possible to construct mobility
models that attain uniform steady-state distributions without resorting to
reflection or ``wrapping'' of nodes at the border of a test region. Finally, we
show that the random waypoint (RWP) model may be reproduced by the application
of a ``volume rule'' to an RD model. This volume rule violates the assumptions
that lead to the diffusion equation. We suggest a generalization of the RWP
model that can provide more uniform mobile node distributions.


title: Calculating modules in contextual logic program refinement

abstract:
  The refinement calculus for logic programs is a framework for deriving logic
programs from specifications. It is based on a wide-spectrum language that can
express both specifications and code, and a refinement relation that models the
notion of correct implementation. In this paper we extend and generalise
earlier work on contextual refinement. Contextual refinement simplifies the
refinement process by abstractly capturing the context of a subcomponent of a
program, which typically includes information about the values of the free
variables. This paper also extends and generalises module refinement. A module
is a collection of procedures that operate on a common data type; module
refinement between a specification module A and an implementation module C
allows calls to the procedures of A to be systematically replaced with calls to
the corresponding procedures of C. Based on the conditions for module
refinement, we present a method for calculating an implementation module from a
specification module. Both contextual and module refinement within the
refinement calculus have been generalised from earlier work and the results are
presented in a unified framework.


title: An Architectural Style for Ajax

abstract:
  A new breed of web application, dubbed AJAX, is emerging in response to a
limited degree of interactivity in large-grain stateless Web interactions. At
the heart of this new approach lies a single page interaction model that
facilitates rich interactivity. We have studied and experimented with several
AJAX frameworks trying to understand their architectural properties. In this
paper, we summarize three of these frameworks and examine their properties and
introduce the SPIAR architectural style. We describe the guiding software
engineering principles and the constraints chosen to induce the desired
properties. The style emphasizes user interface component development, and
intermediary delta-communication between client/server components, to improve
user interactivity and ease of development. In addition, we use the concepts
and principles to discuss various open issues in AJAX frameworks and
application development.


title: Entity Based Peer-to-Peer in a Data Grid Environment

abstract:
  During the last decade there has been a huge interest in Grid technologies,
and numerous Grid projects have been initiated with various visions of the
Grid. While all these visions have the same goal of resource sharing, they
differ in the functionality that a Grid supports, the grid characterisation,
programming environments, etc. In this paper we present a new Grid system
dedicated to deal with data issues, called DGET (Data Grid Environment and
Tools). DGET is characterized by its peer-to-peer communication system and
entity-based architecture, therefore, taking advantage of the main
functionality of both systems; P2P and Grid. DGET is currently under
development and a prototype implementing the main components is in its first
phase of testing. In this paper we limit our description to the system
architectural features and to the main differences with other systems.


title: A Java Based Architecture of P2P-Grid Middleware

abstract:
  During the last decade there has been a huge interest in Grid technologies,
and numerous Grid projects have been initiated with various visions of the
Grid. While all these visions have the same goal of resource sharing, they
differ in the functionality that a Grid supports, characterization, programming
environments, etc. We present a new Grid system dedicated to dealing with data
issues, called DGET (Data Grid Environment and Tools). DGET is characterized by
its peerto- peer communication system and entity-based architecture, therefore,
taking advantage of the main functionality of both systems; P2P and Grid. DGET
is currently under development and a prototype implementing the main components
is in its first phase of testing. In this paper we limit our description to the
system architectural features and to the main differences with other systems.
Keywords: Grid Computing, Peer to Peer, Peer to Peer Grid


title: Reliable multicast fault tolerant MPI in the Grid environment

abstract:
  Grid environments have recently been developed with low stretch and overheads
that increase with the logarithm of the number of nodes in the system. Getting
and sending data to/from a large numbers of nodes is gaining importance due to
an increasing number of independent data providers and the heterogeneity of the
network/Grid. One of the key challenges is to achieve a balance between low
bandwidth consumption and good reliability. In this paper we present an
implementation of a reliable multicast protocol over a fault tolerant MPI:
MPICHV2. It can provide one way to solve the problem of transferring large
chunks of data between applications running on a grid with limited network
links. We first show that we can achieve similar performance as the MPICH-P4
implementation by using multicast with data compression in a cluster. Next, we
provide a theoretical cluster organization and GRID network architecture to
harness the performance provided by using multicast. Finally, we present the
conclusion and future work.


title: Neural Network Clustering Based on Distances Between Objects

abstract:
  We present an algorithm of clustering of many-dimensional objects, where only
the distances between objects are used. Centers of classes are found with the
aid of neuron-like procedure with lateral inhibition. The result of clustering
does not depend on starting conditions. Our algorithm makes it possible to give
an idea about classes that really exist in the empirical data. The results of
computer simulations are presented.


title:
Transparent Migration of Multi-Threaded Applications on a Java Based
  Grid

abstract:
  Grid computing has enabled pooling a very large number of heterogeneous
resource administered by different security domains. Applications are
dynamically deployed on the resources available at the time. Dynamic nature of
the resources and applications requirements makes needs the grid middleware to
support the ability of migrating a running application to a different resource.
Especially, Grid applications are typically long running and thus stoping them
and starting them from scratch is not a feasible option. This paper presents an
overview of migration support in a java based grid middleware called DGET.
Migration support in DGET includes multi-threaded migration and asynchronous
migration as well.


title:
Code Annealing and the Suppressing Effect of the Cyclically Lifted LDPC
  Code Ensemble

abstract:
  Code annealing, a new method of designing good codes of short block length,
is proposed, which is then concatenated with cyclic lifting to create finite
codes of low frame error rate (FER) error floors without performance outliers.
The stopping set analysis is performed on the cyclically lifted code ensemble
assuming uniformly random lifting sequences, and the suppressing effect/weight
of the cyclic lifting is identified for the first time, based on which the
ensemble FER error floor can be analytically determined and a scaling law is
derived. Both the first-order and high-order suppressing effects are discussed
and quantified by different methods including the explicit expression, an
algorithmic upper bound, and an algebraic lower bound.
  The mismatch between the suppressing weight and the stopping distances
explains the dramatic performance discrepancy among different cyclically lifted
codes when the underlying base codes have degree 2 variable nodes or not. For
the former case, a degree augmentation method is further introduced to mitigate
this metric mismatch, and a systematic method of constructing irregular codes
of low FER error floors is presented. Both regular and irregular codes of very
low FER error floors are reported, for which the improvement factor ranges from
10^6-10^4 when compared to the classic graph-based code ensembles.


title: TreeP: A Tree-Based P2P Network Architecture

abstract:
  In this paper we proposed a hierarchical P2P network based on a dynamic
partitioning on a 1-D space. This hierarchy is created and maintained
dynamically and provides a gridmiddleware (like DGET) a P2P basic functionality
for resource discovery and load-balancing.This network architecture is called
TreeP (Tree based P2P network architecture) and is based on atessellation of a
1-D space. We show that this topology exploits in an efficient way
theheterogeneity feature of the network while limiting the overhead introduced
by the overlaymaintenance. Experimental results show that this topology is
highly resilient to a large number ofnetwork failures.


title: Security Analysis of A Chaos-based Image Encryption Algorithm

abstract:
  The security of Fridrich Image Encryption Algorithm against brute-force
attack, statistical attack, known-plaintext attack and select-plaintext attack
is analyzed by investigating the properties of the involved chaotic maps and
diffusion functions. Based on the given analyses, some means are proposed to
strengthen the overall performance of the focused cryptosystem.


title: Controller synthesis & Ordinal Automata

abstract:
  Ordinal automata are used to model physical systems with Zeno behavior. Using
automata and games techniques we solve a control problem formulated and left
open by Demri and Nowak in 2005. It involves partial observability and a new
synchronization between the controller and the environment.


title: Cross Entropy Approximation of Structured Covariance Matrices

abstract:
  We apply two variations of the principle of Minimum Cross Entropy (the
Kullback information measure) to fit parameterized probability density models
to observed data densities. For an array beamforming problem with P incident
narrowband point sources, N > P sensors, and colored noise, both approaches
yield eigenvector fitting methods similar to that of the MUSIC algorithm[1].
Furthermore, the corresponding cross-entropies are related to the MDL model
order selection criterion[2].


title: FOSS-Based Grid Computing

abstract:
  In this expository paper we will be primarily concerned with core aspects of
Grids and Grid computing using free and open-source software with some emphasis
on utility computing. It is based on a technical report entitled
'Grid-Computing Using GNU/Linux' by the present author. This article was
written in 2006 and should be of historical interest.


title: Proof of a Conjecture of Helleseth Regarding Pairs of Binary m-Sequences

abstract:
  This paper has been withdrawn by the author(s), due a crucial sign error in
Thm. 11.


title: The Tree Inclusion Problem: In Linear Space and Faster

abstract:
  Given two rooted, ordered, and labeled trees $P$ and $T$ the tree inclusion
problem is to determine if $P$ can be obtained from $T$ by deleting nodes in
$T$. This problem has recently been recognized as an important query primitive
in XML databases. Kilpel\"ainen and Mannila [\emph{SIAM J. Comput. 1995}]
presented the first polynomial time algorithm using quadratic time and space.
Since then several improved results have been obtained for special cases when
$P$ and $T$ have a small number of leaves or small depth. However, in the worst
case these algorithms still use quadratic time and space. Let $n_S$, $l_S$, and
$d_S$ denote the number of nodes, the number of leaves, and the %maximum depth
of a tree $S \in \{P, T\}$. In this paper we show that the tree inclusion
problem can be solved in space $O(n_T)$ and time: O(\min(l_Pn_T, l_Pl_T\log
\log n_T + n_T, \frac{n_Pn_T}{\log n_T} + n_{T}\log n_{T})). This improves or
matches the best known time complexities while using only linear space instead
of quadratic. This is particularly important in practical applications, such as
XML databases, where the space is likely to be a bottleneck.


title:
Decidability of Type-checking in the Calculus of Algebraic Constructions
  with Size Annotations

abstract:
  Since Val Tannen's pioneer work on the combination of simply-typed
lambda-calculus and first-order rewriting (LICS'88), many authors have
contributed to this subject by extending it to richer typed lambda-calculi and
rewriting paradigms, culminating in calculi like the Calculus of Algebraic
Constructions. These works provide theoretical foundations for type-theoretic
proof assistants where functions and predicates are defined by oriented
higher-order equations. This kind of definitions subsumes induction-based
definitions, is easier to write and provides more automation. On the other
hand, checking that user-defined rewrite rules are strongly normalizing and
confluent, and preserve the decidability of type-checking when combined with
beta-reduction, is more difficult. Most termination criteria rely on the term
structure. In a previous work, we extended to dependent types and higher-order
rewriting, the notion of ``sized types'' studied by several authors in the
simpler framework of ML-like languages, and proved that it preserves strong
normalization. The main contribution of the present paper is twofold. First, we
prove that, in the Calculus of Algebraic Constructions with size annotations,
the problems of type inference and type-checking are decidable, provided that
the sets of constraints generated by size annotations are satisfiable and admit
most general solutions. Second, we prove the later properties for a size
algebra rich enough for capturing usual induction-based definitions and much
more.


title:
A Robust Solution Procedure for Hyperelastic Solids with Large Boundary
  Deformation

abstract:
  Compressible Mooney-Rivlin theory has been used to model hyperelastic solids,
such as rubber and porous polymers, and more recently for the modeling of soft
tissues for biomedical tissues, undergoing large elastic deformations. We
propose a solution procedure for Lagrangian finite element discretization of a
static nonlinear compressible Mooney-Rivlin hyperelastic solid. We consider the
case in which the boundary condition is a large prescribed deformation, so that
mesh tangling becomes an obstacle for straightforward algorithms. Our solution
procedure involves a largely geometric procedure to untangle the mesh: solution
of a sequence of linear systems to obtain initial guesses for interior nodal
positions for which no element is inverted. After the mesh is untangled, we
take Newton iterations to converge to a mechanical equilibrium. The Newton
iterations are safeguarded by a line search similar to one used in
optimization. Our computational results indicate that the algorithm is up to 70
times faster than a straightforward Newton continuation procedure and is also
more robust (i.e., able to tolerate much larger deformations). For a few
extremely large deformations, the deformed mesh could only be computed through
the use of an expensive Newton continuation method while using a tight
convergence tolerance and taking very small steps.


title: On the confluence of lambda-calculus with conditional rewriting

abstract:
  The confluence of untyped lambda-calculus with unconditional rewriting has
already been studied in various directions. In this paper, we investigate the
confluence of lambda-calculus with conditional rewriting and provide general
results in two directions. First, when conditional rules are algebraic. This
extends results of Muller and Dougherty for unconditional rewriting. Two cases
are considered, whether beta-reduction is allowed or not in the evaluation of
conditions. Moreover, Dougherty's result is improved from the assumption of
strongly normalizing beta-reduction to weakly normalizing beta-reduction. We
also provide examples showing that outside these conditions, modularity of
confluence is difficult to achieve. Second, we go beyond the algebraic
framework and get new confluence results using an extended notion of
orthogonality that takes advantage of the conditional part of rewrite rules.


title:
In Quest of Image Semantics: Are We Looking for It Under the Right
  Lamppost?

abstract:
  In the last years we witness a dramatic growth of research focused on
semantic image understanding. Indeed, without understanding image content
successful accomplishment of any image-processing task is simply incredible. Up
to the recent times, the ultimate need for such understanding has been met by
the knowledge that a domain expert or a vision system supervisor have
contributed to every image-processing application. The advent of the Internet
has drastically changed this situation. Internet sources of visual information
are diffused and dispersed over the whole Web, so the duty of information
content discovery and evaluation must be relegated now to an image
understanding agent (a machine or a computer program) capable to perform image
content assessment at a remote image location. Development of Content Based
Image Retrieval (CBIR) techniques was a right move in a right direction,
launched about ten years ago. Unfortunately, very little progress has been made
since then. The reason for this can be seen in a rank of long lasting
misconceptions that CBIR designers are continuing to adhere to. I hope, my
arguments will help them to change their minds.


title:
Equality of complexity classes P and NP: Linear programming formulation
  of the quadratic assignment problem

abstract:
  In this paper, we present a polynomial-sized linear programming formulation
of the Quadratic Assignment Problem (QAP). The proposed linear program is a
network flow-based model. Hence, it provides for the solution of the QAP in
polynomial time. Computational testing and results are discussed.


title: The traveling salesman problem: A Linear programming formulation

abstract:
  In this paper, we present a polynomial-sized linear programming formulation
of the Traveling Salesman Problem (TSP). The proposed linear program is a
network flow-based model. Numerical implementation issues and results are
discussed. (The exposition and proofs are much more detailed in an edition
which I wrote in collaboration with Dr. M.H. Karwan in 2012-2014 . That edition
is available at
http://users.business.uconn.edu/mdiaby/P=NPProofPapers/tspPaper.pdf)


title: New Quasi-Cyclic Codes from Simplex Codes

abstract:
  As a generalization of cyclic codes, quasi-cyclic (QC) codes contain many
good linear codes. But quasi-cyclic codes studied so far are mainly limited to
one generator (1-generator) QC codes. In this correspondence, 2-generator and
3-generator QC codes are studied, and many good, new QC codes are constructed
from simplex codes. Some new binary QC codes or related codes, that improve the
bounds on maximum minimum distance for binary linear codes are constructed.
They are 5-generator QC [93, 17, 34] and [254, 23, 102] codes, and related [96,
17, 36], [256, 23, 104] codes.


title: A Massive Local Rules Search Approach to the Classification Problem

abstract:
  An approach to the classification problem of machine learning, based on
building local classification rules, is developed. The local rules are
considered as projections of the global classification rules to the event we
want to classify. A massive global optimization algorithm is used for
optimization of quality criterion. The algorithm, which has polynomial
complexity in typical case, is used to find all high--quality local rules. The
other distinctive feature of the algorithm is the integration of attributes
levels selection (for ordered attributes) with rules searching and original
conflicting rules resolution strategy. The algorithm is practical; it was
tested on a number of data sets from UCI repository, and a comparison with the
other predicting techniques is presented.


title: On the freeze quantifier in Constraint LTL: decidability and complexity

abstract:
  Constraint LTL, a generalisation of LTL over Presburger constraints, is often
used as a formal language to specify the behavior of operational models with
constraints. The freeze quantifier can be part of the language, as in some
real-time logics, but this variable-binding mechanism is quite general and
ubiquitous in many logical languages (first-order temporal logics, hybrid
logics, logics for sequence diagrams, navigation logics, logics with
lambda-abstraction etc.). We show that Constraint LTL over the simple domain
(N,=) augmented with the freeze quantifier is undecidable which is a surprising
result in view of the poor language for constraints (only equality tests). Many
versions of freeze-free Constraint LTL are decidable over domains with
qualitative predicates and our undecidability result actually establishes
Sigma_1^1-completeness. On the positive side, we provide complexity results
when the domain is finite (EXPSPACE-completeness) or when the formulae are flat
in a sense introduced in the paper. Our undecidability results are sharp (i.e.
with restrictions on the number of variables) and all our complexity
characterisations ensure completeness with respect to some complexity class
(mainly PSPACE and EXPSPACE).


title: Finding heaviest H-subgraphs in real weighted graphs, with applications

abstract:
  For a graph G with real weights assigned to the vertices (edges), the MAX
H-SUBGRAPH problem is to find an H-subgraph of G with maximum total weight, if
one exists. The all-pairs MAX H-SUBGRAPH problem is to find for every pair of
vertices u,v, a maximum H-subgraph containing both u and v, if one exists. Our
main results are new strongly polynomial algorithms for the all-pairs MAX
H-SUBGRAPH problem for vertex weighted graphs. We also give improved algorithms
for the MAX-H SUBGRAPH problem for edge weighted graphs, and various related
problems, including computing the first k most significant bits of the distance
product of two matrices. Some of our algorithms are based, in part, on fast
matrix multiplication.


title:
An effective edge--directed frequency filter for removal of aliasing in
  upsampled images

abstract:
  Raster images can have a range of various distortions connected to their
raster structure. Upsampling them might in effect substantially yield the
raster structure of the original image, known as aliasing. The upsampling
itself may introduce aliasing into the upsampled image as well. The presented
method attempts to remove the aliasing using frequency filters based on the
discrete fast Fourier transform, and applied directionally in certain regions
placed along the edges in the image.
  As opposed to some anisotropic smoothing methods, the presented algorithm
aims to selectively reduce only the aliasing, preserving the sharpness of image
details.
  The method can be used as a post--processing filter along with various
upsampling algorithms. It was experimentally shown that the method can improve
the visual quality of the upsampled images.


title:
Scheduling for Stable and Reliable Communication over Multiaccess
  Channels and Degraded Broadcast Channels

abstract:
  Information-theoretic arguments focus on modeling the reliability of
information transmission, assuming availability of infinite data at sources,
thus ignoring randomness in message generation times at the respective sources.
However, in information transport networks, not only is reliable transmission
important, but also stability, i.e., finiteness of mean delay incurred by
messages from the time of generation to the time of successful reception.
Usually, delay analysis is done separately using queueing-theoretic arguments,
whereas reliable information transmission is studied using information theory.
In this thesis, we investigate these two important aspects of data
communication jointly by suitably combining models from these two fields. In
particular, we model scheduled communication of messages, that arrive in a
random process, (i) over multiaccess channels, with either independent decoding
or joint decoding, and (ii) over degraded broadcast channels. The scheduling
policies proposed permit up to a certain maximum number of messages for
simultaneous transmission.
  In the first part of the thesis, we develop a multi-class discrete-time
processor-sharing queueing model, and then investigate the stability of this
queue. In particular, we model the queue by a discrete-time Markov chain
defined on a countable state space, and then establish (i) a sufficient
condition for $c$-regularity of the chain, and hence positive recurrence and
finiteness of stationary mean of the function $c$ of the state, and (ii) a
sufficient condition for transience of the chain. These stability results form
the basis for the conclusions drawn in the thesis.


title: Baire Categories on Small Complexity Classes and Meager-Comeager Laws

abstract:
  We introduce two resource-bounded Baire category notions on small complexity
classes such as P, SUBEXP, and PSPACE and on probabilistic classes such as BPP,
which differ on how the corresponding finite extension strategies are computed.
We give an alternative characterization of small sets via resource-bounded
Banach-Mazur games.
  As an application of the first notion, we show that for almost every language
A (i.e. all except a meager class) computable in subexponential time,
P(A)=BPP(A). We also show that almost all languages in PSPACE do not have small
nonuniform complexity.
  We then switch to the second Baire category notion (called
locally-computable), and show that the class SPARSE is meager in P. We show
that in contrast to the resource-bounded measure case, meager-comeager laws can
be obtained for many standard complexity classes, relative to
locally-computable Baire category on BPP and PSPACE.
  Another topic where locally-computable Baire categories differ from
resource-bounded measure is regarding weak-completeness: we show that there is
no weak-completeness notion in P based on locally-computable Baire categories,
i.e. every P-weakly-complete set is complete for P. We also prove that the
class of complete sets for P under Turing-logspace reductions is meager in P,
if P is not equal to DSPACE(log n), and that the same holds unconditionally for
quasi-poly time.
  Finally we observe that locally-computable Baire categories are incomparable
with all existing resource-bounded measure notions on small complexity classes,
which might explain why those two settings seem to differ so fundamentally.


title:
Combining typing and size constraints for checking the termination of
  higher-order conditional rewrite systems

abstract:
  In a previous work, the first author extended to higher-order rewriting and
dependent types the use of size annotations in types, a termination proof
technique called type or size based termination and initially developed for
ML-like programs. Here, we go one step further by considering conditional
rewriting and explicit quantifications and constraints on size annotations.
This allows to describe more precisely how the size of the output of a function
depends on the size of its inputs. Hence, we can check the termination of more
functions. We first give a general type-checking algorithm based on constraint
solving. Then, we give a termination criterion with constraints in Presburger
arithmetic. To our knowledge, this is the first termination criterion for
higher-order conditional rewriting taking into account the conditions in
termination.


title: A simple stability condition for RED using TCP mean-field modeling

abstract:
  Congestion on the Internet is an old problem but still a subject of intensive
research. The TCP protocol with its AIMD (Additive Increase and Multiplicative
Decrease) behavior hides very challenging problems; one of them is to
understand the interaction between a large number of users with delayed
feedback. This article will focus on two modeling issues of TCP which appeared
to be important to tackle concrete scenarios when implementing the model
proposed in [Baccelli McDonald Reynier 02] firstly the modeling of the maximum
TCP window size: this maximum can be reached quickly in many practical cases;
secondly the delay structure: the usual Little-like formula behaves really
poorly when queuing delays are variable, and may change dramatically the
evolution of the predicted queue size, which makes it useless to study
drop-tail or RED (Random Early Detection) mechanisms. Within proposed TCP
modeling improvements, we are enabled to look at a concrete example where RED
should be used in FIFO routers instead of letting the default drop-tail happen.
We study mathematically fixed points of the window size distribution and local
stability of RED. An interesting case is when RED operates at the limit when
the congestion starts, it avoids unwanted loss of bandwidth and delay
variations.


title: Residual Finite Tree Automata

abstract:
  Tree automata based algorithms are essential in many fields in computer
science such as verification, specification, program analysis. They become also
essential for databases with the development of standards such as XML. In this
paper, we define new classes of non deterministic tree automata, namely
residual finite tree automata (RFTA). In the bottom-up case, we obtain a new
characterization of regular tree languages. In the top-down case, we obtain a
subclass of regular tree languages which contains the class of languages
recognized by deterministic top-down tree automata. RFTA also come with the
property of existence of canonical non deterministic tree automata.


title: ANAP: Anonymous Authentication Protocol in Mobile Ad hoc Networks

abstract:
  The pervasiveness of wireless communication recently gave mobile ad hoc
networks (MANET) a significant researchers' attention, due to its innate
capabilities of instant communication in many time and mission critical
applications. However, its natural advantages of networking in civilian and
military environments make them vulnerable to security threats. Support for an
anonymity in MANET is an orthogonal to security critical challenge we faced in
this paper. We propose a new anonymous authentication protocol for mobile ad
hoc networks enhanced with a distributed reputation system. The main its
objective is to provide mechanisms concealing a real identity of communicating
nodes with an ability of resist to known attacks. The distributed reputation
system is incorporated for a trust management and malicious behavior detection
in the network. The end-to-end anonymous authentication is conducted in
three-pass handshake based on an asymmetric and symmetric key cryptography.
After successfully finished authentication phase secure and multiple anonymous
data channels are established. The anonymity is guarantied by randomly chosen
pseudonyms owned by a user. Nodes of the network are publicly identified and
are independent of users' pseudonyms. In this paper we presented an example of
the protocol implementation.


title:
On some winning strategies for the Iterated Prisoner's Dilemma or Mr.
  Nice Guy and the Cosa Nostra

abstract:
  We submitted two kinds of strategies to the iterated prisoner's dilemma (IPD)
competitions organized by Graham Kendall, Paul Darwen and Xin Yao in 2004 and
2005. Our strategies performed exceedingly well in both years. One type is an
intelligent and optimistic enhanced version of the well known TitForTat
strategy which we named OmegaTitForTat. It recognizes common behaviour patterns
and detects and recovers from repairable mutual defect deadlock situations,
otherwise behaving much like TitForTat. The second type consists of a set of
strategies working together as a team. These group strategies have one
distinguished individual Godfather strategy that plays OmegaTitForTat against
non-members while heavily profiting from the behaviour of the other members of
his group, the Hitman. The Hitman willingly let themselves being abused by
their Godfather while themselves lowering the scores of all other players as
much as possible, thus further maximizing the performance of their Godfather in
relation to other participants. The study of collusion in the simplified
framework of the iterated prisoner's dilemma allows us to draw parallels to
many common aspects of reality both in Nature as well as Human Society, and
therefore further extends the scope of the iterated prisoner's dilemma as a
metaphor for the study of cooperative behaviour in a new and natural direction.
We further provide evidence that it will be unavoidable that such group
strategies will dominate all future iterated prisoner's dilemma competitions as
they can be stealthy camouflaged as non-group strategies with arbitrary
subtlety. Moreover, we show that the general problem of recognizing stealth
colluding strategies is undecidable in the theoretical sense.


title:
Bilayer Low-Density Parity-Check Codes for Decode-and-Forward in Relay
  Channels

abstract:
  This paper describes an efficient implementation of binning for the relay
channel using low-density parity-check (LDPC) codes. We devise bilayer LDPC
codes to approach the theoretically promised rate of the decode-and-forward
relaying strategy by incorporating relay-generated information bits in
specially designed bilayer graphical code structures. While conventional LDPC
codes are sensitively tuned to operate efficiently at a certain channel
parameter, the proposed bilayer LDPC codes are capable of working at two
different channel parameters and two different rates: that at the relay and at
the destination. To analyze the performance of bilayer LDPC codes, bilayer
density evolution is devised as an extension of the standard density evolution
algorithm. Based on bilayer density evolution, a design methodology is
developed for the bilayer codes in which the degree distribution is iteratively
improved using linear programming. Further, in order to approach the
theoretical decode-and-forward rate for a wide range of channel parameters,
this paper proposes two different forms bilayer codes, the bilayer-expurgated
and bilayer-lengthened codes. It is demonstrated that a properly designed
bilayer LDPC code can achieve an asymptotic infinite-length threshold within
0.24 dB gap to the Shannon limits of two different channels simultaneously for
a wide range of channel parameters. By practical code construction,
finite-length bilayer codes are shown to be able to approach within a 0.6 dB
gap to the theoretical decode-and-forward rate of the relay channel at a block
length of $10^5$ and a bit-error probability (BER) of $10^{-4}$. Finally, it is
demonstrated that a generalized version of the proposed bilayer code
construction is applicable to relay networks with multiple relays.


title: Improving Term Extraction with Terminological Resources

abstract:
  Studies of different term extractors on a corpus of the biomedical domain
revealed decreasing performances when applied to highly technical texts. The
difficulty or impossibility of customising them to new domains is an additional
limitation. In this paper, we propose to use external terminologies to
influence generic linguistic data in order to augment the quality of the
extraction. The tool we implemented exploits testified terms at different steps
of the process: chunking, parsing and extraction of term candidates.
Experiments reported here show that, using this method, more term candidates
can be acquired with a higher level of reliability. We further describe the
extraction process involving endogenous disambiguation implemented in the term
extractor YaTeA.


title: Fast algorithms for computing isogenies between elliptic curves

abstract:
  We survey algorithms for computing isogenies between elliptic curves defined
over a field of characteristic either 0 or a large prime. We introduce a new
algorithm that computes an isogeny of degree $\ell$ ($\ell$ different from the
characteristic) in time quasi-linear with respect to $\ell$. This is based in
particular on fast algorithms for power series expansion of the Weierstrass
$\wp$-function and related functions.


title: Non uniform (hyper/multi)coherence spaces

abstract:
  In (hyper)coherence semantics, proofs/terms are cliques in (hyper)graphs.
Intuitively, vertices represent results of computations and the edge relation
witnesses the ability of being assembled into a same piece of data or a same
(strongly) stable function, at arrow types. In (hyper)coherence semantics, the
argument of a (strongly) stable functional is always a (strongly) stable
function. As a consequence, comparatively to the relational semantics, where
there is no edge relation, some vertices are missing. Recovering these vertices
is essential for the purpose of reconstructing proofs/terms from their
interpretations. It shall also be useful for the comparison with other
semantics, like game semantics. In [BE01], Bucciarelli and Ehrhard introduced a
so called non uniform coherence space semantics where no vertex is missing. By
constructing the co-free exponential we set a new version of this last
semantics, together with non uniform versions of hypercoherences and
multicoherences, a new semantics where an edge is a finite multiset. Thanks to
the co-free construction, these non uniform semantics are deterministic in the
sense that the intersection of a clique and of an anti-clique contains at most
one vertex, a result of interaction, and extensionally collapse onto the
corresponding uniform semantics.


title: Dichotomies and Duality in First-order Model Checking Problems

abstract:
  We study the complexity of the model checking problem, for fixed model A,
over certain fragments L of first-order logic. These are sometimes known as the
expression complexities of L. We obtain various complexity classification
theorems for these logics L as each ranges over models A, in the spirit of the
dichotomy conjecture for the Constraint Satisfaction Problem -- which itself
may be seen as the model checking problem for existential conjunctive positive
first-order logic.


title:
Novel Reversible TSG Gate and Its Application for Designing Components
  of Primitive Reversible/Quantum ALU

abstract:
  In recent years, reversible logic has emerged as a promising computing
paradigm having application in low power CMOS, quantum computing,
nanotechnology, and optical computing. The classical set of gates such as AND,
OR, and EXOR are not reversible. This paper utilizes a new 4 * 4 reversible
gate called TSG gate to build the components of a primitive reversible/quantum
ALU. The most significant aspect of the TSG gate is that it can work singly as
a reversible full adder, that is reversible full adder can now be implemented
with a single gate only. A Novel reversible 4:2 compressor is also designed
from the TSG gate which is later used to design a novel 8x8 reversible Wallace
tree multiplier. It is proved that the adder, 4:2 compressor and multiplier
architectures designed using the TSG gate are better than their counterparts
available in literature, in terms of number of reversible gates and garbage
outputs. This is perhaps, the first attempt to design a reversible 4:2
compressor and a reversible Wallace tree multiplier as far as existing
literature and our knowledge is concerned. Thus, this paper provides an initial
threshold to build more complex systems which can execute complicated
operations using reversible logic.


title: Linux, Open Source and Unicode

abstract: The paper is taken out.


title: A XML Schema Definition based Universal User Interface

abstract: The article is taken out for change of contents.


title: Rarest First and Choke Algorithms Are Enough

abstract:
  The performance of peer-to-peer file replication comes from its piece and
peer selection strategies. Two such strategies have been introduced by the
BitTorrent protocol: the rarest first and choke algorithms. Whereas it is
commonly admitted that BitTorrent performs well, recent studies have proposed
the replacement of the rarest first and choke algorithms in order to improve
efficiency and fairness. In this paper, we use results from real experiments to
advocate that the replacement of the rarest first and choke algorithms cannot
be justified in the context of peer-to-peer file replication in the Internet.
We instrumented a BitTorrent client and ran experiments on real torrents with
different characteristics. Our experimental evaluation is peer oriented,
instead of tracker oriented, which allows us to get detailed information on all
exchanged messages and protocol events. We go beyond the mere observation of
the good efficiency of both algorithms. We show that the rarest first algorithm
guarantees close to ideal diversity of the pieces among peers. In particular,
on our experiments, replacing the rarest first algorithm with source or network
coding solutions cannot be justified. We also show that the choke algorithm in
its latest version fosters reciprocation and is robust to free riders. In
particular, the choke algorithm is fair and its replacement with a bit level
tit-for-tat solution is not appropriate. Finally, we identify new areas of
improvements for efficient peer-to-peer file replication protocols.


title: A Case for Peering of Content Delivery Networks

abstract:
  The proliferation of Content Delivery Networks (CDN) reveals that existing
content networks are owned and operated by individual companies. As a
consequence, closed delivery networks are evolved which do not cooperate with
other CDNs and in practice, islands of CDNs are formed. Moreover, the logical
separation between contents and services in this context results in two content
networking domains. But present trends in content networks and content
networking capabilities give rise to the interest in interconnecting content
networks. Finding ways for distinct content networks to coordinate and
cooperate with other content networks is necessary for better overall service.
In addition to that, meeting the QoS requirements of users according to the
negotiated Service Level Agreements between the user and the content network is
a burning issue in this perspective. In this article, we present an open,
scalable and Service-Oriented Architecture based system to assist the creation
of open Content and Service Delivery Networks (CSDN) that scale and support
sharing of resources with other CSDNs.


title:
VLSI Implementation of RSA Encryption System Using Ancient Indian Vedic
  Mathematics

abstract:
  This paper proposes the hardware implementation of RSA encryption/decryption
algorithm using the algorithms of Ancient Indian Vedic Mathematics that have
been modified to improve performance. The recently proposed hierarchical
overlay multiplier architecture is used in the RSA circuitry for multiplication
operation. The most significant aspect of the paper is the development of a
division architecture based on Straight Division algorithm of Ancient Indian
Vedic Mathematics and embedding it in RSA encryption/decryption circuitry for
improved efficiency. The coding is done in Verilog HDL and the FPGA synthesis
is done using Xilinx Spartan library. The results show that RSA circuitry
implemented using Vedic division and multiplication is efficient in terms of
area/speed compared to its implementation using conventional multiplication and
division architectures


title:
Reversible Programmable Logic Array (RPLA) using Fredkin & Feynman Gates
  for Industrial Electronics and Applications

abstract:
  In recent years, reversible logic has emerged as a promising computing
paradigm having application in low power CMOS, quantum computing,
nanotechnology, and optical computing. The classical set of gates such as AND,
OR, and EXOR are not reversible. In this paper, the authors have proposed
reversible programmable logic array (RPLA) architecture using reversible
Fredkin and Feynman gates. The proposed RPLA has n inputs and m outputs and can
realize m functions of n variables. In order to demonstrate the design of RPLA,
a 3 input RPLA is designed which can perform any 28 functions using the
combination of 8 min terms (23). Furthermore, the application of the designed 3
input RPLA is shown by implementing the full adder and full subtractor
functions through it.


title: Space Division Multiple Access with a Sum Feedback Rate Constraint

abstract:
  On a multi-antenna broadcast channel, simultaneous transmission to multiple
users by joint beamforming and scheduling is capable of achieving high
throughput, which grows double logarithmically with the number of users. The
sum rate for channel state information (CSI) feedback, however, increases
linearly with the number of users, reducing the effective uplink capacity. To
address this problem, a novel space division multiple access (SDMA) design is
proposed, where the sum feedback rate is upper-bounded by a constant. This
design consists of algorithms for CSI quantization, threshold based CSI
feedback, and joint beamforming and scheduling. The key feature of the proposed
approach is the use of feedback thresholds to select feedback users with large
channel gains and small CSI quantization errors such that the sum feedback rate
constraint is satisfied. Despite this constraint, the proposed SDMA design is
shown to achieve a sum capacity growth rate close to the optimal one. Moreover,
the feedback overflow probability for this design is found to decrease
exponentially with the difference between the allowable and the average sum
feedback rates. Numerical results show that the proposed SDMA design is capable
of attaining higher sum capacities than existing ones, even though the sum
feedback rate is bounded.


title: Approximation Algorithms for the Bipartite Multi-cut Problem

abstract:
  We introduce the {\it Bipartite Multi-cut} problem. This is a generalization
of the {\it st-Min-cut} problem, is similar to the {\it Multi-cut} problem
(except for more stringent requirements) and also turns out to be an immediate
generalization of the {\it Min UnCut} problem. We prove that this problem is
{\bf NP}-hard and then present LP and SDP based approximation algorithms. While
the LP algorithm is based on the Garg-Vazirani-Yannakakis algorithm for {\it
Multi-cut}, the SDP algorithm uses the {\it Structure Theorem} of $\ell_2^2$
Metrics.


title: CR-precis: A deterministic summary structure for update data streams

abstract:
  We present the \crprecis structure, that is a general-purpose, deterministic
and sub-linear data structure for summarizing \emph{update} data streams. The
\crprecis structure yields the \emph{first deterministic sub-linear space/time
algorithms for update streams} for answering a variety of fundamental stream
queries, such as, (a) point queries, (b) range queries, (c) finding approximate
frequent items, (d) finding approximate quantiles, (e) finding approximate
hierarchical heavy hitters, (f) estimating inner-products, (g) near-optimal
$B$-bucket histograms, etc..


title: Choosing Colors for Geometric Graphs via Color Space Embeddings

abstract:
  Graph drawing research traditionally focuses on producing geometric
embeddings of graphs satisfying various aesthetic constraints. After the
geometric embedding is specified, there is an additional step that is often
overlooked or ignored: assigning display colors to the graph's vertices. We
study the additional aesthetic criterion of assigning distinct colors to
vertices of a geometric graph so that the colors assigned to adjacent vertices
are as different from one another as possible. We formulate this as a problem
involving perceptual metrics in color space and we develop algorithms for
solving this problem by embedding the graph in color space. We also present an
application of this work to a distributed load-balancing visualization problem.


title:
Social Decision Making with Multi-Relational Networks and Grammar-Based
  Particle Swarms

abstract:
  Social decision support systems are able to aggregate the local perspectives
of a diverse group of individuals into a global social decision. This paper
presents a multi-relational network ontology and grammar-based particle swarm
algorithm capable of aggregating the decisions of millions of individuals. This
framework supports a diverse problem space and a broad range of vote
aggregation algorithms. These algorithms account for individual expertise and
representation across different domains of the group problem space. Individuals
are able to pose and categorize problems, generate potential solutions, choose
trusted representatives, and vote for particular solutions. Ultimately, via a
social decision making algorithm, the system aggregates all the individual
votes into a single collective decision.


title: Rational Secret Sharing and Multiparty Computation: Extended Abstract

abstract:
  We consider the problems of secret sharing and multiparty computation,
assuming that agents prefer to get the secret (resp., function value) to not
getting it, and secondarily, prefer that as few as possible of the other agents
get it. We show that, under these assumptions, neither secret sharing nor
multiparty function computation is possible using a mechanism that has a fixed
running time. However, we show that both are possible using randomized
mechanisms with constant expected running time.


title: Reduced Area Low Power High Throughput BCD Adders for IEEE 754r Format

abstract:
  IEEE 754r is the ongoing revision to the IEEE 754 floating point standard and
a major enhancement to the standard is the addition of decimal format. Firstly,
this paper proposes novel two transistor AND and OR gates. The proposed AND
gate has no power supply, thus it can be referred as the Powerless AND gate.
Similarly, the proposed two transistor OR gate has no ground and can be
referred as Groundless OR. Secondly for IEEE 754r format, two novel BCD adders
called carry skip and carry look-ahead BCD adders are also proposed in this
paper. In order to design the carry look-ahead BCD adder, a novel 4 bit carry
look-ahead adder called NCLA is proposed which forms the basic building block
of the proposed carry look-ahead BCD adder. Finally, the proposed two
transistors AND and OR gates are used to provide the optimized small area low
power high throughput circuitries of the proposed BCD adders.


title: (HO)RPO Revisited

abstract:
  The notion of computability closure has been introduced for proving the
termination of the combination of higher-order rewriting and beta-reduction. It
is also used for strengthening the higher-order recursive path ordering. In the
present paper, we study in more details the relations between the computability
closure and the (higher-order) recursive path ordering. We show that the
first-order recursive path ordering is equal to an ordering naturally defined
from the computability closure. In the higher-order case, we get an ordering
containing the higher-order recursive path ordering whose well-foundedness
relies on the correctness of the computability closure. This provides a simple
way to extend the higher-order recursive path ordering to richer type systems.


title:
On Performance of Event-to-Sink Transport in Transmit-Only Sensor
  Networks

abstract:
  We consider a hybrid wireless sensor network with regular and transmit-only
sensors. The transmit-only sensors do not have receiver circuit, hence are
cheaper and less energy consuming, but their transmissions cannot be
coordinated. Regular sensors, also called cluster-heads, are responsible for
receiving information from transmit-only sensors and forwarding it to sinks.
The main goal of such a hybrid network is to reduce the cost of deployment
while achieving some performance constraints (minimum coverage, sensing rate,
etc). In this paper we are interested in the communication between
transmit-only sensors and cluster-heads. We develop a detailed analytical model
of the physical and MAC layer using tools from queuing theory and stochastic
geometry. (The MAC model, that we call Erlang's loss model with interference,
might be of independent interest as adequate for any non-slotted; i.e.,
unsynchronized, wireless communication channel.) We give an explicit formula
for the frequency of successful packet reception by a cluster-head, given
sensors' locations. We further define packet admission policies at a
cluster-head, and we calculate the optimal policies for different performance
criteria. Finally we show that the proposed hybrid network, using the optimal
policies, can achieve substantial cost savings as compared to conventional
architectures.


title: Higher-Order Termination: from Kruskal to Computability

abstract:
  Termination is a major question in both logic and computer science. In logic,
termination is at the heart of proof theory where it is usually called strong
normalization (of cut elimination). In computer science, termination has always
been an important issue for showing programs correct. In the early days of
logic, strong normalization was usually shown by assigning ordinals to
expressions in such a way that eliminating a cut would yield an expression with
a smaller ordinal. In the early days of verification, computer scientists used
similar ideas, interpreting the arguments of a program call by a natural
number, such as their size. Showing the size of the arguments to decrease for
each recursive call gives a termination proof of the program, which is however
rather weak since it can only yield quite small ordinals. In the sixties, Tait
invented a new method for showing cut elimination of natural deduction, based
on a predicate over the set of terms, such that the membership of an expression
to the predicate implied the strong normalization property for that expression.
The predicate being defined by induction on types, or even as a fixpoint, this
method could yield much larger ordinals. Later generalized by Girard under the
name of reducibility or computability candidates, it showed very effective in
proving the strong normalization property of typed lambda-calculi...


title: Elgot Algebras

abstract:
  Denotational semantics can be based on algebras with additional structure
(order, metric, etc.) which makes it possible to interpret recursive
specifications. It was the idea of Elgot to base denotational semantics on
iterative theories instead, i.e., theories in which abstract recursive
specifications are required to have unique solutions. Later Bloom and Esik
studied iteration theories and iteration algebras in which a specified solution
has to obey certain axioms. We propose so-called Elgot algebras as a convenient
structure for semantics in the present paper. An Elgot algebra is an algebra
with a specified solution for every system of flat recursive equations. That
specification satisfies two simple and well motivated axioms: functoriality
(stating that solutions are stable under renaming of recursion variables) and
compositionality (stating how to perform simultaneous recursion). These two
axioms stem canonically from Elgot's iterative theories: We prove that the
category of Elgot algebras is the Eilenberg-Moore category of the monad given
by a free iterative theory.


title:
Primitive operations for the construction and reorganization of
  minimally persistent formations

abstract:
  In this paper, we study the construction and transformation of
two-dimensional persistent graphs. Persistence is a generalization to directed
graphs of the undirected notion of rigidity. In the context of moving
autonomous agent formations, persistence characterizes the efficacy of a
directed structure of unilateral distances constraints seeking to preserve a
formation shape. Analogously to the powerful results about Henneberg sequences
in minimal rigidity theory, we propose different types of directed graph
operations allowing one to sequentially build any minimally persistent graph
(i.e. persistent graph with a minimal number of edges for a given number of
vertices), each intermediate graph being also minimally persistent. We also
consider the more generic problem of obtaining one minimally persistent graph
from another, which corresponds to the on-line reorganization of an autonomous
agent formation. We prove that we can obtain any minimally persistent formation
from any other one by a sequence of elementary local operations such that
minimal persistence is preserved throughout the reorganization process.


title: On Divergence-Power Inequalities

abstract:
  Expressions for (EPI Shannon type) Divergence-Power Inequalities (DPI) in two
cases (time-discrete and band-limited time-continuous) of stationary random
processes are given. The new expressions connect the divergence rate of the sum
of independent processes, the individual divergence rate of each process, and
their power spectral densities. All divergences are between a process and a
Gaussian process with same second order statistics, and are assumed to be
finite. A new proof of the Shannon entropy-power inequality EPI, based on the
relationship between divergence and causal minimum mean-square error (CMMSE) in
Gaussian channels with large signal-to-noise ratio, is also shown.


title:
Challenging the principle of compositionality in interpreting natural
  language texts

abstract:
  The paper aims at emphasizing that, even relaxed, the hypothesis of
compositionality has to face many problems when used for interpreting natural
language texts. Rather than fixing these problems within the compositional
framework, we believe that a more radical change is necessary, and propose
another approach.


title: The role of time in considering collections

abstract:
  The paper concerns the understanding of plurals in the framework of
Artificial Intelligence and emphasizes the role of time. The construction of
collection(s) and their evolution across time is often crucial and has to be
accounted for. The paper contrasts a "de dicto" collection where the collection
can be considered as persisting over these situations even if its members
change with a "de re" collection whose composition does not vary through time.
It expresses different criteria of choice between the two interpretations (de
re and de dicto) depending on the context of enunciation.


title: Metric entropy in competitive on-line prediction

abstract:
  Competitive on-line prediction (also known as universal prediction of
individual sequences) is a strand of learning theory avoiding making any
stochastic assumptions about the way the observations are generated. The
predictor's goal is to compete with a benchmark class of prediction rules,
which is often a proper Banach function space. Metric entropy provides a
unifying framework for competitive on-line prediction: the numerous known upper
bounds on the metric entropy of various compact sets in function spaces readily
imply bounds on the performance of on-line prediction strategies. This paper
discusses strengths and limitations of the direct approach to competitive
on-line prediction via metric entropy, including comparisons to other
approaches.


title: Exhausting Error-Prone Patterns in LDPC Codes

abstract:
  It is proved in this work that exhaustively determining bad patterns in
arbitrary, finite low-density parity-check (LDPC) codes, including stopping
sets for binary erasure channels (BECs) and trapping sets (also known as
near-codewords) for general memoryless symmetric channels, is an NP-complete
problem, and efficient algorithms are provided for codes of practical short
lengths n~=500. By exploiting the sparse connectivity of LDPC codes, the
stopping sets of size <=13 and the trapping sets of size <=11 can be
efficiently exhaustively determined for the first time, and the resulting
exhaustive list is of great importance for code analysis and finite code
optimization. The featured tree-based narrowing search distinguishes this
algorithm from existing ones for which inexhaustive methods are employed. One
important byproduct is a pair of upper bounds on the bit-error rate (BER) &
frame-error rate (FER) iterative decoding performance of arbitrary codes over
BECs that can be evaluated for any value of the erasure probability, including
both the waterfall and the error floor regions. The tightness of these upper
bounds and the exhaustion capability of the proposed algorithm are proved when
combining an optimal leaf-finding module with the tree-based search. These
upper bounds also provide a worst-case-performance guarantee which is crucial
to optimizing LDPC codes for extremely low error rate applications, e.g.,
optical/satellite communications. Extensive numerical experiments are conducted
that include both randomly and algebraically constructed LDPC codes, the
results of which demonstrate the superior efficiency of the exhaustion
algorithm and its significant value for finite length code optimization.


title:
Topology Control and Network Lifetime in Three-Dimensional Wireless
  Sensor Networks

abstract:
  Coverage and connectivity issues of three-dimensional (3D) networks are
addressed in [2], but that work assumes that a node can be placed at any
arbitrary location. In this work, we drop that assumption and rather assume
that nodes are uniformly and densely deployed in a 3D space. We want to devise
a mechanism that keeps some nodes active and puts other nodes into sleep so
that the number of active nodes at a time is minimized (and thus network life
time is maximized), while maintaining full coverage and connectivity. One
simple way to do that is to partition the 3D space into cells, and only one
node in each cell remains active at a time. Our results show that the number of
active nodes can be minimized if the shape of each cell is a truncated
octahedron. It requires the sensing range to be at least 0.542326 times the
transmission radius. This value is 0.5, 0.53452 and 0.5 for cube, hexagonal
prism, and rhombic dodecahedron, respectively. However, at a time the number of
active nodes for cube, hexagonal prism and rhombic dodecahedron model is
respectively 2.372239, 1.82615 and 1.49468 times of that of truncated
octahedron model. So clearly truncated octahedron model has the highest network
lifetime. We also provide a distributed topology control algorithm that can be
used by each sensor node to determine its cell id using a constant number of
local arithmetic operations provided that the sensor node knows its location.
We also validate our results by simulation.


title: On the logical definability of certain graph and poset languages

abstract:
  We show that it is equivalent, for certain sets of finite graphs, to be
definable in CMS (counting monadic second-order logic, a natural extension of
monadic second-order logic), and to be recognizable in an algebraic framework
induced by the notion of modular decomposition of a finite graph. More
precisely, we consider the set $F\_\infty$ of composition operations on graphs
which occur in the modular decomposition of finite graphs. If $F$ is a subset
of $F\_{\infty}$, we say that a graph is an $\calF$-graph if it can be
decomposed using only operations in $F$. A set of $F$-graphs is recognizable if
it is a union of classes in a finite-index equivalence relation which is
preserved by the operations in $F$. We show that if $F$ is finite and its
elements enjoy only a limited amount of commutativity -- a property which we
call weak rigidity, then recognizability is equivalent to CMS-definability.
This requirement is weak enough to be satisfied whenever all $F$-graphs are
posets, that is, transitive dags. In particular, our result generalizes Kuske's
recent result on series-parallel poset languages.


title:
Scanning and Sequential Decision Making for Multi-Dimensional Data -
  Part I: the Noiseless Case

abstract:
  We investigate the problem of scanning and prediction ("scandiction", for
short) of multidimensional data arrays. This problem arises in several aspects
of image and video processing, such as predictive coding, for example, where an
image is compressed by coding the error sequence resulting from scandicting it.
Thus, it is natural to ask what is the optimal method to scan and predict a
given image, what is the resulting minimum prediction loss, and whether there
exist specific scandiction schemes which are universal in some sense.
  Specifically, we investigate the following problems: First, modeling the data
array as a random field, we wish to examine whether there exists a scandiction
scheme which is independent of the field's distribution, yet asymptotically
achieves the same performance as if this distribution was known. This question
is answered in the affirmative for the set of all spatially stationary random
fields and under mild conditions on the loss function. We then discuss the
scenario where a non-optimal scanning order is used, yet accompanied by an
optimal predictor, and derive bounds on the excess loss compared to optimal
scanning and prediction.
  This paper is the first part of a two-part paper on sequential decision
making for multi-dimensional data. It deals with clean, noiseless data arrays.
The second part deals with noisy data arrays, namely, with the case where the
decision maker observes only a noisy version of the data, yet it is judged with
respect to the original, clean data.


title:
Exact Spectral Analysis of Single-h and Multi-h CPM Signals through PAM
  decomposition and Matrix Series Evaluation

abstract:
  In this paper we address the problem of closed-form spectral evaluation of
CPM. We show that the multi-h CPM signal can be conveniently generated by a PTI
SM. The output is governed by a Markov chain with the unusual peculiarity of
being cyclostationary and reducible; this holds also in the single-h context.
Judicious reinterpretation of the result leads to a formalization through a
stationary and irreducible Markov chain, whose spectral evaluation is known in
closed-form from the literature. Two are the major outcomes of this paper.
First, unlike the literature, we obtain a PSD in true closed-form. Second, we
give novel insights into the CPM format.


title: Multilingual person name recognition and transliteration

abstract:
  We present an exploratory tool that extracts person names from multilingual
news collections, matches name variants referring to the same person, and
infers relationships between people based on the co-occurrence of their names
in related news. A novel feature is the matching of name variants across
languages and writing systems, including names written with the Greek, Cyrillic
and Arabic writing system. Due to our highly multilingual setting, we use an
internal standard representation for name representation and matching, instead
of adopting the traditional bilingual approach to transliteration. This work is
part of the news analysis system NewsExplorer that clusters an average of
25,000 news articles per day to detect related news within the same and across
different languages.


title:
Undecidability of the unification and admissibility problems for modal
  and description logics

abstract:
  We show that the unification problem `is there a substitution instance of a
given formula that is provable in a given logic?' is undecidable for basic
modal logics K and K4 extended with the universal modality. It follows that the
admissibility problem for inference rules is undecidable for these logics as
well. These are the first examples of standard decidable modal logics for which
the unification and admissibility problems are undecidable. We also prove
undecidability of the unification and admissibility problems for K and K4 with
at least two modal operators and nominals (instead of the universal modality),
thereby showing that these problems are undecidable for basic hybrid logics.
Recently, unification has been introduced as an important reasoning service for
description logics. The undecidability proof for K with nominals can be used to
show the undecidability of unification for boolean description logics with
nominals (such as ALCO and SHIQO). The undecidability proof for K with the
universal modality can be used to show that the unification problem relative to
role boxes is undecidable for Boolean description logic with transitive roles,
inverse roles, and role hierarchies (such as SHI and SHIQ).


title:
Navigating multilingual news collections using automatically extracted
  information

abstract:
  We are presenting a text analysis tool set that allows analysts in various
fields to sieve through large collections of multilingual news items quickly
and to find information that is of relevance to them. For a given document
collection, the tool set automatically clusters the texts into groups of
similar articles, extracts names of places, people and organisations, lists the
user-defined specialist terms found, links clusters and entities, and generates
hyperlinks. Through its daily news analysis operating on thousands of articles
per day, the tool also learns relationships between people and other entities.
The fully functional prototype system allows users to explore and navigate
multilingual document collections across languages and time.


title:
High Data-Rate Single-Symbol ML Decodable Distributed STBCs for
  Cooperative Networks

abstract:
  High data-rate Distributed Orthogonal Space-Time Block Codes (DOSTBCs) which
achieve the single-symbol decodability and full diversity order are proposed in
this paper. An upper bound of the data-rate of the DOSTBC is derived and it is
approximately twice larger than that of the conventional repetition-based
cooperative strategy. In order to facilitate the systematic constructions of
the DOSTBCs achieving the upper bound of the data-rate, some special DOSTBCs,
which have diagonal noise covariance matrices at the destination terminal, are
investigated. These codes are referred to as the row-monomial DOSTBCs. An upper
bound of the data-rate of the row-monomial DOSTBC is derived and it is equal to
or slightly smaller than that of the DOSTBC. Lastly, the systematic
construction methods of the row-monomial DOSTBCs achieving the upper bound of
the data-rate are presented.