title: The Average Size of Giant Components Between the Double-Jump

abstract: We study the sizes of connected components according to their excesses during a random graph process built with $n$ vertices. The considered model is the continuous one defined in Janson 2000. An ${\ell}$-component is a connected component with ${\ell}$ edges more than vertices. $\ell$ is also called the \textit{excess} of such component. As our main result, we show that when $\ell$ and ${n \over \ell}$ are both large, the expected number of vertices that ever belong to an $\ell$-component is about ${12}^{1/3} {\ell}^{1/3} n^{2/3}$. We also obtain limit theorems for the number of creations of $\ell$-components.


title: Craig's Interpolation Theorem formalised and mechanised in Isabelle/HOL

abstract: We formalise and mechanise a construtive, proof theoretic proof of Craig's Interpolation Theorem in Isabelle/HOL. We give all the definitions and lemma statements both formally and informally. We also transcribe informally the formal proofs. We detail the main features of our mechanisation, such as the formalisation of binding for first order formulae. We also give some applications of Craig's Interpolation Theorem.


title: Creation and Growth of Components in a Random Hypergraph Process

abstract: Denote by an $\ell$-component a connected $b$-uniform hypergraph with $k$ edges and $k(b-1) - \ell$ vertices. We prove that the expected number of creations of $\ell$-component during a random hypergraph process tends to 1 as $\ell$ and $b$ tend to $\infty$ with the total number of vertices $n$ such that $\ell = o(\sqrt[3]{\frac{n}{b}})$. Under the same conditions, we also show that the expected number of vertices that ever belong to an $\ell$-component is approximately $12^{1/3} (b-1)^{1/3} \ell^{1/3} n^{2/3}$. As an immediate consequence, it follows that with high probability the largest $\ell$-component during the process is of size $O((b-1)^{1/3} \ell^{1/3} n^{2/3})$. Our results give insight about the size of giant components inside the phase transition of random hypergraphs.


title: Circle Formation of Weak Mobile Robots

abstract: In this paper we prove the conjecture of D\'{e}fago & Konagaya. Furthermore, we describe a deterministic protocol for forming a regular n-gon in finite time.


title: On Some Peculiarities of Dynamic Switch between Component Implementations in an Autonomic Computing System

abstract: Behavior of the delta algorithm of autonomic switch between two component implementations is considered on several examples of a client-server systems involving, in particular, periodic change of intensities of requests for the component. It is shown that in the cases of some specific combinations of elementary requests costs, the number of clients in the system, the number of requests per unit of time, and the cost of switch between the implementations, the algorithm may reveal behavior that is rather far from the desired. A sufficient criterion of a success of the algorithm is proposed based on the analysis of the accumulated implementations costs difference as a function of time. Suggestions are pointed out of practical evaluation of the algorithm functioning regarding the observations made in this paper.


title: Get out the vote: Determining support or opposition from Congressional floor-debate transcripts

abstract: We investigate whether one can determine from the transcripts of U.S. Congressional floor debates whether the speeches represent support of or opposition to proposed legislation. To address this problem, we exploit the fact that these speeches occur as part of a discussion; this allows us to use sources of information regarding relationships between discourse segments, such as whether a given utterance indicates agreement with the opinion expressed by another. We find that the incorporation of such information yields substantial improvements over classifying speeches in isolation.


title: Prioritizing Software Inspection Results using Static Profiling

abstract: Static software checking tools are useful as an additional automated software inspection step that can easily be integrated in the development cycle and assist in creating secure, reliable and high quality code. However, an often quoted disadvantage of these tools is that they generate an overly large number of warnings, including many false positives due to the approximate analysis techniques. This information overload effectively limits their usefulness. In this paper we present ELAN, a technique that helps the user prioritize the information generated by a software inspection tool, based on a demand-driven computation of the likelihood that execution reaches the locations for which warnings are reported. This analysis is orthogonal to other prioritization techniques known from literature, such as severity levels and statistical analysis to reduce false positives. We evaluate feasibility of our technique using a number of case studies and assess the quality of our predictions by comparing them to actual values obtained by dynamic profiling.


title: How to Find Good Finite-Length Codes: From Art Towards Science

abstract: We explain how to optimize finite-length LDPC codes for transmission over the binary erasure channel. Our approach relies on an analytic approximation of the erasure probability. This is in turn based on a finite-length scaling result to model large scale erasures and a union bound involving minimal stopping sets to take into account small error events. We show that the performances of optimized ensembles as observed in simulations are well described by our approximation. Although we only address the case of transmission over the binary erasure channel, our method should be applicable to a more general setting.


title: Decomposable Theories

abstract: We present in this paper a general algorithm for solving first-order formulas in particular theories called "decomposable theories". First of all, using special quantifiers, we give a formal characterization of decomposable theories and show some of their properties. Then, we present a general algorithm for solving first-order formulas in any decomposable theory "T". The algorithm is given in the form of five rewriting rules. It transforms a first-order formula "P", which can possibly contain free variables, into a conjunction "Q" of solved formulas easily transformable into a Boolean combination of existentially quantified conjunctions of atomic formulas. In particular, if "P" has no free variables then "Q" is either the formula "true" or "false". The correctness of our algorithm proves the completeness of the decomposable theories. Finally, we show that the theory "Tr" of finite or infinite trees is a decomposable theory and give some benchmarks realized by an implementation of our algorithm, solving formulas on two-partner games in "Tr" with more than 160 nested alternated quantifiers.


title: Generalized h-index for Disclosing Latent Facts in Citation Networks

abstract: What is the value of a scientist and its impact upon the scientific thinking? How can we measure the prestige of a journal or of a conference? The evaluation of the scientific work of a scientist and the estimation of the quality of a journal or conference has long attracted significant interest, due to the benefits from obtaining an unbiased and fair criterion. Although it appears to be simple, defining a quality metric is not an easy task. To overcome the disadvantages of the present metrics used for ranking scientists and journals, J.E. Hirsch proposed a pioneering metric, the now famous h-index. In this article, we demonstrate several inefficiencies of this index and develop a pair of generalizations and effective variants of it to deal with scientist ranking and with publication forum ranking. The new citation indices are able to disclose trendsetters in scientific research, as well as researchers that constantly shape their field with their influential work, no matter how old they are. We exhibit the effectiveness and the benefits of the new indices to unfold the full potential of the h-index, with extensive experimental results obtained from DBLP, a widely known on-line digital library.


title: Competing with stationary prediction strategies

abstract: In this paper we introduce the class of stationary prediction strategies and construct a prediction algorithm that asymptotically performs as well as the best continuous stationary strategy. We make mild compactness assumptions but no stochastic assumptions about the environment. In particular, no assumption of stationarity is made about the environment, and the stationarity of the considered strategies only means that they do not depend explicitly on time; we argue that it is natural to consider only stationary strategies even for highly non-stationary environments.


title: Computation of the Weight Distribution of CRC Codes

abstract: In this article, we illustrate an algorithm for the computation of the weight distribution of CRC codes. The recursive structure of CRC codes will give us an iterative way to compute the weight distribution of their dual codes starting from just some ``representative'' words. Thanks to MacWilliams Theorem, the computation of the weight distribution of dual codes can be easily brought back to that of CRC codes. This algorithm is a good alternative to the standard algorithm that involves listing every word of the code.


title: The B-Exponential Map: A Generalization of the Logistic Map, and Its Applications In Generating Pseudo-random Numbers

abstract: A 1-dimensional generalization of the well known Logistic Map is proposed. The proposed family of maps is referred to as the B-Exponential Map. The dynamics of this map are analyzed and found to have interesting properties. In particular, the B-Exponential Map exhibits robust chaos for all real values of the parameter B >= e^(-4). We then propose a pseudo-random number generator based on the B-Exponential Map by chaotically hopping between different trajectories for different values of B. We call this BEACH (B-Exponential All-Chaotic Map Hopping) pseudo-random number generator. BEACH successfully passes stringent statistical randomness tests such as ENT, NIST and Diehard. An implementation of BEACH is also outlined.


title: Citation as a Representation Process

abstract: The presented work proposes a novel approach to model the citation rate. The paper begins with a brief introduction into informetrics studies and highlights drawbacks of the contemporary approaches to modeling the citation process as a product of social interactions. An alternative modeling framework based on results obtained in cognitive psychology is then introduced and applied in an experiment to investigate properties of the citation process, as they are revealed by a large collection of citation statistics. Major research findings are discussed, and a summary is given.


title: Islands for SAT

abstract: In this note we introduce the notion of islands for restricting local search. We show how we can construct islands for CNF SAT problems, and how much search space can be eliminated by restricting search to the island.


title: Effect of Interface Style in Peer Review Comments for UML Designs

abstract: This paper presents our evaluation of using a Tablet-PC to provide peer-review comments in the first year Computer Science course. Our exploration consisted of an evaluation of how students write comments on other students' assignments using three different methods: pen and paper, a Tablet-PC, and a desktop computer. Our ultimate goal is to explore the effect that interface style (Tablet vs. Desktop) has on the quality and quantity of the comments provided.


title: Counting good truth assignments of random k-SAT formulae

abstract: We present a deterministic approximation algorithm to compute logarithm of the number of `good' truth assignments for a random k-satisfiability (k-SAT) formula in polynomial time (by `good' we mean that violate a small fraction of clauses). The relative error is bounded above by an arbitrarily small constant epsilon with high probability as long as the clause density (ratio of clauses to variables) alpha<alpha_{u}(k) = 2k^{-1}\log k(1+o(1)). The algorithm is based on computation of marginal distribution via belief propagation and use of an interpolation procedure. This scheme substitutes the traditional one based on approximation of marginal probabilities via MCMC, in conjunction with self-reduction, which is not easy to extend to the present problem. We derive 2k^{-1}\log k (1+o(1)) as threshold for uniqueness of the Gibbs distribution on satisfying assignment of random infinite tree k-SAT formulae to establish our results, which is of interest in its own right.


