title: A Neural-Network Technique to Learn Concepts from Electroencephalograms

abstract:
  A new technique is presented developed to learn multi-class concepts from
clinical electroencephalograms. A desired concept is represented as a neuronal
computational model consisting of the input, hidden, and output neurons. In
this model the hidden neurons learn independently to classify the
electroencephalogram segments presented by spectral and statistical features.
This technique has been applied to the electroencephalogram data recorded from
65 sleeping healthy newborns in order to learn a brain maturation concept of
newborns aged between 35 and 51 weeks. The 39399 and 19670 segments from these
data have been used for learning and testing the concept, respectively. As a
result, the concept has correctly classified 80.1% of the testing segments or
87.7% of the 65 records.


title:
The Combined Technique for Detection of Artifacts in Clinical
  Electroencephalograms of Sleeping Newborns

abstract:
  In this paper we describe a new method combining the polynomial neural
network and decision tree techniques in order to derive comprehensible
classification rules from clinical electroencephalograms (EEGs) recorded from
sleeping newborns. These EEGs are heavily corrupted by cardiac, eye movement,
muscle and noise artifacts and as a consequence some EEG features are
irrelevant to classification problems. Combining the polynomial network and
decision tree techniques, we discover comprehensible classification rules
whilst also attempting to keep their classification error down. This technique
is shown to outperform a number of commonly used machine learning technique
applied to automatically recognize artifacts in the sleep EEGs.


title: Proceedings of the Pacific Knowledge Acquisition Workshop 2004

abstract:
  Artificial intelligence (AI) research has evolved over the last few decades
and knowledge acquisition research is at the core of AI research. PKAW-04 is
one of three international knowledge acquisition workshops held in the
Pacific-Rim, Canada and Europe over the last two decades. PKAW-04 has a strong
emphasis on incremental knowledge acquisition, machine learning, neural nets
and active mining.
  The proceedings contain 19 papers that were selected by the program committee
among 24 submitted papers. All papers were peer reviewed by at least two
reviewers. The papers in these proceedings cover the methods and tools as well
as the applications related to develop expert systems or knowledge based
systems.


title:
Knowledge Representation Issues in Semantic Graphs for Relationship
  Detection

abstract:
  An important task for Homeland Security is the prediction of threat
vulnerabilities, such as through the detection of relationships between
seemingly disjoint entities. A structure used for this task is a "semantic
graph", also known as a "relational data graph" or an "attributed relational
graph". These graphs encode relationships as "typed" links between a pair of
"typed" nodes. Indeed, semantic graphs are very similar to semantic networks
used in AI. The node and link types are related through an ontology graph (also
known as a schema). Furthermore, each node has a set of attributes associated
with it (e.g., "age" may be an attribute of a node of type "person").
Unfortunately, the selection of types and attributes for both nodes and links
depends on human expertise and is somewhat subjective and even arbitrary. This
subjectiveness introduces biases into any algorithm that operates on semantic
graphs. Here, we raise some knowledge representation issues for semantic graphs
and provide some possible solutions using recently developed ideas in the field
of complex networks. In particular, we use the concept of transitivity to
evaluate the relevance of individual links in the semantic graph for detecting
relationships. We also propose new statistical measures for semantic graphs and
illustrate these semantic measures on graphs constructed from movies and
terrorism data.


title:
Rendezvous Regions: A Scalable Architecture for Resource Discovery and
  Service Location in Large-Scale Mobile Networks

abstract:
  In large-scale wireless networks such as mobile ad hoc and sensor networks,
efficient and robust service discovery and data-access mechanisms are both
essential and challenging. Rendezvous-based mechanisms provide a valuable
solution for provisioning a wide range of services. In this paper, we describe
Rendezvous Regions (RRs) - a novel scalable rendezvous-based architecture for
wireless networks. RR is a general architecture proposed for service location
and bootstrapping in ad hoc networks, in addition to data-centric storage,
configuration, and task assignment in sensor networks. In RR the network
topology is divided into geographical regions, where each region is responsible
for a set of keys representing the services or data of interest. Each key is
mapped to a region based on a hash-table-like mapping scheme. A few elected
nodes inside each region are responsible for maintaining the mapped
information. The service or data provider stores the information in the
corresponding region and the seekers retrieve it from there. We run extensive
detailed simulations, and high-level simulations and analysis, to investigate
the design space, and study the architecture in various environments including
node mobility and failures. We evaluate it against other approaches to identify
its merits and limitations. The results show high success rate and low overhead
even with dynamics. RR scales to large number of nodes and is highly robust and
efficient to node failures. It is also robust to node mobility and location
inaccuracy with a significant advantage over point-based rendezvous mechanisms.


title: Metalinguistic Information Extraction for Terminology

abstract:
  This paper describes and evaluates the Metalinguistic Operation Processor
(MOP) system for automatic compilation of metalinguistic information from
technical and scientific documents. This system is designed to extract
non-standard terminological resources that we have called Metalinguistic
Information Databases (or MIDs), in order to help update changing glossaries,
knowledge bases and ontologies, as well as to reflect the metastable dynamics
of special-domain knowledge.


title: Dichotomy for Voting Systems

abstract:
  Scoring protocols are a broad class of voting systems. Each is defined by a
vector $(\alpha_1,\alpha_2,...,\alpha_m)$, $\alpha_1 \geq \alpha_2 \geq >...
\geq \alpha_m$, of integers such that each voter contributes $\alpha_1$ points
to his/her first choice, $\alpha_2$ points to his/her second choice, and so on,
and any candidate receiving the most points is a winner.
  What is it about scoring-protocol election systems that makes some have the
desirable property of being NP-complete to manipulate, while others can be
manipulated in polynomial time? We find the complete, dichotomizing answer:
Diversity of dislike. Every scoring-protocol election system having two or more
point values assigned to candidates other than the favorite--i.e., having
$||\{\alpha_i \condition 2 \leq i \leq m\}||\geq 2$--is NP-complete to
manipulate. Every other scoring-protocol election system can be manipulated in
polynomial time. In effect, we show that--other than trivial systems (where all
candidates alway tie), plurality voting, and plurality voting's transparently
disguised translations--\emph{every} scoring-protocol election system is
NP-complete to manipulate.


title: An Improved Remote User Authentication Scheme Using Smart Cards

abstract:
  In 2000, Hwang and Li proposed a new remote user authentication scheme using
smart cards. In the same year, Chan and Cheng pointed out that Hwang and
Li’s scheme is not secure against the masquerade attack. Further, in
2003, Shen, Lin and Hwang pointed out a different type of attack on Hwang and
Li’s scheme and presented a modified scheme to remove its security
pitfalls. This paper presents an improved scheme which is secure against
Chan-Cheng and all the extended attacks.


title: The Modified Scheme is still vulnerable to the parallel Session Attack

abstract:
  In 2002, Chien–Jan–Tseng introduced an efficient remote user
authentication scheme using smart cards. Further, in 2004, W. C. Ku and S. M.
Chen proposed an efficient remote user authentication scheme using smart cards
to solve the security problems of Chien et al.’s scheme. Recently, Hsu
and Yoon et al. pointed out the security weakness of the Ku and Chen’s
scheme Furthermore, Yoon et al. modified the password change phase of Ku and
Chen’s scheme and they also proposed a new efficient remote user
authentication scheme using smart cards. This paper analyzes that the modified
scheme of Yoon et al. still vulnerable to parallel session attack.


title: Adaptive Online Prediction by Following the Perturbed Leader

abstract:
  When applying aggregating strategies to Prediction with Expert Advice, the
learning rate must be adaptively tuned. The natural choice of
sqrt(complexity/current loss) renders the analysis of Weighted Majority
derivatives quite complicated. In particular, for arbitrary weights there have
been no results proven so far. The analysis of the alternative "Follow the
Perturbed Leader" (FPL) algorithm from Kalai & Vempala (2003) (based on
Hannan's algorithm) is easier. We derive loss bounds for adaptive learning rate
and both finite expert classes with uniform weights and countable expert
classes with arbitrary weights. For the former setup, our loss bounds match the
best known results so far, while for the latter our results are new.


title:
Prediction of Large Alphabet Processes and Its Application to Adaptive
  Source Coding

abstract:
  The problem of predicting a sequence $x_1,x_2,...$ generated by a discrete
source with unknown statistics is considered. Each letter $x_{t+1}$ is
predicted using information on the word $x_1x_2... x_t$ only. In fact, this
problem is a classical problem which has received much attention. Its history
can be traced back to Laplace. We address the problem where each $x_i$ belongs
to some large (or even infinite) alphabet. A method is presented for which the
precision is greater than for known algorithms, where precision is estimated by
the Kullback-Leibler divergence. The results can readily be translated to
results about adaptive coding.


title:
Performance of Gaussian Signalling in Non Coherent Rayleigh Fading
  Channels

abstract:
  The mutual information of a discrete time memoryless Rayleigh fading channel
is considered, where neither the transmitter nor the receiver has the knowledge
of the channel state information except the fading statistics. We present the
mutual information of this channel in closed form when the input distribution
is complex Gaussian, and derive a lower bound in terms of the capacity of the
corresponding non fading channel and the capacity when the perfect channel
state information is known at the receiver.


title: A Decomposition Approach to Multi-Vehicle Cooperative Control

abstract:
  We present methods that generate cooperative strategies for multi-vehicle
control problems using a decomposition approach. By introducing a set of tasks
to be completed by the team of vehicles and a task execution method for each
vehicle, we decomposed the problem into a combinatorial component and a
continuous component. The continuous component of the problem is captured by
task execution, and the combinatorial component is captured by task assignment.
In this paper, we present a solver for task assignment that generates
near-optimal assignments quickly and can be used in real-time applications. To
motivate our methods, we apply them to an adversarial game between two teams of
vehicles. One team is governed by simple rules and the other by our algorithms.
In our study of this game we found phase transitions, showing that the task
assignment problem is most difficult to solve when the capabilities of the
adversaries are comparable. Finally, we implement our algorithms in a
multi-level architecture with a variable replanning rate at each level to
provide feedback on a dynamically changing and uncertain environment.


