OpenRaiser/Intern-Atlas huggingface dataset:
Continuation calculus
Venue: arXiv cs.LO 2013
Year: 2013

Programs with control are usually modeled using lambda calculus extended with control operators. Instead of modifying lambda calculus, we consider a different model of computation. We introduce continuation calculus, or CC, a deterministic model of computation that is evaluated using only head reduction, and argue that it is suitable for modeling programs with control. It is demonstrated how to define programs, specify them, and prove them correct. This is shown in detail by presenting in CC a list multiplication program that prematurely returns when it encounters a zero. The correctness proof includes termination of the program. In continuation calculus we can model both call-by-name and call-by-value. In addition, call-by-name functions can be applied to call-by-value results, and conversely.
Combining and Relating Control Effects and their Semantics
Venue: arXiv cs.LO 2013
Year: 2013

Combining local exceptions and first class continuations leads to programs with complex control flow, as well as the possibility of expressing powerful constructs such as resumable exceptions. We describe and compare games models for a programming language which includes these features, as well as higher-order references. They are obtained by contrasting methodologies: by annotating sequences of moves with "control pointers" indicating where exceptions are thrown and caught, and by composing the exceptions and continuations monads. The former approach allows an explicit representation of control flow in games for exceptions, and hence a straightforward proof of definability (full abstraction) by factorization, as well as offering the possibility of a semantic approach to control flow analysis of exception-handling. However, establishing soundness of such a concrete and complex model is a non-trivial problem. It may be resolved by establishing a correspondence with the monad semantics, based on erasing explicit exception moves and replacing them with control pointers.
Intrinsic universality and the computational power of self-assembly
Venue: arXiv cs.CG 2013
Year: 2013

This short survey of recent work in tile self-assembly discusses the use of simulation to classify and separate the computational and expressive power of self-assembly models. The journey begins with the result that there is a single universal tile set that, with proper initialization and scaling, simulates any tile assembly system. This universal tile set exhibits something stronger than Turing universality: it captures the geometry and dynamics of any simulated system. From there we find that there is no such tile set in the noncooperative, or temperature 1, model, proving it weaker than the full tile assembly model. In the two-handed or hierarchal model, where large assemblies can bind together on one step, we encounter an infinite set, of infinite hierarchies, each with strictly increasing simulation power. Towards the end of our trip, we find one tile to rule them all: a single rotatable flipable polygonal tile that can simulate any tile assembly system. It seems this could be the beginning of a much longer journey, so directions for future work are suggested.
Tiling Problems on Baumslag-Solitar groups
Venue: arXiv cs.DM 2013
Year: 2013

We exhibit a weakly aperiodic tile set for Baumslag-Solitar groups, and prove that the domino problem is undecidable on these groups. A consequence of our construction is the existence of an arecursive tile set on Baumslag-Solitar groups.
The $k$-in-a-tree problem for graphs of girth at least~$k$
Venue: arXiv cs.DM 2013
Year: 2013

For all integers $k\geq 3$, we give an $O(n^4)$ time algorithm for the problem whose instance is a graph $G$ of girth at least $k$ together with $k$ vertices and whose question is "Does $G$ contains an induced subgraph containing the $k$ vertices and isomorphic to a tree?". This directly follows for $k=3$ from the three-in-a-tree algorithm of Chudnovsky and Seymour and for $k=4$ from a result of Derhy, Picouleau and Trotignon. Here we solve the problem for $k\geq 5$. Our algorithm relies on a structural description of graphs of girth at least $k$ that do not contain an induced tree covering $k$ given vertices ($k\geq 5$).
Modeling, Analysis and Optimization of Multicast Device-to-Device Transmission
Venue: arXiv cs.IT 2013
Year: 2013

Multicast device-to-device (D2D) transmission is important for applications like local file transfer in commercial networks and is also a required feature in public safety networks. In this paper we propose a tractable baseline multicast D2D model, and use it to analyze important multicast metrics like the coverage probability, mean number of covered receivers and throughput. In addition, we examine how the multicast performance would be affected by certain factors like mobility and network assistance. Take the mean number of covered receivers as an example. We find that simple repetitive transmissions help but the gain quickly diminishes as the repetition time increases. Meanwhile, mobility and network assistance (i.e. allowing the network to relay the multicast signals) can help cover more receivers. We also explore how to optimize multicasting, e.g. by choosing the optimal multicast rate and the optimal number of retransmission times.
Finding an induced subdivision of a digraph
Venue: arXiv cs.DM 2013
Year: 2013

We consider the following problem for oriented graphs and digraphs: Given an oriented graph (digraph) $G$, does it contain an induced subdivision of a prescribed digraph $D$? The complexity of this problem depends on $D$ and on whether $G$ must be an oriented graph or is allowed to contain 2-cycles. We give a number of examples of polynomial instances as well as several NP-completeness proofs.
Hyper-Graph Based Database Partitioning for Transactional Workloads
Venue: arXiv cs.DB 2013
Year: 2013