title: On Construction of the (24,12,8) Golay Codes

abstract: Two product array codes are used to construct the (24, 12, 8) binary Golay code through the direct sum operation. This construction provides a systematic way to find proper (8, 4, 4) linear block component codes for generating the Golay code, and it generates and extends previously existing methods that use a similar construction framework. The code constructed is simple to decode.


title: On entropy for mixtures of discrete and continuous variables

abstract: Let $X$ be a discrete random variable with support $S$ and $f : S \to S^\prime$ be a bijection. Then it is well-known that the entropy of $X$ is the same as the entropy of $f(X)$. This entropy preservation property has been well-utilized to establish non-trivial properties of discrete stochastic processes, e.g. queuing process \cite{prg03}. Entropy as well as entropy preservation is well-defined only in the context of purely discrete or continuous random variables. However for a mixture of discrete and continuous random variables, which arise in many interesting situations, the notions of entropy and entropy preservation have not been well understood. In this paper, we extend the notion of entropy in a natural manner for a mixed-pair random variable, a pair of random variables with one discrete and the other continuous. Our extensions are consistent with the existing definitions of entropy in the sense that there exist natural injections from discrete or continuous random variables into mixed-pair random variables such that their entropy remains the same. This extension of entropy allows us to obtain sufficient conditions for entropy preservation in mixtures of discrete and continuous random variables under bijections. The extended definition of entropy leads to an entropy rate for continuous time Markov chains. As an application, we recover a known probabilistic result related to Poisson process. We strongly believe that the frame-work developed in this paper can be useful in establishing probabilistic properties of complex processes, such as load balancing systems, queuing network, caching algorithms.


title: Capacity of Cooperative Fusion in the Presence of Byzantine Sensors

abstract: The problem of cooperative fusion in the presence of Byzantine sensors is considered. An information theoretic formulation is used to characterize the Shannon capacity of sensor fusion. It is shown that when less than half of the sensors are Byzantine, the effect of Byzantine attack can be entirely mitigated, and the fusion capacity is identical to that when all sensors are honest. But when at least half of the sensors are Byzantine, they can completely defeat the sensor fusion so that no information can be transmitted reliably. A capacity achieving transmit-then-verify strategy is proposed for the case that less than half of the sensors are Byzantine, and its error probability and coding rate is analyzed by using a Markov decision process modeling of the transmission protocol.


title: Fault-Tolerant Real-Time Streaming with FEC thanks to Capillary Multi-Path Routing

abstract: Erasure resilient FEC codes in off-line packetized streaming rely on time diversity. This requires unrestricted buffering time at the receiver. In real-time streaming the playback buffering time must be very short. Path diversity is an orthogonal strategy. However, the large number of long paths increases the number of underlying links and consecutively the overall link failure rate. This may increase the overall requirement in redundant FEC packets for combating the link failures. We introduce the Redundancy Overall Requirement (ROR) metric, a routing coefficient specifying the total number of FEC packets required for compensation of all underlying link failures. We present a capillary routing algorithm for constructing layer by layer steadily diversifying multi-path routing patterns. By measuring the ROR coefficients of a dozen of routing layers on hundreds of network samples, we show that the number of required FEC packets decreases substantially when the path diversity is increased by the capillary routing construction algorithm.


title: Complex Lattice Reduction Algorithm for Low-Complexity MIMO Detection

abstract: Recently, lattice-reduction-aided detectors have been proposed for multiple-input multiple-output (MIMO) systems to give performance with full diversity like maximum likelihood receiver, and yet with complexity similar to linear receivers. However, these lattice-reduction-aided detectors are based on the traditional LLL reduction algorithm that was originally introduced for reducing real lattice bases, in spite of the fact that the channel matrices are inherently complex-valued. In this paper, we introduce the complex LLL algorithm for direct application to reduce the basis of a complex lattice which is naturally defined by a complex-valued channel matrix. We prove that complex LLL reduction-aided detection can also achieve full diversity. Our analysis reveals that the new complex LLL algorithm can achieve a reduction in complexity of nearly 50% over the traditional LLL algorithm, and this is confirmed by simulation. It is noteworthy that the complex LLL algorithm aforementioned has nearly the same bit-error-rate performance as the traditional LLL algorithm.


title: Length-based cryptanalysis: The case of Thompson's Group

abstract: The length-based approach is a heuristic for solving randomly generated equations in groups which possess a reasonably behaved length function. We describe several improvements of the previously suggested length-based algorithms, that make them applicable to Thompson's group with significant success rates. In particular, this shows that the Shpilrain-Ushakov public key cryptosystem based on Thompson's group is insecure, and suggests that no practical public key cryptosystem based on this group can be secure.


title: New Model of Internet Topology Using k-shell Decomposition

abstract: We introduce and use k-shell decomposition to investigate the topology of the Internet at the AS level. Our analysis separates the Internet into three sub-components: (a) a nucleus which is a small (~100 nodes) very well connected globally distributed subgraph; (b) a fractal sub-component that is able to connect the bulk of the Internet without congesting the nucleus, with self similar properties and critical exponents; and (c) dendrite-like structures, usually isolated nodes that are connected to the rest of the network through the nucleus only. This unique decomposition is robust, and provides insight into the underlying structure of the Internet and its functional consequences. Our approach is general and useful also when studying other complex networks.