title: Coloring Artemis graphs

abstract:
  We consider the class A of graphs that contain no odd hole, no antihole, and
no ``prism'' (a graph consisting of two disjoint triangles with three disjoint
paths between them). We show that the coloring algorithm found by the second
and fourth author can be implemented in time O(n^2m) for any graph in A with n
vertices and m edges, thereby improving on the complexity proposed in the
original paper.


title: On the Unicity Distance of Stego Key

abstract:
  Steganography is about how to send secret message covertly. And the purpose
of steganalysis is to not only detect the existence of the hidden message but
also extract it. So far there have been many reliable detecting methods on
various steganographic algorithms, while there are few approaches that can
extract the hidden information. In this paper, the difficulty of extracting
hidden information, which is essentially a kind of privacy, is analyzed with
information-theoretic method in the terms of unicity distance of steganographic
key (abbreviated stego key). A lower bound for the unicity distance is
obtained, which shows the relations between key rate, message rate, hiding
capacity and difficulty of extraction. Furthermore the extracting attack to
steganography is viewed as a special kind of cryptanalysis, and an effective
method on recovering the stego key of popular LSB replacing steganography in
spatial images is presented by combining the detecting technique of
steganalysis and correlation attack of cryptanalysis together. The analysis for
this method and experimental results on steganographic software ``Hide and Seek
4.1" are both accordant with the information-theoretic conclusion.


title: The Convergence of Digital-Libraries and the Peer-Review Process

abstract:
  Pre-print repositories have seen a significant increase in use over the past
fifteen years across multiple research domains. Researchers are beginning to
develop applications capable of using these repositories to assist the
scientific community above and beyond the pure dissemination of information.
The contribution set forth by this paper emphasizes a deconstructed publication
model in which the peer-review process is mediated by an OAI-PMH peer-review
service. This peer-review service uses a social-network algorithm to determine
potential reviewers for a submitted manuscript and for weighting the relative
influence of each participating reviewer's evaluations. This paper also
suggests a set of peer-review specific metadata tags that can accompany a
pre-print's existing metadata record. The combinations of these contributions
provide a unique repository-centric peer-review model that fits within the
widely deployed OAI-PMH framework.


title: Capacity per Unit Energy of Fading Channels with a Peak Constraint

abstract:
  A discrete-time single-user scalar channel with temporally correlated
Rayleigh fading is analyzed. There is no side information at the transmitter or
the receiver. A simple expression is given for the capacity per unit energy, in
the presence of a peak constraint. The simple formula of Verdu for capacity per
unit cost is adapted to a channel with memory, and is used in the proof. In
addition to bounding the capacity of a channel with correlated fading, the
result gives some insight into the relationship between the correlation in the
fading process and the channel capacity. The results are extended to a channel
with side information, showing that the capacity per unit energy is one nat per
Joule, independently of the peak power constraint.
  A continuous-time version of the model is also considered. The capacity per
unit energy subject to a peak constraint (but no bandwidth constraint) is given
by an expression similar to that for discrete time, and is evaluated for
Gauss-Markov and Clarke fading channels.


title: Componentwise Least Squares Support Vector Machines

abstract:
  This chapter describes componentwise Least Squares Support Vector Machines
(LS-SVMs) for the estimation of additive models consisting of a sum of
nonlinear components. The primal-dual derivations characterizing LS-SVMs for
the estimation of the additive model result in a single set of linear equations
with size growing in the number of data-points. The derivation is elaborated
for the classification as well as the regression case. Furthermore, different
techniques are proposed to discover structure in the data by looking for sparse
components in the model based on dedicated regularization schemes on the one
hand and fusion of the componentwise LS-SVMs training with a validation
criterion on the other hand. (keywords: LS-SVMs, additive models,
regularization, structure detection)


title: Improved direct sum theorem in classical communication complexity

abstract: Withdrawn due to critical error.


title: Time, Space, and Energy in Reversible Computing

abstract:
  We survey results of a quarter century of work on computation by reversible
general-purpose computers (in this setting Turing machines), and general
reversible simulation of irreversible computations, with respect to energy-,
time- and space requirements.


title: Universal Similarity

abstract:
  We survey a new area of parameter-free similarity distance measures useful in
data-mining, pattern recognition, learning and automatic semantics extraction.
Given a family of distances on a set of objects, a distance is universal up to
a certain precision for that family if it minorizes every distance in the
family between every two objects in the set, up to the stated precision (we do
not require the universal distance to be an element of the family). We consider
similarity distances for two types of objects: literal objects that as such
contain all of their meaning, like genomes or books, and names for objects. The
latter may have literal embodyments like the first type, but may also be
abstract like ``red'' or ``christianity.'' For the first type we consider a
family of computable distance measures corresponding to parameters expressing
similarity according to particular features between pairs of literal objects.
For the second type we consider similarity distances generated by web users
corresponding to particular semantic relations between the (names for) the
designated objects. For both families we give universal similarity distance
measures, incorporating all particular distance measures in the family. In the
first case the universal distance is based on compression and in the second
case it is based on Google page counts related to search terms. In both cases
experiments on a massive scale give evidence of the viability of the
approaches.


title: Discrete Morse Theory for free chain complexes

abstract:
  We extend the combinatorial Morse complex construction to the arbitrary free
chain complexes, and give a short, self-contained, and elementary proof of the
quasi-isomorphism between the original chain complex and its Morse complex.
  Even stronger, the main result states that, if $C_*$ is a free chain complex,
and $\cm$ an acyclic matching, then $C_*=C_*^\cm\oplus T_*$, where $C_*^\cm$ is
the Morse complex generated by the critical elements, and $T_*$ is an acyclic
complex.


title: A Probabilistic Upper Bound on Differential Entropy

abstract:
  A novel, non-trivial, probabilistic upper bound on the entropy of an unknown
one-dimensional distribution, given the support of the distribution and a
sample from that distribution, is presented. No knowledge beyond the support of
the unknown distribution is required, nor is the distribution required to have
a density. Previous distribution-free bounds on the cumulative distribution
function of a random variable given a sample of that variable are used to
construct the bound. A simple, fast, and intuitive algorithm for computing the
entropy bound from a sample is provided.


title: On Optimality Condition of Complex Systems: Computational Evidence

abstract:
  A general condition determining the optimal performance of a complex system
has not yet been found and the possibility of its existence is unknown. To
contribute in this direction, an optimization algorithm as a complex system is
presented. The performance of the algorithm for any problem is controlled as a
convex function with a single optimum. To characterize the performance
optimums, certain quantities of the algorithm and the problem are suggested and
interpreted as their complexities. An optimality condition of the algorithm is
computationally found: if the algorithm shows its best performance for a
problem, then the complexity of the algorithm is in a linear relationship with
the complexity of the problem. The optimality condition provides a new
perspective to the subject by recognizing that the relationship between certain
quantities of the complex system and the problem may determine the optimal
performance.


title: A Multi-proxy Signature Scheme for Partial delegation with Warrant

abstract:
  In some cases, the original signer may delegate its signing power to a
specified proxy group while ensuring individual accountability of each
participantsigner. The proxy signature scheme that achieves such purpose is
called the multi-proxy signature scheme and the signature generated by the
specified proxy group is called multi-proxy signature for the original signer.
Recently such scheme has been discussed by Lin et al. Lins scheme is based on
partial delegation by Mambo et al. In present chapter we introduce a new
multi-proxy signature scheme, which requires less computational overhead in
comparison to Lin et al, and also fulfill the requirement of partial delegation
with warrant simultaneously.


title:
A New Remote User Authentication Scheme Using Smart Cards with Check
  Digits

abstract:
  Since 1981, when Lamport introduced the remote user authentication scheme
using table, a plenty of schemes had been proposed with table and without table
using. In 1993, Chang and Wu [5] introduced Remote password authentication
scheme with smart cards. A number of remote authentication schemes with smart
cards have been proposed since then. These schemes allow a valid user to login
a remote server and access the services provided by the remote server. But
still there is no scheme to authenticate the remote proxy user. In this paper
we propose firstly, a protocol to authenticate a proxy user remotely using
smartcards.


title:
An Efficient Scheme for Sensitive Message Transmission using Blind
  Signcryption

abstract:
  Blind signature schemes enable a useful protocol that guarantee the anonymity
of the participants while Signcryption offers authentication of message and
confidentiality of messages at the same time and more efficiently. In this
paper, we present a blind signcryption scheme that combines the functionality
of blind signature and signcryption. This blind Signcryption is useful for
applications that are based on anonymity untracebility and unlinkability.


title: P-Selectivity, Immunity, and the Power of One Bit

abstract:
  We prove that P-sel, the class of all P-selective sets, is EXP-immune, but is
not EXP/1-immune. That is, we prove that some infinite P-selective set has no
infinite EXP-time subset, but we also prove that every infinite P-selective set
has some infinite subset in EXP/1. Informally put, the immunity of P-sel is so
fragile that it is pierced by a single bit of information.
  The above claims follow from broader results that we obtain about the
immunity of the P-selective sets. In particular, we prove that for every
recursive function f, P-sel is DTIME(f)-immune. Yet we also prove that P-sel is
not \Pi_2^p/1-immune.


title:
ID-based Ring Signature and Proxy Ring Signature Schemes from Bilinear
  Pairings

abstract:
  In 2001, Rivest et al. firstly introduced the concept of ring signatures. A
ring signature is a simplified group signature without any manager. It protects
the anonymity of a signer. The first scheme proposed by Rivest et al. was based
on RSA cryptosystem and certificate based public key setting. The first ring
signature scheme based on DLP was proposed by Abe, Ohkubo, and Suzuki. Their
scheme is also based on the general certificate-based public key setting too.
In 2002, Zhang and Kim proposed a new ID-based ring signature scheme using
pairings. Later Lin and Wu proposed a more efficient ID-based ring signature
scheme. Both these schemes have some inconsistency in computational aspect.
  In this paper we propose a new ID-based ring signature scheme and a proxy
