OpenRaiser/Intern-Atlas huggingface dataset:
Small Superpatterns for Dominance Drawing
Venue: arXiv cs.CG 2013
Year: 2013

We exploit the connection between dominance drawings of directed acyclic graphs and permutations, in both directions, to provide improved bounds on the size of universal point sets for certain types of dominance drawing and on superpatterns for certain natural classes of permutations. In particular we show that there exist universal point sets for dominance drawings of the Hasse diagrams of width-two partial orders of size O(n^{3/2}), universal point sets for dominance drawings of st-outerplanar graphs of size O(n\log n), and universal point sets for dominance drawings of directed trees of size O(n^2). We show that 321-avoiding permutations have superpatterns of size O(n^{3/2}), riffle permutations (321-, 2143-, and 2413-avoiding permutations) have superpatterns of size O(n), and the concatenations of sequences of riffles and their inverses have superpatterns of size O(n\log n). Our analysis includes a calculation of the leading constants in these bounds.
Cucker-Smale flocking with alternating leaders
Venue: arXiv cs.MA 2013
Year: 2013

We study the emergent flocking behavior in a group of Cucker-Smale flocking agents under rooted leadership with alternating leaders. It is well known that the network topology regulates the emergent behaviors of flocks. All existing results on the Cucker-Smale model with leader-follower topologies assume a fixed leader during temporal evolution process. The rooted leadership is the most general topology taking a leadership. Motivated by collective behaviors observed in the flocks of birds, swarming fishes and potential engineering applications, we consider the rooted leadership with alternating leaders; that is, at each time slice there is a leader but it can be switched among the agents from time to time. We will provide several sufficient conditions leading to the asymptotic flocking among the Cucker-Smale agents under rooted leadership with alternating leaders.
Green Communication via Power-optimized HARQ Protocols
Venue: arXiv cs.IT 2013
Year: 2013

Recently, efficient use of energy has become an essential research topic for green communication. This paper studies the effect of optimal power controllers on the performance of delay-sensitive communication setups utilizing hybrid automatic repeat request (HARQ). The results are obtained for repetition time diversity (RTD) and incremental redundancy (INR) HARQ protocols. In all cases, the optimal power allocation, minimizing the outage-limited average transmission power, is obtained under both continuous and bursting communication models. Also, we investigate the system throughput in different conditions. The results indicate that the power efficiency is increased substantially, if adaptive power allocation is utilized. For instance, assume Rayleigh-fading channel, a maximum of two (re)transmission rounds with rates $\{1,\frac{1}{2}\}$ nats-per-channel-use and an outage probability constraint ${10}^{-3}$. Then, compared to uniform power allocation, optimal power allocation in RTD reduces the average power by 9 and 11 dB in the bursting and continuous communication models, respectively. In INR, these values are obtained to be 8 and 9 dB, respectively.
A Monadic Framework for Interactive Realizability
Venue: arXiv cs.LO 2013
Year: 2013

We give a new presentation of interactive realizability with a more explicit syntax. Interactive realizability is a realizability semantics that extends the Curry-Howard correspondence to (sub-)classical logic, more precisely to first-order intuitionistic arithmetic (Heyting Arithmetic) extended by the law of the excluded middle restricted to simply existential formulas, a system motivated by its applications in proof mining. Monads can be used to structure functional programs by providing a clean and modular way to include impure features in purely functional languages. We express interactive realizers by means of an abstract framework that applies the monadic approach used in functional programming to modified realizability, in order to obtain more "relaxed" realizability notions that are suitable to classical logic. In particular we use a combination of the state and exception monads in order to capture the learning-from-mistakes nature of interactive realizers at the syntactic level.
Efficient Opportunistic Sensing using Mobile Collaborative Platform MOSDEN
Venue: arXiv cs.NI 2013
Year: 2013

Mobile devices are rapidly becoming the primary computing device in people's lives. Application delivery platforms like Google Play, Apple App Store have transformed mobile phones into intelligent computing devices by the means of applications that can be downloaded and installed instantly. Many of these applications take advantage of the plethora of sensors installed on the mobile device to deliver enhanced user experience. The sensors on the smartphone provide the opportunity to develop innovative mobile opportunistic sensing applications in many sectors including healthcare, environmental monitoring and transportation. In this paper, we present a collaborative mobile sensing framework namely Mobile Sensor Data EngiNe (MOSDEN) that can operate on smartphones capturing and sharing sensed data between multiple distributed applications and users. MOSDEN follows a component-based design philosophy promoting reuse for easy and quick opportunistic sensing application deployments. MOSDEN separates the application-specific processing from the sensing, storing and sharing. MOSDEN is scalable and requires minimal development effort from the application developer. We have implemented our framework on Android-based mobile platforms and evaluate its performance to validate the feasibility and efficiency of MOSDEN to operate collaboratively in mobile opportunistic sensing applications. Experimental outcomes and lessons learnt conclude the paper.
A Polyhedral Method to Compute All Affine Solution Sets of Sparse Polynomial Systems
Venue: arXiv cs.SC 2013
Year: 2013

