OpenRaiser/Intern-Atlas huggingface dataset:
Constant for associative patterns ensemble
Venue: arXiv cs.AI 2006
Year: 2006

Creation procedure of associative patterns ensemble in terms of formal logic with using neural net-work (NN) model is formulated. It is shown that the associative patterns set is created by means of unique procedure of NN work which having individual parameters of entrance stimulus transformation. It is ascer-tained that the quantity of the selected associative patterns possesses is a constant.
Stabilization using both noisy and noiseless feedback
Venue: arXiv cs.IT 2006
Year: 2006

When designing a distributed control system, the system designer has a choice in how to connect the different units through communication channels. In practice, noiseless and noisy channels may coexist. Using the standard toy example of scalar stabilization, this paper shows how a small amount of noiseless feedback can perform a ``supervisory'' role and thereby boost the effectiveness of noisy feedback.
A Non-Orthogonal Distributed Space-Time Coded Protocol Part I: Signal Model and Design Criteria
Venue: arXiv cs.IT 2006
Year: 2006

In this two-part series of papers, a generalized non-orthogonal amplify and forward (GNAF) protocol which generalizes several known cooperative diversity protocols is proposed. Transmission in the GNAF protocol comprises of two phases - the broadcast phase and the cooperation phase. In the broadcast phase, the source broadcasts its information to the relays as well as the destination. In the cooperation phase, the source and the relays together transmit a space-time code in a distributed fashion. The GNAF protocol relaxes the constraints imposed by the protocol of Jing and Hassibi on the code structure. In Part-I of this paper, a code design criteria is obtained and it is shown that the GNAF protocol is delay efficient and coding gain efficient as well. Moreover GNAF protocol enables the use of sphere decoders at the destination with a non-exponential Maximum likelihood (ML) decoding complexity. In Part-II, several low decoding complexity code constructions are studied and a lower bound on the Diversity-Multiplexing Gain tradeoff of the GNAF protocol is obtained.
Decentralized Failure Diagnosis of Stochastic Discrete Event Systems
Venue: arXiv cs.AI 2006
Year: 2006

Recently, the diagnosability of {\it stochastic discrete event systems} (SDESs) was investigated in the literature, and, the failure diagnosis considered was {\it centralized}. In this paper, we propose an approach to {\it decentralized} failure diagnosis of SDESs, where the stochastic system uses multiple local diagnosers to detect failures and each local diagnoser possesses its own information. In a way, the centralized failure diagnosis of SDESs can be viewed as a special case of the decentralized failure diagnosis presented in this paper with only one projection. The main contributions are as follows: (1) We formalize the notion of codiagnosability for stochastic automata, which means that a failure can be detected by at least one local stochastic diagnoser within a finite delay. (2) We construct a codiagnoser from a given stochastic automaton with multiple projections, and the codiagnoser associated with the local diagnosers is used to test codiagnosability condition of SDESs. (3) We deal with a number of basic properties of the codiagnoser. In particular, a necessary and sufficient condition for the codiagnosability of SDESs is presented. (4) We give a computing method in detail to check whether codiagnosability is violated. And (5) some examples are described to illustrate the applications of the codiagnosability and its computing method.
ECA-RuleML: An Approach combining ECA Rules with temporal interval-based KR Event/Action Logics and Transactional Update Logics
Venue: arXiv cs.AI 2006
Year: 2006

An important problem to be addressed within Event-Driven Architecture (EDA) is how to correctly and efficiently capture and process the event/action-based logic. This paper endeavors to bridge the gap between the Knowledge Representation (KR) approaches based on durable events/actions and such formalisms as event calculus, on one hand, and event-condition-action (ECA) reaction rules extending the approach of active databases that view events as instantaneous occurrences and/or sequences of events, on the other. We propose formalism based on reaction rules (ECA rules) and a novel interval-based event logic and present concrete RuleML-based syntax, semantics and implementation. We further evaluate this approach theoretically, experimentally and on an example derived from common industry use cases and illustrate its benefits.
On the Analysis and Generalization of Extended Visual Cryptography Schemes
Venue: arXiv cs.CR 2006
Year: 2006

