OpenRaiser/Intern-Atlas huggingface dataset:
Super-Exponential Solution in Markovian Supermarket Models: Framework and Challenge
Venue: arXiv cs.NI 2011
Year: 2011

Marcel F. Neuts opened a key door in numerical computation of stochastic models by means of phase-type (PH) distributions and Markovian arrival processes (MAPs). To celebrate his 75th birthday, this paper reports a more general framework of Markovian supermarket models, including a system of differential equations for the fraction measure and a system of nonlinear equations for the fixed point. To understand this framework heuristically, this paper gives a detailed analysis for three important supermarket examples: M/G/1 type, GI/M/1 type and multiple choices, explains how to derive the system of differential equations by means of density-dependent jump Markov processes, and shows that the fixed point may be simply super-exponential through solving the system of nonlinear equations. Note that supermarket models are a class of complicated queueing systems and their analysis can not apply popular queueing theory, it is necessary in the study of supermarket models to summarize such a more general framework which enables us to focus on important research issues. On this line, this paper develops matrix-analytical methods of Markovian supermarket models. We hope this will be able to open a new avenue in performance evaluation of supermarket models by means of matrix-analytical methods.
Random Deployment of Data Collectors for Serving Randomly-Located Sensors
Venue: arXiv cs.NI 2011
Year: 2011

Recently, wireless communication industries have begun to extend their services to machine-type communication devices as well as to user equipments. Such machine-type communication devices as meters and sensors need intermittent uplink resources to report measured or sensed data to their serving data collector. It is however hard to dedicate limited uplink resources to each of them. Thus, efficient service of a tremendous number of devices with low activities may consider simple random access as a solution. The data collectors receiving the measured data from many sensors simultaneously can successfully decode only signals with signal-to-interference-plus-noise-ratio (SINR) above a certain value. The main design issues for this environment become how many data collectors are needed, how much power sensor nodes transmit with, and how wireless channels affect the performance. This paper provides answers to those questions through a stochastic analysis based on a spatial point process and on simulations.
Python GUI Scripting Interface for Running Atomic Physics Applications
Venue: arXiv cs.HC 2011
Year: 2011

We create a Python GUI scripting interface working under Windows in addition to (UNIX/Linux). The GUI has been built around the Python open-source programming language. We use the Python's GUI library that so called Python Mega Widgets (PMW) and based on Tkinter Python module (http://www.freenetpages.co.uk/hp/alan.gauld/tutgui.htm). The new GUI was motivated primarily by the desire of more updated operations, more flexibility incorporating future and current improvements in producing atomic data. Furthermore it will be useful for a variety of applications of atomic physics, plasma physics and astrophysics and will help in calculating various atomic properties.
Bits from Photons: Oversampled Image Acquisition Using Binary Poisson Statistics
Venue: arXiv cs.IT 2011
Year: 2011

We study a new image sensor that is reminiscent of traditional photographic film. Each pixel in the sensor has a binary response, giving only a one-bit quantized measurement of the local light intensity. To analyze its performance, we formulate the oversampled binary sensing scheme as a parameter estimation problem based on quantized Poisson statistics. We show that, with a single-photon quantization threshold and large oversampling factors, the Cramér-Rao lower bound (CRLB) of the estimation variance approaches that of an ideal unquantized sensor, that is, as if there were no quantization in the sensor measurements. Furthermore, the CRLB is shown to be asymptotically achievable by the maximum likelihood estimator (MLE). By showing that the log-likelihood function of our problem is concave, we guarantee the global optimality of iterative algorithms in finding the MLE. Numerical results on both synthetic data and images taken by a prototype sensor verify our theoretical analysis and demonstrate the effectiveness of our image reconstruction algorithm. They also suggest the potential application of the oversampled binary sensing scheme in high dynamic range photography.
Long-Term Proportional Fair QoS Profile Follower Sub-carrier Allocation Algorithm in Dynamic OFDMA Systems
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, Long-Term Proportional Fair (LTPF) resource allocation algorithm in dynamic OFDMA system is presented, which provides long-term QoS guarantee (mainly throughput requirement satisfaction) to individual user and follows every user's QoS profile at long-term by incremental optimization of proportional fairness and overall system rate maximization. The LTPF algorithm dynamically allocates the OFDMA sub-carriers to the users in such a way that in long-term the individual QoS requirement is achieved as well as fairness among the users is maintained even in a heterogeneous traffic condition. Here more than maintaining individual user's instantaneous QoS; emphasis is given to follow mean QoS profile of all the users in long-term to retain the objectives of both proportional fairness and multi-user raw rate maximization. Compared to the algorithms, which provide proportional fair optimization and raw-rate maximization independently, this algorithm attempts to provide both kinds of optimizations simultaneously and reach an optimum point when computed in long-term by exploiting the time diversity gain of mobile wireless environment.
A study of the singularity locus in the joint space of planar parallel manipulators: special focus on cusps and nodes
Venue: arXiv cs.RO 2011
Year: 2011

