OpenRaiser/Intern-Atlas huggingface dataset:
Asynchronous Transmission of Wireless Multicast System with Genetic Joint Antennas Selection
Venue: arXiv cs.NI 2014
Year: 2014

Optimal antenna selection algorithm of multicast transmission can significantly reduce the number of antennas and can acquire lower complexity and high performance which is close to that of exhaustive search. An asynchronous multicast transmission mechanism based on genetic antenna selection is proposed. The computational complexity of genetic antenna selection algorithm remains moderate while the total number of antennas increases comparing with optimum searching algorithm. Symbol error rate (SER) and capacity of our mechanism are analyzed and simulated, and the simulation results demonstrate that our proposed mechanism can achieve better SER and sub-maximum channel capacity in wireless multicast systems.
Towards a GPU-based implementation of interaction nets
Venue: arXiv cs.PL 2014
Year: 2014

We present ingpu, a GPU-based evaluator for interaction nets that heavily utilizes their potential for parallel evaluation. We discuss advantages and challenges of the ongoing implementation of ingpu and compare its performance to existing interaction nets evaluators.
Non-deterministic computation and the Jayne-Rogers Theorem
Venue: arXiv cs.LO 2014
Year: 2014

We provide a simple proof of a computable analogue to the Jayne Rogers Theorem from descriptive set theory. The difficulty of the proof is delegated to a simulation result pertaining to non-deterministic type-2 machines. Thus, we demonstrate that developments in computational models can have applications in fields thought to be far removed from it.
Toward Parametric Timed Interfaces for Real-Time Components
Venue: arXiv cs.OS 2014
Year: 2014

We propose here a framework to model real-time components consisting of concurrent real-time tasks running on a single processor, using parametric timed automata. Our framework is generic and modular, so as to be easily adapted to different schedulers and more complex task models. We first perform a parametric schedulability analysis of the components using the inverse method. We show that the method unfortunately does not provide satisfactory results when the task periods are consid- ered as parameters. After identifying and explaining the problem, we present a solution adapting the model by making use of the worst-case scenario in schedulability analysis. We show that the analysis with the inverse method always converges on the modified model when the system load is strictly less than 100%. Finally, we show how to use our parametric analysis for the generation of timed interfaces in compositional system design.
Haplotype Assembly: An Information Theoretic View
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the haplotype assembly problem from an information theoretic perspective. A haplotype is a sequence of nucleotide bases on a chromosome, often conveniently represented by a binary string, that differ from the bases in the corresponding positions on the other chromosome in a homologous pair. Information about the order of bases in a genome is readily inferred using short reads provided by high-throughput DNA sequencing technologies. In this paper, the recovery of the target pair of haplotype sequences using short reads is rephrased as a joint source-channel coding problem. Two messages, representing haplotypes and chromosome memberships of reads, are encoded and transmitted over a channel with erasures and errors, where the channel model reflects salient features of high-throughput sequencing. The focus of this paper is on the required number of reads for reliable haplotype reconstruction, and both the necessary and sufficient conditions are presented with order-wise optimal bounds.
Comparative Resilience Notions and Vertex Attack Tolerance of Scale-Free Networks
Venue: arXiv cs.SI 2014
Year: 2014