An Extended Visual Cryptography Scheme (EVCS) was proposed by Ateniese et al. [3] to protect a binary secret image with meaningful (innocent-looking) shares. This is implemented by concatenating an extended matrix to each basis matrix. The minimum size of the extended matrix was obtained from a hypergraph coloring model and the scheme was designed for binary images only [3]. In this paper, we give a more concise derivation for this matrix extension for color images. Furthermore, we present a (k, n) scheme to protect multiple color images with meaningful shares. This scheme is an extension of the (n, n) VCS for multiple binary images proposed in Droste scheme [2].
Efficient constraint propagation engines
Venue: arXiv cs.AI 2006
Year: 2006

This paper presents a model and implementation techniques for speeding up constraint propagation. Three fundamental approaches to improving constraint propagation based on propagators as implementations of constraints are explored: keeping track of which propagators are at fixpoint, choosing which propagator to apply next, and how to combine several propagators for the same constraint. We show how idempotence reasoning and events help track fixpoints more accurately. We improve these methods by using them dynamically (taking into account current domains to improve accuracy). We define priority-based approaches to choosing a next propagator and show that dynamic priorities can improve propagation. We illustrate that the use of multiple propagators for the same constraint can be advantageous with priorities, and introduce staged propagators that combine the effects of multiple propagators with priorities for greater efficiency.
On the structure of generalized toric codes
Venue: arXiv cs.IT 2006
Year: 2006

Toric codes are obtained by evaluating rational functions of a nonsingular toric variety at the algebraic torus. One can extend toric codes to the so called generalized toric codes. This extension consists on evaluating elements of an arbitrary polynomial algebra at the algebraic torus instead of a linear combination of monomials whose exponents are rational points of a convex polytope. We study their multicyclic and metric structure, and we use them to express their dual and to estimate their minimum distance.
Developing strategies to produce better scientific papers: a Recipe for non-native users of English
Venue: arXiv cs.OH 2006
Year: 2006

In this paper we introduce the AMADEUS strategy, which has been used to produce scientific writing tools for non-native users of English for 15 years, and emphasize a learn-by-doing approach through which students and novice writers can improve their scientific writing. More specifically, we provide a 9-step recipe for the students to compile writing material according to a procedure that has proven efficient in scientific writing courses.
On the Fairness of Rate Allocation in Gaussian Multiple Access Channel and Broadcast Channel
Venue: arXiv cs.IT 2006
Year: 2006

The capacity region of a channel consists of all achievable rate vectors. Picking a particular point in the capacity region is synonymous with rate allocation. The issue of fairness in rate allocation is addressed in this paper. We review several notions of fairness, including max-min fairness, proportional fairness and Nash bargaining solution. Their efficiencies for general multiuser channels are discussed. We apply these ideas to the Gaussian multiple access channel (MAC) and the Gaussian broadcast channel (BC). We show that in the Gaussian MAC, max-min fairness and proportional fairness coincide. For both Gaussian MAC and BC, we devise efficient algorithms that locate the fair point in the capacity region. Some elementary properties of fair rate allocations are proved.
An associative memory for the on-line recognition and prediction of temporal sequences
Venue: arXiv cs.NE 2006
Year: 2006

This paper presents the design of an associative memory with feedback that is capable of on-line temporal sequence learning. A framework for on-line sequence learning has been proposed, and different sequence learning models have been analysed according to this framework. The network model is an associative memory with a separate store for the sequence context of a symbol. A sparse distributed memory is used to gain scalability. The context store combines the functionality of a neural layer with a shift register. The sensitivity of the machine to the sequence context is controllable, resulting in different characteristic behaviours. The model can store and predict on-line sequences of various types and length. Numerical simulations on the model have been carried out to determine its properties.
Relatively inertial delays
Venue: arXiv cs.OH 2006
Year: 2006

The paper studies the relatively inertial delays that represent one of the most important concepts in the modeling of the asynchronous circuits.
Faster Streaming algorithms for graph spanners
Venue: arXiv cs.DS 2006
Year: 2006

