OpenRaiser/Intern-Atlas huggingface dataset:
Extended ASP tableaux and rule redundancy in normal logic programs
Venue: arXiv cs.AI 2008
Year: 2008

We introduce an extended tableau calculus for answer set programming (ASP). The proof system is based on the ASP tableaux defined in [Gebser&Schaub, ICLP 2006], with an added extension rule. We investigate the power of Extended ASP Tableaux both theoretically and empirically. We study the relationship of Extended ASP Tableaux with the Extended Resolution proof system defined by Tseitin for sets of clauses, and separate Extended ASP Tableaux from ASP Tableaux by giving a polynomial-length proof for a family of normal logic programs P_n for which ASP Tableaux has exponential-length minimal proofs with respect to n. Additionally, Extended ASP Tableaux imply interesting insight into the effect of program simplification on the lengths of proofs in ASP. Closely related to Extended ASP Tableaux, we empirically investigate the effect of redundant rules on the efficiency of ASP solving. To appear in Theory and Practice of Logic Programming (TPLP).
Algebraic reduction for space-time codes based on quaternion algebras
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we introduce a new right preprocessing method for the decoding of 2x2 algebraic STBCs, called algebraic reduction, which exploits the multiplicative structure of the code. The principle of the new reduction is to absorb part of the channel into the code, by approximating the channel matrix with an element of the maximal order of the algebra. We prove that algebraic reduction attains the receive diversity when followed by a simple ZF detection. Simulation results for the Golden Code show that using MMSE-GDFE left preprocessing, algebraic reduction with simple ZF detection has a loss of only $3 \dB$ with respect to ML decoding.
Optimal Energy Management Policies for Energy Harvesting Sensor Nodes
Venue: arXiv cs.NI 2008
Year: 2008

We study a sensor node with an energy harvesting source. The generated energy can be stored in a buffer. The sensor node periodically senses a random field and generates a packet. These packets are stored in a queue and transmitted using the energy available at that time. We obtain energy management policies that are throughput optimal, i.e., the data queue stays stable for the largest possible data rate. Next we obtain energy management policies which minimize the mean delay in the queue.We also compare performance of several easily implementable sub-optimal energy management policies. A greedy policy is identified which, in low SNR regime, is throughput optimal and also minimizes mean delay.
A Reconfigurable Programmable Logic Block for a Multi-Style Asynchronous FPGA resistant to Side-Channel Attacks
Venue: arXiv cs.CR 2008
Year: 2008

Side-channel attacks are efficient attacks against cryptographic devices. They use only quantities observable from outside, such as the duration and the power consumption. Attacks against synchronous devices using electric observations are facilitated by the fact that all transitions occur simultaneously with some global clock signal. Asynchronous control remove this synchronization and therefore makes it more difficult for the attacker to insulate \emph{interesting intervals}. In addition the coding of data in an asynchronous circuit is inherently more difficult to attack. This article describes the Programmable Logic Block of an asynchronous FPGA resistant against \emph{side-channel attacks}. Additionally it can implement different styles of asynchronous control and of data representation.
Modelling interdependencies between the electricity and information infrastructures
Venue: arXiv cs.DC 2008
Year: 2008

The aim of this paper is to provide qualitative models characterizing interdependencies related failures of two critical infrastructures: the electricity infrastructure and the associated information infrastructure. The interdependencies of these two infrastructures are increasing due to a growing connection of the power grid networks to the global information infrastructure, as a consequence of market deregulation and opening. These interdependencies increase the risk of failures. We focus on cascading, escalating and common-cause failures, which correspond to the main causes of failures due to interdependencies. We address failures in the electricity infrastructure, in combination with accidental failures in the information infrastructure, then we show briefly how malicious attacks in the information infrastructure can be addressed.
Multistep greedy algorithm identifies community structure in real-world and computer-generated networks
Venue: arXiv cs.DS 2008
Year: 2008