We are concerned with an appropriate mathematical measure of resilience in the face of targeted node attacks for arbitrary degree networks, and subsequently comparing the resilience of different scale-free network models with the proposed measure. We strongly motivate our resilience measure termed \emph{vertex attack tolerance} (VAT), which is denoted mathematically as $τ(G) = \min_{S \subset V} \frac{|S|}{|V-S-C_{max}(V-S)|+1}$, where $C_{max}(V-S)$ is the largest connected component in $V-S$. We attempt a thorough comparison of VAT with several existing resilience notions: conductance, vertex expansion, integrity, toughness, tenacity and scattering number. Our comparisons indicate that for artbitrary degree distributions VAT is the only measure that fully captures both the major \emph{bottlenecks} of a network and the resulting \emph{component size distribution} upon targeted node attacks (both captured in a manner proportional to the size of the attack set). For the case of $d$-regular graphs, we prove that $τ(G) \le dΦ(G)$, where $Φ(G)$ is the conductance of the graph $G$. Conductance and expansion are well-studied measures of robustness and bottlenecks in the case of regular graphs but fail to capture resilience in the case of highly heterogeneous degree graphs. Regarding comparison of different scale-free graph models, our experimental results indicate that PLOD graphs with degree distributions identical to BA graphs of the same size exhibit consistently better vertex attack tolerance than the BA type graphs, although both graph types appear asymptotically resilient for BA generative parameter $m = 2$. BA graphs with $m = 1$ also appear to lack resilience, not only exhibiting very low VAT values, but also great transparency in the identification of the vulnerable node sets, namely the hubs, consistent with well known previous work.
Gender Asymmetries in Reality and Fiction: The Bechdel Test of Social Media
Venue: arXiv cs.SI 2014
Year: 2014

The subjective nature of gender inequality motivates the analysis and comparison of data from real and fictional human interaction. We present a computational extension of the Bechdel test: A popular tool to assess if a movie contains a male gender bias, by looking for two female characters who discuss about something besides a man. We provide the tools to quantify Bechdel scores for both genders, and we measure them in movie scripts and large datasets of dialogues between users of MySpace and Twitter. Comparing movies and users of social media, we find that movies and Twitter conversations have a consistent male bias, which does not appear when analyzing MySpace. Furthermore, the narrative of Twitter is closer to the movies that do not pass the Bechdel test than to those that pass it. We link the properties of movies and the users that share trailers of those movies. Our analysis reveals some particularities of movies that pass the Bechdel test: Their trailers are less popular, female users are more likely to share them than male users, and users that share them tend to interact less with male users. Based on our datasets, we define gender independence measurements to analyze the gender biases of a society, as manifested through digital traces of online behavior. Using the profile information of Twitter users, we find larger gender independence for urban users in comparison to rural ones. Additionally, the asymmetry between genders is larger for parents and lower for students. Gender asymmetry varies across US states, increasing with higher average income and latitude. This points to the relation between gender inequality and social, economical, and cultural factors of a society, and how gender roles exist in both fictional narratives and public online dialogues.
Mobile Elements Scheduling for Periodic Sensor Applications
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we investigate the problem of designing the mobile elements tours such that the length of each tour is below a per-determined length and the depth of the multi-hop routing trees bounded by k. The path of the mobile element is designed to visit subset of the nodes (cache points). These cache points store other nodes data. To address this problem, we propose two heuristic-based solutions. Our solutions take into consideration the distribution of the nodes during the establishment of the tour. The results of our experiments indicate that our schemes significantly outperforms the best comparable scheme in the literature.
On Minimizing the Maximum Broadcast Decoding Delay for Instantly Decodable Network Coding
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider the problem of minimizing the maximum broadcast decoding delay experienced by all the receivers of generalized instantly decodable network coding (IDNC). Unlike the sum decoding delay, the maximum decoding delay as a definition of delay for IDNC allows a more equitable distribution of the delays between the different receivers and thus a better Quality of Service (QoS). In order to solve this problem, we first derive the expressions for the probability distributions of maximum decoding delay increments. Given these expressions, we formulate the problem as a maximum weight clique problem in the IDNC graph. Although this problem is known to be NP-hard, we design a greedy algorithm to perform effective packet selection. Through extensive simulations, we compare the sum decoding delay and the max decoding delay experienced when applying the policies to minimize the sum decoding delay [1] and our policy to reduce the max decoding delay. Simulations results show that our policy gives a good agreement among all the delay aspects in all situations and outperforms the sum decoding delay policy to effectively minimize the sum decoding delay when the channel conditions become harsher. They also show that our definition of delay significantly improve the number of served receivers when they are subject to strict delay constraints.
A Continuous Max-Flow Approach to General Hierarchical Multi-Labeling Problems
Venue: arXiv cs.CV 2014
Year: 2014