A common approach to scaling transactional databases in practice is horizontal partitioning, which increases system scalability, high availability and self-manageability. Usu- ally it is very challenging to choose or design an optimal partitioning scheme for a given workload and database. In this technical report, we propose a fine-grained hyper-graph based database partitioning system for transactional work- loads. The partitioning system takes a database, a workload, a node cluster and partitioning constraints as input and out- puts a lookup-table encoding the final database partitioning decision. The database partitioning problem is modeled as a multi-constraints hyper-graph partitioning problem. By deriving a min-cut of the hyper-graph, our system can min- imize the total number of distributed transactions in the workload, balance the sizes and workload accesses of the partitions and satisfy all the partition constraints imposed. Our system is highly interactive as it allows users to im- pose partition constraints, watch visualized partitioning ef- fects, and provide feedback based on human expertise and indirect domain knowledge for generating better partition- ing schemes.
Identification of nonlinear controllers from data: theory and computation
Venue: arXiv cs.SY 2013
Year: 2013

This manuscript contains technical details and proofs of recent results developed by the authors, pertaining to the design of nonlinear controllers from the experimental data measured on an existing feedback control system.
Network-Level Cooperation in Energy Harvesting Wireless Networks
Venue: arXiv cs.IT 2013
Year: 2013

We consider a two-hop communication network consisted of a source node, a relay and a destination node in which the source and the relay node have external traffic arrivals. The relay forwards a fraction of the source node's traffic to the destination and the cooperation is performed at the network level. In addition, both source and relay nodes have energy harvesting capabilities and an unlimited battery to store the harvested energy. We study the impact of the energy constraints on the stability region. Specifically, we provide inner and outer bounds on the stability region of the two-hop network with energy harvesting source and relay.
Fast ranking algorithm for very large data
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we propose a new ranking method inspired from previous results on the diffusion approach to solve linear equation. We describe new mathematical equations corresponding to this method and show through experimental results the potential computational gain. This ranking method is also compared to the well known PageRank model.
Towards a Unified Belief Structure in Games with indeterminate probabilities
Venue: arXiv cs.GT 2013
Year: 2013

This paper provides an analysis of different formal representations of beliefs in epistemic game theory. The aim is to attempt a synthesis of different structures of beliefs in the presence of indeterminate probabilities. Special attention is also paid to the decision-theoretic principle known as the thesis of no subjective probability for self-action. Conditions in cope with this principle are given which underlie the interrelationships between different models of beliefs, and it is shown that under these conditions different doxastic structures can be coherently unified.
Stochastic Agent-Based Simulations of Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

The rapidly growing field of network analytics requires data sets for use in evaluation. Real world data often lack truth and simulated data lack narrative fidelity or statistical generality. This paper presents a novel, mixed-membership, agentbased simulation model to generate activity data with narrative power while providing statistical diversity through random draws. The model generalizes to a variety of network activity types such as Internet and cellular communications, human mobility, and social network interactions. The simulated actions over all agents can then drive an application specific observational model to render measurements as one would collect in real-world experiments. We apply this framework to human mobility and demonstrate its utility in generating high fidelity traffic data for network analytics.
Software Engineering as Instrumentation for the Long Tail of Scientific Software
Venue: arXiv cs.SE 2013
Year: 2013

The vast majority of the long tail of scientific software, the myriads of tools that implement the many analysis and visualization methods for different scientific fields, is highly specialized, purpose-built for a research project, and has to rely on community uptake and reuse for its continued development and maintenance. Although uptake cannot be controlled over even guaranteed, some of the key factors that influence whether new users or developers decide to adopt an existing tool or start a new one are about how easy or difficult it is to use or enhance a tool for a purpose for which it was not originally designed. The science of software engineering has produced techniques and practices that would reduce or remove a variety of barriers to community uptake of software, but for a variety of reasons employing trained software engineers as part of the development of long tail scientific software has proven to be challenging. As a consequence, community uptake of long tail tools is often far more difficult than it would need to be, even though opportunities for reuse abound. We discuss likely reasons why employing software engineering in the long tail is challenging, and propose that many of those obstacles could be addressed in the form of a cross-cutting non-profit center of excellence that makes software engineering broadly accessible as a shared service, conceptually and in its effect similar to shared instrumentation.
On Limits to the Scope of the Extended Formulations "Barriers"
Venue: arXiv cs.DM 2013
Year: 2013