We have recently introduced a multistep extension of the greedy algorithm for modularity optimization. The extension is based on the idea that merging l pairs of communities (l>1) at each iteration prevents premature condensation into few large communities. Here, an empirical formula is presented for the choice of the step width l that generates partitions with (close to) optimal modularity for 17 real-world and 1100 computer-generated networks. Furthermore, an in-depth analysis of the communities of two real-world networks (the metabolic network of the bacterium E. coli and the graph of coappearing words in the titles of papers coauthored by Martin Karplus) provides evidence that the partition obtained by the multistep greedy algorithm is superior to the one generated by the original greedy algorithm not only with respect to modularity but also according to objective criteria. In other words, the multistep extension of the greedy algorithm reduces the danger of getting trapped in local optima of modularity and generates more reasonable partitions.
A computational approach to the covert and overt deployment of spatial attention
Venue: arXiv cs.NE 2008
Year: 2008

Popular computational models of visual attention tend to neglect the influence of saccadic eye movements whereas it has been shown that the primates perform on average three of them per seconds and that the neural substrate for the deployment of attention and the execution of an eye movement might considerably overlap. Here we propose a computational model in which the deployment of attention with or without a subsequent eye movement emerges from local, distributed and numerical computations.
A Computational Study on Emotions and Temperament in Multi-Agent Systems
Venue: arXiv cs.AI 2008
Year: 2008

Recent advances in neurosciences and psychology have provided evidence that affective phenomena pervade intelligence at many levels, being inseparable from the cognitionaction loop. Perception, attention, memory, learning, decisionmaking, adaptation, communication and social interaction are some of the aspects influenced by them. This work draws its inspirations from neurobiology, psychophysics and sociology to approach the problem of building autonomous robots capable of interacting with each other and building strategies based on temperamental decision mechanism. Modelling emotions is a relatively recent focus in artificial intelligence and cognitive modelling. Such models can ideally inform our understanding of human behavior. We may see the development of computational models of emotion as a core research focus that will facilitate advances in the large array of computational systems that model, interpret or influence human behavior. We propose a model based on a scalable, flexible and modular approach to emotion which allows runtime evaluation between emotional quality and performance. The results achieved showed that the strategies based on temperamental decision mechanism strongly influence the system performance and there are evident dependency between emotional state of the agents and their temperamental type, as well as the dependency between the team performance and the temperamental configuration of the team members, and this enable us to conclude that the modular approach to emotional programming based on temperamental theory is the good choice to develop computational mind models for emotional behavioral Multi-Agent systems.
On the Secure Degrees of Freedom of Wireless X Networks
Venue: arXiv cs.IT 2008
Year: 2008

Previous work showed that the X network with M transmitters, N receivers has MN/(M+N-1) degrees of freedom. In this work we study the degrees of freedom of the X network with secrecy constraints, i.e. the X network where some/all messages are confidential. We consider the $M \times N$ network where all messages are secured and show that N(M-1)/(M+N-1) degrees of freedom can be achieved. Secondly, we show that if messages from only M-1 transmitters are confidential, then MN/(M+N-1) degrees of freedom can be achieved meaning that there is no loss of degrees of freedom because of secrecy constraints. We also consider the achievable secure degrees of freedom under a more conservative secrecy constraint. We require that messages from any subset of transmitters are secure even if other transmitters are compromised, i.e., messages from the compromised transmitter are revealed to the unintended receivers. We also study the achievable secure degrees of freedom of the K user Gaussian interference channel under two different secrecy constraints where 1/2 secure degrees of freedom per message can be achieved. The achievable scheme in all cases is based on random binning combined with interference alignment.
On Fan Raspaud Conjecture
Venue: arXiv cs.DM 2008
Year: 2008

A conjecture of Fan and Raspaud [3] asserts that every bridgeless cubic graph con-tains three perfect matchings with empty intersection. Kaiser and Raspaud [6] sug-gested a possible approach to this problem based on the concept of a balanced join in an embedded graph. We give here some new results concerning this conjecture and prove that a minimum counterexample must have at least 32 vertices.
Cross-Layer Adaptive Feedback Scheduling of Wireless Control Systems
Venue: arXiv cs.NI 2008
Year: 2008