ring signature scheme. Both the schemes are more efficient than existing one.
These schemes also take care of the inconsistencies in above two schemes.


title:
The Capacity of Random Ad hoc Networks under a Realistic Link Layer
  Model

abstract:
  The problem of determining asymptotic bounds on the capacity of a random ad
hoc network is considered. Previous approaches assumed a threshold-based link
layer model in which a packet transmission is successful if the SINR at the
receiver is greater than a fixed threshold. In reality, the mapping from SINR
to packet success probability is continuous. Hence, over each hop, for every
finite SINR, there is a non-zero probability of packet loss. With this more
realistic link model, it is shown that for a broad class of routing and
scheduling schemes, a fixed fraction of hops on each route have a fixed
non-zero packet loss probability. In a large network, a packet travels an
asymptotically large number of hops from source to destination. Consequently,
it is shown that the cumulative effect of per-hop packet loss results in a
per-node throughput of only O(1/n) (instead of Theta(1/sqrt{n log{n}})) as
shown previously for the threshold-based link model).
  A scheduling scheme is then proposed to counter this effect. The proposed
scheme improves the link SINR by using conservative spatial reuse, and improves
the per-node throughput to O(1/(K_n sqrt{n log{n}})), where each cell gets a
transmission opportunity at least once every K_n slots, and K_n tends to
infinity as n tends to infinity.


title: A DNA Sequence Compression Algorithm Based on LUT and LZ77

abstract:
  This article introduces a new DNA sequence compression algorithm which is
based on LUT and LZ77 algorithm. Combined a LUT-based pre-coding routine and
LZ77 compression routine,this algorithm can approach a compression ratio of
1.9bits \slash base and even lower.The biggest advantage of this algorithm is
fast execution, small memory occupation and easy implementation.


title: Single-solution Random 3-SAT Instances

abstract:
  We study a class of random 3-SAT instances having exactly one solution. The
properties of this ensemble considerably differ from those of a random 3-SAT
ensemble. It is numerically shown that the running time of several complete and
stochastic local search algorithms monotonically increases as the clause
density is decreased. Therefore, there is no easy-hard-easy pattern of hardness
as for standard random 3-SAT ensemble. Furthermore, the running time for short
single-solution formulas increases with the problem size much faster than for
random 3-SAT formulas from the phase transition region.


title:
Spectral Orbits and Peak-to-Average Power Ratio of Boolean Functions
  with respect to the {I,H,N}^n Transform

abstract:
  We enumerate the inequivalent self-dual additive codes over GF(4) of
blocklength n, thereby extending the sequence A090899 in The On-Line
Encyclopedia of Integer Sequences from n = 9 to n = 12. These codes have a
well-known interpretation as quantum codes. They can also be represented by
graphs, where a simple graph operation generates the orbits of equivalent
codes. We highlight the regularity and structure of some graphs that correspond
to codes with high distance. The codes can also be interpreted as quadratic
Boolean functions, where inequivalence takes on a spectral meaning. In this
context we define PAR_IHN, peak-to-average power ratio with respect to the
{I,H,N}^n transform set. We prove that PAR_IHN of a Boolean function is
equivalent to the the size of the maximum independent set over the associated
orbit of graphs. Finally we propose a construction technique to generate
Boolean functions with low PAR_IHN and algebraic degree higher than 2.


title: Incremental Medians via Online Bidding

abstract:
  In the k-median problem we are given sets of facilities and customers, and
distances between them. For a given set F of facilities, the cost of serving a
customer u is the minimum distance between u and a facility in F. The goal is
to find a set F of k facilities that minimizes the sum, over all customers, of
their service costs.
  Following Mettu and Plaxton, we study the incremental medians problem, where
k is not known in advance, and the algorithm produces a nested sequence of
facility sets where the kth set has size k. The algorithm is c-cost-competitive
if the cost of each set is at most c times the cost of the optimum set of size
k. We give improved incremental algorithms for the metric version: an
8-cost-competitive deterministic algorithm, a 2e ~ 5.44-cost-competitive
randomized algorithm, a (24+epsilon)-cost-competitive, poly-time deterministic
algorithm, and a (6e+epsilon ~ .31)-cost-competitive, poly-time randomized
algorithm.
  The algorithm is s-size-competitive if the cost of the kth set is at most the
minimum cost of any set of size k, and has size at most s k. The optimal
size-competitive ratios for this problem are 4 (deterministic) and e
(randomized). We present the first poly-time O(log m)-size-approximation
algorithm for the offline problem and first poly-time O(log m)-size-competitive
algorithm for the incremental problem.
  Our proofs reduce incremental medians to the following online bidding
problem: faced with an unknown threshold T, an algorithm submits "bids" until
it submits a bid that is at least the threshold. It pays the sum of all its
bids. We prove that folklore algorithms for online bidding are optimally
competitive.


title: The reverse greedy algorithm for the metric k-median problem

abstract:
  The Reverse Greedy algorithm (RGreedy) for the k-median problem works as
follows. It starts by placing facilities on all nodes. At each step, it removes
a facility to minimize the resulting total distance from the customers to the
remaining facilities. It stops when k facilities remain. We prove that, if the
distance function is metric, then the approximation ratio of RGreedy is between
?(log n/ log log n) and O(log n).


title: Wikis in Tuple Spaces

abstract:
  We consider storing the pages of a wiki in a tuple space and the effects this
might have on the wiki experience. In particular, wiki pages are stored in
tuples with a few identifying values such as title, author, revision date,
content, etc. and pages are retrieved by sending the tuple space templates,
such as one that gives the title but nothing else, leaving the tuple space to
resolve to a single tuple. We use a tuple space wiki to avoid deadlocks,
infinite loops, and wasted efforts when page edit contention arises and examine
how a tuple space wiki changes the wiki experience.


title:
A Distributed Multimedia Communication System and its Applications to
  E-Learning

abstract:
  In this paper we report on a multimedia communication system including a
VCoIP (Video Conferencing over IP) software with a distributed architecture and
its applications for teaching scenarios. It is a simple, ready-to-use scheme
for distributed presenting, recording and streaming multimedia content. We also
introduce and investigate concepts and experiments to IPv6 user and session
mobility, with the special focus on real-time video group communication.


title:
k-core decomposition: a tool for the visualization of large scale
  networks

abstract:
  We use the k-core decomposition to visualize large scale complex networks in
two dimensions. This decomposition, based on a recursive pruning of the least
connected vertices, allows to disentangle the hierarchical structure of
networks by progressively focusing on their central cores. By using this
strategy we develop a general visualization algorithm that can be used to
compare the structural properties of various networks and highlight their
hierarchical structure. The low computational complexity of the algorithm,
O(n+e), where 'n' is the size of the network, and 'e' is the number of edges,
makes it suitable for the visualization of very large sparse networks. We apply
the proposed visualization tool to several real and synthetic graphs, showing
its utility in finding specific structural fingerprints of computer generated
and real world networks.


title:
Cooperative Game Theory within Multi-Agent Systems for Systems
  Scheduling

abstract:
  Research concerning organization and coordination within multi-agent systems
continues to draw from a variety of architectures and methodologies. The work
presented in this paper combines techniques from game theory and multi-agent
systems to produce self-organizing, polymorphic, lightweight, embedded agents
for systems scheduling within a large-scale real-time systems environment.
Results show how this approach is used to experimentally produce optimum
real-time scheduling through the emergent behavior of thousands of agents.
These results are obtained using a SWARM simulation of systems scheduling
within a High Energy Physics experiment consisting of 2500 digital signal
processors.


title:
Prototype of Fault Adaptive Embedded Software for Large-Scale Real-Time
  Systems

abstract:
  This paper describes a comprehensive prototype of large-scale fault adaptive