In this paper, we introduce the notion of augmentation for polytopes and use it to show the error in two presumptions that have been key in arriving at over-reaching/over-scoped claims of "impossibility" in recent extended formulations (EF) developments. One of these presumptions is that: "If Polytopes P and Q are described in the spaces of variables x and y respectively, and there exists a linear map x=Ay between the feasible sets of P and Q, then Q is an EF of P". The other is: "(An augmentation of Polytope A projects to Polytope B) ==> (The external descriptions of A and B are related)". We provide counter-examples to these presumptions, and show that in general: (1) If polytopes can always be arbitrarily augmented for the purpose of establishing EF relations, then the notion of EF becomes degenerate/meaningless in some cases, and that: (2) The statement: "(Polytope B is the projection of an augmentation of Polytope A) ==> (Polytope B is the projection of Polytope A)" is not true in general (although, as we show, the converse statement, "(B is the projection of A) ==> (B is the projection of every augmentation of A)", is true in general). We illustrate some of the ideas using the minimum spanning tree problem, as well as the "lower bounds" developments in Fiorini et al. (2011; 2012), in particular.
Edge-colouring and total-colouring chordless graphs
Venue: arXiv cs.DM 2013
Year: 2013

A graph $G$ is \emph{chordless} if no cycle in $G$ has a chord. In the present work we investigate the chromatic index and total chromatic number of chordless graphs. We describe a known decomposition result for chordless graphs and use it to establish that every chordless graph of maximum degree $Δ\geq 3$ has chromatic index $Δ$ and total chromatic number $Δ+ 1$. The proofs are algorithmic in the sense that we actually output an optimal colouring of a graph instance in polynomial time.
Rollover Preventive Force Synthesis at Active Suspensions in a Vehicle Performing a Severe Maneuver with Wheels Lifted off
Venue: arXiv cs.SY 2013
Year: 2013

Among the intelligent safety technologies for road vehicles, active suspensions controlled by embedded computing elements for preventing rollover have received a lot of attention. The existing models for synthesizing and allocating forces in such suspensions are conservatively based on the constraint that no wheels lift off the ground. However, in practice, smart/active suspensions are more necessary in the situation where the wheels have just lifted off the ground. The difficulty in computing control in the last situation is that the problem requires satisfying disjunctive constraints on the dynamics. To the authors',knowledge, no efficient solution method is available for the simulation of dynamics with disjunctive constraints and thus hardware realizable and accurate force allocation in an active suspension tends to be a difficulty. In this work we give an algorithm for and simulate numerical solutions of the force allocation problem as an optimal control problem constrained by dynamics with disjunctive constraints. In particular we study the allocation and synthesis of time-dependent active suspension forces in terms of sensor output data in order to stabilize the roll motion of the road vehicle. An equivalent constraint in the form of a convex combination (hull) is proposed to satisfy the disjunctive constraints. The validated numerical simulations show that it is possible to allocate and synthesize control forces at the active suspensions from sensor output data such that the forces stabilize the roll moment of the vehicle with its wheels just lifted off the ground during arbitrary fish-hook maneuvers.
A Robust Continuous Time Fixed Lag Smoother for Nonlinear Uncertain Systems
Venue: arXiv cs.SY 2013
Year: 2013

This paper presents a robust fixed lag smoother for a class of nonlinear uncertain systems. A unified scheme, which combines a nonlinear robust estimator with a stable fixed lag smoother, is presented to improve the error covariance of the estimation. The robust fixed lag smoother is based on the use of Integral Quadratic Constraints and minimax LQG control. The state estimator uses a copy of the system nonlinearity in the estimator and combines an approximate model of the delayed states to produce a smoothed signal. In order to see the effectiveness of the method, it is applied to a quantum optical phase estimation problem. Results show significant improvement in the error covariance of the estimator using fixed lag smoother in the presence of nonlinear uncertainty.
Single image super resolution in spatial and wavelet domain
Venue: arXiv cs.CV 2013
Year: 2013

Recently single image super resolution is very important research area to generate high resolution image from given low resolution image. Algorithms of single image resolution are mainly based on wavelet domain and spatial domain. Filters support to model the regularity of natural images is exploited in wavelet domain while edges of images get sharp during up sampling in spatial domain. Here single image super resolution algorithm is presented which based on both spatial and wavelet domain and take the advantage of both. Algorithm is iterative and use back projection to minimize reconstruction error. Wavelet based denoising method is also introduced to remove noise.
Determinant versus Permanent: salvation via generalization? The algebraic complexity of the Fermionant and the Immanant
Venue: arXiv cs.CC 2013
Year: 2013

The fermionant can be seen as a generalization of both the permanent (for $k=-1$) and the determinant. We demonstrate that it is VNP-complete for most cases. Furthermore it is #P-complete for the cases. The immanant is also a generalization of the permanent (for a Young diagram with a single line) and of the determinant (when the Young diagram is a column). We demonstrate that the immanant of any family of Young diagrams with bounded width and at least n boxes at the right of the first column is VNP-complete.
A Finite-Blocklength Perspective on Gaussian Multi-Access Channels
Venue: arXiv cs.IT 2013
Year: 2013

