OpenRaiser/Intern-Atlas huggingface dataset:
Module Theorem for The General Theory of Stable Models
Venue: arXiv cs.AI 2012
Year: 2012

The module theorem by Janhunen et al. demonstrates how to provide a modular structure in answer set programming, where each module has a well-defined input/output interface which can be used to establish the compositionality of answer sets. The theorem is useful in the analysis of answer set programs, and is a basis of incremental grounding and reactive answer set programming. We extend the module theorem to the general theory of stable models by Ferraris et al. The generalization applies to non-ground logic programs allowing useful constructs in answer set programming, such as choice rules, the count aggregate, and nested expressions. Our extension is based on relating the module theorem to the symmetric splitting theorem by Ferraris et al. Based on this result, we reformulate and extend the theory of incremental answer set computation to a more general class of programs.
Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings
Venue: arXiv cs.DS 2012
Year: 2012

The notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semi-complete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, Scott, and Seymour [2, 3, 4, 8, 9, 11]. In this work we introduce a new approach to computing these width measures on semi-complete digraphs, via degree orderings. Using the new technique we are able to reprove the main results of [2, 9] in a unified and significantly simplified way, as well as obtain new results. First, we present polynomial-time approximation algorithms for both cutwidth and pathwidth, faster and simpler than the previously known ones; the most significant improvement is in case of pathwidth, where instead of previously known O(OPT)-approximation in fixed-parameter tractable time [6] we obtain a constant-factor approximation in polynomial time. Secondly, by exploiting the new set of obstacles for cutwidth and pathwidth, we show that topological containment and immersion in semi-complete digraphs can be tested in single-exponential fixed-parameter tractable time. Finally, we present how the new approach can be used to obtain exact fixed-parameter tractable algorithms for cutwidth and pathwidth, with single- exponential running time dependency on the optimal width.
Timing Constraints Support on Petri-Net Model for Healthcare System Design
Venue: arXiv cs.SE 2012
Year: 2012

The worldwide healthcare organizations are facing a number of daunting challenges forcing systems to benefit from modern technologies and telecom capabilities. Hence, systems evolution through extension of the existing information technology infrastructure becomes one of the most challenging aspects of healthcare. In this paper, we present a newly architecture for evolving healthcare systems towards a service-oriented architecture. Since healthcare process exists in temporal context, timing constraints satisfiability verification techniques are growing to enable designers to test and repair design errors. Thanks to Hierarchical Timed Predicate Petri-Net based conceptual framework, desirable properties such as deadlock free and safe as well as timing constraints satisfiability can be easily checked by designer.
A Robust Lot Sizing Problem with Ill-known Demands
Venue: arXiv cs.OH 2012
Year: 2012

The paper deals with a lot sizing problem with ill-known demands modeled by fuzzy intervals whose membership functions are possibility distributions for the values of the uncertain demands. Optimization criteria, in the setting of possibility theory, that lead to choose robust production plans under fuzzy demands are given. Some algorithms for determining optimal robust production plans with respect to the proposed criteria, and for evaluating production plans are provided. Some computational experiments are presented.
Enhancing Information Dissemination in Dynamic Wireless Network using Stability and Beamforming
Venue: arXiv cs.NI 2012
Year: 2012

Mobility causes network structures to change. In PSNs where underlying network structure is changing rapidly, we are interested in studying how information dissemination can be enhanced in a sparse disconnected network where nodes lack the global knowledge about the network. We use beamforming to study the enhancement in the information dissemination process. In order to identify potential beamformers and nodes to which beams should be directed we use the concept of stability. We first predict the stability of a node in the dynamic network using truncated levy walk nature of jump lengths of human mobility and then use this measure to identify beamforming nodes and the nodes to which the beams are directed. We also develop our algorithm such that it does not require any global knowledge about the network and works in a distributed manner. We also show the effect of various parameters such as number of sources, number of packets, mobility parameters, antenna parameters, type of stability used and density of the network on information dissemination in the network. We validate our findings with three validation model, no beamforming, beamforming using different stability measure and when no stability measure is associated but same number of node beamform and the selection of the beamforming nodes is random. Our simulation results show that information dissemination can be enhanced using our algorithm over other models.
Implementation of Distributed Time Exchange Based Cooperative Forwarding
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we design and implement time exchange (TE) based cooperative forwarding where nodes use transmission time slots as incentives for relaying. We focus on distributed joint time slot exchange and relay selection in the sum goodput maximization of the overall network. We formulate the design objective as a mixed integer nonlinear programming (MINLP) problem and provide a polynomial time distributed solution of the MINLP. We implement the designed algorithm in the software defined radio enabled USRP nodes of the ORBIT indoor wireless testbed. The ORBIT grid is used as a global control plane for exchange of control information between the USRP nodes. Experimental results suggest that TE can significantly increase the sum goodput of the network. We also demonstrate the performance of a goodput optimization algorithm that is proportionally fair.
The DoF of Network MIMO with Backhaul Delays
Venue: arXiv cs.IT 2012
Year: 2012