embedded software developed for the proposed Fermilab BTeV high energy physics
experiment. Lightweight self-optimizing agents embedded within Level 1 of the
prototype are responsible for proactive and reactive monitoring and mitigation
based on specified layers of competence. The agents are self-protecting,
detecting cascading failures using a distributed approach. Adaptive,
reconfigurable, and mobile objects for reliablility are designed to be
self-configuring to adapt automatically to dynamically changing environments.
These objects provide a self-healing layer with the ability to discover,
diagnose, and react to discontinuities in real-time processing. A generic
modeling environment was developed to facilitate design and implementation of
hardware resource specifications, application data flow, and failure mitigation
strategies. Level 1 of the planned BTeV trigger system alone will consist of
2500 DSPs, so the number of components and intractable fault scenarios involved
make it impossible to design an `expert system' that applies traditional
centralized mitigative strategies based on rules capturing every possible
system state. Instead, a distributed reactive approach is implemented using the
tools and methodologies developed by the Real-Time Embedded Systems group.


title: Computing finite-dimensional bipartite quantum separability

abstract:
  Ever since entanglement was identified as a computational and cryptographic
resource, effort has been made to find an efficient way to tell whether a given
density matrix represents an unentangled, or separable, state. Essentially,
this is the quantum separability problem.
  Chapters 1 to 3 motivate a new interior-point algorithm which, given the
expected values of a subset of an orthogonal basis of observables of an
otherwise unknown quantum state, searches for an entanglement witness in the
span of the subset of observables. When all the expected values are known, the
algorithm solves the separability problem. In Chapter 4, I give the motivation
for the algorithm and show how it can be used in a particular physical scenario
to detect entanglement (or decide separability) of an unknown quantum state
using as few quantum resources as possible. I then explain the intuitive idea
behind the algorithm and relate it to the standard algorithms of its kind. I
end the chapter with a comparison of the complexities of the algorithms
surveyed in Chapter 3. Finally, in Chapter 5, I present the details of the
algorithm and discuss its performance relative to standard methods.


title: Efficient and Robust Geocasting Protocols for Sensor Networks

abstract:
  Geocasting is the delivery of packets to nodes within a certain geographic
area. For many applications in wireless ad hoc and sensor networks, geocasting
is an important and frequent communication service. The challenging problem in
geocasting is distributing the packets to all the nodes within the geocast
region with high probability but with low overhead. According to our study we
notice a clear tradeoff between the proportion of nodes in the geocast region
that receive the packet and the overhead incurred by the geocast packet
especially at low densities and irregular distributions. We present two novel
protocols for geocasting that achieve high delivery rate and low overhead by
utilizing the local location information of nodes to combine geographic routing
mechanisms with region flooding. We show that the first protocol
Geographic-Forwarding-Geocast (GFG) has close-to-minimum overhead in dense
networks and that the second protocol Geographic-Forwarding-Perimeter-Geocast
(GFPG) provides guaranteed delivery without global flooding or global network
information even at low densities and with the existence of region gaps or
obstacles. An adaptive version of the second protocol (GFPG*) has the desirable
property of perfect delivery at all densities and close-to-minimum overhead at
high densities. We evaluate our mechanisms and compare them using simulation to
other proposed geocasting mechanisms. The results show the significant
improvement in delivery rate (up to 63% higher delivery percentage in low
density networks) and reduction in overhead (up to 80% reduction) achieved by
our mechanisms. We hope for our protocols to become building block mechanisms
for dependable sensor network architectures that require robust efficient
geocast services.


title:
Modelling investment in artificial stock markets: Analytical and
  Numerical Results

abstract:
  In this article we study the behavior of a group of economic agents in the
context of cooperative game theory, interacting according to rules based on the
Potts Model with suitable modifications. Each agent can be thought of as
belonging to a chain, where agents can only interact with their nearest
neighbors (periodic boundary conditions are imposed). Each agent can invest an
amount σ_{i}=0,...,q-1. Using the transfer matrix method we study
analytically, among other things, the behavior of the investment as a function
of a control parameter (denoted β) for the cases q=2 and 3. For q>3
numerical evaluation of eigenvalues and high precision numerical derivatives
are used in order to assess this information.


title:
Tight Lower Bounds for Query Processing on Streaming and External Memory
  Data

abstract:
  We study a clean machine model for external memory and stream processing. We
show that the number of scans of the external data induces a strict hierarchy
(as long as work space is sufficiently small, e.g., polylogarithmic in the size
of the input). We also show that neither joins nor sorting are feasible if the
product of the number $r(n)$ of scans of the external memory and the size
$s(n)$ of the internal memory buffers is sufficiently small, e.g., of size
$o(\sqrt[5]{n})$. We also establish tight bounds for the complexity of XPath
evaluation and filtering.


title: A New Kind of Hopfield Networks for Finding Global Optimum

abstract:
  The Hopfield network has been applied to solve optimization problems over
decades. However, it still has many limitations in accomplishing this task.
Most of them are inherited from the optimization algorithms it implements. The
computation of a Hopfield network, defined by a set of difference equations,
can easily be trapped into one local optimum or another, sensitive to initial
conditions, perturbations, and neuron update orders. It doesn't know how long
it will take to converge, as well as if the final solution is a global optimum,
or not. In this paper, we present a Hopfield network with a new set of
difference equations to fix those problems. The difference equations directly
implement a new powerful optimization algorithm.


title: Pluggable AOP: Designing Aspect Mechanisms for Third-party Composition

abstract:
  Studies of Aspect-Oriented Programming (AOP) usually focus on a language in
which a specific aspect extension is integrated with a base language. Languages
specified in this manner have a fixed, non-extensible AOP functionality. In
this paper we consider the more general case of integrating a base language
with a set of domain specific third-party aspect extensions for that language.
We present a general mixin-based method for implementing aspect extensions in
such a way that multiple, independently developed, dynamic aspect extensions
can be subject to third-party composition and work collaboratively.


title: Defragmenting the Module Layout of a Partially Reconfigurable Device

abstract:
  Modern generations of field-programmable gate arrays (FPGAs) allow for
partial reconfiguration. In an online context, where the sequence of modules to
be loaded on the FPGA is unknown beforehand, repeated insertion and deletion of
modules leads to progressive fragmentation of the available space, making
defragmentation an important issue. We address this problem by propose an
online and an offline component for the defragmentation of the available space.
We consider defragmenting the module layout on a reconfigurable device. This
corresponds to solving a two-dimensional strip packing problem. Problems of
this type are NP-hard in the strong sense, and previous algorithmic results are
rather limited. Based on a graph-theoretic characterization of feasible
packings, we develop a method that can solve two-dimensional defragmentation
instances of practical size to optimality. Our approach is validated for a set
of benchmark instances.


title:
Searching for image information content, its discovery, extraction, and
  representation

abstract:
  Image information content is known to be a complicated and controvercial
problem. This paper posits a new image information content definition.
Following the theory of Solomonoff-Kolmogorov-Chaitin's complexity, we define
image information content as a set of descriptions of imafe data structures.
Three levels of such description can be generally distinguished: 1)the global
level, where the coarse structure of the entire scene is initially outlined; 2)
the intermediate level, where structures of separate, non-overlapping image
regions usually associated with individual scene objects are deliniated; and 3)
the low-level description, where local image structures observed in a limited
and restricted field of view are resolved. A technique for creating such image
information content descriptors is developed. Its algorithm is presented and
elucidated with some examples, which demonstrate the effectiveness of the
proposed approach.


title: Adaptive Codes: A New Class of Non-standard Variable-length Codes

abstract:
  We introduce a new class of non-standard variable-length codes, called
adaptive codes. This class of codes associates a variable-length codeword to
the symbol being encoded depending on the previous symbols in the input data
string. An efficient algorithm for constructing adaptive codes of order one is
presented. Then, we introduce a natural generalization of adaptive codes,
called GA codes.


title: Data Mining on Crash Simulation Data

abstract:
  The work presented in this paper is part of the cooperative research project
AUTO-OPT carried out by twelve partners from the automotive industries. One
major work package concerns the application of data mining methods in the area
of automotive design. Suitable methods for data preparation and data analysis
are developed. The objective of the work is the re-use of data stored in the
crash-simulation department at BMW in order to gain deeper insight into the
interrelations between the geometric variations of the car during its design
and its performance in crash testing. In this paper a method for data analysis
of finite element models and results from crash simulation is proposed and
application to recent data from the industrial partner BMW is demonstrated. All
necessary steps from data pre-processing to re-integration into the working
environment of the engineer are covered.


title: Human being is a living random number generator

abstract:
  General wisdom is, mathematical operation is needed to generate number by
numbers. It is pointed out that without any mathematical operation true random
numbers can be generated by numbers through algorithmic process. It implies
that human brain itself is a living true random number generator. Human brain
can meet the enormous human demand of true random numbers.


title: On the Wyner-Ziv problem for individual sequences

abstract:
  We consider a variation of the Wyner-Ziv problem pertaining to lossy
compression of individual sequences using finite-state encoders and decoders.
There are two main results in this paper. The first characterizes the
relationship between the performance of the best $M$-state encoder-decoder pair
to that of the best block code of size $\ell$ for every input sequence, and
shows that the loss of the latter relative to the former (in terms of both rate
and distortion) never exceeds the order of $(\log M)/\ell$, independently of
the input sequence. Thus, in the limit of large $M$, the best rate-distortion
performance of every infinite source sequence can be approached universally by
a sequence of block codes (which are also implementable by finite-state
machines). While this result assumes an asymptotic regime where the number of
states is fixed, and only the length $n$ of the input sequence grows without
bound, we then consider the case where the number of states $M=M_n$ is allowed
to grow concurrently with $n$. Our second result is then about the critical
growth rate of $M_n$ such that the rate-distortion performance of $M_n$-state
encoder-decoder pairs can still be matched by a universal code. We show that
this critical growth rate of $M_n$ is linear in $n$.


title: SWiM: A Simple Window Mover

abstract:
  As computers become more ubiquitous, traditional two-dimensional interfaces
must be replaced with interfaces based on a three-dimensional metaphor.
However, these interfaces must still be as simple and functional as their
two-dimensional predecessors. This paper introduces SWiM, a new interface for
moving application windows between various screens, such as wall displays,
laptop monitors, and desktop displays, in a three-dimensional physical
environment. SWiM was designed based on the results of initial "paper and
pencil" user tests of three possible interfaces. The results of these tests led
to a map-like interface where users select the destination display for their
application from various icons. If the destination is a mobile display it is
not displayed on the map. Instead users can select the screen's name from a
list of all possible destination displays. User testing of SWiM was conducted
to discover whether it is easy to learn and use. Users that were asked to use
SWiM without any instructions found the interface as intuitive to use as users
who were given a demonstration. The results show that SWiM combines simplicity
and functionality to create an interface that is easy to learn and easy to use.


title:
On the Shannon cipher system with a capacity-limited key-distribution
  channel

abstract:
  We consider the Shannon cipher system in a setting where the secret key is
delivered to the legitimate receiver via a channel with limited capacity. For
this setting, we characterize the achievable region in the space of three
figures of merit: the security (measured in terms of the equivocation), the
compressibility of the cryptogram, and the distortion associated with the
reconstruction of the plaintext source. Although lossy reconstruction of the
plaintext does not rule out the option that the (noisy) decryption key would
differ, to a certain extent, from the encryption key, we show, nevertheless,
that the best strategy is to strive for perfect match between the two keys, by
applying reliable channel coding to the key bits, and to control the distortion
solely via rate-distortion coding of the plaintext source before the
encryption. In this sense, our result has a flavor similar to that of the
classical source-channel separation theorem. Some variations and extensions of
this model are discussed as well.


title: Theories for TC0 and Other Small Complexity Classes

abstract:
  We present a general method for introducing finitely axiomatizable "minimal"
two-sorted theories for various subclasses of P (problems solvable in
polynomial time). The two sorts are natural numbers and finite sets of natural
numbers. The latter are essentially the finite binary strings, which provide a
natural domain for defining the functions and sets in small complexity classes.
We concentrate on the complexity class TC^0, whose problems are defined by
uniform polynomial-size families of bounded-depth Boolean circuits with
majority gates. We present an elegant theory VTC^0 in which the provably-total
functions are those associated with TC^0, and then prove that VTC^0 is
"isomorphic" to a different-looking single-sorted theory introduced by
Johannsen and Pollet. The most technical part of the isomorphism proof is
defining binary number multiplication in terms a bit-counting function, and
showing how to formalize the proofs of its algebraic properties.


title:
Interval Neutrosophic Sets and Logic: Theory and Applications in
  Computing

abstract:
  This book presents the advancements and applications of neutrosophics.
Chapter 1 first introduces the interval neutrosophic sets which is an instance
of neutrosophic sets. In this chapter, the definition of interval neutrosophic
sets and set-theoretic operators are given and various properties of interval
neutrosophic set are proved. Chapter 2 defines the interval neutrosophic logic
based on interval neutrosophic sets including the syntax and semantics of first
order interval neutrosophic propositional logic and first order interval
neutrosophic predicate logic. The interval neutrosophic logic can reason and
model fuzzy, incomplete and inconsistent information. In this chapter, we also
design an interval neutrosophic inference system based on first order interval
neutrosophic predicate logic. The interval neutrosophic inference system can be
applied to decision making. Chapter 3 gives one application of interval
neutrosophic sets and logic in the field of relational databases. Neutrosophic
data model is the generalization of fuzzy data model and paraconsistent data
model. Here, we generalize various set-theoretic and relation-theoretic
operations of fuzzy data model to neutrosophic data model. Chapter 4 gives
another application of interval neutrosophic logic. A soft semantic Web
Services agent framework is proposed to faciliate the registration and
discovery of high quality semantic Web Services agent. The intelligent
inference engine module of soft Semantic Web Services agent is implemented
using interval neutrosophic logic.


title:
Complex Mean and Variance of Linear Regression Model for High-Noised
  Systems by Kriging

abstract:
  The aim of the paper is to derive the complex-valued least-squares estimator
for bias-noise mean and variance.


title: Visual Character Recognition using Artificial Neural Networks

abstract:
  The recognition of optical characters is known to be one of the earliest
applications of Artificial Neural Networks, which partially emulate human
thinking in the domain of artificial intelligence. In this paper, a simplified
neural approach to recognition of optical or visual characters is portrayed and
discussed. The document is expected to serve as a resource for learners and
amateur investigators in pattern recognition, neural networking and related
disciplines.


title: Point set stratification and Delaunay depth

abstract:
  In the study of depth functions it is important to decide whether we want
such a function to be sensitive to multimodality or not. In this paper we
analyze the Delaunay depth function, which is sensitive to multimodality and
compare this depth with others, as convex depth and location depth. We study
the stratification that Delaunay depth induces in the point set (layers) and in
the whole plane (levels), and we develop an algorithm for computing the
Delaunay depth contours, associated to a point set in the plane, with running
time O(n log^2 n). The depth of a query point p with respect to a data set S in
the plane is the depth of p in the union of S and p. When S and p are given in
the input the Delaunay depth can be computed in O(n log n), and we prove that
this value is optimal.


title: Temporal and Spatial Data Mining with Second-Order Hidden Models

abstract:
  In the frame of designing a knowledge discovery system, we have developed
stochastic models based on high-order hidden Markov models. These models are
capable to map sequences of data into a Markov chain in which the transitions
between the states depend on the \texttt{n} previous states according to the
order of the model. We study the process of achieving information extraction
fromspatial and temporal data by means of an unsupervised classification. We
use therefore a French national database related to the land use of a region,
named Teruti, which describes the land use both in the spatial and temporal
domain. Land-use categories (wheat, corn, forest, ...) are logged every year on
each site regularly spaced in the region. They constitute a temporal sequence
of images in which we look for spatial and temporal dependencies. The temporal
segmentation of the data is done by means of a second-order Hidden Markov Model
(\hmmd) that appears to have very good capabilities to locate stationary
segments, as shown in our previous work in speech recognition. Thespatial
classification is performed by defining a fractal scanning ofthe images with
the help of a Hilbert-Peano curve that introduces atotal order on the sites,
preserving the relation ofneighborhood between the sites. We show that the
\hmmd performs aclassification that is meaningful for the agronomists.Spatial
and temporal classification may be achieved simultaneously by means of a 2
levels \hmmd that measures the \aposteriori probability to map a temporal
sequence of images onto a set of hidden classes.


title: Artificial Neural Networks and their Applications

abstract:
  The Artificial Neural network is a functional imitation of simplified model
of the biological neurons and their goal is to construct useful computers for
real world problems. The ANN applications have increased dramatically in the
last few years fired by both theoretical and practical applications in a wide
variety of applications. A brief theory of ANN is presented and potential areas
are identified and future trends are discussed.


title:
Asymptotic Capacity Results for Non-Stationary Time-Variant Channels
  Using Subspace Projections

abstract:
  In this paper we deal with a single-antenna discrete-time flat-fading
channel. The fading process is assumed to be stationary for the duration of a
single data block. From block to block the fading process is allowed to be
non-stationary. The number of scatterers bounds the rank of the channels
covariance matrix. The signal-to-noise ratio (SNR), the user velocity, and the
data block-length define the usable rank of the time-variant channel subspace.
The usable channel subspace grows with the SNR. This growth in dimensionality
must be taken into account for asymptotic capacity results in the high-SNR
regime. Using results from the theory of time-concentrated and band-limited
sequences we are able to define an SNR threshold below which the capacity grows
logarithmically. Above this threshold the capacity grows
double-logarithmically.


title: Distant generalization by feedforward neural networks

abstract:
  This paper discusses the notion of generalization of training samples over
long distances in the input space of a feedforward neural network. Such a
generalization might occur in various ways, that differ in how great the
contribution of different training features should be.
  The structure of a neuron in a feedforward neural network is analyzed and it
is concluded, that the actual performance of the discussed generalization in
such neural networks may be problematic -- while such neural networks might be
capable for such a distant generalization, a random and spurious generalization
may occur as well.
  To illustrate the differences in generalizing of the same function by
different learning machines, results given by the support vector machines are
also presented.


title:
Collaborative Beamforming for Distributed Wireless Ad Hoc Sensor
  Networks

abstract:
  The performance of collaborative beamforming is analyzed using the theory of
random arrays. The statistical average and distribution of the beampattern of
randomly generated phased arrays is derived in the framework of wireless ad hoc
sensor networks. Each sensor node is assumed to have a single isotropic antenna
and nodes in the cluster collaboratively transmit the signal such that the
signal in the target direction is coherently added in the far- eld region. It
is shown that with N sensor nodes uniformly distributed over a disk, the
directivity can approach N, provided that the nodes are located sparsely
enough. The distribution of the maximum sidelobe peak is also studied. With the
application to ad hoc networks in mind, two scenarios, closed-loop and
open-loop, are considered. Associated with these scenarios, the effects of
phase jitter and location estimation errors on the average beampattern are also
analyzed.


title: State Space Computation and Analysis of Time Petri Nets

abstract:
  The theory of Petri Nets provides a general framework to specify the
behaviors of real-time reactive systems and Time Petri Nets were introduced to
take also temporal specifications into account. We present in this paper a
forward zone-based algorithm to compute the state space of a bounded Time Petri
Net: the method is different and more efficient than the classical State Class
Graph. We prove the algorithm to be exact with respect to the reachability
problem. Furthermore, we propose a translation of the computed state space into
a Timed Automaton, proved to be timed bisimilar to the original Time Petri Net.
As the method produce a single Timed Automaton, syntactical clocks reduction
methods (Daws and Yovine for instance) may be applied to produce an automaton
with fewer clocks. Then, our method allows to model-check TTPN by the use of
efficient Timed Automata tools.
  To appear in Theory and Practice of Logic Programming (TPLP).


title: Logic Column 12: Logical Verification and Equational Verification

abstract:
  This article examines two approaches to verification, one based on using a
logic for expressing properties of a system, and one based on showing the
system equivalent to a simpler system that obviously has whatever property is
of interest. Using examples such as process calculi and regular programs, the
relationship between these two approaches is explored.


title: Equivalence-Checking on Infinite-State Systems: Techniques and Results

abstract:
  The paper presents a selection of recently developed and/or used techniques
for equivalence-checking on infinite-state systems, and an up-to-date overview
of existing results (as of September 2004).


title: Automatic Verification of Timed Concurrent Constraint Programs

abstract:
  The language Timed Concurrent Constraint (tccp) is the extension over time of
the Concurrent Constraint Programming (cc) paradigm that allows us to specify
concurrent systems where timing is critical, for example reactive systems.
Systems which may have an infinite number of states can be specified in tccp.
Model checking is a technique which is able to verify finite-state systems with
a huge number of states in an automatic way. In the last years several studies
have investigated how to extend model checking techniques to systems with an
infinite number of states. In this paper we propose an approach which exploits
the computation model of tccp. Constraint based computations allow us to define
a methodology for applying a model checking algorithm to (a class of)
infinite-state systems. We extend the classical algorithm of model checking for
LTL to a specific logic defined for the verification of tccp and to the tccp
Structure which we define in this work for modeling the program behavior. We
define a restriction on the time in order to get a finite model and then we
develop some illustrative examples. To the best of our knowledge this is the
first approach that defines a model checking methodology for tccp.


title:
The Generic Multiple-Precision Floating-Point Addition With Exact
  Rounding (as in the MPFR Library)

abstract:
  We study the multiple-precision addition of two positive floating-point
numbers in base 2, with exact rounding, as specified in the MPFR library, i.e.
where each number has its own precision. We show how the best possible
complexity (up to a constant factor that depends on the implementation) can be
obtain.


title: A linear memory algorithm for Baum-Welch training

abstract:
  Background: Baum-Welch training is an expectation-maximisation algorithm for
training the emission and transition probabilities of hidden Markov models in a
fully automated way.
  Methods and results: We introduce a linear space algorithm for Baum-Welch
training. For a hidden Markov model with M states, T free transition and E free
emission parameters, and an input sequence of length L, our new algorithm
requires O(M) memory and O(L M T_max (T + E)) time for one Baum-Welch
iteration, where T_max is the maximum number of states that any state is
connected to. The most memory efficient algorithm until now was the
checkpointing algorithm with O(log(L) M) memory and O(log(L) L M T_max) time
requirement. Our novel algorithm thus renders the memory requirement completely
independent of the length of the training sequences. More generally, for an
n-hidden Markov model and n input sequences of length L, the memory requirement
of O(log(L) L^(n-1) M) is reduced to O(L^(n-1) M) memory while the running time
is changed from O(log(L) L^n M T_max + L^n (T + E)) to O(L^n M T_max (T + E)).
  Conclusions: For the large class of hidden Markov models used for example in
gene prediction, whose number of states does not scale with the length of the
input sequence, our novel algorithm can thus be both faster and more
memory-efficient than any of the existing algorithms.


title: Automated Improvement for Component Reuse

abstract:
  Software component reuse is the key to significant gains in productivity.
However, the major problem is the lack of identifying and developing
potentially reusable components. This paper concentrates on our approach to the
development of reusable software components. A prototype tool has been
developed, known as the Reuse Assessor and Improver System (RAIS) which can
interactively identify, analyse, assess, and modify abstractions, attributes
and architectures that support reuse. Practical and objective reuse guidelines
are used to represent reuse knowledge and to do domain analysis. It takes
existing components, provides systematic reuse assessment which is based on
reuse advice and analysis, and produces components that are improved for reuse.
Our work on guidelines has been extended to a large scale industrial
application.


title: Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix

abstract:
  We reduce the problem of computing the rank and a nullspace basis of a
univariate polynomial matrix to polynomial matrix multiplication. For an input
n x n matrix of degree d over a field K we give a rank and nullspace algorithm
using about the same number of operations as for multiplying two matrices of
dimension n and degree d. If the latter multiplication is done in
MM(n,d)=softO(n^omega d) operations, with omega the exponent of matrix
multiplication over K, then the algorithm uses softO(MM(n,d)) operations in K.
The softO notation indicates some missing logarithmic factors. The method is
randomized with Las Vegas certification. We achieve our results in part through
a combination of matrix Hensel high-order lifting and matrix minimal fraction
reconstruction, and through the computation of minimal or small degree vectors
in the nullspace seen as a K[x]-module


title:
Estudo e Implementacao de Algoritmos de Roteamento sobre Grafos em um
  Sistema de Informacoes Geograficas

abstract:
  This article presents an implementation of a graphical software with various
algorithms in Operations research, like minimum path, minimum tree, chinese
postman problem and travelling salesman.


title: Broadcast Channels with Cooperating Decoders

abstract:
  We consider the problem of communicating over the general discrete memoryless
broadcast channel (BC) with partially cooperating receivers. In our setup,
receivers are able to exchange messages over noiseless conference links of
finite capacities, prior to decoding the messages sent from the transmitter. In
this paper we formulate the general problem of broadcast with cooperation. We
first find the capacity region for the case where the BC is physically
degraded. Then, we give achievability results for the general broadcast
channel, for both the two independent messages case and the single common
message case.


title: Parametric Verification of a Group Membership Algorithm

abstract:
  We address the problem of verifying clique avoidance in the TTP protocol. TTP
allows several stations embedded in a car to communicate. It has many
mechanisms to ensure robustness to faults. In particular, it has an algorithm
that allows a station to recognize itself as faulty and leave the
communication. This algorithm must satisfy the crucial 'non-clique' property:
it is impossible to have two or more disjoint groups of stations communicating
exclusively with stations in their own group.
  In this paper, we propose an automatic verification method for an arbitrary
number of stations $N$ and a given number of faults $k$. We give an abstraction
that allows to model the algorithm by means of unbounded (parametric) counter
automata. We have checked the non-clique property on this model in the case of
one fault, using the ALV tool as well as the LASH tool.


title: Essential Incompleteness of Arithmetic Verified by Coq

abstract:
  A constructive proof of the Goedel-Rosser incompleteness theorem has been
completed using the Coq proof assistant. Some theory of classical first-order
logic over an arbitrary language is formalized. A development of primitive
recursive functions is given, and all primitive recursive functions are proved
to be representable in a weak axiom system. Formulas and proofs are encoded as
natural numbers, and functions operating on these codes are proved to be
primitive recursive. The weak axiom system is proved to be essentially
incomplete. In particular, Peano arithmetic is proved to be consistent in Coq's
type theory and therefore is incomplete.


title: Beyond Hypertree Width: Decomposition Methods Without Decompositions

abstract:
  The general intractability of the constraint satisfaction problem has
motivated the study of restrictions on this problem that permit polynomial-time
solvability. One major line of work has focused on structural restrictions,
which arise from restricting the interaction among constraint scopes. In this
paper, we engage in a mathematical investigation of generalized hypertree
width, a structural measure that has up to recently eluded study. We obtain a
number of computational results, including a simple proof of the tractability
of CSP instances having bounded generalized hypertree width.


title: Minimal Eulerian trail in a labeled digraph

abstract:
  Let $G$ be an Eulerian directed graph with an arc-labeling such that arcs
going out from the same vertex have different labels. In this work, we present
an algorithm to construct the Eulerian trail starting at an arbitrary vertex
$v$ of minimum lexicographical label among labels of all Eulerian trails
starting at this vertex.
  We also show an application of this algorithm to construct the minimal de
Bruijn sequence of a language.


title: General Recursion via Coinductive Types

abstract:
  A fertile field of research in theoretical computer science investigates the
representation of general recursive functions in intensional type theories.
Among the most successful approaches are: the use of wellfounded relations,
implementation of operational semantics, formalization of domain theory, and
inductive definition of domain predicates. Here, a different solution is
proposed: exploiting coinductive types to model infinite computations. To every
type A we associate a type of partial elements Partial(A), coinductively
generated by two constructors: the first, return(a) just returns an element
a:A; the second, step(x), adds a computation step to a recursive element
x:Partial(A). We show how this simple device is sufficient to formalize all
recursive functions between two given types. It allows the definition of fixed
points of finitary, that is, continuous, operators. We will compare this
approach to different ones from the literature. Finally, we mention that the
formalization, with appropriate structural maps, defines a strong monad.


title: Efficient Management of Short-Lived Data

abstract:
  Motivated by the increasing prominence of loosely-coupled systems, such as
mobile and sensor networks, which are characterised by intermittent
connectivity and volatile data, we study the tagging of data with so-called
expiration times. More specifically, when data are inserted into a database,
they may be tagged with time values indicating when they expire, i.e., when
they are regarded as stale or invalid and thus are no longer considered part of
the database. In a number of applications, expiration times are known and can
be assigned at insertion time. We present data structures and algorithms for
online management of data tagged with expiration times. The algorithms are
based on fully functional, persistent treaps, which are a combination of binary
search trees with respect to a primary attribute and heaps with respect to a
secondary attribute. The primary attribute implements primary keys, and the
secondary attribute stores expiration times in a minimum heap, thus keeping a
priority queue of tuples to expire. A detailed and comprehensive experimental
study demonstrates the well-behavedness and scalability of the approach as well
as its efficiency with respect to a number of competitors.


title: Methods for comparing rankings of search engine results

abstract:
  In this paper we present a number of measures that compare rankings of search
engine results. We apply these measures to five queries that were monitored
daily for two periods of about 21 days each. Rankings of the different search
engines (Google, Yahoo and Teoma for text searches and Google, Yahoo and
Picsearch for image searches) are compared on a daily basis, in addition to
longitudinal comparisons of the same engine for the same query over time. The
results and rankings of the two periods are compared as well.


title: Asynchronous pseudo-systems

abstract:
  The paper introduces the concept of asynchronous pseudo-system. Its purpose
is to correct/generalize/continue the study of the asynchronous systems (the
models of the asynchronous circuits) that has been started in [1], [2].


title: Relational reasoning in the region connection calculus

abstract:
  This paper is mainly concerned with the relation-algebraical aspects of the
well-known Region Connection Calculus (RCC). We show that the contact relation
algebra (CRA) of certain RCC model is not atomic complete and hence infinite.
So in general an extensional composition table for the RCC cannot be obtained
by simply refining the RCC8 relations. After having shown that each RCC model
is a consistent model of the RCC11 CT, we give an exhaustive investigation
about extensional interpretation of the RCC11 CT. More important, we show the
complemented closed disk algebra is a representation for the relation algebra
determined by the RCC11 table. The domain of this algebra contains two classes
of regions, the closed disks and closures of their complements in the real
plane.


title: Iterative MILP Methods for Vehicle Control Problems

abstract:
  Mixed integer linear programming (MILP) is a powerful tool for planning and
control problems because of its modeling capability and the availability of
good solvers. However, for large models, MILP methods suffer computationally.
In this paper, we present iterative MILP algorithms that address this issue. We
consider trajectory generation problems with obstacle avoidance requirements
and minimum time trajectory generation problems. The algorithms use fewer
binary variables than standard MILP methods and require less computational
effort.


title:
Estimacao Temporal da Deformacao entre Objectos utilizando uma
  Metodologia Fisica

abstract:
  In this paper, it is presented a methodology to estimate the deformation
involved between two objects attending to its physical properties. This
methodology can be used, for example, in Computational Vision or Computer
Graphics applications, and consists in physically modeling the objects, by
means of the Finite Elements Method, establishing correspondences between some
of its data points, by using Modal Matching, and finally, determining the
displacement field, that is the intermediate shapes, through the resolution of
the Lagrange Dynamic Equilibrium Equation. As in many of the possible
applications of the methodology to present, it is necessary to quantify the
existing deformation, as well as to estimate only the non rigid component of
the involved global deformation. The solutions adopted to satisfy such
intentions will be also presented.


title: Separating a Real-Life Nonlinear Image Mixture

abstract:
  When acquiring an image of a paper document, the image printed on the back
page sometimes shows through. The mixture of the front- and back-page images
thus obtained is markedly nonlinear, and thus constitutes a good real-life test
case for nonlinear blind source separation.
  This paper addresses a difficult version of this problem, corresponding to
the use of "onion skin" paper, which results in a relatively strong
nonlinearity of the mixture, which becomes close to singular in the lighter
regions of the images. The separation is achieved through the MISEP technique,
which is an extension of the well known INFOMAX method. The separation results
are assessed with objective quality measures. They show an improvement over the
results obtained with linear separation, but have room for further improvement.


title:
A T Step Ahead Optimal Target Detection Algorithm for a Multi Sensor
  Surveillance System

abstract:
  This paper presents a methodology for optimal target detection in a multi
sensor surveillance system. The system consists of mobile sensors that guard a
rectangular surveillance zone crisscrossed by moving targets. Targets percolate
the surveillance zone in a poisson fashion with uniform velocities. Under these
statistics this paper computes a motion strategy for a sensor that maximizes
target detections for the next T time steps. A coordination mechanism between
sensors ensures that overlapping areas between sensors is reduced. This
coordination mechanism is interleaved with the motion strategy computation to
reduce detections of the same target by more than one sensor. To avoid an
exhaustive search in the joint space of all sensors the coordination mechanism
constraints the search by assigning priorities to the sensors. A comparison of
this methodology with other multi target tracking schemes verifies its efficacy
in maximizing detections. A tabulation of these comparisons is reported in
results section of the paper


title: Optimum Signal Linear Detector in the Discrete Wavelet Transform-Domain

abstract:
  The problem of known signal detection in Additive White Gaussian Noise is
considered. In this paper a new detection algorithm based on Discrete Wavelet
Transform pre-processing and threshold comparison is introduced. Current
approaches described in [7] use the maximum value obtained in the wavelet
domain for decision. Here, we use all available information in the wavelet
domain with excellent results. Detector performance is presented in Probability
of detection curves for a fixed probability of false alarm.


title: A Simple Proof of the F{\'a}ry-Wagner Theorem

abstract:
  We give a simple proof of the following fundamental result independently due
to Fary (1948) and Wagner (1936): Every plane graph has a drawing in which
every edge is straight.


title:
Improved Combinatorial Group Testing Algorithms for Real-World Problem
  Sizes

abstract:
  We study practically efficient methods for performing combinatorial group
testing. We present efficient non-adaptive and two-stage combinatorial group
testing algorithms, which identify the at most d items out of a given set of n
items that are defective, using fewer tests for all practical set sizes. For
example, our two-stage algorithm matches the information theoretic lower bound
for the number of tests in a combinatorial group testing regimen.


title:
Fading-Resilient Super-Orthogonal Space-Time Signal Sets: Can Good
  Constellations Survive in Fading?

abstract:
  In this correspondence, first-tier indirect (direct) discernible
constellation expansions are defined for generalized orthogonal designs. The
expanded signal constellation, leading to so-called super-orthogonal codes,
allows the achievement of coding gains in addition to diversity gains enabled
by orthogonal designs. Conditions that allow the shape of an expanded
multidimensional constellation to be preserved at the channel output, on an
instantaneous basis, are derived. It is further shown that, for such
constellations, the channel alters neither the relative distances nor the
angles between signal points in the expanded signal constellation.


title:
The QDF file format: an electronic system to describe ancient andean
  khipus

abstract:
  With the goal of bringing to reseachers of the ancient andean khipus with a
tool to share and process electronically the current corpus of these ancient
information devices, I present on this paper a proposal for a Quipu Description
Format (QDF), a XML based file format designed to describe such documents in a
systematic and computer standard way.


title:
Sub-Optimum Signal Linear Detector Using Wavelets and Support Vector
  Machines

abstract:
  The problem of known signal detection in Additive White Gaussian Noise is
considered. In previous work, a new detection scheme was introduced by the
authors, and it was demonstrated that optimum performance cannot be reached in
a real implementation. In this paper we analyse Support Vector Machines (SVM)
as an alternative, evaluating the results in terms of Probability of detection
curves for a fixed Probability of false alarm.


title:
Upgrading Pulse Detection with Time Shift Properties Using Wavelets and
  Support Vector Machines

abstract:
  Current approaches in pulse detection use domain transformations so as to
concentrate frequency related information that can be distinguishable from
noise. In real cases we do not know when the pulse will begin, so we need a
time search process in which time windows are scheduled and analysed. Each
window can contain the pulsed signal (either complete or incomplete) and / or
noise. In this paper a simple search process will be introduced, allowing the
algorithm to process more information, upgrading the capabilities in terms of
probability of detection (Pd) and probability of false alarm (Pfa).


title: Wavelet Time Shift Properties Integration with Support Vector Machines

abstract:
  This paper presents a short evaluation about the integration of information
derived from wavelet non-linear-time-invariant (non-LTI) projection properties
using Support Vector Machines (SVM). These properties may give additional
information for a classifier trying to detect known patterns hidden by noise.
In the experiments we present a simple electromagnetic pulsed signal
recognition scheme, where some improvement is achieved with respect to previous
work. SVMs are used as a tool for information integration, exploiting some
unique properties not easily found in neural networks.


title: The Partition Weight Enumerator of MDS Codes and its Applications

abstract:
  A closed form formula of the partition weight enumerator of maximum distance
separable (MDS) codes is derived for an arbitrary number of partitions. Using
this result, some properties of MDS codes are discussed. The results are
extended for the average binary image of MDS codes in finite fields of
characteristic two. As an application, we study the multiuser error probability
of Reed Solomon codes.


title: A Verifiable Partial Key Escrow, Based on McCurley Encryption Scheme

abstract:
  In this paper, firstly we propose two new concepts concerning the notion of
key escrow encryption schemes: provable partiality and independency. Roughly
speaking we say that a scheme has provable partiality if existing polynomial
time algorithm for recovering the secret knowing escrowed information implies a
polynomial time algorithm that can solve a well-known intractable problem. In
addition, we say that a scheme is independent if the secret key and the
escrowed information are independent. Finally, we propose a new verifiable
partial key escrow, which has both of above criteria. The new scheme use
McCurley encryption scheme as underlying scheme.


title: Text Compression and Superfast Searching

abstract:
  In this paper, a new compression scheme for text is presented. The same is
efficient in giving high compression ratios and enables super fast searching
within the compressed text. Typical compression ratios of 70-80% and reducing
the search time by 80-85% are the features of this paper. Till now, a trade-off
between high ratios and searchability within compressed text has been seen. In
this paper, we show that greater the compression, faster the search. This finds
applicability in so many places where data as natural language text is present.


title:
Improved Bounds on the Parity-Check Density and Achievable Rates of
  Binary Linear Block Codes with Applications to LDPC Codes

abstract:
  We derive bounds on the asymptotic density of parity-check matrices and the
achievable rates of binary linear block codes transmitted over memoryless
binary-input output-symmetric (MBIOS) channels. The lower bounds on the density
of arbitrary parity-check matrices are expressed in terms of the gap between
the rate of these codes for which reliable communication is achievable and the
channel capacity, and the bounds are valid for every sequence of binary linear
block codes. These bounds address the question, previously considered by Sason
and Urbanke, of how sparse can parity-check matrices of binary linear block
codes be as a function of the gap to capacity. Similarly to a previously
reported bound by Sason and Urbanke, the new lower bounds on the parity-check
density scale like the log of the inverse of the gap to capacity, but their
tightness is improved (except for a binary symmetric/erasure channel, where
they coincide with the previous bound). The new upper bounds on the achievable
rates of binary linear block codes tighten previously reported bounds by
Burshtein et al., and therefore enable to obtain tighter upper bounds on the
thresholds of sequences of binary linear block codes under ML decoding. The
bounds are applied to low-density parity-check (LDPC) codes, and the
improvement in their tightness is exemplified numerically. The upper bounds on
the achievable rates enable to assess the inherent loss in performance of
various iterative decoding algorithms as compared to optimal ML decoding. The
lower bounds on the asymptotic parity-check density are helpful in assessing
the inherent tradeoff between the asymptotic performance of LDPC codes and
their decoding complexity (per iteration) under message-passing decoding.


title:
The Cyborg Astrobiologist: Scouting Red Beds for Uncommon Features with
  Geological Significance

abstract:
  The `Cyborg Astrobiologist' (CA) has undergone a second geological field