Given an undirected graph $G=(V,E)$ on $n$ vertices, $m$ edges, and an integer $t\ge 1$, a subgraph $(V,E_S)$, $E_S\subseteq E$ is called a $t$-spanner if for any pair of vertices $u,v \in V$, the distance between them in the subgraph is at most $t$ times the actual distance. We present streaming algorithms for computing a $t$-spanner of essentially optimal size-stretch trade offs for any undirected graph. Our first algorithm is for the classical streaming model and works for unweighted graphs only. The algorithm performs a single pass on the stream of edges and requires $O(m)$ time to process the entire stream of edges. This drastically improves the previous best single pass streaming algorithm for computing a $t$-spanner which requires $θ(mn^{\frac{2}{t}})$ time to process the stream and computes spanner with size slightly larger than the optimal. Our second algorithm is for {\em StreamSort} model introduced by Aggarwal et al. [FOCS 2004], which is the streaming model augmented with a sorting primitive. The {\em StreamSort} model has been shown to be a more powerful and still very realistic model than the streaming model for massive data sets applications. Our algorithm, which works of weighted graphs as well, performs $O(t)$ passes using $O(\log n)$ bits of working memory only. Our both the algorithms require elementary data structures.
A Relational Approach to Functional Decomposition of Logic Circuits
Venue: arXiv cs.DM 2006
Year: 2006

Functional decomposition of logic circuits has profound influence on all quality aspects of the cost-effective implementation of modern digital systems. In this paper, a relational approach to the decomposition of logic circuits is proposed. This approach is parallel to the normalization of relational databases, they are governed by the same concepts of functional dependency (FD) and multi-valued dependency (MVD). It is manifest that the functional decomposition of switching function actually exploits the same idea and serves a similar purpose as database normalization. Partitions play an important role in the decomposition. The interdependency of two partitions can be represented by a bipartite graph. We demonstrate that both FD and MVD can be represented by bipartite graphs with specific topological properties, which are delineated by partitions of minterms. It follows that our algorithms are procedures of constructing those specific bipartite graphs of interest to meet the information-lossless criteria of functional decomposition.
Cryptanalyse de Achterbahn-128/80
Venue: arXiv cs.CR 2006
Year: 2006

This paper presents two attacks against Achterbahn-128/80, the last version of one of the stream cipher proposals in the eSTREAM project. The attack against the 80-bit variant, Achterbahn-80, has complexity 2^{56.32}. The attack against Achterbahn-128 requires 2^{75.4} operations and 2^{61} keystream bits. These attacks are based on an improvement of the attack due to Hell and Johansson against Achterbahn version 2 and also on an algorithm that makes profit of the short lengths of the constituent registers. ***** Ce papier présente deux attaques sur Achterbahn-128/80, la dernière version d'un des algorithmes proposés dans le cadre de eSTREAM. L'attaque sur la version de 80 bits, Achterbahn-80, est en 2^{56.32}. L'attaque sur Achterbahn-128 a besoin de 2^{75.4} calculs et 2^{61} bits de suite chiffrante. Ces attaques sont basées sur une amélioration de l'attaque proposée par Hell et Johansson sur la version 2 d'Achterbahn et aussi sur un algorithme qui tire profit des petites longueurs des registres.
Substitutions for tilings $\{p,q\}$
Venue: arXiv cs.CG 2006
Year: 2006

In this paper we consider tiling $\{p, q \}$ of the Euclidean space and of the hyperbolic space, and its dual graph $Γ_{q, p}$ from a combinatorial point of view. A substitution $σ_{q, p}$ on an appropriate finite alphabet is constructed. The homogeneity of graph $Γ_{q, p}$ and its generation function are the basic tools for the construction. The tree associated with substitution $σ_{q, p}$ is a spanning tree of graph $Γ_{q, p}$. Let $u_n$ be the number of tiles of tiling $\{p, q \}$ of generation $n$. The characteristic polynomial of the transition matrix of substitution $σ_{q, p}$ is a characteristic polynomial of a linear recurrence. The sequence $(u_n)_{n \geq 0}$ is a solution of this recurrence. The growth of sequence $(u_n)_{n \geq 0}$ is given by the dominant root of the characteristic polynomial.
On the Convexity of log det (I + K X^{-1})
Venue: arXiv cs.IT 2006
Year: 2006

