OpenRaiser/Intern-Atlas huggingface dataset:
Area-Universal Rectangular Layouts
Venue: arXiv cs.CG 2009
Year: 2009

A rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. Rectangular layouts appear in various applications: as rectangular cartograms in cartography, as floorplans in building architecture and VLSI design, and as graph drawings. Often areas are associated with the rectangles of a rectangular layout and it might hence be desirable if one rectangular layout can represent several area assignments. A layout is area-universal if any assignment of areas to rectangles can be realized by a combinatorially equivalent rectangular layout. We identify a simple necessary and sufficient condition for a rectangular layout to be area-universal: a rectangular layout is area-universal if and only if it is one-sided. More generally, given any rectangular layout L and any assignment of areas to its regions, we show that there can be at most one layout (up to horizontal and vertical scaling) which is combinatorially equivalent to L and achieves a given area assignment. We also investigate similar questions for perimeter assignments. The adjacency requirements for the rectangles of a rectangular layout can be specified in various ways, most commonly via the dual graph of the layout. We show how to find an area-universal layout for a given set of adjacency requirements whenever such a layout exists.
Improved Delay Estimates for a Queueing Model for Random Linear Coding for Unicast
Venue: arXiv cs.IT 2009
Year: 2009

Consider a lossy communication channel for unicast with zero-delay feedback. For this communication scenario, a simple retransmission scheme is optimum with respect to delay. An alternative approach is to use random linear coding in automatic repeat-request (ARQ) mode. We extend the work of Shrader and Ephremides, by deriving an expression for the delay of random linear coding over field of infinite size. Simulation results for various field sizes are also provided.
Determination of Minimal Sets of Control Places for Safe Petri Nets
Venue: arXiv cs.IT 2009
Year: 2009

Our objective is to design a controlled system with a simple method for discrete event systems based on Petri nets. It is possible to construct the Petri net model of a system and the specification separately. By synchronous composition of both models, the desired functioning closed loop model is deduced. Often uncontrollable transitions lead to forbidden states. The problem of forbidden states is solved using linear constraints. A set of linear constraints allows forbidding the reachability of these states. Generally, the number of these so-called forbidden states and consequently the number of constraints are large and lead to a great number of control places. A systematic method to reduce the size and the number of constraints for safe Petri Nets is given. By using a method based on the Petri nets invariants, maximal permissive controllers are determined. The size of the controller is close to the size of the specified model, and it can be implemented on a PLC in a structural way.
Fixing Convergence of Gaussian Belief Propagation
Venue: arXiv cs.IT 2009
Year: 2009

Gaussian belief propagation (GaBP) is an iterative message-passing algorithm for inference in Gaussian graphical models. It is known that when GaBP converges it converges to the correct MAP estimate of the Gaussian random vector and simple sufficient conditions for its convergence have been established. In this paper we develop a double-loop algorithm for forcing convergence of GaBP. Our method computes the correct MAP estimate even in cases where standard GaBP would not have converged. We further extend this construction to compute least-squares solutions of over-constrained linear systems. We believe that our construction has numerous applications, since the GaBP algorithm is linked to solution of linear systems of equations, which is a fundamental problem in computer science and engineering. As a case study, we discuss the linear detection problem. We show that using our new construction, we are able to force convergence of Montanari's linear detection algorithm, in cases where it would originally fail. As a consequence, we are able to increase significantly the number of users that can transmit concurrently.
Geospatial semantics: beyond ontologies, towards an enactive approach
Venue: arXiv cs.AI 2009
Year: 2009

Current approaches to semantics in the geospatial domain are mainly based on ontologies, but ontologies, since continue to build entirely on the symbolic methodology, suffers from the classical problems, e.g. the symbol grounding problem, affecting representational theories. We claim for an enactive approach to semantics, where meaning is considered to be an emergent feature arising context-dependently in action. Since representational theories are unable to deal with context, a new formalism is required toward a contextual theory of concepts. SCOP is considered a promising formalism in this sense and is briefly described.
LR-aided MMSE lattice decoding is DMT optimal for all approximately universal codes
Venue: arXiv cs.IT 2009
Year: 2009

Currently for the nt x nr MIMO channel, any explicitly constructed space-time (ST) designs that achieve optimality with respect to the diversity multiplexing tradeoff (DMT) are known to do so only when decoded using maximum likelihood (ML) decoding, which may incur prohibitive decoding complexity. In this paper we prove that MMSE regularized lattice decoding, as well as the computationally efficient lattice reduction (LR) aided MMSE decoder, allows for efficient and DMT optimal decoding of any approximately universal lattice-based code. The result identifies for the first time an explicitly constructed encoder and a computationally efficient decoder that achieve DMT optimality for all multiplexing gains and all channel dimensions. The results hold irrespective of the fading statistics.
Physarum boats: If plasmodium sailed it would never leave a port
Venue: arXiv cs.RO 2009
Year: 2009

