title: Universal Filtering via Hidden Markov Modeling

abstract:
  The problem of discrete universal filtering, in which the components of a
discrete signal emitted by an unknown source and corrupted by a known DMC are
to be causally estimated, is considered. A family of filters are derived, and
are shown to be universally asymptotically optimal in the sense of achieving
the optimum filtering performance when the clean signal is stationary, ergodic,
and satisfies an additional mild positivity condition. Our schemes are
comprised of approximating the noisy signal using a hidden Markov process (HMP)
via maximum-likelihood (ML) estimation, followed by the use of the forward
recursions for HMP state estimation. It is shown that as the data length
increases, and as the number of states in the HMP approximation increases, our
family of filters attain the performance of the optimal distribution-dependent
filter.


title: The Complexity of Mean Flow Time Scheduling Problems with Release Times

abstract:
  We study the problem of preemptive scheduling n jobs with given release times
on m identical parallel machines. The objective is to minimize the average flow
time. We show that when all jobs have equal processing times then the problem
can be solved in polynomial time using linear programming. Our algorithm can
also be applied to the open-shop problem with release times and unit processing
times. For the general case (when processing times are arbitrary), we show that
the problem is unary NP-hard.


title:
On the Capacity of Fading MIMO Broadcast Channels with Imperfect
  Transmitter Side-Information

abstract:
  A fading broadcast channel is considered where the transmitter employs two
antennas and each of the two receivers employs a single receive antenna. It is
demonstrated that even if the realization of the fading is precisely known to
the receivers, the high signal-to-noise (SNR) throughput is greatly reduced if,
rather than knowing the fading realization \emph{precisely}, the trasmitter
only knows the fading realization \emph{approximately}. The results are general
and are not limited to memoryless Gaussian fading.


title: A Locating-First Approach for Scalable Overlay Multicast

abstract:
  Recent proposals in multicast overlay construction have demonstrated the
importance of exploiting underlying network topology. However, these
topology-aware proposals often rely on incremental and periodic refinements to
improve the system performance. These approaches are therefore neither
scalable, as they induce high communication cost due to refinement overhead,
nor efficient because long convergence time is necessary to obtain a stabilized
structure. In this paper, we propose a highly scalable locating algorithm that
gradually directs newcomers to their a set of their closest nodes without
inducing high overhead. On the basis of this locating process, we build a
robust and scalable topology-aware clustered hierarchical overlay scheme,
called LCC. We conducted both simulations and PlanetLab experiments to evaluate
the performance of LCC. Results show that the locating process entails modest
resources in terms of time and bandwidth. Moreover, LCC demonstrates promising
performance to support large scale multicast applications.


title: Caract\'{e}ristiques arithm\'{e}tiques des processeurs graphiques

abstract:
  Les unit\'{e}s graphiques (Graphic Processing Units- GPU) sont d\'{e}sormais