Cusps and nodes on plane sections of the singularity locus in the joint space of parallel manipulators play an important role in nonsingular assembly-mode changing motions. This paper analyses in detail such points, both in the joint space and in the workspace. It is shown that a cusp (resp. a node) defines a point of tangency (resp. a crossing point) in the workspace between the singular curves and the curves associated with the so-called characteristics surfaces. The study is conducted on a planar 3-RPR manipulator for illustrative purposes.
Computing the Reveals Relation in Occurrence Nets
Venue: arXiv cs.LO 2011
Year: 2011

Petri net unfoldings are a useful tool to tackle state-space explosion in verification and related tasks. Moreover, their structure allows to access directly the relations of causal precedence, concurrency, and conflict between events. Here, we explore the data structure further, to determine the following relation: event a is said to reveal event b iff the occurrence of a implies that b inevitably occurs, too, be it before, after, or concurrently with a. Knowledge of reveals facilitates in particular the analysis of partially observable systems, in the context of diagnosis, testing or verification; it can also be used to generate more concise representations of behaviours via abstractions. The reveals relation was previously introduced in the context of fault diagnosis, where it was shown that the reveals relation was decidable: for a given pair a,b in the unfolding U of a safe Petri net N, a finite prefix P of U is sufficient to decide whether or not a reveals b. In this paper, we first considerably improve the bound on |P|. We then show that there exists an efficient algorithm for computing the relation on a given prefix. We have implemented the algorithm and report on experiments.
A Decidable Extension of Data Automata
Venue: arXiv cs.FL 2011
Year: 2011

Data automata on data words is a decidable model proposed by Bojańczyk et al. in 2006. Class automata, introduced recently by Bojańczyk and Lasota, is an extension of data automata which unifies different automata models on data words. The nonemptiness of class automata is undecidable, since class automata can simulate two-counter machines. In this paper, a decidable model called class automata with priority class condition, which restricts class automata but strictly extends data automata, is proposed. The decidability of this model is obtained by establishing a correspondence with priority multicounter automata. This correspondence also completes the picture of the links between various class conditions of class automata and various models of counter machines. Moreover, this model is applied to extend a decidability result of Alur, Cerný and Weinstein on the algorithmic analysis of array-accessing programs.
New results on pushdown module checking with imperfect information
Venue: arXiv cs.LO 2011
Year: 2011