There is a trend towards using wireless technologies in networked control systems. However, the adverse properties of the radio channels make it difficult to design and implement control systems in wireless environments. To attack the uncertainty in available communication resources in wireless control systems closed over WLAN, a cross-layer adaptive feedback scheduling (CLAFS) scheme is developed, which takes advantage of the co-design of control and wireless communications. By exploiting cross-layer design, CLAFS adjusts the sampling periods of control systems at the application layer based on information about deadline miss ratio and transmission rate from the physical layer. Within the framework of feedback scheduling, the control performance is maximized through controlling the deadline miss ratio. Key design parameters of the feedback scheduler are adapted to dynamic changes in the channel condition. An event-driven invocation mechanism for the feedback scheduler is also developed. Simulation results show that the proposed approach is efficient in dealing with channel capacity variations and noise interference, thus providing an enabling technology for control over WLAN.
On the Influence of Carrier Frequency Offset and Sampling Frequency Offset in MIMO-OFDM Systems for Future Digital TV
Venue: arXiv cs.NI 2008
Year: 2008

This paper investigates the impact of carrier frequency offset (CFO) and sampling frequency offset (SFO) on the performance of different MIMO-OFDM schemes with high spectral efficiency for next generation of terrestrial digital TV. We analyze particularly orthogonal Alamouti scheme, and non-orthogonal (NO) schemes like VBLAST, linear dispersion (LD) code and Golden code. This analysis gives a global view on the best suitable MIMO-OFDM scheme with respect to CFO and SFO. We show that for high spectral efficiency, Alamouti is more sensitive to CFO and SFO. Moreover, we show that all studied MIMO-OFDM schemes are sensitive to CFO when it is greater than 1% of inter-carrier spacing. Their sensitivity due to SFO is less than that due to CFO.
A New Upper Bound on the Capacity of a Class of Primitive Relay Channels
Venue: arXiv cs.IT 2008
Year: 2008

We obtain a new upper bound on the capacity of a class of discrete memoryless relay channels. For this class of relay channels, the relay observes an i.i.d. sequence $T$, which is independent of the channel input $X$. The channel is described by a set of probability transition functions $p(y|x,t)$ for all $(x,t,y)\in \mathcal{X}\times \mathcal{T}\times \mathcal{Y}$. Furthermore, a noiseless link of finite capacity $R_{0}$ exists from the relay to the receiver. Although the capacity for these channels is not known in general, the capacity of a subclass of these channels, namely when $T=g(X,Y)$, for some deterministic function $g$, was obtained in [1] and it was shown to be equal to the cut-set bound. Another instance where the capacity was obtained was in [2], where the channel output $Y$ can be written as $Y=X\oplus Z$, where $\oplus$ denotes modulo-$m$ addition, $Z$ is independent of $X$, $|\mathcal{X}|=|\mathcal{Y}|=m$, and $T$ is some stochastic function of $Z$. The compress-and-forward (CAF) achievability scheme [3] was shown to be capacity achieving in both cases. Using our upper bound we recover the capacity results of [1] and [2]. We also obtain the capacity of a class of channels which does not fall into either of the classes studied in [1] and [2]. For this class of channels, CAF scheme is shown to be optimal but capacity is strictly less than the cut-set bound for certain values of $R_{0}$. We also evaluate our outer bound for a particular relay channel with binary multiplicative states and binary additive noise for which the channel is given as $Y=TX+N$. We show that our upper bound is strictly better than the cut-set upper bound for certain values of $R_{0}$ but it lies strictly above the rates yielded by the CAF achievability scheme.
Load Repartition for Congestion Control in Multimedia Wireless Sensor Networks with Multipath Routing
Venue: arXiv cs.NI 2008
Year: 2008