trial, at a red sandstone site in northern Guadalajara, Spain, near Riba de
Santiuste. The Cyborg Astrobiologist is a wearable computer and video camera
system that has demonstrated a capability to find uncommon interest points in
geological imagery in real-time in the field. The first (of three) geological
structures that we studied was an outcrop of nearly homogeneous sandstone,
which exhibits oxidized-iron impurities in red and and an absence of these iron
impurities in white. The white areas in these ``red beds'' have turned white
because the iron has been removed by chemical reduction, perhaps by a
biological agent. The computer vision system found in one instance several
(iron-free) white spots to be uncommon and therefore interesting, as well as
several small and dark nodules. The second geological structure contained
white, textured mineral deposits on the surface of the sandstone, which were
found by the CA to be interesting. The third geological structure was a 50 cm
thick paleosol layer, with fossilized root structures of some plants, which
were found by the CA to be interesting. A quasi-blind comparison of the Cyborg
Astrobiologist's interest points for these images with the interest points
determined afterwards by a human geologist shows that the Cyborg Astrobiologist
concurred with the human geologist 68% of the time (true positive rate), with a
32% false positive rate and a 32% false negative rate.
  (abstract has been abridged).

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


title:
Consistent query answers on numerical databases under aggregate
  constraints

abstract:
  The problem of extracting consistent information from relational databases