Plasmodium of \emph{Physarum polycephalum} is a single huge (visible by naked eye) cell with myriad of nuclei. The plasmodium is a promising substrate for non-classical, nature-inspired, computing devices. It is capable for approximation of shortest path, computation of planar proximity graphs and plane tessellations, primitive memory and decision-making. The unique properties of the plasmodium make it an ideal candidate for a role of amorphous biological robots with massive parallel information processing and distributed inputs and outputs. We show that when adhered to light-weight object resting on a water surface the plasmodium can propel the object by oscillating its protoplasmic pseudopodia. In experimental laboratory conditions and computational experiments we study phenomenology of the plasmodium-floater system, and possible mechanisms of controlling motion of objects propelled by on board plasmodium.
Ethemba Trusted Host EnvironmentMainly Based on Attestation
Venue: arXiv cs.CR 2009
Year: 2009

Ethemba provides a framework and demonstrator for TPM applications.
Robust Key Agreement Schemes
Venue: arXiv cs.IT 2009
Year: 2009

This paper considers a key agreement problem in which two parties aim to agree on a key by exchanging messages in the presence of adversarial tampering. The aim of the adversary is to disrupt the key agreement process, but there are no secrecy constraints (i.e. we do not insist that the key is kept secret from the adversary). The main results of the paper are coding schemes and bounds on maximum key generation rates for this problem.
Square root meadows
Venue: arXiv cs.LO 2009
Year: 2009

Let Q_0 denote the rational numbers expanded to a meadow by totalizing inversion such that 0^{-1}=0. Q_0 can be expanded by a total sign function s that extracts the sign of a rational number. In this paper we discuss an extension Q_0(s ,\sqrt) of the signed rationals in which every number has a unique square root.
Space Efficient Secret Sharing
Venue: arXiv cs.CR 2009
Year: 2009

This note proposes a method of space efficient secret sharing in which k secrets are mapped into n shares (n>=k) of the same size. Since, n can be chosen to be equal to k, the method is space efficient. This method may be compared with conventional secret sharing schemes that divide a single secret into n shares.
How Emotional Mechanism Helps Episodic Learning in a Cognitive Agent
Venue: arXiv cs.AI 2009
Year: 2009

In this paper we propose the CTS (Concious Tutoring System) technology, a biologically plausible cognitive agent based on human brain functions.This agent is capable of learning and remembering events and any related information such as corresponding procedures, stimuli and their emotional valences. Our proposed episodic memory and episodic learning mechanism are closer to the current multiple-trace theory in neuroscience, because they are inspired by it [5] contrary to other mechanisms that are incorporated in cognitive agents. This is because in our model emotions play a role in the encoding and remembering of events. This allows the agent to improve its behavior by remembering previously selected behaviors which are influenced by its emotional mechanism. Moreover, the architecture incorporates a realistic memory consolidation process based on a data mining algorithm.
Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals
Venue: arXiv cs.IT 2009
Year: 2009

Wideband analog signals push contemporary analog-to-digital conversion systems to their performance limits. In many applications, however, sampling at the Nyquist rate is inefficient because the signals of interest contain only a small number of significant frequencies relative to the bandlimit, although the locations of the frequencies may not be known a priori. For this type of sparse signal, other sampling strategies are possible. This paper describes a new type of data acquisition system, called a random demodulator, that is constructed from robust, readily available components. Let K denote the total number of frequencies in the signal, and let W denote its bandlimit in Hz. Simulations suggest that the random demodulator requires just O(K log(W/K)) samples per second to stably reconstruct the signal. This sampling rate is exponentially lower than the Nyquist rate of W Hz. In contrast with Nyquist sampling, one must use nonlinear methods, such as convex programming, to recover the signal from the samples taken by the random demodulator. This paper provides a detailed theoretical analysis of the system's performance that supports the empirical observations.
An Alternative Cracking of The Genetic Code
Venue: arXiv cs.OH 2009
Year: 2009

We Propose 22 unique Solutions to the Genetic Code. An Alternative Cracking, from the Perspective of a Mathematician.
Asymmetric numeral systems
Venue: arXiv cs.IT 2009
Year: 2009