title: Syst\`{e}me de repr\'{e}sentation d'aide au besoin dans le domaine architectural

abstract: The image is a very important mean of communication in the field of architectural who intervenes in the various phases of the design of a project. It can be regarded as a tool of decision-making aid. The study of our research aims at to see the contribution of the Economic Intelligence in the resolution of a decisional problem of the various partners (Architect, Contractor, Customer) in the architectural field, in order to make strategic decisions within the framework of the realization or design of an architectural work. The economic Intelligence allows the taking into account of the real needs for the user-decision makers, so that their waiting are considered at the first stage of a search for information and not in the final stage of the development of the tool in the evaluation of this last.


title: Well quasi-orders and the shuffle closure of finite sets

abstract: Given a set I of word, the set of all words obtained by the shuffle of (copies of) words of I is naturally provided with a partial order. In [FS05], the authors have opened the problem of the characterization of the finite sets I such that the order is a well quasi-order . In this paper we give an answer in the case when I consists of a single word w.


title: Mathematical Modelling of the Thermal Accumulation in Hot Water Solar Systems

abstract: Mathematical modelling and defining useful recommendations for construction and regimes of exploitation for hot water solar installation with thermal stratification is the main purpose of this work. A special experimental solar module for hot water was build and equipped with sufficient measure apparatus. The main concept of investigation is to optimise the stratified regime of thermal accumulation and constructive parameters of heat exchange equipment (heat serpentine in tank). Accumulation and heat exchange processes were investigated by theoretical end experimental means. Special mathematical model was composed to simulate the energy transfer in stratified tank. Computer program was developed to solve mathematical equations for thermal accumulation and energy exchange. Extensive numerical and experimental tests were carried out. A good correspondence between theoretical and experimental data was arrived. Keywords: Mathematical modelling, accumulation


title: About Norms and Causes

abstract: Knowing the norms of a domain is crucial, but there exist no repository of norms. We propose a method to extract them from texts: texts generally do not describe a norm, but rather how a state-of-affairs differs from it. Answers concerning the cause of the state-of-affairs described often reveal the implicit norm. We apply this idea to the domain of driving, and validate it by designing algorithms that identify, in a text, the "basic" norms to which it refers implicitly.


title: Using Pseudo-Stochastic Rational Languages in Probabilistic Grammatical Inference

abstract: In probabilistic grammatical inference, a usual goal is to infer a good approximation of an unknown distribution P called a stochastic language. The estimate of P stands in some class of probabilistic models such as probabilistic automata (PA). In this paper, we focus on probabilistic models based on multiplicity automata (MA). The stochastic languages generated by MA are called rational stochastic languages; they strictly include stochastic languages generated by PA; they also admit a very concise canonical representation. Despite the fact that this class is not recursively enumerable, it is efficiently identifiable in the limit by using the algorithm DEES, introduced by the authors in a previous paper. However, the identification is not proper and before the convergence of the algorithm, DEES can produce MA that do not define stochastic languages. Nevertheless, it is possible to use these MA to define stochastic languages. We show that they belong to a broader class of rational series, that we call pseudo-stochastic rational languages. The aim of this paper is twofold. First we provide a theoretical study of pseudo-stochastic rational languages, the languages output by DEES, showing for example that this class is decidable within polynomial time. Second, we have carried out a lot of experiments in order to compare DEES to classical inference algorithms such as ALERGIA and MDI. They show that DEES outperforms them in most cases.


title: Representing Knowledge about Norms

abstract: Norms are essential to extend inference: inferences based on norms are far richer than those based on logical implications. In the recent decades, much effort has been devoted to reason on a domain, once its norms are represented. How to extract and express those norms has received far less attention. Extraction is difficult: as the readers are supposed to know them, the norms of a domain are seldom made explicit. For one thing, extracting norms requires a language to represent them, and this is the topic of this paper. We apply this language to represent norms in the domain of driving, and show that it is adequate to reason on the causes of accidents, as described by car-crash reports.


title: Un filtre temporel cr\'edibiliste pour la reconnaissance d'actions humaines dans les vid\'eos

abstract: In the context of human action recognition in video sequences, a temporal belief filter is presented. It allows to cope with human action disparity and low quality videos. The whole system of action recognition is based on the Transferable Belief Model (TBM) proposed by P. Smets. The TBM allows to explicitly model the doubt between actions. Furthermore, the TBM emphasizes the conflict which is exploited for action recognition. The filtering performance is assessed on real video sequences acquired by a moving camera and under several unknown view angles.


Using Answer Set Programming in an Inference-Based approach to Natural Language Semantics


title: Superregular Matrices and the Construction of Convolutional Codes having a Maximum Distance Profile

abstract: Superregular matrices are a class of lower triangular Toeplitz matrices that arise in the context of constructing convolutional codes having a maximum distance profile. These matrices are characterized by the property that no submatrix has a zero determinant unless it is trivially zero due to the lower triangular structure. In this paper, we discuss how superregular matrices may be used to construct codes having a maximum distance profile. We also introduce group actions that preserve the superregularity property and present an upper bound on the minimum size a finite field must have in order that a superregular matrix of a given size can exist over that field.


title: Neural Networks with Complex and Quaternion Inputs

abstract: This article investigates Kak neural networks, which can be instantaneously trained, for complex and quaternion inputs. The performance of the basic algorithm has been analyzed and shown how it provides a plausible model of human perception and understanding of images. The motivation for studying quaternion inputs is their use in representing spatial rotations that find applications in computer graphics, robotics, global navigation, computer vision and the spatial orientation of instruments. The problem of efficient mapping of data in quaternion neural networks is examined. Some problems that need to be addressed before quaternion neural networks find applications are identified.


title: Finite element method for thermal analysis of concentrating solar receivers

abstract: Application of finite element method and heat conductivity transfer model for calculation of temperature distribution in receiver for dish-Stirling concentrating solar system is described. The method yields discretized equations that are entirely local to the elements and provides complete geometric flexibility. A computer program solving the finite element method problem is created and great number of numerical experiments is carried out. Illustrative numerical results are given for an array of triangular elements in receiver for dish-Stirling system.


title: Representing graphs as the intersection of axis-parallel cubes

abstract: A unit cube in $k$ dimensional space (or \emph{$k$-cube} in short) is defined as the Cartesian product $R_1\times R_2\times...\times R_k$ where $R_i$(for $1\leq i\leq k$) is a closed interval of the form $[a_i,a_i+1]$ on the real line. A $k$-cube representation of a graph $G$ is a mapping of the vertices of $G$ to $k$-cubes such that two vertices in $G$ are adjacent if and only if their corresponding $k$-cubes have a non-empty intersection. The \emph{cubicity} of $G$, denoted as $\cubi(G)$, is the minimum $k$ such that $G$ has a $k$-cube representation. Roberts \cite{Roberts} showed that for any graph $G$ on $n$ vertices, $\cubi(G)\leq 2n/3$. Many NP-complete graph problems have polynomial time deterministic algorithms or have good approximation ratios in graphs of low cubicity. In most of these algorithms, computing a low dimensional cube representation of the given graph is usually the first step. We present an efficient algorithm to compute the $k$-cube representation of $G$ with maximum degree $\Delta$ in $O(\Delta \ln b)$ dimensions where $b$ is the bandwidth of $G$. Bandwidth of $G$ is at most $n$ and can be much lower. The algorithm takes as input a bandwidth ordering of the vertices in $G$. Though computing the bandwidth ordering of vertices for a graph is NP-hard, there are heuristics that perform very well in practice. Even theoretically, there is an $O(\log^4 n)$ approximation algorithm for computing the bandwidth ordering of a graph using which our algorithm can produce a $k$-cube representation of any given graph in $k=O(\Delta(\ln b + \ln\ln n))$ dimensions. Both the bounds on cubicity are shown to be tight upto a factor of $O(\log\log n)$.


title: An Elegant Argument that P is not NP

abstract: In this note, we present an elegant argument that P is not NP by demonstrating that the Meet-in-the-Middle algorithm must have the fastest running-time of all deterministic and exact algorithms which solve the SUBSET-SUM problem on a classical computer.


title: Upright-Quad Drawing of st-Planar Learning Spaces

abstract: We consider graph drawing algorithms for learning spaces, a type of st-oriented partial cube derived from antimatroids and used to model states of knowledge of students. We show how to draw any st-planar learning space so all internal faces are convex quadrilaterals with the bottom side horizontal and the left side vertical, with one minimal and one maximal vertex. Conversely, every such drawing represents an st-planar learning space. We also describe connections between these graphs and arrangements of translates of a quadrant.


title: Gallager's Exponent for MIMO Channels: A Reliability-Rate Tradeoff

abstract: In this paper, we derive Gallager's random coding error exponent for multiple-input multiple-output (MIMO) channels, assuming no channel-state information (CSI) at the transmitter and perfect CSI at the receiver. This measure gives insight into a fundamental tradeoff between the communication reliability and information rate of MIMO channels, enabling to determine the required codeword length to achieve a prescribed error probability at a given rate below the channel capacity. We quantify the effects of the number of antennas, channel coherence time, and spatial fading correlation on the MIMO exponent. In addition, general formulae for the ergodic capacity and the cutoff rate in the presence of spatial correlation are deduced from the exponent expressions. These formulae are applicable to arbitrary structures of transmit and receive correlation, encompassing all the previously known results as special cases of our expressions.


title: Logical settings for concept learning from incomplete examples in First Order Logic

abstract: We investigate here concept learning from incomplete examples. Our first purpose is to discuss to what extent logical learning settings have to be modified in order to cope with data incompleteness. More precisely we are interested in extending the learning from interpretations setting introduced by L. De Raedt that extends to relational representations the classical propositional (or attribute-value) concept learning from examples framework. We are inspired here by ideas presented by H. Hirsh in a work extending the Version space inductive paradigm to incomplete data. H. Hirsh proposes to slightly modify the notion of solution when dealing with incomplete examples: a solution has to be a hypothesis compatible with all pieces of information concerning the examples. We identify two main classes of incompleteness. First, uncertainty deals with our state of knowledge concerning an example. Second, generalization (or abstraction) deals with what part of the description of the example is sufficient for the learning purpose. These two main sources of incompleteness can be mixed up when only part of the useful information is known. We discuss a general learning setting, referred to as "learning from possibilities" that formalizes these ideas, then we present a more specific learning setting, referred to as "assumption-based learning" that cope with examples which uncertainty can be reduced when considering contextual information outside of the proper description of the examples. Assumption-based learning is illustrated on a recent work concerning the prediction of a consensus secondary structure common to a set of RNA sequences.


title: Dynamic Packet Aggregation to Solve Performance Anomaly in 802.11 Wireless Networks

abstract: In the widely used 802.11 standard, the so called performance anomaly is a well known issue. Several works have tried to solve this problem by introducing mechanisms such as packet fragmentation, backoff adaptation, or packet aggregation during a fixed time interval. In this paper, we propose a novel approach solving the performance anomaly problem by packet aggregation using a dynamic time interval, which depends on the busy time of the wireless medium. Our solution differs from other proposition in the literature because of this dynamic time interval, which allows increasing fairness, reactivity, and in some cases efficiency. In this article, we emphasize the performance evaluation of our proposal.


title: List decoding of noisy Reed-Muller-like codes

abstract: First- and second-order Reed-Muller (RM(1) and RM(2), respectively) codes are two fundamental error-correcting codes which arise in communication as well as in probabilistically-checkable proofs and learning. In this paper, we take the first steps toward extending the quick randomized decoding tools of RM(1) into the realm of quadratic binary and, equivalently, Z_4 codes. Our main algorithmic result is an extension of the RM(1) techniques from Goldreich-Levin and Kushilevitz-Mansour algorithms to the Hankel code, a code between RM(1) and RM(2). That is, given signal s of length N, we find a list that is a superset of all Hankel codewords phi with dot product to s at least (1/sqrt(k)) times the norm of s, in time polynomial in k and log(N). We also give a new and simple formulation of a known Kerdock code as a subcode of the Hankel code. As a corollary, we can list-decode Kerdock, too. Also, we get a quick algorithm for finding a sparse Kerdock approximation. That is, for k small compared with 1/sqrt{N} and for epsilon > 0, we find, in time polynomial in (k log(N)/epsilon), a k-Kerdock-term approximation s~ to s with Euclidean error at most the factor (1+epsilon+O(k^2/sqrt{N})) times that of the best such approximation.


title: Degrees of Freedom Region for the MIMO X Channel

abstract: We provide achievability as well as converse results for the degrees of freedom region of a MIMO $X$ channel, i.e., a system with two transmitters, two receivers, each equipped with multiple antennas, where independent messages need to be conveyed over fixed channels from each transmitter to each receiver. With M=1 antennas at each node, we find that the total (sum rate) degrees of freedom are bounded above and below as $1 \leq\eta_X^\star \leq {4/3}$. If $M>1$ and channel matrices are non-degenerate then the precise degrees of freedom $\eta_X^\star = {4/3}M$. Simple zero forcing without dirty paper encoding or successive decoding, suffices to achieve the ${4/3}M$ degrees of freedom. With equal number of antennas at all nodes, we explore the increase in degrees of freedom when some of the messages are made available to a transmitter or receiver in the manner of cognitive radio. With a cognitive transmitter we show that the number of degrees of freedom $\eta = {3/2}M$ (for $M>1$) on the MIMO $X$ channel. The same degrees of freedom are obtained on the MIMO $X$ channel with a cognitive receiver as well. In contrast to the $X$ channel result, we show that for the MIMO \emph{interference} channel, the degrees of freedom are not increased even if both the transmitter and the receiver of one user know the other user's message. However, the interference channel can achieve the full $2M$ degrees of freedom if \emph{each} user has either a cognitive transmitter or a cognitive receiver. Lastly, if the channels vary with time/frequency then the $X$ channel with single antennas $(M=1)$ at all nodes has exactly 4/3 degrees of freedom with no shared messages and exactly 3/2 degrees of freedom with a cognitive transmitter or a cognitive receiver.


title: New Upper Bounds on The Approximability of 3D Strip Packing

abstract: In this paper, we study the 3D strip packing problem in which we are given a list of 3-dimensional boxes and required to pack all of them into a 3-dimensional strip with length 1 and width 1 and unlimited height to minimize the height used. Our results are below: i) we give an approximation algorithm with asymptotic worst-case ratio 1.69103, which improves the previous best bound of $2+\epsilon$ by Jansen and Solis-Oba of SODA 2006; ii) we also present an asymptotic PTAS for the case in which all items have {\em square} bases.


title: Deriving Escape Analysis by Abstract Interpretation: Proofs of results

abstract: Escape analysis of object-oriented languages approximates the set of objects which do not escape from a given context. If we take a method as context, the non-escaping objects can be allocated on its activation stack; if we take a thread, Java synchronisation locks on such objects are not needed. In this paper, we formalise a basic escape domain e as an abstract interpretation of concrete states, which we then refine into an abstract domain er which is more concrete than e and, hence, leads to a more precise escape analysis than e. We provide optimality results for both e and er, in the form of Galois insertions from the concrete to the abstract domains and of optimal abstract operations. The Galois insertion property is obtained by restricting the abstract domains to those elements which do not contain garbage, by using an abstract garbage collector. Our implementation of er is hence an implementation of a formally correct escape analyser, able to detect the stack allocatable creation points of Java (bytecode) applications. This report contains the proofs of results of a paper with the same title and authors and to be published in the Journal "Higher-Order Symbolic Computation".


title: Multiaccess Channels with State Known to Some Encoders and Independent Messages

abstract: We consider a state-dependent multiaccess channel (MAC) with state non-causally known to some encoders. We derive an inner bound for the capacity region in the general discrete memoryless case and specialize to a binary noiseless case. In the case of maximum entropy channel state, we obtain the capacity region for binary noiseless MAC with one informed encoder by deriving a non-trivial outer bound for this case. For a Gaussian state-dependent MAC with one encoder being informed of the channel state, we present an inner bound by applying a slightly generalized dirty paper coding (GDPC) at the informed encoder that allows for partial state cancellation, and a trivial outer bound by providing channel state to the decoder also. The uninformed encoders benefit from the state cancellation in terms of achievable rates, however, appears that GDPC cannot completely eliminate the effect of the channel state on the achievable rate region, in contrast to the case of all encoders being informed. In the case of infinite state variance, we analyze how the uninformed encoder benefits from the informed encoder's actions using the inner bound and also provide a non-trivial outer bound for this case which is better than the trivial outer bound.


title: Ideas by Statistical Mechanics (ISM)

abstract: Ideas by Statistical Mechanics (ISM) is a generic program to model evolution and propagation of ideas/patterns throughout populations subjected to endogenous and exogenous interactions. The program is based on the author's work in Statistical Mechanics of Neocortical Interactions (SMNI), and uses the author's Adaptive Simulated Annealing (ASA) code for optimizations of training sets, as well as for importance-sampling to apply the author's copula financial risk-management codes, Trading in Risk Dimensions (TRD), for assessments of risk and uncertainty. This product can be used for decision support for projects ranging from diplomatic, information, military, and economic (DIME) factors of propagation/evolution of ideas, to commercial sales, trading indicators across sectors of financial markets, advertising and political campaigns, etc. A statistical mechanical model of neocortical interactions, developed by the author and tested successfully in describing short-term memory and EEG indicators, is the proposed model. Parameters with a given subset of macrocolumns will be fit using ASA to patterns representing ideas. Parameters of external and inter-regional interactions will be determined that promote or inhibit the spread of these ideas. Tools of financial risk management, developed by the author to process correlated multivariate systems with differing non-Gaussian distributions using modern copula analysis, importance-sampled using ASA, will enable bona fide correlations and uncertainties of success and failure to be calculated. Marginal distributions will be evolved to determine their expected duration and stability using algorithms developed by the author, i.e., PATHTREE and PATHINT codes.


title: Reducing the Computation of Linear Complexities of Periodic Sequences over $GF(p^m)$

abstract: The linear complexity of a periodic sequence over $GF(p^m)$ plays an important role in cryptography and communication [12]. In this correspondence, we prove a result which reduces the computation of the linear complexity and minimal connection polynomial of a period $un$ sequence over $GF(p^m)$ to the computation of the linear complexities and minimal connection polynomials of $u$ period $n$ sequences. The conditions $u|p^m-1$ and $\gcd(n,p^m-1)=1$ are required for the result to hold. Some applications of this reduction in fast algorithms to determine the linear complexities and minimal connection polynomials of sequences over $GF(p^m)$ are presented.


title: Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

abstract: We present a randomized algorithm that, on input a symmetric, weakly diagonally dominant n-by-n matrix A with m nonzero entries and an n-vector b, produces a y such that $\norm{y - \pinv{A} b}_{A} \leq \epsilon \norm{\pinv{A} b}_{A}$ in expected time $O (m \log^{c}n \log (1/\epsilon)),$ for some constant c. By applying this algorithm inside the inverse power method, we compute approximate Fiedler vectors in a similar amount of time. The algorithm applies subgraph preconditioners in a recursive fashion. These preconditioners improve upon the subgraph preconditioners first introduced by Vaidya (1990). For any symmetric, weakly diagonally-dominant matrix A with non-positive off-diagonal entries and $k \geq 1$, we construct in time $O (m \log^{c} n)$ a preconditioner B of A with at most $2 (n - 1) + O ((m/k) \log^{39} n)$ nonzero off-diagonal entries such that the finite generalized condition number $\kappa_{f} (A,B)$ is at most k, for some other constant c. In the special case when the nonzero structure of the matrix is planar the corresponding linear system solver runs in expected time $ O (n \log^{2} n + n \log n \ \log \log n \ \log (1/\epsilon))$. We hope that our introduction of algorithms of low asymptotic complexity will lead to the development of algorithms that are also fast in practice.


title: The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case

abstract: The constraint satisfaction probem (CSP) is a well-acknowledged framework in which many combinatorial search problems can be naturally formulated. The CSP may be viewed as the problem of deciding the truth of a logical sentence consisting of a conjunction of constraints, in front of which all variables are existentially quantified. The quantified constraint satisfaction problem (QCSP) is the generalization of the CSP where universal quantification is permitted in addition to existential quantification. The general intractability of these problems has motivated research studying the complexity of these problems under a restricted constraint language, which is a set of relations that can be used to express constraints. This paper introduces collapsibility, a technique for deriving positive complexity results on the QCSP. In particular, this technique allows one to show that, for a particular constraint language, the QCSP reduces to the CSP. We show that collapsibility applies to three known tractable cases of the QCSP that were originally studied using disparate proof techniques in different decades: Quantified 2-SAT (Aspvall, Plass, and Tarjan 1979), Quantified Horn-SAT (Karpinski, Kleine B\"{u}ning, and Schmitt 1987), and Quantified Affine-SAT (Creignou, Khanna, and Sudan 2001). This reconciles and reveals common structure among these cases, which are describable by constraint languages over a two-element domain. In addition to unifying these known tractable cases, we study constraint languages over domains of larger size.


title: Linear Predictive Coding as an Estimator of Volatility

abstract: In this paper, we present a method of estimating the volatility of a signal that displays stochastic noise (such as a risky asset traded on an open market) utilizing Linear Predictive Coding. The main purpose is to associate volatility with a series of statistical properties that can lead us, through further investigation, toward a better understanding of structural volatility as well as to improve the quality of our current estimates.


title: Properties of subspace subcodes of optimum codes in rank metric

abstract: Maximum rank distance codes denoted MRD-codes are the equivalent in rank metric of MDS-codes. Given any integer $q$ power of a prime and any integer $n$ there is a family of MRD-codes of length $n$ over $\FF{q^n}$ having polynomial-time decoding algorithms. These codes can be seen as the analogs of Reed-Solomon codes (hereafter denoted RS-codes) for rank metric. In this paper their subspace subcodes are characterized. It is shown that hey are equivalent to MRD-codes constructed in the same way but with smaller parameters. A specific polynomial-time decoding algorithm is designed. Moreover, it is shown that the direct sum of subspace subcodes is equivalent to the direct product of MRD-codes with smaller parameters. This implies that the decoding procedure can correct errors of higher rank than the error-correcting capability. Finally it is shown that, for given parameters, subfield subcodes are completely characterized by elements of the general linear group ${GL}_n(\FF{q})$ of non-singular $q$-ary matrices of size $n$.


title: Complexity and Applications of Edge-Induced Vertex-Cuts

abstract: Motivated by hypergraph decomposition algorithms, we introduce the notion of edge-induced vertex-cuts and compare it with the well-known notions of edge-cuts and vertex-cuts. We investigate the complexity of computing minimum edge-induced vertex-cuts and demonstrate the usefulness of our notion by applications in network reliability and constraint satisfaction.


title: A Theory of Probabilistic Boosting, Decision Trees and Matryoshki

abstract: We present a theory of boosting probabilistic classifiers. We place ourselves in the situation of a user who only provides a stopping parameter and a probabilistic weak learner/classifier and compare three types of boosting algorithms: probabilistic Adaboost, decision tree, and tree of trees of ... of trees, which we call matryoshka. "Nested tree," "embedded tree" and "recursive tree" are also appropriate names for this algorithm, which is one of our contributions. Our other contribution is the theoretical analysis of the algorithms, in which we give training error bounds. This analysis suggests that the matryoshka leverages probabilistic weak classifiers more efficiently than simple decision trees.


title: UCLog+ : A Security Data Management System for Correlating Alerts, Incidents, and Raw Data From Remote Logs

abstract: Source data for computer network security analysis takes different forms (alerts, incidents, logs) and each source may be voluminous. Due to the challenge this presents for data management, this has often lead to security stovepipe operations which focus primarily on a small number of data sources for analysis with little or no automated correlation between data sources (although correlation may be done manually). We seek to address this systemic problem. In previous work we developed a unified correlated logging system (UCLog) that automatically processes alerts from different devices. We take this work one step further by presenting the architecture and applications of UCLog+ which adds the new capability to correlate between alerts and incidents and raw data located on remote logs. UCLog+ can be used for forensic analysis including queries and report generation but more importantly it can be used for near-real-time situational awareness of attack patterns in progress. The system, implemented with open source tools, can also be a repository for secure information sharing by different organizations.


title: Improving convergence of Belief Propagation decoding

abstract: The decoding of Low-Density Parity-Check codes by the Belief Propagation (BP) algorithm is revisited. We check the iterative algorithm for its convergence to a codeword (termination), we run Monte Carlo simulations to find the probability distribution function of the termination time, n_it. Tested on an example [155, 64, 20] code, this termination curve shows a maximum and an extended algebraic tail at the highest values of n_it. Aiming to reduce the tail of the termination curve we consider a family of iterative algorithms modifying the standard BP by means of a simple relaxation. The relaxation parameter controls the convergence of the modified BP algorithm to a minimum of the Bethe free energy. The improvement is experimentally demonstrated for Additive-White-Gaussian-Noise channel in some range of the signal-to-noise ratios. We also discuss the trade-off between the relaxation parameter of the improved iterative scheme and the number of iterations.


title: Trees with Convex Faces and Optimal Angles

abstract: We consider drawings of trees in which all edges incident to leaves can be extended to infinite rays without crossing, partitioning the plane into infinite convex polygons. Among all such drawings we seek the one maximizing the angular resolution of the drawing. We find linear time algorithms for solving this problem, both for plane trees and for trees without a fixed embedding. In any such drawing, the edge lengths may be set independently of the angles, without crossing; we describe multiple strategies for setting these lengths.


title: Revising Type-2 Computation and Degrees of Discontinuity

abstract: By the sometimes so-called MAIN THEOREM of Recursive Analysis, every computable real function is necessarily continuous. Weihrauch and Zheng (TCS'2000), Brattka (MLQ'2005), and Ziegler (ToCS'2006) have considered different relaxed notions of computability to cover also discontinuous functions. The present work compares and unifies these approaches. This is based on the concept of the JUMP of a representation: both a TTE-counterpart to the well known recursion-theoretic jump on Kleene's Arithmetical Hierarchy of hypercomputation: and a formalization of revising computation in the sense of Shoenfield. We also consider Markov and Banach/Mazur oracle-computation of discontinuous fu nctions and characterize the computational power of Type-2 nondeterminism to coincide with the first level of the Analytical Hierarchy.


title: Polynomial-time algorithm for vertex k-colorability of P_5-free graphs

abstract: We give the first polynomial-time algorithm for coloring vertices of P_5-free graphs with k colors. This settles an open problem and generalizes several previously known results.


title: Program Spectra Analysis in Embedded Software: A Case Study

abstract: Because of constraints imposed by the market, embedded software in consumer electronics is almost inevitably shipped with faults and the goal is just to reduce the inherent unreliability to an acceptable level before a product has to be released. Automatic fault diagnosis is a valuable tool to capture software faults without extra effort spent on testing. Apart from a debugging aid at design and integration time, fault diagnosis can help analyzing problems during operation, which allows for more accurate system recovery. In this paper we discuss perspectives and limitations for applying a particular fault diagnosis technique, namely the analysis of program spectra, in the area of embedded software in consumer electronics devices. We illustrate these by our first experience with a test case from industry.


title: Bidding to the Top: VCG and Equilibria of Position-Based Auctions

abstract: Many popular search engines run an auction to determine the placement of advertisements next to search results. Current auctions at Google and Yahoo! let advertisers specify a single amount as their bid in the auction. This bid is interpreted as the maximum amount the advertiser is willing to pay per click on its ad. When search queries arrive, the bids are used to rank the ads linearly on the search result page. The advertisers pay for each user who clicks on their ad, and the amount charged depends on the bids of all the advertisers participating in the auction. In order to be effective, advertisers seek to be as high on the list as their budget permits, subject to the market. We study the problem of ranking ads and associated pricing mechanisms when the advertisers not only specify a bid, but additionally express their preference for positions in the list of ads. In particular, we study "prefix position auctions" where advertiser $i$ can specify that she is interested only in the top $b_i$ positions. We present a simple allocation and pricing mechanism that generalizes the desirable properties of current auctions that do not have position constraints. In addition, we show that our auction has an "envy-free" or "symmetric" Nash equilibrium with the same outcome in allocation and pricing as the well-known truthful Vickrey-Clarke-Groves (VCG) auction. Furthermore, we show that this equilibrium is the best such equilibrium for the advertisers in terms of the profit made by each advertiser. We also discuss other position-based auctions.


title: A new function algebra of EXPTIME functions by safe nested recursion

abstract: Bellantoni and Cook have given a function-algebra characterization of the polynomial-time computable functions via an unbounded recursion scheme which is called safe recursion. Inspired by their work, we characterize the exponential-time computable functions with the use of a safe variant of nested recursion.


title: Web-Based Enterprise Information Systems Development: The Integrated Methodology

abstract: The paper considers software development issues for large-scale enterprise information systems (IS) with databases (DB) in global heterogeneous distributed computational environment. Due to high IT development rates, the present-day society has accumulated and rapidly increases an extremely huge data burden. Manipulating with such huge data arrays becomes an essential problem, particularly due to their global distribution, heterogeneous and weak-structured character. The conceptual approach to integrated Internet-based IS design, development and implementation is presented, including formal models, software development methodology and original software development tools for visual problem-oriented development and content management. IS implementation results proved shortening terms and reducing costs of implementation compared to commercial software available.


title: Expressing Implicit Semantic Relations without Supervision

abstract: We present an unsupervised learning algorithm that mines large text corpora for patterns that express implicit semantic relations. For a given input word pair X:Y with some unspecified semantic relations, the corresponding output list of patterns <P1,...,Pm> is ranked according to how well each pattern Pi expresses the relations between X and Y. For example, given X=ostrich and Y=bird, the two highest ranking output patterns are "X is the largest Y" and "Y such as the X". The output patterns are intended to be useful for finding further pairs with the same relations, to support the construction of lexicons, ontologies, and semantic networks. The patterns are sorted by pertinence, where the pertinence of a pattern Pi for a word pair X:Y is the expected relational similarity between the given pair and typical pairs for Pi. The algorithm is empirically evaluated on two tasks, solving multiple-choice SAT word analogy questions and classifying semantic relations in noun-modifier pairs. On both tasks, the algorithm achieves state-of-the-art results, performing significantly better than several alternative pattern ranking algorithms, based on tf-idf.


title: Object-Based Groupware: Theory, Design and Implementation Issues

abstract: Document management software systems are having a wide audience at present. However, groupware as a term has a wide variety of possible definitions. Groupware classification attempt is made in this paper. Possible approaches to groupware are considered including document management, document control and mailing systems. Lattice theory and concept modelling are presented as a theoretical background for the systems in question. Current technologies in state-of-the-art document managenent software are discussed. Design and implementation aspects for user-friendly integrate enterprise systems are described. Results for a real system to be implemented are given. Perspectives of the field in question are discussed.


title: Enterprise Content Management: Theory and Engineering for Entire Lifecycle Support

abstract: The paper considers enterprise content management (ECM) issues in global heterogeneous distributed computational environment. Present-day enterprises have accumulated a huge data burden. Manipulating with such a bulk becomes an essential problem, particularly due to its global distribution, heterogeneous and weak-structured character. The conceptual approach to integrated ECM lifecycle support is presented, including overview of formal models, software development methodology and innovative software development tools. Implementation results proved shortening terms and reducing costs of implementation compared to commercial software available.


title: Enterprise Portal Development Tools: Problem-Oriented Approach

abstract: The paper deals with problem-oriented visual information system (IS) engineering for enterprise Internet-based applications, which is a vital part of the whole development process. The suggested approach is based on semantic network theory and a novel ConceptModeller CASE tool.


title: ConceptModeller: a Problem-Oriented Visual SDK for Globally Distributed Enterprise Systems

abstract: The paper describes problem-oriented approach to software development. The approach is a part of the original integrated methodology of enterprise Internet-based software design and implementation. All aspects of software development, from theory to implementation, are covered.


title: Enterprise Portal: from Model to Implementation

abstract: Portal technology can significantly improve the entire corporate information infrastructure. The approach proposed is based on rigorous and consistent (meta)data model and provides for efficient and accurate front-end integration of heterogeneous corporate applications including enterprise resource planning (ERP) systems, multimedia data warehouses and proprietary content databases. The methodology proposed embraces entire software lifecycle; it is illustrated by an enterprise-level Intranet portal implementation.


title: Abstract Machine as a Model of Content Management Information System

abstract: Enterprise content management is an urgent issue of current scientific and practical activities in software design and implementation. However, papers known as yet give insufficient coverage of theoretical background of the software in question. The paper gives an attempt of building a state-based model of content management. In accordance with the theoretical principles outlined, a content management information system (CMIS) has been implemented in a large international oil-and-gas group of companies.


title: Integrating Enterprise Software Applications with Web Portal Technology

abstract: Web-portal based approach can significantly improve the entire corporate information infrastructure. The approach proposed provides for rapid and accurate front-end integration of heterogeneous corporate applications including enterprise resource planning (ERP) systems. Human resources ERP component and multimedia data warehouse implementations are discussed as essential instances.


title: The Integrated Approach to ERP: Embracing the Web

abstract: Integrated approach to enterprise resource planning (ERP) software design and implementation can significantly improve the entire corporate information infrastructure and it helps to benefit from power of Internet services. The approach proposed provides for corporate Web portal integrity, consistency, urgency and front-end data processing. Human resources (HR) ERP component implementation is discussed as an essential instance.


title: Enterprise Resource Planning Systems: the Integrated Approach

abstract: Enterprise resource planning (ERP) systems enjoy an increasingly wide coverage. However, no truly integrate solution has been proposed as yet. ERP classification is given. Recent trends in commercial systems are analyzed on the basis of human resources (HR) management software. An innovative "straight through" design and implementation process of an open, secure, and scalable integrated event-driven enterprise solution is suggested. Implementation results are presented.


title: Towards Implementing an Enterprise Groupware-Integrated Human Resources Information System

abstract: Human resources management software is having a wide audience at present. However, no truly integrate solution has been proposed yet to improve the systems concerned. Approaches to extra data collection for appraisal decision-making are considered on the concept modeling theoretical basis. Current technologies in state-of-the-art HR management software are compared. Design and implementation aspects for a Web-wired truly integrated secure and scalable event-driven enterprise system are described. Benchmark results are presented. Field perspectives are discussed.


title: Tardos fingerprinting is better than we thought

abstract: We review the fingerprinting scheme by Tardos and show that it has a much better performance than suggested by the proofs in Tardos' original paper. In particular, the length of the codewords can be significantly reduced. First we generalize the proofs of the false positive and false negative error probabilities with the following modifications: (1) we replace Tardos' hard-coded numbers by variables and (2) we allow for independently chosen false positive and false negative error rates. It turns out that all the collusion-resistance properties can still be proven when the code length is reduced by a factor of more than 2. Second, we study the statistical properties of the fingerprinting scheme, in particular the average and variance of the accusations. We identify which colluder strategy forces the content owner to employ the longest code. Using a gaussian approximation for the probability density functions of the accusations, we show that the required false negative and false positive error rate can be achieved with codes that are a factor 2 shorter than required for rigid proofs. Combining the results of these two approaches, we show that the Tardos scheme can be used with a code length approximately 5 times shorter than in the original construction.


title: On q-ary codes correcting all unidirectional errors of a limited magnitude

abstract: We consider codes over the alphabet Q={0,1,..,q-1}intended for the control of unidirectional errors of level l. That is, the transmission channel is such that the received word cannot contain both a component larger than the transmitted one and a component smaller than the transmitted one. Moreover, the absolute value of the difference between a transmitted component and its received version is at most l. We introduce and study q-ary codes capable of correcting all unidirectional errors of level l. Lower and upper bounds for the maximal size of those codes are presented. We also study codes for this aim that are defined by a single equation on the codeword coordinates(similar to the Varshamov-Tenengolts codes for correcting binary asymmetric errors). We finally consider the problem of detecting all unidirectional errors of level l.


title: Self-Replication and Self-Assembly for Manufacturing

abstract: It has been argued that a central objective of nanotechnology is to make products inexpensively, and that self-replication is an effective approach to very low-cost manufacturing. The research presented here is intended to be a step towards this vision. We describe a computational simulation of nanoscale machines floating in a virtual liquid. The machines can bond together to form strands (chains) that self-replicate and self-assemble into user-specified meshes. There are four types of machines and the sequence of machine types in a strand determines the shape of the mesh they will build. A strand may be in an unfolded state, in which the bonds are straight, or in a folded state, in which the bond angles depend on the types of machines. By choosing the sequence of machine types in a strand, the user can specify a variety of polygonal shapes. A simulation typically begins with an initial unfolded seed strand in a soup of unbonded machines. The seed strand replicates by bonding with free machines in the soup. The child strands fold into the encoded polygonal shape, and then the polygons drift together and bond to form a mesh. We demonstrate that a variety of polygonal meshes can be manufactured in the simulation, by simply changing the sequence of machine types in the seed.


title: Leading strategies in competitive on-line prediction

abstract: We start from a simple asymptotic result for the problem of on-line regression with the quadratic loss function: the class of continuous limited-memory prediction strategies admits a "leading prediction strategy", which not only asymptotically performs at least as well as any continuous limited-memory strategy but also satisfies the property that the excess loss of any continuous limited-memory strategy is determined by how closely it imitates the leading strategy. More specifically, for any class of prediction strategies constituting a reproducing kernel Hilbert space we construct a leading strategy, in the sense that the loss of any prediction strategy whose norm is not too large is determined by how closely it imitates the leading strategy. This result is extended to the loss functions given by Bregman divergences and by strictly proper scoring rules.


title: A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs

abstract: We show that the number of $k$-matching in a given undirected graph $G$ is equal to the number of perfect matching of the corresponding graph $G_k$ on an even number of vertices divided by a suitable factor. If $G$ is bipartite then one can construct a bipartite $G_k$. For bipartite graphs this result implies that the number of $k$-matching has a polynomial-time approximation algorithm. The above results are extended to permanents and hafnians of corresponding matrices.


title: Competing with Markov prediction strategies

abstract: Assuming that the loss function is convex in the prediction, we construct a prediction strategy universal for the class of Markov prediction strategies, not necessarily continuous. Allowing randomization, we remove the requirement of convexity.


title: Multicasting with selective delivery: A SafetyNet for vertical handoffs

abstract: In future mobility support will require handling roaming in heterogeneous access networks. In order to enable seamless roaming it is necessary to minimize the impact of the vertical handoffs. Localized mobility management schemes such as FMIPv6 and HMIPv6 do not provide sufficient handoff performance, since they have been designed for horizontal handoffs. In this paper, we propose the SafetyNet protocol, which allows a Mobile Node to perform seamless vertical handoffs. Further, we propose a handoff timing algorithm which allows a Mobile Node to delay or even completely avoid upward vertical handoffs. We implement the SafetyNet protocol and compare its performance with the Fast Handovers for Mobile IPv6 protocol in our wireless test bed and analyze the results. The experimental results indicate that the proposed SafetyNet protocol can provide an improvement of up to 95% for TCP performance in vertical handoffs, when compared with FMIPv6 and an improvement of 64% over FMIPv6 with bicasting. We use numerical analysis of the protocol to show that its signaling and data transmission overhead is comparable to Fast Mobile IPv6 and significantly smaller than that of FMIPv6 with bicasting.


title: A Foundation to Perception Computing, Logic and Automata

abstract: In this report, a novel approach to intelligence and learning is introduced, this approach is based on what we call 'perception logic'. Based on this logic, a computing mechanism and automata are introduced. Multi-resolution analysis of perceptual information is given, in which learning is accomplished in at most O(log(N))epochs, where N is the number of samples, and the convergence is guarnteed. This approach combines the favors of computational modeles in the sense that they are structured and mathematically well-defined, and the adaptivity of soft computing approaches, in addition to the continuity and real-time response of dynamical systems.


title: Parallel repetition: simplifications and the no-signaling case

abstract: Consider a game where a refereed a referee chooses (x,y) according to a publicly known distribution P_XY, sends x to Alice, and y to Bob. Without communicating with each other, Alice responds with a value "a" and Bob responds with a value "b". Alice and Bob jointly win if a publicly known predicate Q(x,y,a,b) holds. Let such a game be given and assume that the maximum probability that Alice and Bob can win is v<1. Raz (SIAM J. Comput. 27, 1998) shows that if the game is repeated n times in parallel, then the probability that Alice and Bob win all games simultaneously is at most v'^(n/log(s)), where s is the maximal number of possible responses from Alice and Bob in the initial game, and v' is a constant depending only on v. In this work, we simplify Raz's proof in various ways and thus shorten it significantly. Further we study the case where Alice and Bob are not restricted to local computations and can use any strategy which does not imply communication among them.


title: Stylized Facts in Internal Rates of Return on Stock Index and its Derivative Transactions

abstract: Universal features in stock markets and their derivative markets are studied by means of probability distributions in internal rates of return on buy and sell transaction pairs. Unlike the stylized facts in log normalized returns, the probability distributions for such single asset encounters encorporate the time factor by means of the internal rate of return defined as the continuous compound interest. Resulting stylized facts are shown in the probability distributions derived from the daily series of TOPIX, S & P 500 and FTSE 100 index close values. The application of the above analysis to minute-tick data of NIKKEI 225 and its futures market, respectively, reveals an interesting diffference in the behavior of the two probability distributions, in case a threshold on the minimal duration of the long position is imposed. It is therefore suggested that the probability distributions of the internal rates of return could be used for causality mining between the underlying and derivative stock markets. The highly specific discrete spectrum, which results from noise trader strategies as opposed to the smooth distributions observed for fundamentalist strategies in single encounter transactions may be also useful in deducing the type of investment strategy from trading revenues of small portfolio investors.


title: Logic Column 16: Higher-Order Abstract Syntax: Setting the Record Straight

abstract: This article responds to a critique of higher-order abstract syntax appearing in Logic Column 14, ``Nominal Logic and Abstract Syntax'', cs.LO/0511025.


title: Employing Trusted Computing for the forward pricing of pseudonyms in reputation systems

abstract: Reputation and recommendation systems are fundamental for the formation of community market places. Yet, they are easy targets for attacks which disturb a market's equilibrium and are often based on cheap pseudonyms used to submit ratings. We present a method to price ratings using trusted computing, based on pseudonymous tickets.


title: Target Type Tracking with PCR5 and Dempster's rules: A Comparative Analysis

abstract: In this paper we consider and analyze the behavior of two combinational rules for temporal (sequential) attribute data fusion for target type estimation. Our comparative analysis is based on Dempster's fusion rule proposed in Dempster-Shafer Theory (DST) and on the Proportional Conflict Redistribution rule no. 5 (PCR5) recently proposed in Dezert-Smarandache Theory (DSmT). We show through very simple scenario and Monte-Carlo simulation, how PCR5 allows a very efficient Target Type Tracking and reduces drastically the latency delay for correct Target Type decision with respect to Demspter's rule. For cases presenting some short Target Type switches, Demspter's rule is proved to be unable to detect the switches and thus to track correctly the Target Type changes. The approach proposed here is totally new, efficient and promising to be incorporated in real-time Generalized Data Association - Multi Target Tracking systems (GDA-MTT) and provides an important result on the behavior of PCR5 with respect to Dempster's rule. The MatLab source code is provided in


title: Levels of Product Differentiation in the Global Mobile Phones Market

abstract: The sixth product level called compliant product is a connecting element between the physical product characteristics and the strategy of the producer company. The article discusses the differentiation among the product offers of companies working in the global markets, as well as the strategies which they use and could use in that respect.


title: Geometric definition of a new skeletonization concept

abstract: The Divider set, as an innovative alternative concept to maximal disks, Voronoi sets and cut loci, is presented with a formal definition based on topology and differential geometry. The relevant mathematical theory by previous authors and a comparison with other medial axis definitions is presented. Appropriate applications are proposed and examined.


title: Modeling Adversaries in a Logic for Security Protocol Analysis

abstract: Logics for security protocol analysis require the formalization of an adversary model that specifies the capabilities of adversaries. A common model is the Dolev-Yao model, which considers only adversaries that can compose and replay messages, and decipher them with known keys. The Dolev-Yao model is a useful abstraction, but it suffers from some drawbacks: it cannot handle the adversary knowing protocol-specific information, and it cannot handle probabilistic notions, such as the adversary attempting to guess the keys. We show how we can analyze security protocols under different adversary models by using a logic with a notion of algorithmic knowledge. Roughly speaking, adversaries are assumed to use algorithms to compute their knowledge; adversary capabilities are captured by suitable restrictions on the algorithms used. We show how we can model the standard Dolev-Yao adversary in this setting, and how we can capture more general capabilities including protocol-specific knowledge and guesses.


title: Fusion of qualitative beliefs using DSmT

abstract: This paper introduces the notion of qualitative belief assignment to model beliefs of human experts expressed in natural language (with linguistic labels). We show how qualitative beliefs can be efficiently combined using an extension of Dezert-Smarandache Theory (DSmT) of plausible and paradoxical quantitative reasoning to qualitative reasoning. We propose a new arithmetic on linguistic labels which allows a direct extension of classical DSm fusion rule or DSm Hybrid rules. An approximate qualitative PCR5 rule is also proposed jointly with a Qualitative Average Operator. We also show how crisp or interval mappings can be used to deal indirectly with linguistic labels. A very simple example is provided to illustrate our qualitative fusion rules.


title: A Finite Equational Base for CCS with Left Merge and Communication Merge

abstract: Using the left merge and communication merge from ACP, we present an equational base (i.e., a ground-complete and $\omega$-complete set of valid equations) for the fragment of CCS without recursion, restriction and relabelling. Our equational base is finite if the set of actions is finite.


title: An Introduction to the DSm Theory for the Combination of Paradoxical, Uncertain, and Imprecise Sources of Information

abstract: The management and combination of uncertain, imprecise, fuzzy and even paradoxical or high conflicting sources of information has always been, and still remains today, of primal importance for the development of reliable modern information systems involving artificial reasoning. In this introduction, we present a survey of our recent theory of plausible and paradoxical reasoning, known as Dezert-Smarandache Theory (DSmT) in the literature, developed for dealing with imprecise, uncertain and paradoxical sources of information. We focus our presentation here rather on the foundations of DSmT, and on the two important new rules of combination, than on browsing specific applications of DSmT available in literature. Several simple examples are given throughout the presentation to show the efficiency and the generality of this new approach.


title: On a solution to display non-filled-in quaternionic Julia sets

abstract: During early 1980s, the so-called `escape time' method, developed to display the Julia sets for complex dynamical systems, was exported to quaternions in order to draw analogous pictures in this wider numerical field. Despite of the fine results in the complex plane, where all topological configurations of Julia sets have been successfully displayed, the `escape time' method fails to render properly the non-filled-in variety of quaternionic Julia sets. So their digital visualisation remained an open problem for several years. Both the solution for extending this old method to non-filled-in quaternionic Julia sets and its implementation into a program are explained here.