violating integrity constraints on numerical data is addressed. In particular,
aggregate constraints defined as linear inequalities on aggregate-sum queries
on input data are considered. The notion of repair as consistent set of updates
at attribute-value level is exploited, and the characterization of several
complexity issues related to repairing data and computing consistent query
answers is provided.


title:
A Unified Subspace Outlier Ensemble Framework for Outlier Detection in
  High Dimensional Spaces

abstract:
  The task of outlier detection is to find small groups of data objects that
are exceptional when compared with rest large amount of data. Detection of such
outliers is important for many applications such as fraud detection and
customer migration. Most such applications are high dimensional domains in
which the data may contain hundreds of dimensions. However, the outlier
detection problem itself is not well defined and none of the existing
definitions are widely accepted, especially in high dimensional space. In this
paper, our first contribution is to propose a unified framework for outlier
detection in high dimensional spaces from an ensemble-learning viewpoint. In
our new framework, the outlying-ness of each data object is measured by fusing
outlier factors in different subspaces using a combination function.
Accordingly, we show that all existing researches on outlier detection can be
regarded as special cases in the unified framework with respect to the set of
subspaces considered and the type of combination function used. In addition, to
demonstrate the usefulness of the ensemble-learning based outlier detection
framework, we developed a very simple and fast algorithm, namely SOE1 (Subspace
Outlier Ensemble using 1-dimensional Subspaces) in which only subspaces with
one dimension is used for mining outliers from large categorical datasets. The
SOE1 algorithm needs only two scans over the dataset and hence is very
appealing in real data mining applications. Experimental results on real
datasets and large synthetic datasets show that: (1) SOE1 has comparable
performance with respect to those state-of-art outlier detection algorithms on
identifying true outliers and (2) SOE1 can be an order of magnitude faster than
one of the fastest outlier detection algorithms known so far.