Motivated by the growing application of wireless multi-access networks with stringent delay constraints, we investigate the Gaussian multiple access channel (MAC) in the finite blocklength regime. Building upon information spectrum concepts, we develop several non-asymptotic inner bounds on channel coding rates over the Gaussian MAC with a given finite blocklength, positive average error probability, and maximal power constraints. Employing Central Limit Theorem (CLT) approximations, we also obtain achievable second-order coding rates for the Gaussian MAC based on an explicit expression for its dispersion matrix. We observe that, unlike the pentagon shape of the asymptotic capacity region, the second-order region has a curved shape with no sharp corners. A main emphasis of the paper is to provide a new perspective on the procedure of handling input cost constraints for tight achievability proofs. Contrary to the complicated achievability techniques in the literature, we show that with a proper choice of input distribution, tight bounds can be achieved via the standard random coding argument and a modified typicality decoding. In particular, we prove that codebooks generated randomly according to independent uniform distributions on the respective "power shells" perform far better than both independent and identically distributed (i.i.d.) Gaussian inputs and TDMA with power control. Interestingly, analogous to an error exponent result of Gallager, the resulting achievable region lies roughly halfway between that of the i.i.d. Gaussian inputs and that of a hypothetical "sum-power shell" input. However, dealing with such a non-i.i.d. input requires additional analysis such as a new change of measure technique and application of a Berry-Esseen CLT for functions of random variables.
Elementos de ingeniería de explotación de la información aplicados a la investigación tributaria fiscal
Venue: arXiv cs.AI 2013
Year: 2013

By introducing elements of information mining to tax analysis, by means of data mining software and advanced computational concepts of artificial intelligence, the problem of tax evader's crime against public property has been addressed. Through an empirical approach from a hypothetical case of use, induction algorithms, neural networks and bayesian networks are applied to determine the feasibility of its heuristic application by the tax public administrator. Different strategies are explored to facilitate the work of local and regional federal tax inspectors, considering their limited computational capabilities, but equally effective for those social scientist committed to handcrafting tax research. ----- Apresentando a introdução de elementos de exploração de informações para análise fiscal, por meio de software de mineração de dados e conceitos avançados computacionais de inteligência artificial, foi abordado o problema do crime de sonegador fiscal contra o patrimônio público. Através de uma abordagem empírica a partir de um caso hipotético de uso, os algoritmos de indução, redes neurais e redes bayesianas são aplicados para determinar a viabilidade de sua aplicação heurística pelo administrador público tributário. Diferentes estratégias são exploradas para facilitar o trabalho dos inspectores tributários federais locais e regionais, tendo em conta as suas capacidades computacionais limitados, mas igualmente eficaz para aqueles cientista social comprometido com a investigação fiscal.
Implementation of Function Point Analysis in Measuring The Volume Estimation of Software System in Object Oriented and Structural Model of Academic System
Venue: arXiv cs.SE 2013
Year: 2013

In the software development required a fidelity and accuracy in determining the size or value of the software to fit the operation is executed. Various methods of calculation has been widely applied to estimate the size, and one of them is by using the method of Function Point Analysis (FPA). The method is then applied by author to measure the complexity of an academic information system by using the two modeling approaches, namely object oriented and structural models. Measurements in this paper consists of several stages, namely describing the information system that will be built into the UML models and structured. Then the model is analyzed by calculating Crude Function Points (CRP), Relative Complexity Adjustment Factor (RCAF), and then calculate its function point. From the result of a calculation using the FPA to the academic system software development, FP values of object oriented model obtained for 174,64 and the FP value of structured models for 180,93. The result of function point that will be used by developers in determining the price and cost of software systems to be built.
Finding knowledge paths among scientific disciplines
Venue: arXiv cs.DL 2013
Year: 2013

This paper discovers patterns of knowledge dissemination among scientific disciplines. While the transfer of knowledge is largely unobservable, citations from one discipline to another have been proven to be an effective proxy to study disciplinary knowledge flow. This study constructs a knowledge flow network in that a node represents a Journal Citation Report subject category and a link denotes the citations from one subject category to another. Using the concept of shortest path, several quantitative measurements are proposed and applied to a knowledge flow network. Based on an examination of subject categories in Journal Citation Report, this paper finds that social science domains tend to be more self-contained and thus it is more difficult for knowledge from other domains to flow into them; at the same time, knowledge from science domains, such as biomedicine-, chemistry-, and physics-related domains can access and be accessed by other domains more easily. This paper also finds that social science domains are more disunified than science domains, as three fifths of the knowledge paths from one social science domain to another need at least one science domain to serve as an intermediate. This paper contributes to discussions on disciplinarity and interdisciplinarity by providing empirical analysis.