To compute solutions of sparse polynomial systems efficiently we have to exploit the structure of their Newton polytopes. While the application of polyhedral methods naturally excludes solutions with zero components, an irreducible decomposition of a variety is typically understood in affine space, including also those components with zero coordinates. We present a polyhedral method to compute all affine solution sets of a polynomial system. The method enumerates all factors contributing to a generalized permanent. Toric solution sets are recovered as a special case of this enumeration. For sparse systems as adjacent 2-by-2 minors our methods scale much better than the techniques from numerical algebraic geometry.
A Mobile Robotic Personal Nightstand with Integrated Perceptual Processes
Venue: arXiv cs.RO 2013
Year: 2013

We present an intelligent interactive nightstand mounted on a mobile robot, to aid the elderly in their homes using physical, tactile and visual percepts. We show the integration of three different sensing modalities for controlling the navigation of a robot mounted nightstand within the constrained environment of a general purpose living room housing a single aging individual in need of assistance and monitoring. A camera mounted on the ceiling of the room, gives a top-down view of the obstacles, the person and the nightstand. Pressure sensors mounted beneath the bed-stand of the individual provide physical perception of the person's state. A proximity IR sensor on the nightstand acts as a tactile interface along with a Wii Nunchuck (Nintendo) to control mundane operations on the nightstand. Intelligence from these three modalities are combined to enable path planning for the nightstand to approach the individual. With growing emphasis on assistive technology for the aging individuals who are increasingly electing to stay in their homes, we show how ubiquitous intelligence can be brought inside homes to help monitor and provide care to an individual. Our approach goes one step towards achieving pervasive intelligence by seamlessly integrating different sensors embedded in the fabric of the environment.
Fingerprinting Internet DNS Amplification DDoS Activities
Venue: arXiv cs.CR 2013
Year: 2013

This work proposes a novel approach to infer and characterize Internet-scale DNS amplification DDoS attacks by leveraging the darknet space. Complementary to the pioneer work on inferring Distributed Denial of Service (DDoS) activities using darknet, this work shows that we can extract DDoS activities without relying on backscattered analysis. The aim of this work is to extract cyber security intelligence related to DNS Amplification DDoS activities such as detection period, attack duration, intensity, packet size, rate and geo-location in addition to various network-layer and flow-based insights. To achieve this task, the proposed approach exploits certain DDoS parameters to detect the attacks. We empirically evaluate the proposed approach using 720 GB of real darknet data collected from a /13 address space during a recent three months period. Our analysis reveals that the approach was successful in inferring significant DNS amplification DDoS activities including the recent prominent attack that targeted one of the largest anti-spam organizations. Moreover, the analysis disclosed the mechanism of such DNS amplification DDoS attacks. Further, the results uncover high-speed and stealthy attempts that were never previously documented. The case study of the largest DDoS attack in history lead to a better understanding of the nature and scale of this threat and can generate inferences that could contribute in detecting, preventing, assessing, mitigating and even attributing of DNS amplification DDoS activities.
Extending Common Intervals Searching from Permutations to Sequences
Venue: arXiv cs.DS 2013
Year: 2013

Common intervals have been defined as a modelisation of gene clusters in genomes represented either as permutations or as sequences. Whereas optimal algorithms for finding common intervals in permutations exist even for an arbitrary number of permutations, in sequences no optimal algorithm has been proposed yet even for only two sequences. Surprisingly enough, when sequences are reduced to permutations, the existing algorithms perform far from the optimum, showing that their performances are not dependent, as they should be, on the structural complexity of the input sequences. In this paper, we propose to characterize the structure of a sequence by the number $q$ of different dominating orders composing it (called the domination number), and to use a recent algorithm for permutations in order to devise a new algorithm for two sequences. Its running time is in $O(q_1q_2p+q_1n_1+q_2n_2+N)$, where $n_1, n_2$ are the sizes of the two sequences, $q_1,q_2$ are their respective domination numbers, $p$ is the alphabet size and $N$ is the number of solutions to output. This algorithm performs better as $q_1$ and/or $q_2$ reduce, and when the two sequences are reduced to permutations (i.e. when $q_1=q_2=1$) it has the same running time as the best algorithms for permutations. It is also the first algorithm for sequences whose running time involves the parameter size of the solution. As a counterpart, when $q_1$ and $q_2$ are of $O(n_1)$ and $O(n_2)$ respectively, the algorithm is less efficient than other approaches.
Adoption of bundled services with network externalities and correlated affinities
Venue: arXiv cs.NI 2013
Year: 2013