title: Separating the articles of authors with the same name

abstract: I describe a method to separate the articles of different authors with the same name. It is based on a distance between any two publications, defined in terms of the probability that they would have as many coincidences if they were drawn at random from all published documents. Articles with a given author name are then clustered according to their distance, so that all articles in a cluster belong very likely to the same author. The method has proven very useful in generating groups of papers that are then selected manually. This simplifies considerably citation analysis when the author publication lists are not available.


title: A field-theory motivated approach to symbolic computer algebra

abstract: Field theory is an area in physics with a deceptively compact notation. Although general purpose computer algebra systems, built around generic list-based data structures, can be used to represent and manipulate field-theory expressions, this often leads to cumbersome input formats, unexpected side-effects, or the need for a lot of special-purpose code. This makes a direct translation of problems from paper to computer and back needlessly time-consuming and error-prone. A prototype computer algebra system is presented which features TeX-like input, graph data structures, lists with Young-tableaux symmetries and a multiple-inheritance property system. The usefulness of this approach is illustrated with a number of explicit field-theory problems.


title: A Graph-based Framework for Transmission of Correlated Sources over Broadcast Channels

abstract: In this paper we consider the communication problem that involves transmission of correlated sources over broadcast channels. We consider a graph-based framework for this information transmission problem. The system involves a source coding module and a channel coding module. In the source coding module, the sources are efficiently mapped into a nearly semi-regular bipartite graph, and in the channel coding module, the edges of this graph are reliably transmitted over a broadcast channel. We consider nearly semi-regular bipartite graphs as discrete interface between source coding and channel coding in this multiterminal setting. We provide an information-theoretic characterization of (1) the rate of exponential growth (as a function of the number of channel uses) of the size of the bipartite graphs whose edges can be reliably transmitted over a broadcast channel and (2) the rate of exponential growth (as a function of the number of source samples) of the size of the bipartite graphs which can reliably represent a pair of correlated sources to be transmitted over a broadcast channel.