Multi-region segmentation algorithms often have the onus of incorporating complex anatomical knowledge representing spatial or geometric relationships between objects, and general-purpose methods of addressing this knowledge in an optimization-based manner have thus been lacking. This paper presents Generalized Hierarchical Max-Flow (GHMF) segmentation, which captures simple anatomical part-whole relationships in the form of an unconstrained hierarchy. Regularization can then be applied to both parts and wholes independently, allowing for spatial grouping and clustering of labels in a globally optimal convex optimization framework. For the purposes of ready integration into a variety of segmentation tasks, the hierarchies can be presented in run-time, allowing for the segmentation problem to be readily specified and alternatives explored without undue programming effort or recompilation.
New Shortest Lattice Vector Problems of Polynomial Complexity
Venue: arXiv cs.DS 2014
Year: 2014

The Shortest Lattice Vector (SLV) problem is in general hard to solve, except for special cases (such as root lattices and lattices for which an obtuse superbase is known). In this paper, we present a new class of SLV problems that can be solved efficiently. Specifically, if for an $n$-dimensional lattice, a Gram matrix is known that can be written as the difference of a diagonal matrix and a positive semidefinite matrix of rank $k$ (for some constant $k$), we show that the SLV problem can be reduced to a $k$-dimensional optimization problem with countably many candidate points. Moreover, we show that the number of candidate points is bounded by a polynomial function of the ratio of the smallest diagonal element and the smallest eigenvalue of the Gram matrix. Hence, as long as this ratio is upper bounded by a polynomial function of $n$, the corresponding SLV problem can be solved in polynomial complexity. Our investigations are motivated by the emergence of such lattices in the field of Network Information Theory. Further applications may exist in other areas.
The Complexity of the Simplex Method
Venue: arXiv cs.DS 2014
Year: 2014

The simplex method is a well-studied and widely-used pivoting method for solving linear programs. When Dantzig originally formulated the simplex method, he gave a natural pivot rule that pivots into the basis a variable with the most violated reduced cost. In their seminal work, Klee and Minty showed that this pivot rule takes exponential time in the worst case. We prove two main results on the simplex method. Firstly, we show that it is PSPACE-complete to find the solution that is computed by the simplex method using Dantzig's pivot rule. Secondly, we prove that deciding whether Dantzig's rule ever chooses a specific variable to enter the basis is PSPACE-complete. We use the known connection between Markov decision processes (MDPs) and linear programming, and an equivalence between Dantzig's pivot rule and a natural variant of policy iteration for average-reward MDPs. We construct MDPs and show PSPACE-completeness results for single-switch policy iteration, which in turn imply our main results for the simplex method.
Conceptive Artificial Intelligence: Insights from design theory
Venue: arXiv cs.AI 2014
Year: 2014

The current paper offers a perspective on what we term conceptive intelligence - the capacity of an agent to continuously think of new object definitions (tasks, problems, physical systems, etc.) and to look for methods to realize them. The framework, called a Brouwer machine, is inspired by previous research in design theory and modeling, with its roots in the constructivist mathematics of intuitionism. The dual constructivist perspective we describe offers the possibility to create novelty both in terms of the types of objects and the methods for constructing objects. More generally, the theoretical work on which Brouwer machines are based is called imaginative constructivism. Based on the framework and the theory, we discuss many paradigms and techniques omnipresent in AI research and their merits and shortcomings for modeling aspects of design, as described by imaginative constructivism. To demonstrate and explain the type of creative process expressed by the notion of a Brouwer machine, we compare this concept with a system using genetic algorithms for scientific law discovery.
Tighter Undecidability Bounds for Matrix Mortality, Zero-in-the-Corner Problems, and More
Venue: arXiv cs.DM 2014
Year: 2014