des processeurs puissants et flexibles. Les derni\`{e}res g\'{e}n\'{e}rations
de GPU contiennent des unit\'{e}s programmables de traitement des sommets
(vertex shader) et des pixels (pixel shader) supportant des op\'{e}rations en
virgule flottante sur 8, 16 ou 32 bits. La repr\'{e}sentation flottante sur 32
bits correspond \`{a} la simple pr\'{e}cision de la norme IEEE sur
l'arithm\'{e}tique en virgule flottante (IEEE-754). Les GPU sont bien
adapt\'{e}s aux applications avec un fort parall\'{e}lisme de donn\'{e}es.
Cependant ils ne sont que peu utilis\'{e}s en dehors des calculs graphiques
(General Purpose computation on GPU -- GPGPU). Une des raisons de cet \'{e}tat
de faits est la pauvret\'{e} des documentations techniques fournies par les
fabricants (ATI et Nvidia), particuli\`{e}rement en ce qui concerne
l'implantation des diff\'{e}rents op\'{e}rateurs arithm\'{e}tiques
embarqu\'{e}s dans les diff\'{e}rentes unit\'{e}s de traitement. Or ces
informations sont essentielles pour estimer et contr\^{o}ler les erreurs
d'arrondi ou pour mettre en oeuvre des techniques de r\'{e}duction ou de
compensation afin de travailler en pr\'{e}cision double, quadruple ou
arbitrairement \'{e}tendue. Nous proposons dans cet article un ensemble de
programmes qui permettent de d\'{e}couvrir les caract\'{e}ristiques principales
des GPU en ce qui concerne l'arithm\'{e}tique \`{a} virgule flottante. Nous
donnons les r\'{e}sultats obtenus sur deux cartes graphiques r\'{e}centes: la
Nvidia 7800GTX et l'ATI RX1800XL.


title:
Efficient algorithm for computing the Euler-Poincar\'e characteristic of
  a semi-algebraic set defined by few quadratic inequalities

abstract:
  We present an algorithm which takes as input a closed semi-algebraic set, $S
\subset \R^k$, defined by \[ P_1 \leq 0, ..., P_\ell \leq 0, P_i \in
\R[X_1,...,X_k], \deg(P_i) \leq 2, \] and computes the Euler-Poincar\'e
characteristic of $S$. The complexity of the algorithm is $k^{O(\ell)}$.


title: Classical Authentication Aided Three-Stage Quantum Protocol

abstract:
  This paper modifies Kak's three-stage protocol so that it can guarantee
secure transmission of information. Although avoiding man-in-the-middle attack
is our primary objective in the introduction of classical authentication inside
the three-stage protocol, we also benefit from the inherent advantages of the
chosen classical authentication protocol. We have tried to implement ideas like
key distribution center, session key, time-stamp, and nonce, within the quantum
cryptography protocol.


title: The Generalized Multiple Access Channel with Confidential Messages

abstract:
  A discrete memoryless generalized multiple access channel (GMAC) with
confidential messages is studied, where two users attempt to transmit common
information to a destination and each user also has private (confidential)
information intended for the destination. This channel generalizes the multiple
access channel (MAC) in that the two users also receive channel outputs. It is
assumed that each user views the other user as a wire-tapper, and wishes to
keep its confidential information as secret as possible from the other user.
The level of secrecy of the confidential information is measured by the
equivocation rate. The performance measure of interest is the rate-equivocation
tuple that includes the common rate, two private rates and two equivocation
rates as components. The set that includes all achievable rate-equivocation
tuples is referred to as the capacity-equivocation region. For the GMAC with
one confidential message set, where only one user (user 1) has private
(confidential) information for the destination, inner and outer bounds on the
capacity-equivocation region are derived. The secrecy capacity region is
established, which is the set of all achievable rates with user 2 being
perfectly ignorant of confidential messages of user 1. Furthermore, the
capacity-equivocation region and the secrecy capacity region are established
for the degraded GMAC with one confidential message set. For the GMAC with two
confidential message sets, where both users have confidential messages for the
destination, inner bounds on the capacity-equivocation region and the secrecy
capacity region are obtained.


title: A Scalable Algorithm for Minimal Unsatisfiable Core Extraction

abstract:
  We propose a new algorithm for minimal unsatisfiable core extraction, based
on a deeper exploration of resolution-refutation properties. We provide
experimental results on formal verification benchmarks confirming that our
algorithm finds smaller cores than suboptimal algorithms; and that it runs
faster than those algorithms that guarantee minimality of the core.


title:
Upper Bounding the Performance of Arbitrary Finite LDPC Codes on Binary
  Erasure Channels

abstract:
  Assuming iterative decoding for binary erasure channels (BECs), a novel
tree-based technique for upper bounding the bit error rates (BERs) of
arbitrary, finite low-density parity-check (LDPC) codes is provided and the
resulting bound can be evaluated for all operating erasure probabilities,
including both the waterfall and the error floor regions. This upper bound can
also be viewed as a narrowing search of stopping sets, which is an approach
different from the stopping set enumeration used for lower bounding the error
floor. When combined with optimal leaf-finding modules, this upper bound is
guaranteed to be tight in terms of the asymptotic order. The Boolean framework
proposed herein further admits a composite search for even tighter results. For
comparison, a refinement of the algorithm is capable of exhausting all stopping
sets of size <14 for irregular LDPC codes of length n=500, which requires
approximately 1.67*10^25 trials if a brute force approach is taken. These
experiments indicate that this upper bound can be used both as an analytical
tool and as a deterministic worst-performance (error floor) guarantee, the
latter of which is crucial to optimizing LDPC codes for extremely low BER
applications, e.g., optical/satellite communications.


title: Error Exponents and Cutoff Rate for Noncoherent Rician Fading Channels

abstract:
  In this paper, random coding error exponents and cutoff rate are studied for
noncoherent Rician fading channels, where neither the receiver nor the
transmitter has channel side information. First, it is assumed that the input
is subject only to an average power constraint. In this case, a lower bound to
the random coding error exponent is considered and the optimal input achieving
this lower bound is shown to have a discrete amplitude and uniform phase. If
the input is subject to both average and peak power constraints, it is proven
that the optimal input achieving the random coding error exponent has again a
discrete nature. Finally, the cutoff rate is analyzed, and the optimality of
the single-mass input amplitude distribution in the low-power regime is
discussed.


title:
TARMAC: Traffic-Analysis Reslient MAC Protocol for Multi-Hop Wireless
  Networks

abstract:
  Traffic analysis in Multi-hop Wireless Networks can expose the structure of
the network allowing attackers to focus their efforts on critical nodes. For
example, jamming the only data sink in a sensor network can cripple the
network. We propose a new communication protocol that is part of the MAC layer,
but resides conceptually between the routing layer and MAC, that is resilient
to traffic analysis. Each node broadcasts the data that it has to transmit
according to a fixed transmission schedule that is independent of the traffic
being generated, making the network immune to time correlation analysis. The
transmission pattern is identical, with the exception of a possible time shift,
at all nodes, removing spatial correlation of transmissions to network
strucutre. Data for all neighbors resides in the same encrypted packet. Each
neighbor then decides which subset of the data in a packet to forward onwards
using a routing protocol whose details are orthogonal to the proposed scheme.
We analyze the basic scheme, exploring the tradeoffs in terms of frequency of
transmission and packet size. We also explore adaptive and time changing
patterns and analyze their performance under a number of representative
scenarios.


title: Aligned Virtual Coordinates for Greedy Routing in WSNs

abstract:
  Geographic routing provides relatively good performance at a much lower
overhead than conventional routing protocols such as AODV. However, the
performance of these protocols is impacted by physical voids, and localization
errors. Accordingly, virtual coordinate systems (VCS) were proposed as an
alternative approach that is resilient to localization errors and that
naturally routes around physical voids. However, we show that VCS is vulnerable
to different forms of the void problem and the performance of greedy routing on
VCS is worse than that of geographic forwarding. We show that these anomalies
are due to the integral nature of VCS, which causes quantization noise in the
estimate of connectivity and node location. We propose an aligned virtual
coordinate system (AVCS) on which the greedy routing success can be
significantly improved. With our approach, and for the first time, we show that
greedy routing on VCS out-performs that on physical coordinate systems even in
the absence of localization errors. We compare AVCS against some of the most
popular geographical routing protocols both on physical coordinate system and
the virtual coordinate systems and show that AVCS significantly improves
performance over the best known solutions.


title: Mathematica: A System of Computer Programs

abstract:
  Starting from the basic level of mathematica here we illustrate how to use a
mathematica notebook and write a program in the notebook. Next, we investigate
elaborately the way of linking of external programs with mathematica, so-called
the mathlink operation. Using this technique we can run very tedious jobs quite
efficiently, and the operations become extremely fast. Sometimes it is quite
desirable to run jobs in background of a computer which can take considerable
amount of time to finish, and this allows us to do work on other tasks, while
keeping the jobs running. The way of running jobs, written in a mathematica
notebook, in background is quite different from the conventional methods i.e.,
the techniques for the programs written in other languages like C, C++, F77,
F90, F95, etc. To illustrate it, in the present article we study how to create
a mathematica batch-file from a mathematica notebook and run it in the
background. Finally, we explore the most significant issue of this article.
Here we describe the basic ideas for parallelizing a mathematica program by
sharing its independent parts into all other remote computers available in the
network. Doing the parallelization, we can perform large computational
operations within a very short period of time, and therefore, the efficiency of
the numerical works can be achieved. Parallel computation supports any version
of mathematica and it also works significantly well even if different versions
of mathematica are installed in different computers. All the operations studied
in this article run under any supported operating system like Unix, Windows,
Macintosh, etc. For the sake of our illustrations, here we concentrate all the
discussions only for the Unix based operating system.


title:
Low-density constructions can achieve the Wyner-Ziv and Gelfand-Pinsker
  bounds

abstract:
  We describe and analyze sparse graphical code constructions for the problems
of source coding with decoder side information (the Wyner-Ziv problem), and
channel coding with encoder side information (the Gelfand-Pinsker problem). Our
approach relies on a combination of low-density parity check (LDPC) codes and
low-density generator matrix (LDGM) codes, and produces sparse constructions
that are simultaneously good as both source and channel codes. In particular,
we prove that under maximum likelihood encoding/decoding, there exist
low-density codes (i.e., with finite degrees) from our constructions that can
saturate both the Wyner-Ziv and Gelfand-Pinsker bounds.


title: The Multiple Access Channel with Feedback and Correlated Sources

abstract:
  In this paper, we investigate communication strategies for the multiple
access channel with feedback and correlated sources (MACFCS). The MACFCS models
a wireless sensor network scenario in which sensors distributed throughout an
arbitrary random field collect correlated measurements and transmit them to a
common sink. We derive achievable rate regions for the three-node MACFCS.
First, we study the strategy when source coding and channel coding are
combined, which we term full decoding at sources. Second, we look at several
strategies when source coding and channel coding are separated, which we term
full decoding at destination. From numerical computations on Gaussian channels,
we see that different strategies perform better under certain source
correlations and channel setups.


title:
The Capacity of the Single Source Multiple Relay Single Destination Mesh
  Network

abstract:
  In this paper, we derive the capacity of a special class of mesh networks. A
mesh network is defined as a heterogeneous wireless network in which the
transmission among power limited nodes is assisted by powerful relays, which
use the same wireless medium. We find the capacity of the mesh network when
there is one source, one destination, and multiple relays. We call this channel
the single source multiple relay single destination (SSMRSD) mesh network. Our
approach is as follows. We first look at an upper bound on the information
theoretic capacity of these networks in the Gaussian setting. We then show that
the bound is achievable asymptotically using the compress-forward strategy for
the multiple relay channel. Theoretically, the results indicate the value of
cooperation and the utility of carefully deployed relays in wireless ad-hoc and
sensor networks. The capacity characterization quantifies how the relays can be
used to either conserve node energy or to increase transmission rate.


title: Proof Search in Hajek's Basic Logic

abstract:
  We introduce a proof system for Hajek's logic BL based on a relational
hypersequents framework. We prove that the rules of our logical calculus,
called RHBL, are sound and invertible with respect to any valuation of BL into
a suitable algebra, called omega[0,1]. Refining the notion of reduction tree
that arises naturally from RHBL, we obtain a decision algorithm for BL
provability whose running time upper bound is 2^O(n), where n is the number of
connectives of the input formula. Moreover, if a formula is unprovable, we
exploit the constructiveness of a polynomial time algorithm for leaves validity
for providing a procedure to build countermodels in omega[0,1]. Finally, since
the size of the reduction tree branches is O(n^3), we can describe a polynomial
time verification algorithm for BL unprovability.


title:
Single-Symbol-Decodable Differential Space-Time Modulation Based on
  QO-STBC

abstract:
  We present a novel differential space-time modulation (DSTM) scheme that is
single-symbol decodable and can provide full transmit diversity. It is the
first known singlesymbol- decodable DSTM scheme not based on Orthogonal STBC
(O-STBC), and it is constructed based on the recently proposed
Minimum-Decoding-Complexity Quasi-Orthogonal Space-Time Block Code
(MDC-QOSTBC). We derive the code design criteria and present systematic
methodology to find the solution sets. The proposed DSTM scheme can provide
higher code rate than DSTM schemes based on O-STBC. Its decoding complexity is
also considerably lower than DSTM schemes based on Sp(2) and
double-symbol-decodable QOSTBC, with negligible or slight trade-off in decoding
error probability performance.


title: Circle Formation of Weak Robots and Lyndon Words

abstract:
  A Lyndon word is a non-empty word strictly smaller in the lexicographic order
than any of its suffixes, except itself and the empty word. In this paper, we
show how Lyndon words can be used in the distributed control of a set of n weak
mobile robots. By weak, we mean that the robots are anonymous, memoryless,
without any common sense of direction, and unable to communicate in an other
way than observation. An efficient and simple deterministic protocol to form a
regular n-gon is presented and proven for n prime.


title:
A Generalized Two-Phase Analysis of Knowledge Flows in Security
  Protocols

abstract:
  We introduce knowledge flow analysis, a simple and flexible formalism for
checking cryptographic protocols. Knowledge flows provide a uniform language
for expressing the actions of principals, assump- tions about intruders, and
the properties of cryptographic primitives. Our approach enables a generalized
two-phase analysis: we extend the two-phase theory by identifying the necessary
and sufficient proper- ties of a broad class of cryptographic primitives for
which the theory holds. We also contribute a library of standard primitives and
show that they satisfy our criteria.


title: Energy Efficiency in Multi-hop CDMA Networks: A Game Theoretic Analysis

abstract:
  A game-theoretic analysis is used to study the effects of receiver choice on
the energy efficiency of multi-hop networks in which the nodes communicate
using Direct-Sequence Code Division Multiple Access (DS-CDMA). A Nash
equilibrium of the game in which the network nodes can choose their receivers
as well as their transmit powers to maximize the total number of bits they
transmit per unit of energy is derived. The energy efficiencies resulting from
the use of different linear multiuser receivers in this context are compared,
looking at both the non-cooperative game and the Pareto optimal solution. For
analytical ease, particular attention is paid to asymptotically large networks.
Significant gains in energy efficiency are observed when multiuser receivers,
particularly the linear minimum mean-square error (MMSE) receiver, are used
instead of conventional matched filter receivers.


title: Alphabetic Coding with Exponential Costs

abstract:
  An alphabetic binary tree formulation applies to problems in which an outcome
needs to be determined via alphabetically ordered search prior to the
termination of some window of opportunity. Rather than finding a decision tree
minimizing $\sum_{i=1}^n w(i) l(i)$, this variant involves minimizing $\log_a
\sum_{i=1}^n w(i) a^{l(i)}$ for a given $a \in (0,1)$. This note introduces a
dynamic programming algorithm that finds the optimal solution in polynomial
time and space, and shows that methods traditionally used to improve the speed
of optimizations in related problems, such as the Hu-Tucker procedure, fail for
this problem. This note thus also introduces two approximation algorithms which
can find a suboptimal solution in linear time (for one) or $\order(n \log n)$
time (for the other), with associated coding redundancy bounds.


title: Network Inference from Co-Occurrences

abstract:
  The recovery of network structure from experimental data is a basic and
fundamental problem. Unfortunately, experimental data often do not directly
reveal structure due to inherent limitations such as imprecision in timing or
other observation mechanisms. We consider the problem of inferring network
structure in the form of a directed graph from co-occurrence observations. Each
observation arises from a transmission made over the network and indicates
which vertices carry the transmission without explicitly conveying their order
in the path. Without order information, there are an exponential number of
feasible graphs which agree with the observed data equally well. Yet, the basic
physical principles underlying most networks strongly suggest that all feasible
graphs are not equally likely. In particular, vertices that co-occur in many
observations are probably closely connected. Previous approaches to this
problem are based on ad hoc heuristics. We model the experimental observations
as independent realizations of a random walk on the underlying graph, subjected
to a random permutation which accounts for the lack of order information.
Treating the permutations as missing data, we derive an exact
expectation-maximization (EM) algorithm for estimating the random walk
parameters. For long transmission paths the exact E-step may be computationally
intractable, so we also describe an efficient Monte Carlo EM (MCEM) algorithm
and derive conditions which ensure convergence of the MCEM algorithm with high
probability. Simulations and experiments with Internet measurements demonstrate
the promise of this approach.


title: Modeling the Dynamics of Social Networks

abstract:
  Modeling human dynamics responsible for the formation and evolution of the
so-called social networks - structures comprised of individuals or
organizations and indicating connectivities existing in a community - is a
topic recently attracting a significant research interest. It has been claimed
that these dynamics are scale-free in many practically important cases, such as
impersonal and personal communication, auctioning in a market, accessing sites
on the WWW, etc., and that human response times thus conform to the power law.
While a certain amount of progress has recently been achieved in predicting the
general response rate of a human population, existing formal theories of human
behavior can hardly be found satisfactory to accommodate and comprehensively
explain the scaling observed in social networks. In the presented study, a
novel system-theoretic modeling approach is proposed and successfully applied
to determine important characteristics of a communication network and to
analyze consumer behavior on the WWW.

categories: cs.CY cs.CE cs.CL cs.HC cs.NI physics.data-an


title: Restricted Strip Covering and the Sensor Cover Problem

abstract:
  Given a set of objects with durations (jobs) that cover a base region, can we
schedule the jobs to maximize the duration the original region remains covered?
We call this problem the sensor cover problem. This problem arises in the
context of covering a region with sensors. For example, suppose you wish to
monitor activity along a fence by sensors placed at various fixed locations.
Each sensor has a range and limited battery life. The problem is to schedule
when to turn on the sensors so that the fence is fully monitored for as long as
possible. This one dimensional problem involves intervals on the real line.
Associating a duration to each yields a set of rectangles in space and time,
each specified by a pair of fixed horizontal endpoints and a height. The
objective is to assign a position to each rectangle to maximize the height at
which the spanning interval is fully covered. We call this one dimensional
problem restricted strip covering. If we replace the covering constraint by a
packing constraint, the problem is identical to dynamic storage allocation, a
scheduling problem that is a restricted case of the strip packing problem. We
show that the restricted strip covering problem is NP-hard and present an O(log
log n)-approximation algorithm. We present better approximations or exact
algorithms for some special cases. For the uniform-duration case of restricted
strip covering we give a polynomial-time, exact algorithm but prove that the
uniform-duration case for higher-dimensional regions is NP-hard. Finally, we
consider regions that are arbitrary sets, and we present an O(log
n)-approximation algorithm.


title: A Better Alternative to Piecewise Linear Time Series Segmentation

abstract:
  Time series are difficult to monitor, summarize and predict. Segmentation
organizes time series into few intervals having uniform characteristics
(flatness, linearity, modality, monotonicity and so on). For scalability, we
require fast linear time algorithms. The popular piecewise linear model can
determine where the data goes up or down and at what rate. Unfortunately, when
the data does not follow a linear model, the computation of the local slope
creates overfitting. We propose an adaptive time series model where the
polynomial degree of each interval vary (constant, linear and so on). Given a
number of regressors, the cost of each interval is its polynomial degree:
constant intervals cost 1 regressor, linear intervals cost 2 regressors, and so
on. Our goal is to minimize the Euclidean (l_2) error for a given model
complexity. Experimentally, we investigate the model where intervals can be
either constant or linear. Over synthetic random walks, historical stock market
prices, and electrocardiograms, the adaptive model provides a more accurate
segmentation than the piecewise linear model without increasing the
cross-validation error or the running time, while providing a richer vocabulary
to applications. Implementation issues, such as numerical stability and
real-world performance, are discussed.


title: Parsing Transformative LR(1) Languages

abstract:
  We consider, as a means of making programming languages more flexible and
powerful, a parsing algorithm in which the parser may freely modify the grammar
while parsing. We are particularly interested in a modification of the
canonical LR(1) parsing algorithm in which, after the reduction of certain
productions, we examine the source sentence seen so far to determine the
grammar to use to continue parsing. A naive modification of the canonical LR(1)
parsing algorithm along these lines cannot be guaranteed to halt; as a result,
we develop a test which examines the grammar as it changes, stopping the parse
if the grammar changes in a way that would invalidate earlier assumptions made
by the parser. With this test in hand, we can develop our parsing algorithm and
prove that it is correct. That being done, we turn to earlier, related work;
the idea of programming languages which can be extended to include new
syntactic constructs has existed almost as long as the idea of high-level
programming languages. Early efforts to construct such a programming language
were hampered by an immature theory of formal languages. More recent efforts to
construct transformative languages relied either on an inefficient chain of
source-to-source translators; or they have a defect, present in our naive
parsing algorithm, in that they cannot be known to halt. The present algorithm
does not have these undesirable properties, and as such, it should prove a
useful foundation for a new kind of programming language.


title: An outer bound to the capacity region of the broadcast channel

abstract:
  An outer bound to the capacity region of the two-receiver discrete memoryless
broadcast channel is given. The outer bound is tight for all cases where the
capacity region is known. When specialized to the case of no common
information, this outer bound is contained in the Korner-Marton outer bound.
This containment is shown to be strict for the binary skew-symmetric broadcast
channel. Thus, this outer bound is in general tighter than all other known
outer bounds on the discrete memoryless broadcast channel.


title: Supervisory Control of Fuzzy Discrete Event Systems: A Formal Approach

abstract:
  Fuzzy {\it discrete event systems} (DESs) were proposed recently by Lin and
Ying [19], which may better cope with the real-world problems with fuzziness,
impreciseness, and subjectivity such as those in biomedicine. As a continuation
of [19], in this paper we further develop fuzzy DESs by dealing with
supervisory control of fuzzy DESs. More specifically, (i) we reformulate the
parallel composition of crisp DESs, and then define the parallel composition of
fuzzy DESs that is equivalent to that in [19]; {\it max-product} and {\it
max-min} automata for modeling fuzzy DESs are considered; (ii) we deal with a
number of fundamental problems regarding supervisory control of fuzzy DESs,
particularly demonstrate controllability theorem and nonblocking
controllability theorem of fuzzy DESs, and thus present the conditions for the
existence of supervisors in fuzzy DESs; (iii) we analyze the complexity for
presenting a uniform criterion to test the fuzzy controllability condition of
fuzzy DESs modeled by max-product automata; in particular, we present in detail
a general computing method for checking whether or not the fuzzy
controllability condition holds, if max-min automata are used to model fuzzy
DESs, and by means of this method we can search for all possible fuzzy states
reachable from initial fuzzy state in max-min automata; also, we introduce the
fuzzy $n$-controllability condition for some practical problems; (iv) a number
of examples serving to illustrate the applications of the derived results and
methods are described; some basic properties related to supervisory control of
fuzzy DESs are investigated. To conclude, some related issues are raised for
further consideration.


title:
Fuzzy Discrete Event Systems under Fuzzy Observability and a
  test-algorithm

abstract:
  In order to more effectively cope with the real-world problems of vagueness,
impreciseness, and subjectivity, fuzzy discrete event systems (FDESs) were
proposed recently. Notably, FDESs have been applied to biomedical control for
HIV/AIDS treatment planning and sensory information processing for robotic
control. Qiu, Cao and Ying independently developed supervisory control theory
of FDESs. We note that the controllability of events in Qiu's work is fuzzy but
the observability of events is crisp, and, the observability of events in Cao
and Ying's work is also crisp although the controllability is not completely
crisp since the controllable events can be disabled with any degrees. Motivated
by the necessity to consider the situation that the events may be observed or
controlled with some membership degrees, in this paper, we establish the
supervisory control theory of FDESs with partial observations, in which both
the observability and controllability of events are fuzzy instead. We formalize
the notions of fuzzy controllability condition and fuzzy observability
condition. And Controllability and Observability Theorem of FDESs is set up in
a more generic framework. In particular, we present a detailed computing flow
to verify whether the controllability and observability conditions hold. Thus,
this result can decide the existence of supervisors. Also, we use this
computing method to check the existence of supervisors in the Controllability
and Observability Theorem of classical discrete event systems (DESs), which is
a new method and different from classical case. A number of examples are
elaborated on to illustrate the presented results.


title: Diagnosability of Fuzzy Discrete Event Systems

abstract:
  In order to more effectively cope with the real-world problems of vagueness,
{\it fuzzy discrete event systems} (FDESs) were proposed recently, and the
supervisory control theory of FDESs was developed. In view of the importance of
failure diagnosis, in this paper, we present an approach of the failure
diagnosis in the framework of FDESs. More specifically: (1) We formalize the
definition of diagnosability for FDESs, in which the observable set and failure
set of events are {\it fuzzy}, that is, each event has certain degree to be
observable and unobservable, and, also, each event may possess different
possibility of failure occurring. (2) Through the construction of
observability-based diagnosers of FDESs, we investigate its some basic
properties. In particular, we present a necessary and sufficient condition for
diagnosability of FDESs. (3) Some examples serving to illuminate the
applications of the diagnosability of FDESs are described. To conclude, some
related issues are raised for further consideration.


title: Knowledge Flow Analysis for Security Protocols

abstract:
  Knowledge flow analysis offers a simple and flexible way to find flaws in
security protocols. A protocol is described by a collection of rules
constraining the propagation of knowledge amongst principals. Because this
characterization corresponds closely to informal descriptions of protocols, it
allows a succinct and natural formalization; because it abstracts away message
ordering, and handles communications between principals and applications of
cryptographic primitives uniformly, it is readily represented in a standard
logic. A generic framework in the Alloy modelling language is presented, and
instantiated for two standard protocols, and a new key management scheme.


title: Mapping the Bid Behavior of Conference Referees

abstract:
  The peer-review process, in its present form, has been repeatedly criticized.
Of the many critiques ranging from publication delays to referee bias, this
paper will focus specifically on the issue of how submitted manuscripts are
distributed to qualified referees. Unqualified referees, without the proper
knowledge of a manuscript's domain, may reject a perfectly valid study or
potentially more damaging, unknowingly accept a faulty or fraudulent result. In
this paper, referee competence is analyzed with respect to referee bid data
collected from the 2005 Joint Conference on Digital Libraries (JCDL). The
analysis of the referee bid behavior provides a validation of the intuition
that referees are bidding on conference submissions with regards to the subject
domain of the submission. Unfortunately, this relationship is not strong and
therefore suggests that there exists other factors beyond subject domain that
may be influencing referees to bid for particular submissions.


title: A Metadata Registry from Vocabularies UP: The NSDL Registry Project

abstract:
  The NSDL Metadata Registry is designed to provide humans and machines with
the means to discover, create, access and manage metadata schemes, schemas,
application profiles, crosswalks and concept mappings. This paper describes the
general goals and architecture of the NSDL Metadata Registry as well as issues
encountered during the first year of the project's implementation.


title: An Algorithm to Determine Peer-Reviewers

abstract:
  The peer-review process is the most widely accepted certification mechanism
for officially accepting the written results of researchers within the
scientific community. An essential component of peer-review is the
identification of competent referees to review a submitted manuscript. This
article presents an algorithm to automatically determine the most appropriate
reviewers for a manuscript by way of a co-authorship network data structure and
a relative-rank particle-swarm algorithm. This approach is novel in that it is
not limited to a pre-selected set of referees, is computationally efficient,
requires no human-intervention, and, in some instances, can automatically
identify conflict of interest situations. A useful application of this
algorithm would be to open commentary peer-review systems because it provides a
weighting for each referee with respects to their expertise in the domain of a
manuscript. The algorithm is validated using referee bid data from the 2005
Joint Conference on Digital Libraries.


title: An Architecture for the Aggregation and Analysis of Scholarly Usage Data

abstract:
  Although recording of usage data is common in scholarly information services,
its exploitation for the creation of value-added services remains limited due
to concerns regarding, among others, user privacy, data validity, and the lack
of accepted standards for the representation, sharing and aggregation of usage
data. This paper presents a technical, standards-based architecture for sharing
usage information, which we have designed and implemented. In this
architecture, OpenURL-compliant linking servers aggregate usage information of
a specific user community as it navigates the distributed information
environment that it has access to. This usage information is made OAI-PMH
harvestable so that usage information exposed by many linking servers can be
aggregated to facilitate the creation of value-added services with a reach
beyond that of a single community or a single information service. This paper
also discusses issues that were encountered when implementing the proposed
approach, and it presents preliminary results obtained from analyzing a usage
data set containing about 3,500,000 requests aggregated by a federation of
linking servers at the California State University system over a 20 month
period.


title: Oblivious Transfer using Elliptic Curves

abstract:
  This paper proposes an algorithm for oblivious transfer using elliptic
curves. Also, we present its application to chosen one-out-of-two oblivious
transfer.


title: Key Distillation and the Secret-Bit Fraction

abstract:
  We consider distillation of secret bits from partially secret noisy
correlations P_ABE, shared between two honest parties and an eavesdropper. The
most studied distillation scenario consists of joint operations on a large
number of copies of the distribution (P_ABE)^N, assisted with public
communication. Here we consider distillation with only one copy of the
distribution, and instead of rates, the 'quality' of the distilled secret bits
is optimized, where the 'quality' is quantified by the secret-bit fraction of
the result. The secret-bit fraction of a binary distribution is the proportion
which constitutes a secret bit between Alice and Bob. With local operations and
public communication the maximal extractable secret-bit fraction from a
distribution P_ABE is found, and is denoted by Lambda[P_ABE]. This quantity is
shown to be nonincreasing under local operations and public communication, and
nondecreasing under eavesdropper's local operations: it is a secrecy monotone.
It is shown that if Lambda[P_ABE]>1/2 then P_ABE is distillable, thus providing
a sufficient condition for distillability. A simple expression for
Lambda[P_ABE] is found when the eavesdropper is decoupled, and when the honest
parties' information is binary and the local operations are reversible.
Intriguingly, for general distributions the (optimal) operation requires local
degradation of the data.


title: Optimal Distortion-Power Tradeoffs in Gaussian Sensor Networks

abstract:
  We investigate the optimal performance of dense sensor networks by studying
the joint source-channel coding problem. The overall goal of the sensor network
is to take measurements from an underlying random process, code and transmit
those measurement samples to a collector node in a cooperative multiple access
channel with imperfect feedback, and reconstruct the entire random process at
the collector node. We provide lower and upper bounds for the minimum
achievable expected distortion when the underlying random process is Gaussian.
In the case where the random process satisfies some general conditions, we
evaluate the lower and upper bounds explicitly and show that they are of the
same order for a wide range of sum power constraints. Thus, for these random
processes, under these sum power constraints, we determine the achievability
scheme that is order-optimal, and express the minimum achievable expected
distortion as a function of the sum power constraint.


title: A Lattice-Based MIMO Broadcast Precoder for Multi-Stream Transmission

abstract:
  Precoding with block diagonalization is an attractive scheme for approaching
sum capacity in multiuser multiple input multiple output (MIMO) broadcast
channels. This method requires either global channel state information at every
receiver or an additional training phase, which demands additional system
planning. In this paper we propose a lattice based multi-user precoder that
uses block diagonalization combined with pre-equalization and perturbation for
the multiuser MIMO broadcast channel. An achievable sum rate of the proposed
scheme is derived and used to show that the proposed technique approaches the
achievable sum rate of block diagonalization with water-filling but does not
require the additional information at the receiver. Monte Carlo simulations
with equal power allocation show that the proposed method provides better bit
error rate and diversity performance than block diagonalization with a
zero-forcing receiver. Additionally, the proposed method shows similar
performance to the maximum likelihood receiver but with much lower receiver
complexity.


title: Pseudocodeword weights for non-binary LDPC codes

abstract:
  Pseudocodewords of q-ary LDPC codes are examined and the weight of a
pseudocodeword on the q-ary symmetric channel is defined. The weight definition
of a pseudocodeword on the AWGN channel is also extended to two-dimensional
q-ary modulation such as q-PAM and q-PSK. The tree-based lower bounds on the
minimum pseudocodeword weight are shown to also hold for q-ary LDPC codes on
these channels.


title: An Internet-enabled technology to support Evolutionary Design

abstract:
  This paper discusses the systematic use of product feedback information to
support life-cycle design approaches and provides guidelines for developing a
design at both the product and the system levels. Design activities are
surveyed in the light of the product life cycle, and the design information
flow is interpreted from a semiotic perspective. The natural evolution of a
design is considered, the notion of design expectations is introduced, and the
importance of evaluation of these expectations in dynamic environments is
argued. Possible strategies for reconciliation of the expectations and
environmental factors are described. An Internet-enabled technology is proposed
to monitor product functionality, usage, and operational environment and supply
the designer with relevant information. A pilot study of assessing design
expectations of a refrigerator is outlined, and conclusions are drawn.


title:
Understanding Design Fundamentals: How Synthesis and Analysis Drive
  Creativity, Resulting in Emergence

abstract:
  This paper presents results of an ongoing interdisciplinary study to develop
a computational theory of creativity for engineering design. Human design
activities are surveyed, and popular computer-aided design methodologies are
examined. It is argued that semiotics has the potential to merge and unite
various design approaches into one fundamental theory that is naturally
interpretable and so comprehensible in terms of computer use. Reviewing related
work in philosophy, psychology, and cognitive science provides a general and
encompassing vision of the creativity phenomenon. Basic notions of algebraic
semiotics are given and explained in terms of design. This is to define a model
of the design creative process, which is seen as a process of semiosis, where
concepts and their attributes represented as signs organized into systems are
evolved, blended, and analyzed, resulting in the development of new concepts.
The model allows us to formally describe and investigate essential properties
of the design process, namely its dynamics and non-determinism inherent in
creative thinking. A stable pattern of creative thought - analogical and
metaphorical reasoning - is specified to demonstrate the expressive power of
the modeling approach; illustrative examples are given. The developed theory is
applied to clarify the nature of emergence in design: it is shown that while
emergent properties of a product may influence its creative value, emergence
can simply be seen as a by-product of the creative process. Concluding remarks
summarize the research, point to some unresolved issues, and outline directions
for future work.


title:
Communication of Social Agents and the Digital City - A Semiotic
  Perspective

abstract:
  This paper investigates the concept of digital city. First, a functional
analysis of a digital city is made in the light of the modern study of
urbanism; similarities between the virtual and urban constructions are pointed
out. Next, a semiotic perspective on the subject matter is elaborated, and a
terminological basis is introduced to treat a digital city as a self-organizing
meaning-producing system intended to support social or spatial navigation. An
explicit definition of a digital city is formulated. Finally, the proposed
approach is discussed, conclusions are given, and future work is outlined.


title: Modeling Hypermedia-Based Communication

abstract:
  In this article, we explore two approaches to modeling hypermedia-based
communication. It is argued that the classical conveyor-tube framework is not
applicable to the case of computer- and Internet- mediated communication. We
then present a simple but very general system-theoretic model of the
communication process, propose its mathematical interpretation, and derive
several formulas, which qualitatively and quantitatively accord with data
obtained on-line. The devised theoretical results generalize and correct the
Zipf-Mandelbrot law and can be used in information system design. At the
paper's end, we give some conclusions and draw implications for future work.


title: Classification of Ordinal Data

abstract:
  Classification of ordinal data is one of the most important tasks of relation
learning. In this thesis a novel framework for ordered classes is proposed. The
technique reduces the problem of classifying ordered classes to the standard
two-class problem. The introduced method is then mapped into support vector
machines and neural networks. Compared with a well-known approach using
pairwise objects as training samples, the new algorithm has a reduced
complexity and training time. A second novel model, the unimodal model, is also
introduced and a parametric version is mapped into neural networks. Several
case studies are presented to assert the validity of the proposed models.


title: Semantics and Complexity of SPARQL

abstract:
  SPARQL is the W3C candidate recommendation query language for RDF. In this
paper we address systematically the formal study of SPARQL, concentrating in
its graph pattern facility. We consider for this study a fragment without
literals and a simple version of filters which encompasses all the main issues
yet is simple to formalize. We provide a compositional semantics, prove there
are normal forms, prove complexity bounds, among others that the evaluation of
SPARQL patterns is PSPACE-complete, compare our semantics to an alternative
operational semantics, give simple and natural conditions when both semantics
coincide and discuss optimizations procedures.


title: Combinational Logic Circuit Design with the Buchberger Algorithm

abstract:
  We detail a procedure for the computation of the polynomial form of an
electronic combinational circuit from the design equations in a truth table.
The method uses the Buchberger algorithm rather than current traditional
methods based on search algorithms. We restrict the analysis to a single
output, but the procedure can be generalized to multiple outputs. The procedure
is illustrated with the design of a simple arithmetic and logic unit with two
3-bit operands and two control bits.


title: Power-aware scheduling for makespan and flow

abstract:
  We consider offline scheduling algorithms that incorporate speed scaling to
address the bicriteria problem of minimizing energy consumption and a
scheduling metric. For makespan, we give linear-time algorithms to compute all
non-dominated solutions for the general uniprocessor problem and for the
multiprocessor problem when every job requires the same amount of work. We also
show that the multiprocessor problem becomes NP-hard when jobs can require
different amounts of work.
  For total flow, we show that the optimal flow corresponding to a particular
energy budget cannot be exactly computed on a machine supporting arithmetic and
the extraction of roots. This hardness result holds even when scheduling
equal-work jobs on a uniprocessor. We do, however, extend previous work by
Pruhs et al. to give an arbitrarily-good approximation for scheduling
equal-work jobs on a multiprocessor.


title: Analyzing Large Collections of Electronic Text Using OLAP

abstract:
  Computer-assisted reading and analysis of text has various applications in
the humanities and social sciences. The increasing size of many electronic text
archives has the advantage of a more complete analysis but the disadvantage of
taking longer to obtain results. On-Line Analytical Processing is a method used
to store and quickly analyze multidimensional data. By storing text analysis
information in an OLAP system, a user can obtain solutions to inquiries in a
matter of seconds as opposed to minutes, hours, or even days. This analysis is
user-driven allowing various users the freedom to pursue their own direction of
research.


title: Logic Column 15: Coalgebras and Their Logics

abstract:
  This article describes recent work on the topic of specifying properties of
transition systems. By giving a suitably abstract description of transition
systems as coalgebras, it is possible to derive logics for capturing properties
of these transition systems in an elegant way.


title: An Outer Bound for the Multi-Terminal Rate-Distortion Region

abstract:
  The multi-terminal rate-distortion problem has been studied extensively.
Notably, among these, Tung and Housewright have provided the best known inner
and outer bounds for the rate region under certain distortion constraints. In
this paper, we first propose an outer bound for the rate region, and show that
it is tighter than the outer bound of Tung and Housewright. Our outer bound
involves some $n$-letter Markov chain constraints, which cause computational
difficulties. We utilize a necessary condition for the Markov chain constraints
to obtain another outer bound, which is represented in terms of some
single-letter mutual information expressions evaluated over probability
distributions that satisfy some single-letter conditions.


title:
Error Exponents of Low-Density Parity-Check Codes on the Binary Erasure
  Channel

abstract:
  We introduce a thermodynamic (large deviation) formalism for computing error
exponents in error-correcting codes. Within this framework, we apply the
heuristic cavity method from statistical mechanics to derive the average and
typical error exponents of low-density parity-check (LDPC) codes on the binary
erasure channel (BEC) under maximum-likelihood decoding.


title:
Notes on Geometric Measure Theory Applications to Image Processing;
  De-noising, Segmentation, Pattern, Texture, Lines, Gestalt and Occlusion

abstract:
  Regularization functionals that lower level set boundary length when used
with L^1 fidelity functionals on signal de-noising on images create artifacts.
These are (i) rounding of corners, (ii) shrinking of radii, (iii) shrinking of
cusps, and (iv) non-smoothing of staircasing. Regularity functionals based upon
total curvature of level set boundaries do not create artifacts (i) and (ii).
An adjusted fidelity term based on the flat norm on the current (a
distributional graph) representing the density of curvature of level sets
boundaries can minimize (iii) by weighting the position of a cusp. A regularity
term to eliminate staircasing can be based upon the mass of the current
representing the graph of an image function or its second derivatives.
Densities on the Grassmann bundle of the Grassmann bundle of the ambient space
of the graph can be used to identify patterns, textures, occlusion and lines.


title: Stable partitions in coalitional games

abstract:
  We propose a notion of a stable partition in a coalitional game that is
parametrized by the concept of a defection function. This function assigns to
each partition of the grand coalition a set of different coalition arrangements
for a group of defecting players. The alternatives are compared using their
social welfare. We characterize the stability of a partition for a number of
most natural defection functions and investigate whether and how so defined
stable partitions can be reached from any initial partition by means of simple
transformations. The approach is illustrated by analyzing an example in which a
set of stores seeks an optimal transportation arrangement.


title: Efficient Route Tracing from a Single Source

abstract:
  Traceroute is a networking tool that allows one to discover the path that
packets take from a source machine, through the network, to a destination
machine. It is widely used as an engineering tool, and also as a scientific
tool, such as for discovery of the network topology at the IP level. In prior
work, authors on this technical report have shown how to improve the efficiency
of route tracing from multiple cooperating monitors. However, it is not unusual
for a route tracing monitor to operate in isolation. Somewhat different
strategies are required for this case, and this report is the first systematic
study of those requirements. Standard traceroute is inefficient when used
repeatedly towards multiple destinations, as it repeatedly probes the same
interfaces close to the source. Others have recognized this inefficiency and
have proposed tracing backwards from the destinations and stopping probing upon
encounter with a previously-seen interface. One of this technical report's
contributions is to quantify for the first time the efficiency of this
approach. Another contribution is to describe the effect of non-responding
destinations on this efficiency. Since a large portion of destination machines
do not reply to probe packets, backwards probing from the destination is often
infeasible. We propose an algorithm to tackle non-responding destinations, and
we find that our algorithm can strongly decrease probing redundancy at the cost
of a small reduction in node and link discovery.


title: DSR with Non-Optimal Route Suppression for MANETs

abstract:
  This paper revisits the issue of route discovery in dynamic source routing
(DSR) for mobile ad hoc networks (MANETs), and puts forward a proposal of a
lightweight non-optimal route suppression technique based on the observation of
a rarely noted but commonly occurring phenomenon in route discovery. The
technique exploits the observed phenomenon to extract query state information
that permits intermediate nodes to identify and suppress the initiation of
route replies with non-optimal routes, even if the route query is received for
the first time. A detailed evaluation of DSR with non-optimal route suppression
is found to yield significant improvements in both protocol efficiency and
performance.


title:
On the Role of Estimate-and-Forward with Time-Sharing in Cooperative
  Communications

abstract:
  In this work we focus on the general relay channel. We investigate the
application of estimate-and-forward (EAF) to different scenarios. Specifically,
we consider assignments of the auxiliary random variables that always satisfy
the feasibility constraints. We first consider the multiple relay channel and
obtain an achievable rate without decoding at the relays. We demonstrate the
benefits of this result via an explicit discrete memoryless multiple relay
scenario where multi-relay EAF is superior to multi-relay decode-and-forward
(DAF). We then consider the Gaussian relay channel with coded modulation, where
we show that a three-level quantization outperforms the Gaussian quantization
commonly used to evaluate the achievable rates in this scenario. Finally we
consider the cooperative general broadcast scenario with a multi-step
conference. We apply estimate-and-forward to obtain a general multi-step
achievable rate region. We then give an explicit assignment of the auxiliary
random variables, and use this result to obtain an explicit expression for the
single common message broadcast scenario with a two-step conference.


title: Attaque algebrique de NTRU a l'aide des vecteurs de Witt

abstract:
  One improves an algebraic attack of NTRU due to Silverman, Smart and
Vercauteren; the latter considered the first 2 bits of a Witt vector attached
to the research of the secret key; here the first 4 bits are considered, which
provides additional equations of degrees 4 and 8.


title:
Capacity Results for Block-Stationary Gaussian Fading Channels with a
  Peak Power Constraint

abstract:
  We consider a peak-power-limited single-antenna block-stationary Gaussian
fading channel where neither the transmitter nor the receiver knows the channel
state information, but both know the channel statistics. This model subsumes
most previously studied Gaussian fading models. We first compute the asymptotic
channel capacity in the high SNR regime and show that the behavior of channel
capacity depends critically on the channel model. For the special case where
the fading process is symbol-by-symbol stationary, we also reveal a fundamental
interplay between the codeword length, communication rate, and decoding error
probability. Specifically, we show that the codeword length must scale with SNR
in order to guarantee that the communication rate can grow logarithmically with
SNR with bounded decoding error probability, and we find a necessary condition
for the growth rate of the codeword length. We also derive an expression for
the capacity per unit energy. Furthermore, we show that the capacity per unit
energy is achievable using temporal ON-OFF signaling with optimally allocated
ON symbols, where the optimal ON-symbol allocation scheme may depend on the
peak power constraint.


title: The meaning of manufacturing know-how

abstract:
  This paper investigates the phenomenon of manufacturing know-how. First, the
abstract notion of knowledge is discussed, and a terminological basis is
introduced to treat know-how as a kind of knowledge. Next, a brief survey of
the recently reported works dealt with manufacturing know-how is presented, and
an explicit definition of know-how is formulated. Finally, the problem of
utilizing know-how with knowledge-based systems is analyzed, and some ideas
useful for its solving are given.


title:
Construction and Count of Boolean Functions of an Odd Number of
  Variables with Maximum Algebraic Immunity

abstract:
  Algebraic immunity has been proposed as an important property of Boolean
functions. To resist algebraic attack, a Boolean function should possess high
algebraic immunity. It is well known now that the algebraic immunity of an
$n$-variable Boolean function is upper bounded by $\left\lceil {\frac{n}{2}}
\right\rceil $. In this paper, for an odd integer $n$, we present a
construction method which can efficiently generate a Boolean function of $n$
variables with maximum algebraic immunity, and we also show that any such
function can be generated by this method. Moreover, the number of such Boolean
functions is greater than $2^{2^{n-1}}$.


title: Inapproximability of the Tutte polynomial

abstract:
  The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that
encodes many interesting properties of the graph. We study the complexity of
the following problem, for rationals x and y: take as input a graph G, and
output a value which is a good approximation to T(G;x,y). Jaeger, Vertigan and
Welsh have completely mapped the complexity of exactly computing the Tutte
polynomial. They have shown that this is #P-hard, except along the hyperbola
(x-1)(y-1)=1 and at four special points. We are interested in determining for
which points (x,y) there is a "fully polynomial randomised approximation
scheme" (FPRAS) for T(G;x,y). Under the assumption RP is not equal to NP, we
prove that there is no FPRAS at (x,y) if (x,y) is in one of the half-planes
x<-1 or y<-1 (excluding the easy-to-compute cases mentioned above). Two
exceptions to this result are the half-line x<-1, y=1 (which is still open) and
the portion of the hyperbola (x-1)(y-1)=2 corresponding to y<-1 which we show
to be equivalent in difficulty to approximately counting perfect matchings. We
give further intractability results for (x,y) in the vicinity of the origin. A
corollary of our results is that, under the assumption RP is not equal to NP,
there is no FPRAS at the point (x,y)=(0,1--lambda) when \lambda>2 is a positive
integer. Thus there is no FPRAS for counting nowhere-zero \lambda flows for
\lambda>2. This is an interesting consequence of our work since the
corresponding decision problem is in P for example for \lambda=6.


title: General Compact Labeling Schemes for Dynamic Trees

abstract:
  Let $F$ be a function on pairs of vertices. An {\em $F$- labeling scheme} is
composed of a {\em marker} algorithm for labeling the vertices of a graph with
short labels, coupled with a {\em decoder} algorithm allowing one to compute
$F(u,v)$ of any two vertices $u$ and $v$ directly from their labels. As
applications for labeling schemes concern mainly large and dynamically changing
networks, it is of interest to study {\em distributed dynamic} labeling
schemes. This paper investigates labeling schemes for dynamic trees.
  This paper presents a general method for constructing labeling schemes for
dynamic trees. Our method is based on extending an existing {\em static} tree
labeling scheme to the dynamic setting. This approach fits many natural
functions on trees, such as ancestry relation, routing (in both the adversary
and the designer port models), nearest common ancestor etc.. Our resulting
dynamic schemes incur overheads (over the static scheme) on the label size and
on the communication complexity. Informally, for any function $k(n)$ and any
static $F$-labeling scheme on trees, we present an $F$-labeling scheme on
dynamic trees incurring multiplicative overhead factors
  (over the static scheme) of $O(\log_{k(n)} n)$ on the label size and
$O(k(n)\log_{k(n)} n)$ on the amortized message complexity. In particular, by
setting $k(n)=n^{\epsilon}$ for any $0<\epsilon<1$, we obtain dynamic labeling
schemes with asymptotically optimal label sizes and sublinear amortized message
complexity for all the above mentioned functions.


title:
Int\'{e}gration de la synth\`{e}se m\'{e}moire dans l'outil de
  synth\`{e}se d'architecture GAUT Low Power

abstract:
  The systems supporting signal and image applications process large amount of
data. That involves an intensive use of the memory which becomes the bottleneck
of systems. Memory limits performances and represents a significant proportion
of total consumption. In the development high level synthesis tool called GAUT
Low Power, we are interested in the synthesis of the memory unit. In this work,
we integrate the data storage and data transfert to constraint the high level
synthesis of the datapath's execution unit.


title: High-level synthesis under I/O Timing and Memory constraints

abstract:
  The design of complex Systems-on-Chips implies to take into account
communication and memory access constraints for the integration of dedicated
hardware accelerator. In this paper, we present a methodology and a tool that
allow the High-Level Synthesis of DSP algorithm, under both I/O timing and
memory constraints. Based on formal models and a generic architecture, this
tool helps the designer to find a reasonable trade-off between both the
required I/O timing behavior and the internal memory access parallelism of the
circuit. The interest of our approach is demonstrated on the case study of a
FFT algorithm.


title: A Memory Aware High Level Synthesis Too

abstract:
  We introduce a new approach to take into account the memory architecture and
the memory mapping in High- Level Synthesis for data intensive applications. We
formalize the memory mapping as a set of constraints for the synthesis, and
defined a Memory Constraint Graph and an accessibility criterion to be used in
the scheduling step. We use a memory mapping file to include those memory
constraints in our HLS tool GAUT. It is possible, with the help of GAUT, to
explore a wide range of solutions, and to reach a good tradeoff between time,
power-consumption, and area.


title: Memory Aware High-Level Synthesis for Embedded Systems

abstract:
  We introduce a new approach to take into account the memory architecture and
the memory mapping in the High- Level Synthesis of Real-Time embedded systems.
We formalize the memory mapping as a set of constraints used in the scheduling
step. We use a memory mapping file to include those memory constraints in our
HLS tool GAUT. Our scheduling algorithm exhibits a relatively low complexity
that permits to tackle complex designs in a reasonable time. Finally, we show
how to explore, with the help of GAUT, a wide range of solutions, and to reach
a good tradeoff between time, power-consumption, and area.


title:
Synth\`{e}se Comportementale Sous Contraintes de Communication et de
  Placement M\'{e}moire pour les composants du TDSI

abstract:
  The design of complex Digital Signal Processing systems implies to minimize
architectural cost and to maximize timing performances while taking into
account communication and memory accesses constraints for the integration of
dedicated hardware accelerator. Unfortunately, the traditional Matlab/ Simulink
design flows gather not very flexible hardware blocs. In this paper, we present
a methodology and a tool that permit the High-Level Synthesis of DSP
applications, under both I/O timing and memory constraints. Based on formal
models and a generic architecture, our tool GAUT helps the designer in finding
a reasonable trade-off between the circuit's performance and its architectural
complexity. The efficiency of our approach is demonstrated on the case study of
a FFT algorithm.


title:
Utilisation de la linguistique en reconnaissance de la parole : un
  \'{e}tat de l'art

abstract:
  To transcribe speech, automatic speech recognition systems use statistical
methods, particularly hidden Markov model and N-gram models. Although these
techniques perform well and lead to efficient systems, they approach their
maximum possibilities. It seems thus necessary, in order to outperform current
results, to use additional information, especially bound to language. However,
introducing such knowledge must be realized taking into account specificities
of spoken language (hesitations for example) and being robust to possible
misrecognized words. This document presents a state of the art of these
researches, evaluating the impact of the insertion of linguistic information on
the quality of the transcription.


title:
Tight Bounds for the Min-Max Boundary Decomposition Cost of Weighted
  Graphs

abstract:
  Many load balancing problems that arise in scientific computing applications
ask to partition a graph with weights on the vertices and costs on the edges
into a given number of almost equally-weighted parts such that the maximum
boundary cost over all parts is small.
  Here, this partitioning problem is considered for bounded-degree graphs
G=(V,E) with edge costs c: E->R+ that have a p-separator theorem for some p>1,
i.e., any (arbitrarily weighted) subgraph of G can be separated into two parts
of roughly the same weight by removing a vertex set S such that the edges
incident to S in the subgraph have total cost at most proportional to (SUM_e
c^p_e)^(1/p), where the sum is over all edges e in the subgraph.
  We show for all positive integers k and weights w that the vertices of G can
be partitioned into k parts such that the weight of each part differs from the
average weight by less than MAX{w_v; v in V}, and the boundary edges of each
part have cost at most proportional to (SUM_e c_e^p/k)^(1/p) + MAX_e c_e. The
partition can be computed in time nearly proportional to the time for computing
a separator S of G.
  Our upper bound on the boundary costs is shown to be tight up to a constant
factor for infinitely many instances with a broad range of parameters. Previous
results achieved this bound only if one has c=1, w=1, and one allows parts with
weight exceeding the average by a constant fraction.


title: Mining Behavioral Groups in Large Wireless LANs

abstract:
  One vision of future wireless networks is that they will be deeply integrated
and embedded in our lives and will involve the use of personalized mobile
devices. User behavior in such networks is bound to affect the network
performance. It is imperative to study and characterize the fundamental
structure of wireless user behavior in order to model, manage, leverage and
design efficient mobile networks. It is also important to make such study as
realistic as possible, based on extensive measurements collected from existing
deployed wireless networks.
  In this study, using our systematic TRACE approach, we analyze wireless
users' behavioral patterns by extensively mining wireless network logs from two
major university campuses. We represent the data using location preference
vectors, and utilize unsupervised learning (clustering) to classify trends in
user behavior using novel similarity metrics. Matrix decomposition techniques
are used to identify (and differentiate between) major patterns. While our
findings validate intuitive repetitive behavioral trends and user grouping, it
is surprising to find the qualitative commonalities of user behaviors from the
two universities. We discover multi-modal user behavior for more than 60% of
the users, and there are hundreds of distinct groups with unique behavioral
patterns in both campuses. The sizes of the major groups follow a power-law
distribution. Our methods and findings provide an essential step towards
network management and behavior-aware network protocols and applications, to
name a few.


title: Modeling Aspect Mechanisms: A Top-Down Approach

abstract:
  A plethora of diverse aspect mechanisms exist today, all of which integrate
concerns into artifacts that exhibit crosscutting structure. What we lack and
need is a characterization of the design space that these aspect mechanisms
inhabit and a model description of their weaving processes. A good design space
representation provides a common framework for understanding and evaluating
existing mechanisms. A well-understood model of the weaving process can guide
the implementor of new aspect mechanisms. It can guide the designer when
mechanisms implementing new kinds of weaving are needed. It can also help teach
aspect-oriented programming (AOP). In this paper we present and evaluate such a
model of the design space for aspect mechanisms and their weaving processes. We
model weaving, at an abstract level, as a concern integration process. We
derive a weaving process model (WPM) top-down, differentiating a reactive from
a nonreactive process. The model provides an in-depth explanation of the key
subpro existing aspect mechanisms.


title:
A Framework for the Development of Manufacturing Simulators: Towards New
  Generation of Simulation Systems

abstract:
  In this paper, an attempt is made to systematically discuss the development
of simulation systems for manufacturing system design. General requirements on
manufacturing simulators are formulated and a framework to address the
requirements is suggested. Problems of information representation as an
activity underlying simulation are considered. This is to form the necessary
mathematical foundation for manufacturing simulations. The theoretical findings
are explored through a pilot study. A conclusion about the suitability of the
suggested approach to the development of simulation systems for manufacturing
system design is made, and implications for future research are described.


title: The KAA project: a trust policy point of view

abstract:
  In the context of ambient networks where each small device must trust its
neighborhood rather than a fixed network, we propose in this paper a
\textit{trust management framework} inspired by known social patterns and based
on the following statements: each mobile constructs itself a local level of
trust what means that it does not accept recommendation by other peers, and the
only relevant parameter, beyond some special cases discussed later, to evaluate
the level of trust is the number of common trusted mobiles. These trusted
mobiles are considered as entries in a local database called history for each
device and we use identity-based cryptography to ensure strong security:
history must be a non-tansferable object.


title: Foundations of Modern Language Resource Archives

abstract:
  A number of serious reasons will convince an increasing amount of researchers
to store their relevant material in centers which we will call "language
resource archives". They combine the duty of taking care of long-term
preservation as well as the task to give access to their material to different
user groups. Access here is meant in the sense that an active interaction with
the data will be made possible to support the integration of new data, new
versions or commentaries of all sort. Modern Language Resource Archives will
have to adhere to a number of basic principles to fulfill all requirements and
they will have to be involved in federations to create joint language resource
domains making it even more simple for the researchers to access the data. This
paper makes an attempt to formulate the essential pillars language resource
archives have to adhere to.


title:
A parent-centered radial layout algorithm for interactive graph
  visualization and animation

abstract:
  We have developed (1) a graph visualization system that allows users to
explore graphs by viewing them as a succession of spanning trees selected
interactively, (2) a radial graph layout algorithm, and (3) an animation
algorithm that generates meaningful visualizations and smooth transitions
between graphs while minimizing edge crossings during transitions and in static
layouts.
  Our system is similar to the radial layout system of Yee et al. (2001), but
differs primarily in that each node is positioned on a coordinate system
centered on its own parent rather than on a single coordinate system for all
nodes. Our system is thus easy to define recursively and lends itself to
parallelization. It also guarantees that layouts have many nice properties,
such as: it guarantees certain edges never cross during an animation.
  We compared the layouts and transitions produced by our algorithms to those
produced by Yee et al. Results from several experiments indicate that our
system produces fewer edge crossings during transitions between graph drawings,
and that the transitions more often involve changes in local scaling rather
than structure.
  These findings suggest the system has promise as an interactive graph
exploration tool in a variety of settings.


title: Repository Replication Using NNTP and SMTP

abstract:
  We present the results of a feasibility study using shared, existing,
network-accessible infrastructure for repository replication. We investigate
how dissemination of repository contents can be ``piggybacked'' on top of
existing email and Usenet traffic. Long-term persistence of the replicated
repository may be achieved thanks to current policies and procedures which
ensure that mail messages and news posts are retrievable for evidentiary and
other legal purposes for many years after the creation date. While the
preservation issues of migration and emulation are not addressed with this
approach, it does provide a simple method of refreshing content with unknown
partners.


title: The Consequences of Eliminating NP Solutions

abstract:
  Given a function based on the computation of an NP machine, can one in
general eliminate some solutions? That is, can one in general decrease the
ambiguity? This simple question remains, even after extensive study by many
researchers over many years, mostly unanswered. However, complexity-theoretic
consequences and enabling conditions are known. In this tutorial-style article
we look at some of those, focusing on the most natural framings: reducing the
number of solutions of NP functions, refining the solutions of NP functions,
and subtracting from or otherwise shrinking #P functions. We will see how small
advice strings are important here, but we also will see how increasing advice
size to achieve robustness is central to the proof of a key ambiguity-reduction
result for NP functions.


title: A Decision-Making Support System Based on Know-How

abstract:
  The research results described are concerned with: - developing a domain
modeling method and tools to provide the design and implementation of
decision-making support systems for computer integrated manufacturing; -
building a decision-making support system based on know-how and its software
environment. The research is funded by NEDO, Japan.


title: Vectorial Resilient $PC(l)$ of Order $k$ Boolean Functions from AG-Codes

abstract:
  Propagation criterion of degree $l$ and order $k$ ($PC(l)$ of order $k$) and
resiliency of vectorial Boolean functions are important for cryptographic
purpose (see [1, 2, 3,6, 7,8,10,11,16]. Kurosawa, Stoh [8] and Carlet [1] gave
a construction of Boolean functions satisfying $PC(l)$ of order $k$ from binary
linear or nonlinear codes in. In this paper, algebraic-geometric codes over
$GF(2^m)$ are used to modify Carlet and Kurosawa-Satoh's construction for
giving vectorial resilient Boolean functions satisfying $PC(l)$ of order $k$.
The new construction is compared with previously known results.


title:
On the communication between cells of a cellular automaton on the penta-
  and heptagrids of the hyperbolic plane

abstract:
  This contribution belongs to a combinatorial approach to hyperbolic geometry
and it is aimed at possible applications to computer simulations.
  It is based on the splitting method which was introduced by the author and
which is reminded in the second section of the paper. Then we sketchily remind
the application to the classical case of the pentagrid, i.e. the tiling of the
hyperbolic plane which is generated by reflections of the regular rectangular
pentagon in its sides and, recursively, of its images in their sides. From this
application, we derived a system of coordinates to locate the tiles, allowing
an implementation of cellular automata.
  At the software level, cells exchange messages thanks to a new representation
which improves the speed of contacts between cells. In the new setting,
communications are exchanged along actual geodesics and the contribution of the
cellular automaton is also linear in the coordinates of the cells.


title: Good Illumination of Minimum Range

abstract:
  A point p is 1-well illuminated by a set F of n point lights if p lies in the
interior of the convex hull of F. This concept corresponds to triangle-guarding
or well-covering. In this paper we consider the illumination range of the light
sources as a parameter to be optimized. First, we solve the problem of
minimizing the light sources' illumination range to 1-well illuminate a given
point p. We also compute a minimal set of light sources that 1-well illuminates
p with minimum illumination range. Second, we solve the problem of minimizing
the light sources' illumination range to 1-well illuminate all the points of a
line segment with an O(n^2) algorithm. Finally, we give an O(n^2 log n)
algorithm for preprocessing the data so that one can obtain the illumination
range needed to 1-well illuminate a point of a line segment in O(log n) time.
These results can be applied to solve problems of 1-well illuminating a
trajectory by approaching it to a polygonal path.


title:
On the Capacity of Multiple Access Channels with State Information and
  Feedback

abstract:
  In this paper, the multiple access channel (MAC) with channel state is
analyzed in a scenario where a) the channel state is known non-causally to the
transmitters and b) there is perfect causal feedback from the receiver to the
transmitters. An achievable region and an outer bound are found for a discrete
memoryless MAC that extend existing results, bringing together ideas from the
two separate domains of MAC with state and MAC with feedback. Although this
achievable region does not match the outer bound in general, special cases
where they meet are identified.
  In the case of a Gaussian MAC, a specialized achievable region is found by
using a combination of dirty paper coding and a generalization of the
Schalkwijk-Kailath, Ozarow and Merhav-Weissman schemes, and this region is
found to be capacity achieving. Specifically, it is shown that additive
Gaussian interference that is known non-causally to the transmitter causes no
loss in capacity for the Gaussian MAC with feedback.


title: The Size of Optimal Sequence Sets for Synchronous CDMA Systems

abstract:
  The sum capacity on a symbol-synchronous CDMA system having processing gain
$N$ and supporting $K$ power constrained users is achieved by employing at most
$2N-1$ sequences. Analogously, the minimum received power (energy-per-chip) on
the symbol-synchronous CDMA system supporting $K$ users that demand specified
data rates is attained by employing at most $2N-1$ sequences. If there are $L$
oversized users in the system, at most $2N-L-1$ sequences are needed. $2N-1$ is
the minimum number of sequences needed to guarantee optimal allocation for
single dimensional signaling. $N$ orthogonal sequences are sufficient if a few
users (at most $N-1$) are allowed to signal in multiple dimensions. If there
are no oversized users, these split users need to signal only in two dimensions
each. The above results are shown by proving a converse to a well-known result
of Weyl on the interlacing eigenvalues of the sum of two Hermitian matrices,
one of which is of rank 1. The converse is analogous to Mirsky's converse to
the interlacing eigenvalues theorem for bordering matrices.


title:
Performance Analysis of Iterative Channel Estimation and Multiuser
  Detection in Multipath DS-CDMA Channels

abstract:
  This paper examines the performance of decision feedback based iterative
channel estimation and multiuser detection in channel coded aperiodic DS-CDMA
systems operating over multipath fading channels. First, explicit expressions
describing the performance of channel estimation and parallel interference
cancellation based multiuser detection are developed. These results are then
combined to characterize the evolution of the performance of a system that
iterates among channel estimation, multiuser detection and channel decoding.
Sufficient conditions for convergence of this system to a unique fixed point
are developed.


title:
From semiotics of hypermedia to physics of semiosis: A view from system
  theory

abstract:
  Given that theoretical analysis and empirical validation is fundamental to
any model, whether conceptual or formal, it is surprising that these two tools
of scientific discovery are so often ignored in the contemporary studies of
communication. In this paper, we pursued the ideas of a) correcting and
expanding the modeling approaches of linguistics, which are otherwise
inapplicable (more precisely, which should not but are widely applied), to the
general case of hypermedia-based communication, and b) developing techniques
for empirical validation of semiotic models, which are nowadays routinely used
to explore (in fact, to conjecture about) internal mechanisms of complex
systems, yet on a purely speculative basis. This study thus offers two
experimentally tested substantive contributions: the formal representation of
communication as the mutually-orienting behavior of coupled autonomous systems,
and the mathematical interpretation of the semiosis of communication, which
together offer a concrete and parsimonious understanding of diverse
communication phenomena.


title: Emerging Markets for RFID Traces

abstract:
  RFID tags are held to become ubiquitous in logistics in the near future, and
item-level tagging will pave the way for Ubiquitous Computing, for example in
application fields like smart homes. Our paper addresses the value and the
production cost of information that can be gathered by observing these tags
over time and different locations. We argue that RFID technology will induce a
thriving market for such information, resulting in easy data access for
analysts to infer business intelligence and individual profiles of unusually
high detail. Understanding these information markets is important for many
reasons: They represent new business opportunities, and market players need to
be aware of their roles in these markets. Policy makers need to confirm that
the market structure will not negatively affect overall welfare. Finally,
though we are not addressing the complex issue of privacy, we are convinced
that market forces will have a significant impact on the effectiveness of
deployed security enhancements to RFID technology. In this paper we take a few
first steps into a relatively new field of economic research and conclude with
a list of research problems that promise deeper insights into the matter.


title: A synchronous pi-calculus

abstract:
  The SL synchronous programming model is a relaxation of the Esterel
synchronous model where the reaction to the absence of a signal within an
instant can only happen at the next instant. In previous work, we have
revisited the SL synchronous programming model. In particular, we have
discussed an alternative design of the model including thread spawning and
recursive definitions, introduced a CPS translation to a tail recursive form,
and proposed a notion of bisimulation equivalence. In the present work, we
extend the tail recursive model with first-order data types obtaining a
non-deterministic synchronous model whose complexity is comparable to the one
of the pi-calculus. We show that our approach to bisimulation equivalence can
cope with this extension and in particular that labelled bisimulation can be
characterised as a contextual bisimulation.


title: Imagination as Holographic Processor for Text Animation

abstract:
  Imagination is the critical point in developing of realistic artificial
intelligence (AI) systems. One way to approach imagination would be simulation
of its properties and operations. We developed two models: AI-Brain Network
Hierarchy of Languages and Semantical Holographic Calculus as well as
simulation system ScriptWriter that emulate the process of imagination through
an automatic animation of English texts. The purpose of this paper is to
demonstrate the model and to present ScriptWriter system
http://nvo.sdsc.edu/NVO/JCSG/get_SRB_mime_file2.cgi//home/tamara.sdsc/test/demo.zip?F=/home/tamara.sdsc/test/demo.zip&M=application/x-gtar
for simulation of the imagination.


title:
A simulation engine to support production scheduling using
  genetics-based machine learning

abstract:
  The ever higher complexity of manufacturing systems, continually shortening
life cycles of products and their increasing variety, as well as the unstable
market situation of the recent years require introducing grater flexibility and
responsiveness to manufacturing processes. From this perspective, one of the
critical manufacturing tasks, which traditionally attract significant attention
in both academia and the industry, but which have no satisfactory universal
solution, is production scheduling. This paper proposes an approach based on
genetics-based machine learning (GBML) to treat the problem of flow shop
scheduling. By the approach, a set of scheduling rules is represented as an
individual of genetic algorithms, and the fitness of the individual is
estimated based on the makespan of the schedule generated by using the
rule-set. A concept of the interactive software environment consisting of a
simulator and a GBML simulation engine is introduced to support human
decision-making during scheduling. A pilot study is underway to evaluate the
performance of the GBML technique in comparison with other methods (such as
Johnson's algorithm and simulated annealing) while completing test examples.


title: Limited Feedback Beamforming Over Temporally-Correlated Channels

abstract:
  Feedback of quantized channel state information (CSI), called limited
feedback, enables transmit beamforming in multiple-input-multiple-output (MIMO)
wireless systems with a small amount of overhead. Due to its efficiency,
beamforming with limited feedback has been adopted in several wireless
communication standards. Prior work on limited feedback commonly adopts the
block fading channel model where temporal correlation in wireless channels is
neglected. This paper considers temporally-correlated channels and designs
single-user transmit beamforming with limited feedback. Analytical results
concerning CSI feedback are derived by modeling quantized CSI as a first-order
finite-state Markov chain. These results include the source bit rate generated
by time-varying quantized CSI, the required bit rate for a CSI feedback
channel, and the effect of feedback delay. In particular, based on the theory
of Markov chain convergence rate, feedback delay is proved to reduce the
throughput gain due to CSI feedback at least exponentially. Furthermore, an
algorithm is proposed for CSI feedback compression in time. Combining the
results in this work leads to a new method for designing limited feedback
beamforming as demonstrated by a design example.


title:
Parallel Evaluation of Mathematica Programs in Remote Computers
  Available in Network

abstract:
  Mathematica is a powerful application package for doing mathematics and is
used almost in all branches of science. It has widespread applications ranging
from quantum computation, statistical analysis, number theory, zoology,
astronomy, and many more. Mathematica gives a rich set of programming
extensions to its end-user language, and it permits us to write programs in
procedural, functional, or logic (rule-based) style, or a mixture of all three.
For tasks requiring interfaces to the external environment, mathematica
provides mathlink, which allows us to communicate mathematica programs with
external programs written in C, C++, F77, F90, F95, Java, or other languages.
It has also extensive capabilities for editing graphics, equations, text, etc.
  In this article, we explore the basic mechanisms of parallelization of a
mathematica program by sharing different parts of the program into all other
computers available in the network. Doing the parallelization, we can perform
large computational operations within a very short period of time, and
therefore, the efficiency of the numerical works can be achieved. Parallel
computation supports any version of mathematica and it also works as well even
if different versions of mathematica are installed in different computers. The
whole operation can run under any supported operating system like Unix,
Windows, Macintosh, etc. Here we focus our study only for the Unix based
operating system, but this method works as well for all other cases.


title: Consecutive Support: Better Be Close!

abstract:
  We propose a new measure of support (the number of occur- rences of a
pattern), in which instances are more important if they occur with a certain
frequency and close after each other in the stream of trans- actions. We will
explain this new consecutive support and discuss how patterns can be found
faster by pruning the search space, for instance using so-called parent support
recalculation. Both consecutiveness and the notion of hypercliques are
incorporated into the Eclat algorithm. Synthetic examples show how interesting
phenomena can now be discov- ered in the datasets. The new measure can be
applied in many areas, ranging from bio-informatics to trade, supermarkets, and
even law en- forcement. E.g., in bio-informatics it is important to find
patterns con- tained in many individuals, where patterns close together in one
chro- mosome are more significant.


title: A Chaotic Cipher Mmohocc and Its Security Analysis

abstract:
  In this paper we introduce a new chaotic stream cipher Mmohocc which utilizes
the fundamental chaos characteristics. The designs of the major components of
the cipher are given. Its cryptographic properties of period, auto- and
cross-correlations, and the mixture of Markov processes and spatiotemporal
effects are investigated. The cipher is resistant to the related-key-IV
attacks, Time/Memory/Data tradeoff attacks, algebraic attacks, and chosen-text
attacks. The keystreams successfully passed two batteries of statistical tests
and the encryption speed is comparable with RC4.


title:
Generating parity check equations for bounded-distance iterative erasure
  decoding

abstract:
  A generic $(r,m)$-erasure correcting set is a collection of vectors in
$\bF_2^r$ which can be used to generate, for each binary linear code of
codimension $r$, a collection of parity check equations that enables iterative
decoding of all correctable erasure patterns of size at most $m$.
  That is to say, the only stopping sets of size at most $m$ for the generated
parity check equations are the erasure patterns for which there is more than
one manner to fill in theerasures to obtain a codeword.
  We give an explicit construction of generic $(r,m)$-erasure correcting sets
of cardinality $\sum_{i=0}^{m-1} {r-1\choose i}$. Using a random-coding-like
argument, we show that for fixed $m$, the minimum size of a generic
$(r,m)$-erasure correcting set is linear in $r$.
  Keywords: iterative decoding, binary erasure channel, stopping set


title: Building a logical model in the machining domain for CAPP expert systems

abstract:
  Recently, extensive efforts have been made on the application of expert
system technique to solving the process planning task in the machining domain.
This paper introduces a new formal method to design CAPP expert systems. The
formal method is applied to provide a contour of the CAPP expert system
building technology. Theoretical aspects of the formalism are described and
illustrated by an example of know-how analysis. Flexible facilities to utilize
multiple knowledge types and multiple planning strategies within one system are
provided by the technology.


title:
Affine Transformations of Loop Nests for Parallel Execution and
  Distribution of Data over Processors

abstract:
  The paper is devoted to the problem of mapping affine loop nests onto
distributed memory parallel computers. A method to find affine transformations
of loop nests for parallel execution and distribution of data over processors
is presented. The method tends to minimize the number of communications between
processors and to improve locality of data within one processor. A problem of
determination of data exchange sequence is investigated. Conditions to
determine the ability to arrange broadcast is presented.


title: Belief Calculus

abstract:
  In Dempster-Shafer belief theory, general beliefs are expressed as belief
mass distribution functions over frames of discernment. In Subjective Logic
beliefs are expressed as belief mass distribution functions over binary frames
of discernment. Belief representations in Subjective Logic, which are called
opinions, also contain a base rate parameter which express the a priori belief
in the absence of evidence. Philosophically, beliefs are quantitative
representations of evidence as perceived by humans or by other intelligent
agents. The basic operators of classical probability calculus, such as addition
and multiplication, can be applied to opinions, thereby making belief calculus
practical. Through the equivalence between opinions and Beta probability
density functions, this also provides a calculus for Beta probability density
functions. This article explains the basic elements of belief calculus.