title: On the randomness of independent experiments

abstract: Given a probability distribution P, what is the minimum amount of bits needed to store a value x sampled according to P, such that x can later be recovered (except with some small probability)? Or, what is the maximum amount of uniform randomness that can be extracted from x? Answering these and similar information-theoretic questions typically boils down to computing so-called smooth entropies. In this paper, we derive explicit and almost tight bounds on the smooth entropies of n-fold product distributions.


title: The minimum linear arrangement problem on proper interval graphs

abstract: We present a linear time algorithm for the minimum linear arrangement problem on proper interval graphs. The obtained ordering is a 4-approximation for general interval graphs


title: Stability in multidimensional Size Theory

abstract: This paper proves that in Size Theory the comparison of multidimensional size functions can be reduced to the 1-dimensional case by a suitable change of variables. Indeed, we show that a foliation in half-planes can be given, such that the restriction of a multidimensional size function to each of these half-planes turns out to be a classical size function in two scalar variables. This leads to the definition of a new distance between multidimensional size functions, and to the proof of their stability with respect to that distance.


title: MIMO scheme performance and detection in epsilon noise

abstract: New approach for analysis and decoding MIMO signaling is developed for usual model of nongaussion noise consists of background and impulsive noise named epsilon - noise. It is shown that non-gaussion noise performance significantly worse than gaussion ones. Stimulation results strengthen out theory. Robust in statistical sense detection rule is suggested for such kind of noise features much best robust detector performance than detector designed for Gaussian noise in impulsive environment and modest margin in background noise. Proposed algorithms performance are comparable with developed potential bound. Proposed tool, is crucial issue for MIMO communication system design, since real noise environment has impulsive character that contradict with wide used Gaussian approach, so real MIMO performance much different for Gaussian a non-Gaussian noise model.