We study the decidability of three well-known problems related to integer matrix multiplication: Mortality (M), Zero in the Left-Upper Corner (Z), and Zero in the Right-Upper Corner (R). Let d and k be positive integers. Define M(k, d x d) as the following special case of the Mortality problem: given a set X of d -by-d integer matrices such that the cardinality of X is not greater than k, decide whether the d-by-d zero matrix belongs to X^+, where X^+ denotes the closure of X under the usual matrix multiplication. In the same way, define the Z(k, d x d) problem as: given an instance X of M(k, d x d) (the instances of Z(k, d x d) are the same as those of M(k, d x d)), decide whether at least one matrix in X^+ has a zero in the left-upper corner. Define R(k, d x d) as the variant of Z(k, d x d) where "left-upper corner" is replaced with "right-upper corner". In the paper, we prove that M(6, 3 x 3), M(4, 5 x 5), M(3, 9 x 9), M(2, 15 x 15), Z(5, 3 x 3), Z(3, 5 x 5), Z(2, 9 x 9), R(6, 3 x 3), R(5, 4 x 4), and R(3, 6 x 6) are undecidable. The previous best comparable results were the undecidabilities of M(7, 3 x 3), M(3, 13 x 13), M(2, 21 x 21), Z(7, 3 x 3), Z(2, 13 x 13), R(7, 3 x 3), and R(2, 10 x 10).
GPU Accelerated Fractal Image Compression for Medical Imaging in Parallel Computing Platform
Venue: arXiv cs.DC 2014
Year: 2014

In this paper, we implemented both sequential and parallel version of fractal image compression algorithms using CUDA (Compute Unified Device Architecture) programming model for parallelizing the program in Graphics Processing Unit for medical images, as they are highly similar within the image itself. There are several improvement in the implementation of the algorithm as well. Fractal image compression is based on the self similarity of an image, meaning an image having similarity in majority of the regions. We take this opportunity to implement the compression algorithm and monitor the effect of it using both parallel and sequential implementation. Fractal compression has the property of high compression rate and the dimensionless scheme. Compression scheme for fractal image is of two kind, one is encoding and another is decoding. Encoding is very much computational expensive. On the other hand decoding is less computational. The application of fractal compression to medical images would allow obtaining much higher compression ratios. While the fractal magnification an inseparable feature of the fractal compression would be very useful in presenting the reconstructed image in a highly readable form. However, like all irreversible methods, the fractal compression is connected with the problem of information loss, which is especially troublesome in the medical imaging. A very time consuming encoding pro- cess, which can last even several hours, is another bothersome drawback of the fractal compression.
Breadth-first serialisation of trees and rational languages
Venue: arXiv cs.FL 2014
Year: 2014

We present here the notion of breadth-first signature and its relationship with numeration system theory. It is the serialisation into an infinite word of an ordered infinite tree of finite degree. We study which class of languages corresponds to which class of words and,more specifically, using a known construction from numeration system theory, we prove that the signature of rational languages are substitutive sequences.
Multiple Access Channels with Combined Cooperation and Partial Cribbing
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we study the multiple access channel (MAC) with combined cooperation and partial cribbing and characterize its capacity region. Cooperation means that the two encoders send a message to one another via a rate-limited link prior to transmission, while partial cribbing means that each of the two encoders obtains a deterministic function of the other encoder's output with or without delay. Prior work in this field dealt separately with cooperation and partial cribbing. However, by combining these two methods we can achieve significantly higher rates. Remarkably, the capacity region does not require an additional auxiliary random variable (RV) since the purpose of both cooperation and partial cribbing is to generate a common message between the encoders. In the proof we combine methods of block Markov coding, backward decoding, double rate-splitting, and joint typicality decoding. Furthermore, we present the Gaussian MAC with combined one-sided cooperation and quantized cribbing. For this model, we give an achievability scheme that shows how many cooperation or quantization bits are required in order to achieve a Gaussian MAC with full cooperation/cribbing capacity region. After establishing our main results, we consider two cases where only one auxiliary RV is needed. The first is a rate distortion dual setting for the MAC with a common message, a private message and combined cooperation and cribbing. The second is a state-dependent MAC with cooperation, where the state is known at a partially cribbing encoder and at the decoder. However, there are cases where more than one auxiliary RV is needed, e.g., when the cooperation and cribbing are not used for the same purposes. We present a MAC with an action-dependent state, where the action is based on the cooperation but not on the cribbing. Therefore, in this case more than one auxiliary RV is needed.
Refining and Delegating Strategic Ability in ATL
Venue: arXiv cs.LO 2014
Year: 2014