title: EAH: A New Encoder based on Adaptive Variable-length Codes

abstract:
  Adaptive variable-length codes associate a variable-length codeword to the
symbol being encoded depending on the previous symbols in the input string.
This class of codes has been recently presented in [Dragos Trinca,
arXiv:cs.DS/0505007] as a new class of non-standard variable-length codes. New
algorithms for data compression, based on adaptive variable-length codes of
order one and Huffman's algorithm, have been recently presented in [Dragos
Trinca, ITCC 2004]. In this paper, we extend the work done so far by the
following contributions: first, we propose an improved generalization of these
algorithms, called EAHn. Second, we compute the entropy bounds for EAHn, using
the well-known bounds for Huffman's algorithm. Third, we discuss implementation
details and give reports of experimental results obtained on some well-known
corpora. Finally, we describe a parallel version of EAHn using the PRAM model
of computation.


title:
Gossip Codes for Fingerprinting: Construction, Erasure Analysis and
  Pirate Tracing

abstract:
  This work presents two new construction techniques for q-ary Gossip codes
from tdesigns and Traceability schemes. These Gossip codes achieve the shortest
code length specified in terms of code parameters and can withstand erasures in
digital fingerprinting applications. This work presents the construction of
embedded Gossip codes for extending an existing Gossip code into a bigger code.
It discusses the construction of concatenated codes and realisation of erasure
model through concatenated codes.