The goal of this paper is to develop a principled understanding of when it is beneficial to bundle technologies or services whose value is heavily dependent on the size of their user base, i.e., exhibits positive exernalities. Of interest is how the joint distribution, and in particular the correlation, of the values users assign to components of a bundle affect its odds of success. The results offer insight and guidelines for deciding when bundling new Internet technologies or services can help improve their overall adoption. In particular, successful outcomes appear to require a minimum level of value correlation.
Network Parameters Impact on Dynamic Transmission Power Control in Vehicular Ad hoc Networks
Venue: arXiv cs.NI 2013
Year: 2013

In vehicular ad hoc networks, the dynamic change in transmission power is very effective to increase the throughput of the wireless vehicular network and decrease the delay of the message communication between vehicular nodes on the highway. Transmission range is directly proportional to the transmission power the moving node. If the transmission power will be high, the interference increases that can cause higher delay in message reception at receiver end, hence the performance of the network decreased. In this paper, it is analyzed that how transmission power can be controlled by considering other different parameter of the network such as; density, distance between moving nodes, different types of messages dissemination with their priority, selection of an antenna also affects on the transmission power. The dynamic control of transmission power in VANETs serves also for the optimization of the resources where it needs, can be decreased and increased depending on the circumstances of the network. Different applications and events of different types also cause changes in transmission power to enhance the reach-ability. The analysis in this paper is comprised of density, distance with single hop and multi-hop message broadcasting based dynamic transmission power control as well as antenna selection and applications based. Some summarized tables are produced according to the respective parameters of the vehicular network. At the end some valuable observations are made and discussed in detail. This paper concludes with a grand summary of all the protocols discussed in it.
Extended Connectors: Structuring Glue Operators in BIP
Venue: arXiv cs.LO 2013
Year: 2013

Based on a variation of the BIP operational semantics using the offer predicate introduced in our previous work, we extend the algebras used to model glue operators in BIP to encompass priorities. This extension uses the Algebra of Causal Interaction Trees, T(P), as a pivot: existing transformations automatically provide the extensions for the Algebra of Connectors. We then extend the axiomatisation of T(P), since the equivalence induced by the new operational semantics is weaker than that induced by the interaction semantics. This extension leads to canonical normal forms for all structures and to a simplification of the algorithm for the synthesis of connectors from Boolean coordination constraints.
On Context Bisimulation for Parameterized Higher-order Processes
Venue: arXiv cs.LO 2013
Year: 2013

This paper studies context bisimulation for higher-order processes, in the presence of parameterization (viz. abstraction). We show that the extension of higher-order processes with process parameterization retains the characterization of context bisimulation by a much simpler form of bisimulation called normal bisimulation (viz. they are coincident), in which universal quantifiers are eliminated; whereas it is not the same with name parameterization. These results clarify further the bisimulation theory of higher-order processes, and also shed light on the essential distinction between the two kinds of parameterization.
Using multiobjective optimization to map the entropy region of four random variables
Venue: arXiv cs.IT 2013
Year: 2013

Presently the only available method of exploring the 15-dimensional entropy region formed by the entropies of four random variables is the one of Zhang and Yeung from 1998. It is argued that their method is equivalent to solving linear multiobjective optimization problems. Benson's outer approximation algorithm is a fundamental tool for solving these optimization problems. An improved version of Benson's algorithm is described which requires solving one scalar linear program in each iteration rather than two or three as in previous versions. During the algorithm design special care was taken for numerical stability. The implemented algorithm was used to check previous statements about the entropy region, and to gain new information on that region. The experimental results demonstrate the viability of the method for determining the extremal set of medium size, numerically ill-posed optimization problems. With growing problem size two limitations of Benson's algorithm have been observed: the inefficiency of the scalar LP solver on one hand and the unexpectedly large number of intermediate vertices on the other.
Census Data Mining and Data Analysis using WEKA
Venue: arXiv cs.DB 2013
Year: 2013

Data mining (also known as knowledge discovery from databases) is the process of extraction of hidden, previously unknown and potentially useful information from databases. The outcome of the extracted data can be analyzed for the future planning and development perspectives. In this paper, we have made an attempt to demonstrate how one can extract the local (district) level census, socio-economic and population related other data for knowledge discovery and their analysis using the powerful data mining tool Weka.
Calibration of an Articulated Camera System with Scale Factor Estimation
Venue: arXiv cs.CV 2013
Year: 2013