We propose extending Alternating-time Temporal Logic (ATL) by an operator <i refines-to G> F to express that agent i can distribute its powers to a set of sub-agents G in a way which satisfies ATL condition f on the strategic ability of the coalitions they may form, possibly together with others agents. We prove the decidability of model-checking of formulas whose subformulas with this operator as the main connective have the form <i_1 refines-to G_1>...<i_m refines-to G_m> f, with no further occurrences of this operator in f.
First Cycle Games
Venue: arXiv cs.LO 2014
Year: 2014

First cycle games (FCG) are played on a finite graph by two players who push a token along the edges until a vertex is repeated, and a simple cycle is formed. The winner is determined by some fixed property Y of the sequence of labels of the edges (or nodes) forming this cycle. These games are traditionally of interest because of their connection with infinite-duration games such as parity and mean-payoff games. We study the memory requirements for winning strategies of FCGs and certain associated infinite duration games. We exhibit a simple FCG that is not memoryless determined (this corrects a mistake in \it Memoryless determinacy of parity and mean payoff games: a simple proof by Björklund, Sandberg, Vorobyov (2004) that claims that FCGs for which Y is closed under cyclic permutations are memoryless determined). We show that /Theta(n)! memory (where n is the number of nodes in the graph), which is always sufficient, may be necessary to win some FCGs. On the other hand, we identify easy to check conditions on Y (i.e., Y is closed under cyclic permutations, and both Y and its complement are closed under concatenation) that are sufficient to ensure that the corresponding FCGs and their associated infinite duration games are memoryless determined. We demonstrate that many games considered in the literature, such as mean-payoff, parity, energy, etc., satisfy these conditions. On the complexity side, we show (for efficiently computable Y) that while solving FCGs is in PSPACE, solving some families of FCGs is PSPACE-hard.
Partial Preferences for Mediated Bargaining
Venue: arXiv cs.GT 2014
Year: 2014

In this work we generalize standard Decision Theory by assuming that two outcomes can also be incomparable. Two motivating scenarios show how incomparability may be helpful to represent those situations where, due to lack of information, the decision maker would like to maintain different options alive and defer the final decision. In particular, a new axiomatization is given which turns out to be a weakening of the classical set of axioms used in Decision Theory. Preliminary results show how preferences involving complex distributions are related to judgments on single alternatives.
Towards Verifying Safety Properties of Real-Time Probabilistic Systems
Venue: arXiv cs.SE 2014
Year: 2014

Using probabilities in the formal-methods-based development of safety-critical software has quickened interests in academia and industry. We address this area by our model-driven engineering method for reactive systems SPACE and its tool-set Reactive Blocks that provide an extension to support the modeling and verification of real-time behaviors. The approach facilitates the composition of system models from reusable building blocks as well as the verification of functional and real-time properties and the automatic generation of Java code. In this paper, we describe the extension of the tool-set to enable the modeling and verification of probabilistic real-time system behavior with the focus on spatial properties that ensure system safety. In particular, we incorporate descriptions of probabilistic behavior into our Reactive Blocks models and integrate the model checker PRISM which allows to verify that a real-time system satisfies certain safety properties with a given probability. Moreover, we consider the spatial implication of probabilistic system specifications by integrating the spatial verification tool BeSpaceD and give an automatic approach to translate system specifications to the input languages of PRISM and BeSpaceD. The approach is highlighted by an example.