Model checking of open pushdown systems (OPD) w.r.t. standard branching temporal logics (pushdown module checking or PMC) has been recently investigated in the literature, both in the context of environments with perfect and imperfect information about the system (in the last case, the environment has only a partial view of the system's control states and stack content). For standard CTL, PMC with imperfect information is known to be undecidable. If the stack content is assumed to be visible, then the problem is decidable and 2EXPTIME-complete (matching the complexity of PMC with perfect information against CTL). The decidability status of PMC with imperfect information against CTL restricted to the case where the depth of the stack content is visible is open. In this paper, we show that with this restriction, PMC with imperfect information against CTL remains undecidable. On the other hand, we individuate an interesting subclass of OPDS with visible stack content depth such that PMC with imperfect information against the existential fragment of CTL is decidable and in 2EXPTIME. Moreover, we show that the program complexity of PMC with imperfect information and visible stack content against CTL is 2EXPTIME-complete (hence, exponentially harder than the program complexity of PMC with perfect information, which is known to be EXPTIME-complete).
Representation Sharing for Prolog
Venue: arXiv cs.PL 2011
Year: 2011

Representation sharing can reduce the memory footprint of a program by sharing one representation between duplicate terms. The most common implementation of representation sharing in functional programming systems is known as hash-consing. In the context of Prolog, representation sharing has been given little attention. Some current techniques that deal with representation sharing are reviewed. The new contributions are: (1) an easy implementation of {\em input sharing} for {\em findall/3}; (2) a description of a {\em sharer} module that introduces representation sharing at runtime. Their realization is shown in the context of the WAM as implemented by hProlog. Both can be adapted to any WAM-like Prolog implementation. The sharer works independently of the garbage collector, but it can be made to cooperate with the garbage collector. Benchmark results show that the sharer has a cost comparable to the heap garbage collector, that its effectiveness is highly application dependent, and that its policy must be tuned to the collector. To appear in Theory and Practice of Logic Programming (TPLP)
Worst-Case SINR Constrained Robust Coordinated Beamforming for Multicell Wireless Systems
Venue: arXiv cs.IT 2011
Year: 2011

Multicell coordinated beamforming (MCBF) has been recognized as a promising approach to enhancing the system throughput and spectrum efficiency of wireless cellular systems. In contrast to the conventional single-cell beamforming (SBF) design, MCBF jointly optimizes the beamforming vectors of cooperative base stations (BSs) (via a central processing unit(CPU)) in order to mitigate the intercell interference. While most of the existing designs assume that the CPU has the perfect knowledge of the channel state information (CSI) of mobile stations (MSs), this paper takes into account the inevitable CSI errors at the CPU, and study the robust MCBF design problem. Specifically, we consider the worst-case robust design formulation that minimizes the weighted sum transmission power of BSs subject to worst-case signal-to-interference-plus-noise ratio (SINR) constraints on MSs. The associated optimization problem is challenging because it involves infinitely many nonconvex SINR constraints. In this paper, we show that the worst-case SINR constraints can be reformulated as linear matrix inequalities, and the approximation method known as semidefinite relation can be used to efficiently handle the worst-case robust MCBF problem. Simulation results show that the proposed robustMCBF design can provide guaranteed SINR performance for the MSs and outperforms the robust SBF design.
Exploiting Dynamically Propositional Logic Structures in SAT
Venue: arXiv cs.LO 2011
Year: 2011

The 32-bit hwb (hwb-n32 for short) problem is from equivalence checking that arises in combining two circuits computing the hidden weighted bit function. Since 2002, it remains still unsolvable in every SAT competition. This paper focuses on solving problems such as hwb-n32. Generally speaking, modern solvers can detect only XOR, AND, OR and ITE gates. Other non-clausal formulas (propositional logic structures) cannot be detected. To solve the hwb-n32 problem, we extract dynamically some special propositional logic structures, and then use a variant of DPLL-based solvers to solve the subproblem simplified by the extracted structure information. Using the dynamic extraction technique, we solved efficiently the hwb-n32 problem, even some of which were solved within 3000 seconds.
Communautés Web 2.0 d'apprenants de langue avec parcours d'apprentissage : rôles, pédagogie et rapports au contenu
Venue: arXiv cs.CY 2011
Year: 2011

Among the various types of online language learner collective types, we analyze in this contribution Web 2.0 communities featuring an explicit progression. We use three analysis angles (user roles, pedagogical progression and content) in order to provides leads towards expressing the interrelations between the implementation choices regarding the concepts linked to Web 2.0 and the learning experience of the users.
Distributed Wake-Up Scheduling for Energy Saving in Wireless Networks
Venue: arXiv cs.NI 2011
Year: 2011

A customary solution to reduce the energy consumption of wireless communication devices is to periodically put the radio into low-power sleep mode. A relevant problem is to schedule the wake-up of nodes in such a way as to ensure proper coordination among devices, respecting delay constraints while still saving energy. In this paper, we introduce a simple algebraic characterization of the problem of periodic wake-up scheduling under both energy consumption and delay constraints. We demonstrate that the general problem of wake-up times coordination is equivalent to integer factorization and discuss the implications on the design of efficient scheduling algorithms. We then propose simple polynomial time heuristic algorithms that can be implemented in a distributed fashion and present a message complexity of the order of the number of links in the network. Numerical results are provided in order to assess the performance of the proposed techniques when applied to wireless sensor networks.
Transmission with Energy Harvesting Nodes in Fading Wireless Channels: Optimal Policies
Venue: arXiv cs.IT 2011
Year: 2011

Wireless systems comprised of rechargeable nodes have a significantly prolonged lifetime and are sustainable. A distinct characteristic of these systems is the fact that the nodes can harvest energy throughout the duration in which communication takes place. As such, transmission policies of the nodes need to adapt to these harvested energy arrivals. In this paper, we consider optimization of point-to-point data transmission with an energy harvesting transmitter which has a limited battery capacity, communicating in a wireless fading channel. We consider two objectives: maximizing the throughput by a deadline, and minimizing the transmission completion time of the communication session. We optimize these objectives by controlling the time sequence of transmit powers subject to energy storage capacity and causality constraints. We, first, study optimal offline policies. We introduce a directional water-filling algorithm which provides a simple and concise interpretation of the necessary optimality conditions. We show the optimality of an adaptive directional water-filling algorithm for the throughput maximization problem. We solve the transmission completion time minimization problem by utilizing its equivalence to its throughput maximization counterpart. Next, we consider online policies. We use stochastic dynamic programming to solve for the optimal online policy that maximizes the average number of bits delivered by a deadline under stochastic fading and energy arrival processes with causal channel state feedback. We also propose near-optimal policies with reduced complexity, and numerically study their performances along with the performances of the offline and online optimal policies under various different configurations.
A Sequence of Relaxations Constraining Hidden Variable Models
Venue: arXiv cs.AI 2011
Year: 2011

Many widely studied graphical models with latent variables lead to nontrivial constraints on the distribution of the observed variables. Inspired by the Bell inequalities in quantum mechanics, we refer to any linear inequality whose violation rules out some latent variable model as a "hidden variable test" for that model. Our main contribution is to introduce a sequence of relaxations which provides progressively tighter hidden variable tests. We demonstrate applicability to mixtures of sequences of i.i.d. variables, Bell inequalities, and homophily models in social networks. For the last, we demonstrate that our method provides a test that is able to rule out latent homophily as the sole explanation for correlations on a real social network that are known to be due to influence.
Parameter Learning of Logic Programs for Symbolic-Statistical Modeling
Venue: arXiv cs.AI 2011
Year: 2011

We propose a logical/mathematical framework for statistical parameter learning of parameterized logic programs, i.e. definite clause programs containing probabilistic facts with a parameterized distribution. It extends the traditional least Herbrand model semantics in logic programming to distribution semantics, possible world semantics with a probability distribution which is unconditionally applicable to arbitrary logic programs including ones for HMMs, PCFGs and Bayesian networks. We also propose a new EM algorithm, the graphical EM algorithm, that runs for a class of parameterized logic programs representing sequential decision processes where each decision is exclusive and independent. It runs on a new data structure called support graphs describing the logical relationship between observations and their explanations, and learns parameters by computing inside and outside probability generalized for logic programs. The complexity analysis shows that when combined with OLDT search for all explanations for observations, the graphical EM algorithm, despite its generality, has the same time complexity as existing EM algorithms, i.e. the Baum-Welch algorithm for HMMs, the Inside-Outside algorithm for PCFGs, and the one for singly connected Bayesian networks that have been developed independently in each research field. Learning experiments with PCFGs using two corpora of moderate size indicate that the graphical EM algorithm can significantly outperform the Inside-Outside algorithm.
Efficient Solution Algorithms for Factored MDPs
Venue: arXiv cs.AI 2011
Year: 2011

This paper addresses the problem of planning under uncertainty in large Markov Decision Processes (MDPs). Factored MDPs represent a complex state space using state variables and the transition model using a dynamic Bayesian network. This representation often allows an exponential reduction in the representation size of structured MDPs, but the complexity of exact solution algorithms for such MDPs can grow exponentially in the representation size. In this paper, we present two approximate solution algorithms that exploit structure in factored MDPs. Both use an approximate value function represented as a linear combination of basis functions, where each basis function involves only a small subset of the domain variables. A key contribution of this paper is that it shows how the basic operations of both algorithms can be performed efficiently in closed form, by exploiting both additive and context-specific structure in a factored MDP. A central element of our algorithms is a novel linear program decomposition technique, analogous to variable elimination in Bayesian networks, which reduces an exponentially large LP to a provably equivalent, polynomial-sized one. One algorithm uses approximate linear programming, and the second approximate dynamic programming. Our dynamic programming algorithm is novel in that it uses an approximation based on max-norm, a technique that more directly minimizes the terms that appear in error bounds for approximate MDP algorithms. We provide experimental results on problems with over 10^40 states, demonstrating a promising indication of the scalability of our approach, and compare our algorithm to an existing state-of-the-art approach, showing, in some problems, exponential gains in computation time.
Fixed points avoiding Abelian $k$-powers
Venue: arXiv cs.FL 2011
Year: 2011

We show that the problem of whether the fixed point of a morphism avoids Abelian $k$-powers is decidable under rather general conditions
Interdefinability of defeasible logic and logic programming under the well-founded semantics
Venue: arXiv cs.AI 2011
Year: 2011

We provide a method of translating theories of Nute's defeasible logic into logic programs, and a corresponding translation in the opposite direction. Under certain natural restrictions, the conclusions of defeasible theories under the ambiguity propagating defeasible logic ADL correspond to those of the well-founded semantics for normal logic programs, and so it turns out that the two formalisms are closely related. Using the same translation of logic programs into defeasible theories, the semantics for the ambiguity blocking defeasible logic NDL can be seen as indirectly providing an ambiguity blocking semantics for logic programs. We also provide antimonotone operators for both ADL and NDL, each based on the Gelfond-Lifschitz (GL) operator for logic programs. For defeasible theories without defeaters or priorities on rules, the operator for ADL corresponds to the GL operator and so can be seen as partially capturing the consequences according to ADL. Similarly, the operator for NDL captures the consequences according to NDL, though in this case no restrictions on theories apply. Both operators can be used to define stable model semantics for defeasible theories.
Zen Puzzle Garden is NP-complete
Venue: arXiv cs.CC 2011
Year: 2011

Zen Puzzle Garden (ZPG) is a one-player puzzle game. In this paper, we prove that deciding the solvability of ZPG is NP-complete.