title: The Many Faces of Rationalizability

abstract: The rationalizability concept was introduced in \cite{Ber84} and \cite{Pea84} to assess what can be inferred by rational players in a non-cooperative game in the presence of common knowledge. However, this notion can be defined in a number of ways that differ in seemingly unimportant minor details. We shed light on these differences, explain their impact, and clarify for which games these definitions coincide. Then we apply the same analysis to explain the differences and similarities between various ways the iterated elimination of strictly dominated strategies was defined in the literature. This allows us to clarify the results of \cite{DS02} and \cite{CLL05} and improve upon them. We also consider the extension of these results to strict dominance by a mixed strategy. Our approach is based on a general study of the operators on complete lattices. We allow transfinite iterations of the considered operators and clarify the need for them. The advantage of such a general approach is that a number of results, including order independence for some of the notions of rationalizability and strict dominance, come for free.


title: Opti{c,m}al: Optical/Optimal Routing in Massively Dense Wireless Networks

abstract: We study routing for massively dense wireless networks, i.e., wireless networks that contain so many nodes that, in addition to their usual microscopic description, a novel macroscopic description becomes possible. The macroscopic description is not detailed, but nevertheless contains enough information to permit a meaningful study and performance optimization of the network. Within this context, we continue and significantly expand previous work on the analogy between optimal routing and the propagation of light according to the laws of Geometrical Optics. Firstly, we pose the analogy in a more general framework than previously, notably showing how the eikonal equation, which is the central equation of Geometrical Optics, also appears in the networking context. Secondly, we develop a methodology for calculating the cost function, which is the function describing the network at the macroscopic level. We apply this methodology for two important types of networks: bandwidth limited and energy limited.