Wireless sensor networks hold a great potential in the deployment of several applications of a paramount importance in our daily life. Video sensors are able to improve a number of these applications where new approaches adapted to both wireless sensor networks and video transport specific characteristics are required. The aim of this work is to provide the necessary bandwidth and to alleviate the congestion problem to video streaming. In this paper, we investigate various load repartition strategies for congestion control mechanism on top of a multipath routing feature. Simulations are performed in order to get insight into the performances of our proposals.
Une grammaire formelle du créole martiniquais pour la génération automatique
Venue: arXiv cs.CL 2008
Year: 2008

In this article, some first elements of a computational modelling of the grammar of the Martiniquese French Creole dialect are presented. The sources of inspiration for the modelling is the functional description given by Damoiseau (1984), and Pinalie's & Bernabe's (1999) grammar manual. Based on earlier works in text generation (Vaillant, 1997), a unification grammar formalism, namely Tree Adjoining Grammars (TAG), and a modelling of lexical functional categories based on syntactic and semantic properties, are used to implement a grammar of Martiniquese Creole which is used in a prototype of text generation system. One of the main applications of the system could be its use as a tool software supporting the task of learning Creole as a second language. -- Nous présenterons dans cette communication les premiers travaux de modélisation informatique d'une grammaire de la langue créole martiniquaise, en nous inspirant des descriptions fonctionnelles de Damoiseau (1984) ainsi que du manuel de Pinalie & Bernabé (1999). Prenant appui sur des travaux antérieurs en génération de texte (Vaillant, 1997), nous utilisons un formalisme de grammaires d'unification, les grammaires d'adjonction d'arbres (TAG d'après l'acronyme anglais), ainsi qu'une modélisation de catégories lexicales fonctionnelles à base syntaxico-sémantique, pour mettre en oeuvre une grammaire du créole martiniquais utilisable dans une maquette de système de génération automatique. L'un des intérêts principaux de ce système pourrait être son utilisation comme logiciel outil pour l'aide à l'apprentissage du créole en tant que langue seconde.
Soft Uncoupling of Markov Chains for Permeable Language Distinction: A New Algorithm
Venue: arXiv cs.CL 2008
Year: 2008

Without prior knowledge, distinguishing different languages may be a hard task, especially when their borders are permeable. We develop an extension of spectral clustering -- a powerful unsupervised classification toolbox -- that is shown to resolve accurately the task of soft language distinction. At the heart of our approach, we replace the usual hard membership assignment of spectral clustering by a soft, probabilistic assignment, which also presents the advantage to bypass a well-known complexity bottleneck of the method. Furthermore, our approach relies on a novel, convenient construction of a Markov chain out of a corpus. Extensive experiments with a readily available system clearly display the potential of the method, which brings a visually appealing soft distinction of languages that may define altogether a whole corpus.
Demonstration of Time-Reversal in Indoor Ultra-Wideband Communication: Time Domain Measurement
Venue: arXiv cs.NI 2008
Year: 2008

Using time domain measurements, we assess the feasibility of time-reversal technique in ultra-wideband (UWB) communication. A typical indoor propagation channel is selected for the exploration. The channel response between receive and transmit antenna pairs is measured using time domain equipments which include an arbitrary wave generator (AWG) and a digital storage oscilloscope (DSO). The time-reversed version of the channel response is constructed with AWG and re-transmitted in the channel. The equivalent time reversed channel response is recorded. The properties of the time reversal technique in the line of sight (LOS) co-polar and cross-polar scenarios are measured.
Distributed Kalman Filter via Gaussian Belief Propagation
Venue: arXiv cs.IT 2008
Year: 2008