In this paper will be presented new approach to entropy coding: family of generalizations of standard numeral systems which are optimal for encoding sequence of equiprobable symbols, into asymmetric numeral systems - optimal for freely chosen probability distributions of symbols. It has some similarities to Range Coding but instead of encoding symbol in choosing a range, we spread these ranges uniformly over the whole interval. This leads to simpler encoder - instead of using two states to define range, we need only one. This approach is very universal - we can obtain from extremely precise encoding (ABS) to extremely fast with possibility to additionally encrypt the data (ANS). This encryption uses the key to initialize random number generator, which is used to calculate the coding tables. Such preinitialized encryption has additional advantage: is resistant to brute force attack - to check a key we have to make whole initialization. There will be also presented application for new approach to error correction: after an error in each step we have chosen probability to observe that something was wrong. There will be also presented application for new approach to error correction: after an error in each step we have chosen probability to observe that something was wrong. We can get near Shannon's limit for any noise level this way with expected linear time of correction.
Multiple time-delays system modeling and control for router management
Venue: arXiv cs.NI 2009
Year: 2009

This paper investigates the overload problem of a single congested router in TCP (Transmission Control Protocol) networks. To cope with the congestion phenomenon, we design a feedback control based on a multiple time-delays model of the set TCP/AQM (Active Queue Management). Indeed, using robust control tools, especially in the quadratic separation framework, the TCP/AQM model is rewritten as an intercon- nected system and a structured state feedback is constructed to stabilize the network variables. Finally, we illustrate the proposed methodology with a numerical example and simulations using NS-2 simulator.
Robust control tools for traffic monitoring in TCP/AQM networks
Venue: arXiv cs.NI 2009
Year: 2009

Several studies have considered control theory tools for traffic control in communication networks, as for example the congestion control issue in IP (Internet Protocol) routers. In this paper, we propose to design a linear observer for time-delay systems to address the traffic monitoring issue in TCP/AQM (Transmission Control Protocol/Active Queue Management) networks. Due to several propagation delays and the queueing delay, the set TCP/AQM is modeled as a multiple delayed system of a particular form. Hence, appropriate robust control tools as quadratic separation are adopted to construct a delay dependent observer for TCP flows estimation. Note that, the developed mechanism enables also the anomaly detection issue for a class of DoS (Denial of Service) attacks. At last, simulations via the network simulator NS-2 and an emulation experiment validate the proposed methodology.
Optimal design and optimal control of structures undergoing finite rotations and elastic deformations
Venue: arXiv cs.NE 2009
Year: 2009

In this work we deal with the optimal design and optimal control of structures undergoing large rotations. In other words, we show how to find the corresponding initial configuration and the corresponding set of multiple load parameters in order to recover a desired deformed configuration or some desirable features of the deformed configuration as specified more precisely by the objective or cost function. The model problem chosen to illustrate the proposed optimal design and optimal control methodologies is the one of geometrically exact beam. First, we present a non-standard formulation of the optimal design and optimal control problems, relying on the method of Lagrange multipliers in order to make the mechanics state variables independent from either design or control variables and thus provide the most general basis for developing the best possible solution procedure. Two different solution procedures are then explored, one based on the diffuse approximation of response function and gradient method and the other one based on genetic algorithm. A number of numerical examples are given in order to illustrate both the advantages and potential drawbacks of each of the presented procedures.
Fast solving of Weighted Pairing Least-Squares systems
Venue: arXiv cs.MS 2009
Year: 2009

This paper presents a generalization of the "weighted least-squares" (WLS), named "weighted pairing least-squares" (WPLS), which uses a rectangular weight matrix and is suitable for data alignment problems. Two fast solving methods, suitable for solving full rank systems as well as rank deficient systems, are studied. Computational experiments clearly show that the best method, in terms of speed, accuracy, and numerical stability, is based on a special {1, 2, 3}-inverse, whose computation reduces to a very simple generalization of the usual "Cholesky factorization-backward substitution" method for solving linear systems.
Weak Mso with the Unbounding Quantifier
Venue: arXiv cs.FL 2009
Year: 2009

A new class of languages of infinite words is introduced, called the max-regular languages, extending the class of $ω$-regular languages. The class has two equivalent descriptions: in terms of automata (a type of deterministic counter automaton), and in terms of logic (weak monadic second-order logic with a bounding quantifier). Effective translations between the logic and automata are given.
Extraction de concepts sous contraintes dans des données d'expression de gènes
Venue: arXiv cs.LG 2009
Year: 2009

In this paper, we propose a technique to extract constrained formal concepts.
Personalised and Dynamic Trust in Social Networks
Venue: arXiv cs.CY 2009
Year: 2009

We propose a novel trust metric for social networks which is suitable for application in recommender systems. It is personalised and dynamic and allows to compute the indirect trust between two agents which are not neighbours based on the direct trust between agents that are neighbours. In analogy to some personalised versions of PageRank, this metric makes use of the concept of feedback centrality and overcomes some of the limitations of other trust metrics.In particular, it does not neglect cycles and other patterns characterising social networks, as some other algorithms do. In order to apply the metric to recommender systems, we propose a way to make trust dynamic over time. We show by means of analytical approximations and computer simulations that the metric has the desired properties. Finally, we carry out an empirical validation on a dataset crawled from an Internet community and compare the performance of a recommender system using our metric to one using collaborative filtering.
Forward analysis for WSTS, Part I: Completions
Venue: arXiv cs.LO 2009
Year: 2009