title: Pull-Based Data Broadcast with Dependencies: Be Fair to Users, not to Items

abstract: Broadcasting is known to be an efficient means of disseminating data in wireless communication environments (such as Satellite, mobile phone networks,...). It has been recently observed that the average service time of broadcast systems can be considerably improved by taking into consideration existing correlations between requests. We study a pull-based data broadcast system where users request possibly overlapping sets of items; a request is served when all its requested items are downloaded. We aim at minimizing the average user perceived latency, i.e. the average flow time of the requests. We first show that any algorithm that ignores the dependencies can yield arbitrary bad performances with respect to the optimum even if it is given arbitrary extra resources. We then design a $(4+\epsilon)$-speed $O(1+1/\epsilon^2)$-competitive algorithm for this setting that consists in 1) splitting evenly the bandwidth among each requested set and in 2) broadcasting arbitrarily the items still missing in each set into the bandwidth the set has received. Our algorithm presents several interesting features: it is simple to implement, non-clairvoyant, fair to users so that no user may starve for a long period of time, and guarantees good performances in presence of correlations between user requests (without any change in the broadcast protocol). We also present a $ (4+\epsilon)$-speed $O(1+1/\epsilon^3)$-competitive algorithm which broadcasts at most one item at any given time and preempts each item broadcast at most once on average. As a side result of our analysis, we design a competitive algorithm for a particular setting of non-clairvoyant job scheduling with dependencies, which might be of independent interest.