A simple proof is given for the convexity of log det (I+K X^{-1}) in the positive definite matrix variable X with a given positive semidefinite K.
Formalising Sylow's theorems in Coq
Venue: arXiv cs.LO 2006
Year: 2006

This report presents a formalisation of Sylow's theorems done in {\sc Coq}. The formalisation has been done in a couple of weeks on top of Georges Gonthier's {\sc ssreflect} \cite{ssreflect}. There were two ideas behind formalising Sylow's theorems. The first one was to get familiar with Georges way of doing proofs. The second one was to contribute to the collective effort to formalise a large subset of group theory in {\sc Coq} with some non-trivial proofs.}
A modular eballot system - V0.6
Venue: arXiv cs.CR 2006
Year: 2006

We consider a reasonably simple voting system which can be implemented for web-based ballots. Simplicity, modularity and the requirement of compatibility with current web browsers leads to a system which satisfies a set of security requirements for a ballot system which is not complete but sufficient in many cases. Due to weak-eligibility and vote-selling, this system cannot be used for political or similar ballots.
On "P = NP: Linear Programming Formulation of the Traveling Salesman Problem": A reply to Hofman's Claim of a "Counter-Example"
Venue: arXiv cs.CC 2006
Year: 2006

We show that Hofman's claim of a "counter-example" to Diaby's LP formulation of the TSP is invalid.
A Combined LIFO-Priority Scheme for Overload Control of E-commerce Web Servers
Venue: arXiv cs.PF 2006
Year: 2006

E-commerce Web-servers often face overload conditions during which revenue-generating requests may be dropped or abandoned due to an increase in the browsing requests. In this paper we present a simple, yet effective, mechanism for overload control of E-commerce Web-servers. We develop an E-commerce workload model that separates the browsing requests from revenue-generating transaction requests. During overload, we apply LIFO discipline in the browsing queues and use a dynamic priority model to service them. The transaction queues are given absolute priority over the browsing queues. This is called the LIFO-Pri scheduling discipline. Experimental results show that LIFO-Pri dramatically improves the overall Web-server throughput while also increasing the completion rate of revenue-generating requests. The Web-server was able to operate at nearly 60% of its maximum capacity even when offered load was 1.5 times its capacity. Further, when compared to a single queue FIFO system, there was a seven-fold increase in the number of completed revenue-generating requests during overload.
On the Rate Distortion Function of Certain Sources with a Proportional Mean-Square Error Distortion Measure
Venue: arXiv cs.IT 2006
Year: 2006

New bounds on the rate distortion function of certain non-Gaussian sources, with a proportional-weighted mean-square error (MSE) distortion measure, are given. The growth, g, of the rate distortion function, as a result of changing from a non-weighted MSE distortion measure to a proportional-weighted distortion criterion is analyzed. It is shown that for a small distortion, d, the growth, g, and the difference between the rate distortion functions of a Gaussian memoryless source and a source with memory, both with the same marginal statistics and MSE distortion measure, share the same lower bound. Several examples and applications are also given.
Mixing and non-mixing local minima of the entropy contrast for blind source separation
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, both non-mixing and mixing local minima of the entropy are analyzed from the viewpoint of blind source separation (BSS); they correspond respectively to acceptable and spurious solutions of the BSS problem. The contribution of this work is twofold. First, a Taylor development is used to show that the \textit{exact} output entropy cost function has a non-mixing minimum when this output is proportional to \textit{any} of the non-Gaussian sources, and not only when the output is proportional to the lowest entropic source. Second, in order to prove that mixing entropy minima exist when the source densities are strongly multimodal, an entropy approximator is proposed. The latter has the major advantage that an error bound can be provided. Even if this approximator (and the associated bound) is used here in the BSS context, it can be applied for estimating the entropy of any random variable with multimodal density.
Low-rank matrix factorization with attributes
Venue: arXiv cs.LG 2006
Year: 2006