We consider the problem of downlink precoding for Network (multi-cell) MIMO networks where Transmitters (TXs) are provided with imperfect Channel State Information (CSI). Specifically, each TX receives a delayed channel estimate with the delay being specific to each channel component. This model is particularly adapted to the scenarios where a user feeds back its CSI to its serving base only as it is envisioned in future LTE networks. We analyze the impact of the delay during the backhaul-based CSI exchange on the rate performance achieved by Network MIMO. We highlight how delay can dramatically degrade system performance if existing precoding methods are to be used. We propose an alternative robust beamforming strategy which achieves the maximal performance, in DoF sense. We verify by simulations that the theoretical DoF improvement translates into a performance increase at finite Signal-to-Noise Ratio (SNR) as well.
Modeling with Copulas and Vines in Estimation of Distribution Algorithms
Venue: arXiv cs.NE 2012
Year: 2012

The aim of this work is studying the use of copulas and vines in the optimization with Estimation of Distribution Algorithms (EDAs). Two EDAs are built around the multivariate product and normal copulas, and other two are based on pair-copula decomposition of vine models. Empirically we study the effect of both marginal distributions and dependence structure separately, and show that both aspects play a crucial role in the success of the optimization. The results show that the use of copulas and vines opens new opportunities to a more appropriate modeling of search distributions in EDAs.
Hidden Trends in 90 Years of Harvard Business Review
Venue: arXiv cs.CL 2012
Year: 2012

In this paper, we demonstrate and discuss results of our mining the abstracts of the publications in Harvard Business Review between 1922 and 2012. Techniques for computing n-grams, collocations, basic sentiment analysis, and named-entity recognition were employed to uncover trends hidden in the abstracts. We present findings about international relationships, sentiment in HBR's abstracts, important international companies, influential technological inventions, renown researchers in management theories, US presidents via chronological analyses.
Characterizing Properties for Q-Clustering
Venue: arXiv cs.DS 2012
Year: 2012