title: Localization for Anchoritic Sensor Networks

abstract: We introduce a class of anchoritic sensor networks, where communications between sensor nodes is undesirable or infeasible, e.g., due to harsh environment, energy constraints, or security considerations.


title: Towards "Propagation = Logic + Control"

abstract: Constraint propagation algorithms implement logical inference. For efficiency, it is essential to control whether and in what order basic inference steps are taken. We provide a high-level framework that clearly differentiates between information needed for controlling propagation versus that needed for the logical semantics of complex constraints composed from primitive ones. We argue for the appropriateness of our controlled propagation framework by showing that it captures the underlying principles of manually designed propagation algorithms, such as literal watching for unit clause propagation and the lexicographic ordering constraint. We provide an implementation and benchmark results that demonstrate the practicality and efficiency of our framework.


title: ACD Term Rewriting

abstract: We introduce Associative Commutative Distributive Term Rewriting (ACDTR), a rewriting language for rewriting logical formulae. ACDTR extends AC term rewriting by adding distribution of conjunction over other operators. Conjunction is vital for expressive term rewriting systems since it allows us to require that multiple conditions hold for a term rewriting rule to be used. ACDTR uses the notion of a "conjunctive context", which is the conjunction of constraints that must hold in the context of a term, to enable the programmer to write very expressive and targeted rewriting rules. ACDTR can be seen as a general logic programming language that extends Constraint Handling Rules and AC term rewriting. In this paper we define the semantics of ACDTR and describe our prototype implementation.


title: Infinite Qualitative Simulations by Means of Constraint Programming

abstract: We introduce a constraint-based framework for studying infinite qualitative simulations concerned with contingencies such as time, space, shape, size, abstracted into a finite set of qualitative relations. To define the simulations, we combine constraints that formalize the background knowledge concerned with qualitative reasoning with appropriate inter-state constraints that are formulated using linear temporal logic. We implemented this approach in a constraint programming system by drawing on ideas from bounded model checking. The resulting system allows us to test and modify the problem specifications in a straightforward way and to combine various knowledge aspects.


title: The single-serving channel capacity

abstract: In this paper we provide the answer to the following question: Given a noisy channel and epsilon>0, how many bits can be transmitted with an error of at most epsilon by a single use of the channel?


title: Relation Variables in Qualitative Spatial Reasoning

abstract: We study an alternative to the prevailing approach to modelling qualitative spatial reasoning (QSR) problems as constraint satisfaction problems. In the standard approach, a relation between objects is a constraint whereas in the alternative approach it is a variable. The relation-variable approach greatly simplifies integration and implementation of QSR. To substantiate this point, we discuss several QSR algorithms from the literature which in the relation-variable approach reduce to the customary constraint propagation algorithm enforcing generalised arc-consistency.


title: Quasi-friendly sup-interpretations

abstract: In a previous paper, the sup-interpretation method was proposed as a new tool to control memory resources of first order functional programs with pattern matching by static analysis. Basically, a sup-interpretation provides an upper bound on the size of function outputs. In this former work, a criterion, which can be applied to terminating as well as non-terminating programs, was developed in order to bound polynomially the stack frame size. In this paper, we suggest a new criterion which captures more algorithms computing values polynomially bounded in the size of the inputs. Since this work is related to quasi-interpretations, we compare the two notions obtaining two main features. The first one is that, given a program, we have heuristics for finding a sup-interpretation when we consider polynomials of bounded degree. The other one consists in the characterizations of the set of function computable in polynomial time and in polynomial space.


title: The Shannon capacity of a graph and the independence numbers of its powers

abstract: The independence numbers of powers of graphs have been long studied, under several definitions of graph products, and in particular, under the strong graph product. We show that the series of independence numbers in strong powers of a fixed graph can exhibit a complex structure, implying that the Shannon Capacity of a graph cannot be approximated (up to a sub-polynomial factor of the number of vertices) by any arbitrarily large, yet fixed, prefix of the series. This is true even if this prefix shows a significant increase of the independence number at a given power, after which it stabilizes for a while.


title: Expressing Security Properties Using Selective Interleaving Functions

abstract: McLean's notion of Selective Interleaving Functions (SIFs) is perhaps the best-known attempt to construct a framework for expressing various security properties. We examine the expressive power of SIFs carefully. We show that SIFs cannot capture nondeducibility on strategies (NOS). We also prove that the set of security properties expressed with SIFs is not closed under conjunction, from which it follows that separability is strictly stronger than double generalized noninterference. However, we show that if we generalize the notion of SIF in a natural way, then NOS is expressible, and the set of security properties expressible by generalized SIFs is closed under conjunction.


title: Optimal resource allocation for OFDM multiuser channels

abstract: In this paper, a unifying framework for orthogonal frequency division multiplexing (OFDM) multiuser resource allocation is presented. The isolated seeming problems of maximizing a weighted sum of rates for a given power budget $\bar{P}$ and minimizing sum power for given rate requirements $\mathbf{\bar{R}}$ can be interpreted jointly in this framework. To this end we embed the problems in a higher dimensional space. Based on these results, we subsequently consider the combined problem of maximizing a weighted sum of rates under given rate requirements $\mathbf{\bar{R}}$ and a fixed power budget $\bar{P}$. This new problem is challenging, since the additional constraints do not allow to use the hitherto existing approaches. Interestingly, the optimal decoding orders turn out to be the ordering of the Lagrangian factors in all problems.


title: Cryptanalysis of an Encryption Scheme Based on Blind Source Separation

abstract: Recently Lin et al. proposed a method of using the underdetermined BSS (blind source separation) problem to realize image and speech encryption. In this paper, we give a cryptanalysis of this BSS-based encryption and point out that it is not secure against known/chosen-plaintext attack and chosen-ciphertext attack. In addition, there exist some other security defects: low sensitivity to part of the key and the plaintext, a ciphertext-only differential attack, divide-and-conquer (DAC) attack on part of the key. We also discuss the role of BSS in Lin et al.'s efforts towards cryptographically secure ciphers.


title: User-Network Association in a WLAN-UMTS Hybrid Cell: Global & Individual Optimality

abstract: We study optimal user-network association in an integrated 802.11 WLAN and 3G-UMTS hybrid cell. Assuming saturated resource allocation on the downlink of WLAN and UMTS networks and a single QoS class of mobiles arriving at an average location in the hybrid cell, we formulate the problem with two different approaches: Global and Individual optimality. The Globally optimal association is formulated as an SMDP (Semi Markov Decision Process) connection routing decision problem where rewards comprise a financial gain component and an aggregate network throughput component. The corresponding Dynamic Programming equations are solved using Value Iteration method and a stationary optimal policy with neither convex nor concave type switching curve structure is obtained. Threshold type and symmetric switching curves are observed for the analogous homogenous network cases. The Individual optimality is studied under a non-cooperative dynamic game framework with expected service time of a mobile as the decision cost criteria. It is shown that individual optimality in a WLAN-UMTS hybrid cell, results in a threshold policy curve of descending staircase form with increasing Poisson arrival rate of mobiles.