Recent result shows how to compute distributively and efficiently the linear MMSE for the multiuser detection problem, using the Gaussian BP algorithm. In the current work, we extend this construction, and show that operating this algorithm twice on the matching inputs, has several interesting interpretations. First, we show equivalence to computing one iteration of the Kalman filter. Second, we show that the Kalman filter is a special case of the Gaussian information bottleneck algorithm, when the weight parameter $β= 1$. Third, we discuss the relation to the Affine-scaling interior-point method and show it is a special case of Kalman filter. Besides of the theoretical interest of this linking estimation, compression/clustering and optimization, we allow a single distributed implementation of those algorithms, which is a highly practical and important task in sensor and mobile ad-hoc networks. Application to numerous problem domains includes collaborative signal processing and distributed allocation of resources in a communication network.
Identifying almost sorted permutations from TCP buffer dynamics
Venue: arXiv cs.DS 2008
Year: 2008

Associate to each sequence $A$ of integers (intending to represent packet IDs) a sequence of positive integers of the same length ${\mathcal M}(A)$. The $i$'th entry of ${\mathcal M}(A)$ is the size (at time $i$) of the smallest buffer needed to hold out-of-order packets, where space is accounted for unreceived packets as well. Call two sequences $A$, $B$ {\em equivalent} (written $A\equiv_{FB} B$) if ${\mathcal M}(A)={\mathcal M}(B)$. We prove the following result: any two permutations $A,B$ of the same length with $SUS(A)$, $SUS(B)\leq 3$ (where SUS is the {\em shuffled-up-sequences} reordering measure), and such that $A\equiv_{FB} B$ are identical. The result (which is no longer valid if we replace the upper bound 3 by 4) was motivated by RESTORED, a receiver-oriented model of network traffic we have previously introduced.
Introduction to Searching with Regular Expressions
Venue: arXiv cs.IR 2008
Year: 2008

The explosive rate of information growth and availability often makes it increasingly difficult to locate information pertinent to your needs. These problems are often compounded when keyword based search methodologies are not adequate for describing the information you seek. In many instances, information such as Web site URLs, phone numbers, etc. can often be better identified through the use of a textual pattern than by keyword. For example, many more phone numbers could be picked up by a search for the pattern (XXX) XXX-XXXX, where X could be any digit, than would be by a search for any specific phone number (i.e. the keyword approach). Programming languages typically allow for the matching of textual patterns via the usage of regular expressions. This tutorial will provide an introduction to the basics of programming regular expressions as well as provide an introduction to how regular expressions can be applied to data processing tasks such as information extraction and search refinement.
Unsatisfiable (k,(4*2^k/k))-CNF formulas
Venue: arXiv cs.DM 2008
Year: 2008

A boolean formula in a conjuctive normal form is called a (k,s)-formula if every clause contains exactly k variables and every variable occurs in at most s clauses. We prove the existence of a (k, 4 * (2^k/k))-CNF formula which is unsatisfiable.
Fetching Strategy in the Startup Stage of p2p Live Streaming
Venue: arXiv cs.NI 2008
Year: 2008

A protocol named Threshold Bipolar (TB) is proposed as a fetching strategy at the startup stage of p2p live streaming systems. In this protocol, chunks are fetched consecutively from buffer head at the beginning. After the buffer is filled into a threshold, chunks at the buffer tail will be fetched first while keeping the contiguously filled part in the buffer above the threshold even when the buffer is drained at a playback rate. High download rate, small startup latency and natural strategy handover can be reached at the same time by this protocol. Important parameters in this protocol are identified. The buffer progress under this protocol is then expressed as piecewise lines specified by those parameters. Startup traces of peers measured from PPLive are studied to show the real performance of TB protocol in a real system. A simple design model of TB protocol is proposed to reveal important considerations in a practical design.
On combinations of local theory extensions
Venue: arXiv cs.LO 2008
Year: 2008

In this paper we study possibilities of efficient reasoning in combinations of theories over possibly non-disjoint signatures. We first present a class of theory extensions (called local extensions) in which hierarchical reasoning is possible, and give several examples from computer science and mathematics in which such extensions occur in a natural way. We then identify situations in which combinations of local extensions of a theory are again local extensions of that theory. We thus obtain criteria both for recognizing wider classes of local theory extensions, and for modular reasoning in combinations of theories over non-disjoint signatures.