We develop a new collaborative filtering (CF) method that combines both previously known users' preferences, i.e. standard CF, as well as product/user attributes, i.e. classical function approximation, to predict a given user's interest in a particular product. Our method is a generalized low rank matrix completion problem, where we learn a function whose inputs are pairs of vectors -- the standard low rank matrix completion problem being a special case where the inputs to the function are the row and column indices of the matrix. We solve this generalized matrix completion problem using tensor product kernels for which we also formally generalize standard kernel properties. Benchmark experiments on movie ratings show the advantages of our generalized matrix completion method over the standard matrix completion one with no information about movies or people, as well as over standard multi-task or single task learning methods.
Static Safety for an Actor Dedicated Process Calculus by Abstract Interpretation
Venue: arXiv cs.DC 2006
Year: 2006

The actor model eases the definition of concurrent programs with non uniform behaviors. Static analysis of such a model was previously done in a data-flow oriented way, with type systems. This approach was based on constraint set resolution and was not able to deal with precise properties for communications of behaviors. We present here a new approach, control-flow oriented, based on the abstract interpretation framework, able to deal with communication of behaviors. Within our new analyses, we are able to verify most of the previous properties we observed as well as new ones, principally based on occurrence counting.
A Generic Global Constraint based on MDDs
Venue: arXiv cs.AI 2006
Year: 2006

The paper suggests the use of Multi-Valued Decision Diagrams (MDDs) as the supporting data structure for a generic global constraint. We give an algorithm for maintaining generalized arc consistency (GAC) on this constraint that amortizes the cost of the GAC computation over a root-to-terminal path in the search tree. The technique used is an extension of the GAC algorithm for the regular language constraint on finite length input. Our approach adds support for skipped variables, maintains the reduced property of the MDD dynamically and provides domain entailment detection. Finally we also show how to adapt the approach to constraint types that are closely related to MDDs, such as AOMDDs and Case DAGs.
Complementary Sets, Generalized Reed-Muller Codes, and Power Control for OFDM
Venue: arXiv cs.IT 2006
Year: 2006

The use of error-correcting codes for tight control of the peak-to-mean envelope power ratio (PMEPR) in orthogonal frequency-division multiplexing (OFDM) transmission is considered in this correspondence. By generalizing a result by Paterson, it is shown that each q-phase (q is even) sequence of length 2^m lies in a complementary set of size 2^{k+1}, where k is a nonnegative integer that can be easily determined from the generalized Boolean function associated with the sequence. For small k this result provides a reasonably tight bound for the PMEPR of q-phase sequences of length 2^m. A new 2^h-ary generalization of the classical Reed-Muller code is then used together with the result on complementary sets to derive flexible OFDM coding schemes with low PMEPR. These codes include the codes developed by Davis and Jedwab as a special case. In certain situations the codes in the present correspondence are similar to Paterson's code constructions and often outperform them.
High SNR Analysis for MIMO Broadcast Channels: Dirty Paper Coding vs. Linear Precoding
Venue: arXiv cs.IT 2006
Year: 2006

We study the MIMO broadcast channel and compare the achievable throughput for the optimal strategy of dirty paper coding to that achieved with sub-optimal and lower complexity linear precoding (e.g., zero-forcing and block diagonalization) transmission. Both strategies utilize all available spatial dimensions and therefore have the same multiplexing gain, but an absolute difference in terms of throughput does exist. The sum rate difference between the two strategies is analytically computed at asymptotically high SNR, and it is seen that this asymptotic statistic provides an accurate characterization at even moderate SNR levels. Furthermore, the difference is not affected by asymmetric channel behavior when each user a has different average SNR. Weighted sum rate maximization is also considered, and a similar quantification of the throughput difference between the two strategies is performed. In the process, it is shown that allocating user powers in direct proportion to user weights asymptotically maximizes weighted sum rate. For multiple antenna users, uniform power allocation across the receive antennas is applied after distributing power proportional to the user weight.