Well-structured transition systems provide the right foundation to compute a finite basis of the set of predecessors of the upward closure of a state. The dual problem, to compute a finite representation of the set of successors of the downward closure of a state, is harder: Until now, the theoretical framework for manipulating downward-closed sets was missing. We answer this problem, using insights from domain theory (dcpos and ideal completions), from topology (sobrifications), and shed new light on the notion of adequate domains of limits.
Convergence and Tradeoff of Utility-Optimal CSMA
Venue: arXiv cs.IT 2009
Year: 2009

It has been recently suggested that in wireless networks, CSMA-based distributed MAC algorithms could achieve optimal utility without any message passing. We present the first proof of convergence of such adaptive CSMA algorithms towards an arbitrarily tight approximation of utility-optimizing schedule. We also briefly discuss the tradeoff between optimality at equilibrium and short-term fairness practically achieved by such algorithms.
Computing Graph Roots Without Short Cycles
Venue: arXiv cs.DM 2009
Year: 2009

Graph G is the square of graph H if two vertices x, y have an edge in G if and only if x, y are of distance at most two in H. Given H it is easy to compute its square H2, however Motwani and Sudan proved that it is NP-complete to determine if a given graph G is the square of some graph H (of girth 3). In this paper we consider the characterization and recognition problems of graphs that are squares of graphs of small girth, i.e. to determine if G = H2 for some graph H of small girth. The main results are the following. - There is a graph theoretical characterization for graphs that are squares of some graph of girth at least 7. A corollary is that if a graph G has a square root H of girth at least 7 then H is unique up to isomorphism. - There is a polynomial time algorithm to recognize if G = H2 for some graph H of girth at least 6. - It is NP-complete to recognize if G = H2 for some graph H of girth 4. These results almost provide a dichotomy theorem for the complexity of the recognition problem in terms of girth of the square roots. The algorithmic and graph theoretical results generalize previous results on tree square roots, and provide polynomial time algorithms to compute a graph square root of small girth if it exists. Some open questions and conjectures will also be discussed.
Online Scheduling of Bounded Length Jobs to Maximize Throughput
Venue: arXiv cs.DS 2009
Year: 2009

We consider an online scheduling problem, motivated by the issues present at the joints of networks using ATM and TCP/IP. Namely, IP packets have to broken down to small ATM cells and sent out before their deadlines, but cells corresponding to different packets can be interwoven. More formally, we consider the online scheduling problem with preemptions, where each job j is revealed at release time r_j, has processing time p_j, deadline d_j and weight w_j. A preempted job can be resumed at any time. The goal is to maximize the total weight of all jobs completed on time. Our main result are as follows: we prove that if all jobs have processing time exactly k, the deterministic competitive ratio is between 2.598 and 5, and when the processing times are at most k, the deterministic competitive ratio is Theta(k/log k).
On Isometries for Convolutional Codes
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we will discuss isometries and strong isometries for convolutional codes. Isometries are weight-preserving module isomorphisms whereas strong isometries are, in addition, degree-preserving. Special cases of these maps are certain types of monomial transformations. We will show a form of MacWilliams Equivalence Theorem, that is, each isometry between convolutional codes is given by a monomial transformation. Examples show that strong isometries cannot be characterized this way, but special attention paid to the weight adjacency matrices allows for further descriptions. Various distance parameters appearing in the literature on convolutional codes will be discussed as well.
A Time Lower Bound for Multiple Nucleation on a Surface
Venue: arXiv cs.CC 2009
Year: 2009

Majumder, Reif and Sahu have presented a stochastic model of reversible, error-permitting, two-dimensional tile self-assembly, and showed that restricted classes of tile assembly systems achieved equilibrium in (expected) polynomial time. One open question they asked was how much computational power would be added if the model permitted multiple nucleation, i.e., independent groups of tiles growing before attaching to the original seed assembly. This paper provides a partial answer, by proving that if a tile assembly model uses only local binding rules, then it cannot use multiple nucleation on a surface to solve certain "simple" problems in constant time (time independent of the size of the surface). Moreover, this time bound applies to macroscale robotic systems that assemble in a three-dimensional grid, not just to tile assembly systems on a two-dimensional surface. The proof technique defines a new model of distributed computing that simulates tile (and robotic) self-assembly. Keywords: self-assembly, multiple nucleation, locally checkable labeling.