Multiple Camera Systems (MCS) have been widely used in many vision applications and attracted much attention recently. There are two principle types of MCS, one is the Rigid Multiple Camera System (RMCS); the other is the Articulated Camera System (ACS). In a RMCS, the relative poses (relative 3-D position and orientation) between the cameras are invariant. While, in an ACS, the cameras are articulated through movable joints, the relative pose between them may change. Therefore, through calibration of an ACS we want to find not only the relative poses between the cameras but also the positions of the joints in the ACS. In this paper, we developed calibration algorithms for the ACS using a simple constraint: the joint is fixed relative to the cameras connected with it during the transformations of the ACS. When the transformations of the cameras in an ACS can be estimated relative to the same coordinate system, the positions of the joints in the ACS can be calculated by solving linear equations. However, in a non-overlapping view ACS, only the ego-transformations of the cameras and can be estimated. We proposed a two-steps method to deal with this problem. In both methods, the ACS is assumed to have performed general transformations in a static environment. The efficiency and robustness of the proposed methods are tested by simulation and real experiments. In the real experiment, the intrinsic and extrinsic parameters of the ACS are obtained simultaneously by our calibration procedure using the same image sequences, no extra data capturing step is required. The corresponding trajectory is recovered and illustrated using the calibration results of the ACS. Since the estimated translations of different cameras in an ACS may scaled by different scale factors, a scale factor estimation algorithm is also proposed. To our knowledge, we are the first to study the calibration of ACS.
On Robustness Analysis of Stochastic Biochemical Systems by Probabilistic Model Checking
Venue: arXiv cs.NA 2013
Year: 2013

This report proposes a novel framework for a rigorous robustness analysis of stochastic biochemical systems. The technique is based on probabilistic model checking. We adapt the general definition of robustness introduced by Kitano to the class of stochastic systems modelled as continuous time Markov Chains in order to extensively analyse and compare robustness of biological models with uncertain parameters. The framework utilises novel computational methods that enable to effectively evaluate the robustness of models with respect to quantitative temporal properties and parameters such as reaction rate constants and initial conditions. The framework is applied to gene regulation as an example of a central biological mechanism where intrinsic and extrinsic stochasticity plays crucial role due to low numbers of DNA and RNA molecules. Using our methods we have obtained a comprehensive and precise analysis of stochastic dynamics under parameter uncertainty. Furthermore, we apply our framework to compare several variants of two-component signalling networks from the perspective of robustness with respect to intrinsic noise caused by low populations of signalling components. We succeeded to extend previous studies performed on deterministic models (ODE) and show that stochasticity may significantly affect obtained predictions. Our case studies demonstrate that the framework can provide deeper insight into the role of key parameters in maintaining the system functionality and thus it significantly contributes to formal methods in computational systems biology.
Effectiveness of pre- and inprocessing for CDCL-based SAT solving
Venue: arXiv cs.LO 2013
Year: 2013

Applying pre- and inprocessing techniques to simplify CNF formulas both before and during search can considerably improve the performance of modern SAT solvers. These algorithms mostly aim at reducing the number of clauses, literals, and variables in the formula. However, to be worthwhile, it is necessary that their additional runtime does not exceed the runtime saved during the subsequent SAT solver execution. In this paper we investigate the efficiency and the practicability of selected simplification algorithms for CDCL-based SAT solving. We first analyze them by means of their expected impact on the CNF formula and SAT solving at all. While testing them on real-world and combinatorial SAT instances, we show which techniques and combinations of them yield a desirable speedup and which ones should be avoided.
Towards Energy Neutrality in Energy Harvesting Wireless Sensor Networks: A Case for Distributed Compressive Sensing?
Venue: arXiv cs.IT 2013
Year: 2013

This paper advocates the use of the emerging distributed compressive sensing (DCS) paradigm in order to deploy energy harvesting (EH) wireless sensor networks (WSN) with practical network lifetime and data gathering rates that are substantially higher than the state-of-the-art. In particular, we argue that there are two fundamental mechanisms in an EH WSN: i) the energy diversity associated with the EH process that entails that the harvested energy can vary from sensor node to sensor node, and ii) the sensing diversity associated with the DCS process that entails that the energy consumption can also vary across the sensor nodes without compromising data recovery. We also argue that such mechanisms offer the means to match closely the energy demand to the energy supply in order to unlock the possibility for energy-neutral WSNs that leverage EH capability. A number of analytic and simulation results are presented in order to illustrate the potential of the approach.