title: Approximate reasoning for real-time probabilistic processes

abstract:
  We develop a pseudo-metric analogue of bisimulation for generalized
semi-Markov processes. The kernel of this pseudo-metric corresponds to
bisimulation; thus we have extended bisimulation for continuous-time
probabilistic processes to a much broader class of distributions than
exponential distributions. This pseudo-metric gives a useful handle on
approximate reasoning in the presence of numerical information -- such as
probabilities and time -- in the model. We give a fixed point characterization
of the pseudo-metric. This makes available coinductive reasoning principles for
reasoning about distances. We demonstrate that our approach is insensitive to
potentially ad hoc articulations of distance by showing that it is intrinsic to
an underlying uniformity. We provide a logical characterization of this
uniformity using a real-valued modal logic. We show that several quantitative
properties of interest are continuous with respect to the pseudo-metric. Thus,
if two processes are metrically close, then observable quantitative properties
of interest are indeed close.


title:
Multi-Modal Human-Machine Communication for Instructing Robot Grasping
  Tasks

abstract:
  A major challenge for the realization of intelligent robots is to supply them
with cognitive abilities in order to allow ordinary users to program them
easily and intuitively. One way of such programming is teaching work tasks by
interactive demonstration. To make this effective and convenient for the user,
the machine must be capable to establish a common focus of attention and be
able to use and integrate spoken instructions, visual perceptions, and
non-verbal clues like gestural commands. We report progress in building a
hybrid architecture that combines statistical methods, neural networks, and
finite state machines into an integrated system for instructing grasping tasks
by man-machine interaction. The system combines the GRAVIS-robot for visual
attention and gestural instruction with an intelligent interface for speech
recognition and linguistic interpretation, and an modality fusion module to
allow multi-modal task-oriented man-machine communication with respect to
dextrous robot manipulation of objects.


abstract:
  A dissipative particle swarm optimization is developed according to the
self-organization of dissipative structure. The negative entropy is introduced
to construct an opening dissipative system that is far-from-equilibrium so as
to driving the irreversible evolution process with better fitness. The testing
of two multimodal functions indicates it improves the performance effectively


title: Decision Sort and its Parallel Implementation

abstract:
  In this paper, a sorting technique is presented that takes as input a data
set whose primary key domain is known to the sorting algorithm, and works with
an time efficiency of O(n+k), where k is the primary key domain. It is shown
that the algorithm has applicability over a wide range of data sets. Later, a
parallel formulation of the same is proposed and its effectiveness is argued.
Though this algorithm is applicable over a wide range of general data sets, it
finds special application (much superior to others) in places where sorting
information that arrives in parts and in cases where input data is huge in
size.


title: Optimizing semiconductor devices by self-organizing particle swarm

abstract:
  A self-organizing particle swarm is presented. It works in dissipative state
by employing the small inertia weight, according to experimental analysis on a
simplified model, which with fast convergence. Then by recognizing and
replacing inactive particles according to the process deviation information of
device parameters, the fluctuation is introduced so as to driving the
irreversible evolution process with better fitness. The testing on benchmark
functions and an application example for device optimization with designed
fitness function indicates it improves the performance effectively.


title:
Handling equality constraints by adaptive relaxing rule for swarm
  algorithms

abstract:
  The adaptive constraints relaxing rule for swarm algorithms to handle with
the problems with equality constraints is presented. The feasible space of such
problems may be similiar to ridge function class, which is hard for applying
swarm algorithms. To enter the solution space more easily, the relaxed quasi
feasible space is introduced and shrinked adaptively. The experimental results
on benchmark functions are compared with the performance of other algorithms,
which show its efficiency.


title:
Handling boundary constraints for numerical optimization by particle
  swarm flying in periodic search space

abstract:
  The periodic mode is analyzed together with two conventional boundary
handling modes for particle swarm. By providing an infinite space that
comprises periodic copies of original search space, it avoids possible
disorganizing of particle swarm that is induced by the undesired mutations at
the boundary. The results on benchmark functions show that particle swarm with
periodic mode is capable of improving the search performance significantly, by
compared with that of conventional modes and other algorithms.


title: SWAF: Swarm Algorithm Framework for Numerical Optimization

abstract:
  A swarm algorithm framework (SWAF), realized by agent-based modeling, is
presented to solve numerical optimization problems. Each agent is a bare bones
cognitive architecture, which learns knowledge by appropriately deploying a set
of simple rules in fast and frugal heuristics. Two essential categories of
rules, the generate-and-test and the problem-formulation rules, are
implemented, and both of the macro rules by simple combination and subsymbolic
deploying of multiple rules among them are also studied. Experimental results
on benchmark problems are presented, and performance comparison between SWAF
and other existing algorithms indicates that it is efficiently.


title: Summarization Techniques for Pattern Collections in Data Mining

abstract:
  Discovering patterns from data is an important task in data mining. There
exist techniques to find large collections of many kinds of patterns from data
very efficiently. A collection of patterns can be regarded as a summary of the
data. A major difficulty with patterns is that pattern collections summarizing
the data well are often very large.
  In this dissertation we describe methods for summarizing pattern collections
in order to make them also more understandable. More specifically, we focus on
the following themes: 1) Quality value simplifications. 2) Pattern orderings.
3) Pattern chains and antichains. 4) Change profiles. 5) Inverse pattern
discovery.


title: Steganographic Codes -- a New Problem of Coding Theory

abstract:
  To study how to design steganographic algorithm more efficiently, a new
coding problem -- steganographic codes (abbreviated stego-codes) -- is
presented in this paper. The stego-codes are defined over the field with
$q(q\ge2)$ elements. Firstly a method of constructing linear stego-codes is
proposed by using the direct sum of vector subspaces. And then the problem of
linear stego-codes is converted to an algebraic problem by introducing the
concept of $t$th dimension of vector space. And some bounds on the length of
stego-codes are obtained, from which the maximum length embeddable (MLE) code
is brought up. It is shown that there is a corresponding relation between MLE
codes and perfect error-correcting codes. Furthermore the classification of all
MLE codes and a lower bound on the number of binary MLE codes are obtained
based on the corresponding results on perfect codes. Finally hiding redundancy
is defined to value the performance of stego-codes.


title: Reasoning about transfinite sequences

abstract:
  We introduce a family of temporal logics to specify the behavior of systems
with Zeno behaviors. We extend linear-time temporal logic LTL to authorize
models admitting Zeno sequences of actions and quantitative temporal operators
indexed by ordinals replace the standard next-time and until future-time
operators. Our aim is to control such systems by designing controllers that
safely work on $\omega$-sequences but interact synchronously with the system in
order to restrict their behaviors. We show that the satisfiability problem for
the logics working on $\omega^k$-sequences is EXPSPACE-complete when the
integers are represented in binary, and PSPACE-complete with a unary
representation. To do so, we substantially extend standard results about LTL by
introducing a new class of succinct ordinal automata that can encode the
interaction between the different quantitative temporal operators.