We uniquely characterize two members of the Q-Clustering family in an axiomatic framework. We introduce properties that use known tree constructions for the purpose of characterization. To characterize the Max-Sum clustering algorithm, we use the Gomory-Hu construction, and to characterize Single-Linkage, we use the Maximum Spanning Tree. Although at first glance it seems these properties are `obviously' all that are necessary to characterize Max-Sum and Single-Linkage, we show that this is not the case, by investigating how subsets of properties interact. We conclude by proposing additions to the taxonomy of clustering paradigms currently in use.
Local Correction with Constant Error Rate
Venue: arXiv cs.CC 2012
Year: 2012

A Boolean function f of n variables is said to be q-locally correctable if, given a black-box access to a function g which is "close" to an isomorphism f_sigma(x)=f_sigma(x_1, ..., x_n) = f(x_sigma(1), ..., x_sigma(n)) of f, we can compute f_sigma(x) for any x in {0,1}^n with good probability using q queries to g. It is known that degree d polynomials are O(2^d)-locally correctable, and that most k-juntas are O(k log k)-locally correctable, where the closeness parameter, or more precisely the distance between g and f_sigma, is required to be exponentially small (in d and k respectively). In this work we relax the requirement for the closeness parameter by allowing the distance between the functions to be a constant. We first investigate the family of juntas, and show that almost every k-junta is O(k log^2 k)-locally correctable for any distance epsilon < 0.001. A similar result is shown for the family of partially symmetric functions, that is functions which are indifferent to any reordering of all but a constant number of their variables. For both families, the algorithms provided here use non-adaptive queries and are applicable to most but not all functions of each family (as it is shown to be impossible to locally correct all of them). Our approach utilizes the measure of symmetric influence introduced in the recent analysis of testing partial symmetry of functions.
Obstructions to chordal circular-arc graphs of small independence number
Venue: arXiv cs.DM 2012
Year: 2012

A blocking quadruple (BQ) is a quadruple of vertices of a graph such that any two vertices of the quadruple either miss (have no neighbours on) some path connecting the remaining two vertices of the quadruple, or are connected by some path missed by the remaining two vertices. This is akin to the notion of asteroidal triple used in the classical characterization of interval graphs by Lekkerkerker and Boland. We show that a circular-arc graph cannot have a blocking quadruple. We also observe that the absence of blocking quadruples is not in general sufficient to guarantee that a graph is a circular-arc graph. Nonetheless, it can be shown to be sufficient for some special classes of graphs, such as those investigated by Bonomo et al. In this note, we focus on chordal graphs, and study the relationship between the structure of chordal graphs and the presence/absence of blocking quadruples. Our contribution is two-fold. Firstly, we provide a forbidden induced subgraph characterization of chordal graphs without blocking quadruples. In particular, we observe that all the forbidden subgraphs are variants of the subgraphs forbidden for interval graphs. Secondly, we show that the absence of blocking quadruples is sufficient to guarantee that a chordal graph with no independent set of size five is a circular-arc graph. In our proof we use a novel geometric approach, constructing a circular-arc representation by traversing around a carefully chosen clique tree.
Optimizing Tile Concentrations to Minimize Errors and Time for DNA Tile Self-Assembly Systems
Venue: arXiv cs.DS 2012
Year: 2012

DNA tile self-assembly has emerged as a rich and promising primitive for nano-technology. This paper studies the problems of minimizing assembly time and error rate by changing the tile concentrations because changing the tile concentrations is easy to implement in actual lab experiments. We prove that setting the concentration of tile $T_i$ proportional to the square root of $N_i$ where $N_i$ is the number of times $T_i$ appears outside the seed structure in the final assembled shape minimizes the rate of growth errors for rectilinear tile systems. We also show that the same concentrations minimize the expected assembly time for a feasible class of tile systems. Moreover, for general tile systems, given tile concentrations, we can approximate the expected assembly time with high accuracy and probability by running only a polynomial number of simulations in the size of the target shape.
Leveraging Peer Centrality in the Design of Socially-Informed Peer-to-Peer Systems
Venue: arXiv cs.SI 2012
Year: 2012

Social applications mine user social graphs to improve performance in search, provide recommendations, allow resource sharing and increase data privacy. When such applications are implemented on a peer-to-peer (P2P) architecture, the social graph is distributed on the P2P system: the traversal of the social graph translates into a socially-informed routing in the peer-to-peer layer. In this work we introduce the model of a projection graph that is the result of decentralizing a social graph onto a peer-to-peer network. We focus on three social network metrics: degree, node betweenness and edge betweenness centrality and analytically formulate the relation between metrics in the social graph and in the projection graph. Through experimental evaluation on real networks, we demonstrate that when mapping user communities of sizes up to 50-150 users on each peer, the association between the properties of the social graph and the projection graph is high, and thus the properties of the (dynamic) projection graph can be inferred from the properties of the (slower changing) social graph. Furthermore, we demonstrate with two application scenarios on large-scale social networks the usability of the projection graph in designing social search applications and unstructured P2P overlays.
Analyzing Consistency of Behavioral REST Web Service Interfaces
Venue: arXiv cs.SE 2012
Year: 2012

REST web services can offer complex operations that do more than just simply creating, retrieving, updating and deleting information from a database. We have proposed an approach to design the interfaces of behavioral REST web services by defining a resource and a behavioral model using UML. In this paper we discuss the consistency between the resource and behavioral models that represent service states using state invariants. The state invariants are defined as predicates over resources and describe what are the valid state configurations of a behavioral model. If a state invariant is unsatisfiable then there is no valid state configuration containing the state and there is no service that can implement the service interface. We also show how we can use reasoning tools to determine the consistency between these design models.
Game Theory in Oligopoly
Venue: arXiv cs.GT 2012
Year: 2012

The game theory techniques are used to find the equilibrium of a market. Game theory refers to the ways in which strategic interactions among economic agents produce outcomes with respect to the preferences (or utilities) of those agents, where the outcomes in question might have been intended by none of the agents. The oligopolistic market structures are taken and how game theory applies to them is explained.
Designing a High Efficiency Pulse Width Modulation Step-Down DC/DC Converter for Mobile Phone Applications
Venue: arXiv cs.OH 2012
Year: 2012

This paper presents the design and analysis of a high efficiency, PWM (Pulse-Width-Modulation) Buck converters for mobile phone applications. The steady-state and average-value models for the proposed converter are developed and simulated. A practical design approach which aims at systematizing the procedure for the selection of the control parameters is introduced. The switching losses are reduced by using soft switching, additionally, a simple analog and digital form of the controller for practical realization is provided. It is found that this controller adopts a structure similar to the conventional PWM voltage mode controller. The proposed circuit uses a current-mode control and a voltage-to-pulse converter for the PWM. The circuit, fabricated using a 0.18-μm CMOS technology, reaches a peak load regulation of 20 mV/V and line regulation of 0.5 mV/V at Current load equal 300 mA. The used 10μH inductance and 22μF capacitor and requires clock and Vref/Vramp input of 1,23V.
Phase Noise Estimation for Uncoded/Coded SISO and MIMO Systems
Venue: arXiv cs.IT 2012
Year: 2012

Non-ideal oscillators both at the transmitter and the receiver introduces time varying phase noise which interacts with the transmitted data in a non-linear fashion. Phase noise becomes a detrimental problem and needs to be estimated and compensated. In this thesis receiver algorithms are derived and evaluated to mitigate the effects of the phase noise in digital communication systems. In Chapter 3 phase noise estimation in single-input single-output (SISO) systems is investigated. First, a hard decision directed extended Kalman filter (EKF) is applied to an uncoded system. Next, an iterative receiver algorithm performing code-aided turbo synchronization is derived using the expectation maximization (EM) framework for a coded system. Two soft-decision directed estimators in the literature based on Kalman filtering are evaluated. Low density parity check (LDPC) codes are proposed to calculate marginal a posteriori probabilities and to construct soft decision symbols. Error rate performance of both estimators are compared through simulations. In Chapter 4 phase noise estimation in multi-input multi-output (MIMO) systems is investigated. First, a low complexity hard decision directed EKF is applied to an uncoded system. Next, a new receiver algorithm based on the EM framework for joint estimation and detection in coded MIMO systems is proposed. A low complexity soft decision directed extended Kalman filter and smoother (EKFS) that tracks the phase noise parameters over a frame is proposed in order to carry out the maximization step. The proposed EKFS based approach is combined with an iterative detector that utilizes bit interleaved coded modulation and employs LDPC codes. Finally, simulation results confirm that the error rate performance of the proposed EM-based approach is close to the scenario of perfect knowledge of phase noise at low-to-medium signal-to-noise ratios.
The price of re-establishing perfect, almost perfect or public monitoring in games with arbitrary monitoring
Venue: arXiv cs.IT 2012
Year: 2012

This paper establishes a connection between the notion of observation (or monitoring) structure in game theory and the one of communication channels in Shannon theory. One of the objectives is to know under which conditions an arbitrary monitoring structure can be transformed into a more pertinent monitoring structure. To this end, a mediator is added to the game. The objective of the mediator is to choose a signalling scheme that allows the players to have perfect, almost perfect or public monitoring and all of this, at a minimum cost in terms of signalling. Graph coloring, source coding, and channel coding are exploited to deal with these issues. A wireless power control game is used to illustrate these notions but the applicability of the provided results and, more importantly, the framework of transforming monitoring structures go much beyond this example.
"To sense" or "not to sense" in energy-efficient power control games
Venue: arXiv cs.GT 2012
Year: 2012

A network of cognitive transmitters is considered. Each transmitter has to decide his power control policy in order to maximize energy-efficiency of his transmission. For this, a transmitter has two actions to take. He has to decide whether to sense the power levels of the others or not (which corresponds to a finite sensing game), and to choose his transmit power level for each block (which corresponds to a compact power control game). The sensing game is shown to be a weighted potential game and its set of correlated equilibria is studied. Interestingly, it is shown that the general hybrid game where each transmitter can jointly choose the hybrid pair of actions (to sense or not to sense, transmit power level) leads to an outcome which is worse than the one obtained by playing the sensing game first, and then playing the power control game. This is an interesting Braess-type paradox to be aware of for energy-efficient power control in cognitive networks.
Implicit cooperation in distributed energy-efficient networks
Venue: arXiv cs.GT 2012
Year: 2012

We consider the problem of cooperation in distributed wireless networks of selfish and free transmitters aiming at maximizing their energy-efficiency. The strategy of each transmitter consists in choosing his power control (PC) policy. Two scenarios are considered: the case where transmitters can update their power levels within time intervals less than the channel coherence time (fast PC) and the case where it is updated only once per time interval (slow PC). One of our objectives is to show how cooperation can be stimulated without assuming cooperation links between the transmitters but only by repeating the corresponding PC game and by signals from the receiver. In order to design efficient PC policies, standard and stochastic repeated games are respectively exploited to analyze the fast and slow PC problems. In the first case a cooperation plan between transmitters, that is both efficient and relies on mild information assumptions, is proposed. In the second case, the region of equilibrium utilities is derived from very recent and powerful results in game theory.