OpenRaiser/Intern-Atlas huggingface dataset:
An Efficient Algorithm for the Equation Tree Automaton via the $k$-C-Continuations
Venue: arXiv cs.FL 2014
Year: 2014

Champarnaud and Ziadi, and Khorsi et al. show how to compute the equation automaton of word regular expression $E$ via the $k$-C-Continuations. Kuske and Meinecke extend the computation of the equation automaton to a regular tree expression $E$ over a ranked alphabet $Σ$ and produce a $O(R\cdot|E|^2)$ time and space complexity algorithm, where $R$ is the maximal rank of a symbol occurring in $Σ$ and $|E|$ is the size of $E$. In this paper, we give a full description of the algorithm based on the acyclic minimization of Revuz. Our algorithm, which is performed in an $O(|Q|\cdot|E|)$ time and space complexity, where $|Q|$ is the number of states of the produced automaton, is more efficient than the one obtained by Kuske and Meinecke.
A Generalization of the Łoś-Tarski Preservation Theorem over Classes of Finite Structures
Venue: arXiv cs.LO 2014
Year: 2014

We investigate a generalization of the Łoś-Tarski preservation theorem via the semantic notion of \emph{preservation under substructures modulo $k$-sized cores}. It was shown earlier that over arbitrary structures, this semantic notion for first-order logic corresponds to definability by $\exists^k\forall^*$ sentences. In this paper, we identify two properties of classes of finite structures that ensure the above correspondence. The first is based on well-quasi-ordering under the embedding relation. The second is a logic-based combinatorial property that strictly generalizes the first. We show that starting with classes satisfying any of these properties, the classes obtained by applying operations like disjoint union, cartesian and tensor products, or by forming words and trees over the classes, inherit the same property. As a fallout, we obtain interesting classes of structures over which an effective version of the Łoś-Tarski theorem holds.
Ring Paxos: High-Throughput Atomic Broadcast
Venue: arXiv cs.DC 2014
Year: 2014

Atomic broadcast is an important communication primitive often used to implement state-machine replication. Despite the large number of atomic broadcast algorithms proposed in the literature, few papers have discussed how to turn these algorithms into efficient executable protocols. This paper focuses on a class of atomic broadcast algorithms based on Paxos, with its corresponding desirable properties: safety under asynchrony assumptions, liveness under weak synchrony assumptions, and resiliency-optimality. The paper presents two protocols, M-Ring Paxos and U-Ring Paxos, derived from Paxos. The protocols inherit the properties of Paxos and can be implemented very efficiently. We report a detailed performance analysis of M-Ring Paxos and U-Ring Paxos and compare them to other atomic broadcast protocols.
A Brief Review on Models for Performance Evaluation in DSS Architecture
Venue: arXiv cs.PF 2014
Year: 2014

Distributed Software Systems are used these days by many people in the real time operations and modern enterprise applications. One of the most important and essential attributes of measurements for the quality of service of distributed software is performance. Performance models can be employed at early stages of the software development cycle to characterize the quantitative behavior of software systems. In this research, performance models based on fuzzy logic approach, queuing network approach and Petri net approach have been reviewed briefly. One of the most common ways in performance analysis of distributed software systems is translating the UML diagrams to mathematical modeling languages for the description of distributed systems such as queuing networks or Petri nets. In this paper, some of these approaches are reviewed briefly. Attributes which are used for performance modeling in the literature are mostly machine based. On the other hand, end users and client parameters for performance evaluation are not covered extensively. In this way, future research could be based on developing hybrid models to capture user decision variables which make system performance evaluation more user driven.
On Fence Patrolling by Mobile Agents
Venue: arXiv cs.DS 2014
Year: 2014

Suppose that a fence needs to be protected (perpetually) by $k$ mobile agents with maximum speeds $v_1,\ldots,v_k$ so that no point on the fence is left unattended for more than a given amount of time. The problem is to determine if this requirement can be met, and if so, to design a suitable patrolling schedule for the agents. Alternatively, one would like to find a schedule that minimizes the \emph{idle time}, that is, the longest time interval during which some point is not visited by any agent. We revisit this problem, introduced by Czyzowicz et al.(2011), and discuss several strategies for the cases where the fence is an open and a closed curve, respectively. In particular: (i) we disprove a conjecture by Czyzowicz et al. regarding the optimality of their Algorithm ${\mathcal A_2}$ for unidirectional patrolling of a closed fence; (ii) we present an algorithm with a lower idle time for patrolling an open fence, improving an earlier result of Kawamura and Kobayashi.
Software Architecture and Subclassing Technique for Semiconductor Manufacturing Machines
Venue: arXiv cs.OH 2014
Year: 2014

This paper proposed software architecture for operating an automatic semiconductor manufacturing machine. Recent machines for semiconductor process are required for high level of automation which are composed of motion control, machine vision, data acquisition and networking. These functions are executed through industrial equipments that are generally installed in a computer. The equipments occupy a great part of system resource and generate a lot of computation, so the software structure should be designed for efficiency. The proposed architecture is consisted of four layers and virtual equipments(VEs). The VEs are made by subclassing the physical equipments(PEs) and the layers are coded into thread which updates the status of VEs. Subroutines in a program refer to the pointer of VEs, and direct access to physical equipment are prohibited. The number of access (NOA) to PEs in typical industrial application was simulated for the unlimited access structure and the presented structure. The result showed that the proposed structure was more efficient than typical ones and irrespective of subroutines. This architecture was also applied to design a machine operating software and performed automatic wafer dicing.
Parallel Genetic Algorithm to Solve Traveling Salesman Problem on MapReduce Framework using Hadoop Cluster
Venue: arXiv cs.DC 2014
Year: 2014

Traveling Salesman Problem (TSP) is one of the most common studied problems in combinatorial optimization. Given the list of cities and distances between them, the problem is to find the shortest tour possible which visits all the cities in list exactly once and ends in the city where it starts. Despite the Traveling Salesman Problem is NP-Hard, a lot of methods and solutions are proposed to the problem. One of them is Genetic Algorithm (GA). GA is a simple but an efficient heuristic method that can be used to solve Traveling Salesman Problem. In this paper, we will show a parallel genetic algorithm implementation on MapReduce framework in order to solve Traveling Salesman Problem. MapReduce is a framework used to support distributed computation on clusters of computers. We used free licensed Hadoop implementation as MapReduce framework.
Safety verification of asynchronous pushdown systems with shaped stacks
Venue: arXiv cs.LO 2014
Year: 2014

In this paper, we study the program-point reachability problem of concurrent pushdown systems that communicate via unbounded and unordered message buffers. Our goal is to relax the common restriction that messages can only be retrieved by a pushdown process when its stack is empty. We use the notion of partially commutative context-free grammars to describe a new class of asynchronously communicating pushdown systems with a mild shape constraint on the stacks for which the program-point coverability problem remains decidable. Stacks that fit the shape constraint may reach arbitrary heights; further a process may execute any communication action (be it process creation, message send or retrieval) whether or not its stack is empty. This class extends previous computational models studied in the context of asynchronous programs, and enables the safety verification of a large class of message passing programs.
A Fluid Approach for Poisson Wireless Networks
Venue: arXiv cs.IT 2014
Year: 2014

Among the different models of networks usually considered, the hexagonal network model is the most popular. However, it requires extensive numerical computations. The Poisson network model, for which the base stations (BS) locations form a spatial Poisson process, allows to consider a non constant distance between base stations. Therefore, it may characterize more realistically operational networks. The Fluid network model, for which the interfering BS are replaced by a continuum of infinitesimal interferers, allows to establish closed-form formula for the SINR (Signal on Interference plus Noise Ratio). This model was validated by comparison with an hexagonal network. The two models establish very close results. As a consequence, the Fluid network model can be used to analyze hexagonal networks. In this paper, we show that the Fluid network model can also be used to analyze Poisson networks. Therefore, the analysis of performance and quality of service becomes very easy, whatever the type of network model, by using the analytical expression of the SINR established by considering the Fluid network model.
Control of Multiple Remote Servers for Quality-Fair Delivery of Multimedia Contents
Venue: arXiv cs.MM 2014
Year: 2014

This paper proposes a control scheme for the quality-fair delivery of several encoded video streams to mobile users sharing a common wireless resource. Video quality fairness, as well as similar delivery delays are targeted among streams. The proposed controller is implemented within some aggregator located near the bottleneck of the network. The transmission rate among streams is adapted based on the quality of the already encoded and buffered packets in the aggregator. Encoding rate targets are evaluated by the aggregator and fed back to each remote video server (fully centralized solution), or directly evaluated by each server in a distributed way (partially distributed solution). Each encoding rate target is adjusted for each stream independently based on the corresponding buffer level or buffering delay in the aggregator. Communication delays between the servers and the aggregator are taken into account. The transmission and encoding rate control problems are studied with a control-theoretic perspective. The system is described with a multi-input multi-output model. Proportional Integral (PI) controllers are used to adjust the video quality and control the aggregator buffer levels. The system equilibrium and stability properties are studied. This provides guidelines for choosing the parameters of the PI controllers. Experimental results show the convergence of the proposed control system and demonstrate the improvement in video quality fairness compared to a classical transmission rate fair streaming solution and to a utility max-min fair approach.
On Convergence of Approximate Message Passing
Venue: arXiv cs.IT 2014
Year: 2014

Approximate message passing is an iterative algorithm for compressed sensing and related applications. A solid theory about the performance and convergence of the algorithm exists for measurement matrices having iid entries of zero mean. However, it was observed by several authors that for more general matrices the algorithm often encounters convergence problems. In this paper we identify the reason of the non-convergence for measurement matrices with iid entries and non-zero mean in the context of Bayes optimal inference. Finally we demonstrate numerically that when the iterative update is changed from parallel to sequential the convergence is restored.
Android Anti-forensics: Modifying CyanogenMod
Venue: arXiv cs.CR 2014
Year: 2014

Mobile devices implementing Android operating systems inherently create opportunities to present environments that are conducive to anti-forensic activities. Previous mobile forensics research focused on applications and data hiding anti-forensics solutions. In this work, a set of modifications were developed and implemented on a CyanogenMod community distribution of the Android operating system. The execution of these solutions successfully prevented data extractions, blocked the installation of forensic tools, created extraction delays and presented false data to industry accepted forensic analysis tools without impacting normal use of the device. The research contribution is an initial empirical analysis of the viability of operating system modifications in an anti-forensics context along with providing the foundation for future research.
Adaptive Video Streaming in MU-MIMO Networks
Venue: arXiv cs.IT 2014
Year: 2014

We consider extensions and improvements on our previous work on dynamic adaptive video streaming in a multi-cell multiuser ``small cell'' wireless network. Previously, we treated the case of single-antenna base stations and, starting from a network utility maximization (NUM) formulation, we devised a ``push'' scheduling policy, where users place requests to sequential video chunks to possibly different base stations with adaptive video quality, and base stations schedule their downlink transmissions in order to stabilize their transmission queues. In this paper we consider a ``pull'' strategy, where every user maintains a request queue, such that users keep track of the video chunks that are effectively delivered. The pull scheme allows to download the chunks in the playback order without skipping or missing them. In addition, motivated by the recent/forthcoming progress in small cell networks (e.g., in wave-2 of the recent IEEE 802.11ac standard), we extend our dynamic streaming approach to the case of base stations capable of multiuser MIMO downlink, i.e., serving multiple users on the same time-frequency slot by spatial multiplexing. By exploiting the ``channel hardening'' effect of high dimensional MIMO channels, we devise a low complexity user selection scheme to solve the underlying max-weighted rate scheduling, which can be easily implemented and runs independently at each base station. Through simulations, we show MIMO gains in terms of video streaming QoE metrics like the pre-buffering and re-buffering times.
Identification of Protein Coding Regions in Genomic DNA Using Unsupervised FMACA Based Pattern Classifier
Venue: arXiv cs.CE 2014
Year: 2014

Genes carry the instructions for making proteins that are found in a cell as a specific sequence of nucleotides that are found in DNA molecules. But, the regions of these genes that code for proteins may occupy only a small region of the sequence. Identifying the coding regions play a vital role in understanding these genes. In this paper we propose a unsupervised Fuzzy Multiple Attractor Cellular Automata (FMCA) based pattern classifier to identify the coding region of a DNA sequence. We propose a distinct K-Means algorithm for designing FMACA classifier which is simple, efficient and produces more accurate classifier than that has previously been obtained for a range of different sequence lengths. Experimental results confirm the scalability of the proposed Unsupervised FCA based classifier to handle large volume of datasets irrespective of the number of classes, tuples and attributes. Good classification accuracy has been established.
Generalized Sphere Packing Bound
Venue: arXiv cs.IT 2014
Year: 2014

Kulkarni and Kiyavash recently introduced a new method to establish upper bounds on the size of deletion-correcting codes. This method is based upon tools from hypergraph theory. The deletion channel is represented by a hypergraph whose edges are the deletion balls (or spheres), so that a deletion-correcting code becomes a matching in this hypergraph. Consequently, a bound on the size of such a code can be obtained from bounds on the matching number of a hypergraph. Classical results in hypergraph theory are then invoked to compute an upper bound on the matching number as a solution to a linear-programming problem. The method by Kulkarni and Kiyavash can be applied not only for the deletion channel but also for other error channels. This paper studies this method in its most general setup. First, it is shown that if the error channel is regular and symmetric then this upper bound coincides with the sphere packing bound and thus is called the generalized sphere packing bound. Even though this bound is explicitly given by a linear programming problem, finding its exact value may still be a challenging task. In order to simplify the complexity of the problem, we present a technique based upon graph automorphisms that in many cases reduces the number of variables and constraints in the problem. We then apply this method on specific examples of error channels. We start with the $Z$ channel and show how to exactly find the generalized sphere packing bound for this setup. Next studied is the non-binary limited magnitude channel both for symmetric and asymmetric errors, where we focus on the single-error case. We follow up on the deletion and grain-error channels and show how to improve upon the existing upper bounds for single deletion/error. Finally, we apply this method for projective spaces and find its generalized sphere packing bound for the single-error case.
Holographic Transformation for Quantum Factor Graphs
Venue: arXiv cs.IT 2014
Year: 2014

Recently, a general tool called a holographic transformation, which transforms an expression of the partition function to another form, has been used for polynomial-time algorithms and for improvement and understanding of the belief propagation. In this work, the holographic transformation is generalized to quantum factor graphs.
Payoff Allocation of Service Coalition in Wireless Mesh Network: A Cooperative Game Perspective
Venue: arXiv cs.GT 2014
Year: 2014

In wireless mesh network (WMN), multiple service providers (SPs) can cooperate to share resources (e.g., relay nodes and spectrum), to serve their collective subscribed customers for better service. As a reward, SPs are able to achieve more individual benefits, i.e., increased revenue or decreased cost, through efficient utilization of shared network resources. However, this cooperation can be realized only if fair allocation of aggregated payoff, which is the sum of the payoff of all the cooperative SPs, can be achieved. We first formulate such cooperation as a coalitional game with transferable utility, specifically, a linear programming game, in which, each SP should obtain the fair share of the aggregated payoff. Then we study the problem of allocating aggregated payoff which leads to stable service coalition of SPs in WMN based on the concepts of dual payoff and Shapley value.
On Near-controllability, Nearly-controllable Subspaces, and Near-controllability Index of a Class of Discrete-time Bilinear Systems: A Root Locus Approach
Venue: arXiv cs.SY 2014
Year: 2014

This paper studies near-controllability of a class of discrete-time bilinear systems via a root locus approach. A necessary and sufficient criterion for the systems to be nearly controllable is given. In particular, by using the root locus approach, the control inputs which achieve the state transition for the nearly controllable systems can be computed. Furthermore, for the non-nearly controllable systems, nearly-controllable subspaces are derived and near-controllability index is defined. Accordingly, the controllability properties of such class of discrete-time bilinear systems are fully characterized. Finally, examples are provided to demonstrate the results of the paper.
Quality of Geographic Information: Ontological approach and Artificial Intelligence Tools
Venue: arXiv cs.AI 2014
Year: 2014

The objective is to present one important aspect of the European IST-FET project "REV!GIS"1: the methodology which has been developed for the translation (interpretation) of the quality of the data into a "fitness for use" information, that we can confront to the user needs in its application. This methodology is based upon the notion of "ontologies" as a conceptual framework able to capture the explicit and implicit knowledge involved in the application. We do not address the general problem of formalizing such ontologies, instead, we rather try to illustrate this with three applications which are particular cases of the more general "data fusion" problem. In each application, we show how to deploy our methodology, by comparing several possible solutions, and we try to enlighten where are the quality issues, and what kind of solution to privilege, even at the expense of a highly complex computational approach. The expectation of the REV!GIS project is that computationally tractable solutions will be available among the next generation AI tools.
How to Run a Campaign: Optimal Control of SIS and SIR Information Epidemics
Venue: arXiv cs.SY 2014
Year: 2014

Information spreading in a population can be modeled as an epidemic. Campaigners (e.g. election campaign managers, companies marketing products or movies) are interested in spreading a message by a given deadline, using limited resources. In this paper, we formulate the above situation as an optimal control problem and the solution (using Pontryagin's Maximum Principle) prescribes an optimal resource allocation over the time of the campaign. We consider two different scenarios --- in the first, the campaigner can adjust a direct control (over time) which allows her to recruit individuals from the population (at some cost) to act as spreaders for the Susceptible-Infected-Susceptible (SIS) epidemic model. In the second case, we allow the campaigner to adjust the effective spreading rate by incentivizing the infected in the Susceptible-Infected-Recovered (SIR) model, in addition to the direct recruitment. We consider time varying information spreading rate in our formulation to model the changing interest level of individuals in the campaign, as the deadline is reached. In both the cases, we show the existence of a solution and its uniqueness for sufficiently small campaign deadlines. For the fixed spreading rate, we show the effectiveness of the optimal control strategy against the constant control strategy, a heuristic control strategy and no control. We show the sensitivity of the optimal control to the spreading rate profile when it is time varying.
Multi-Channel Cognitive Radio Networks: Modeling, Analysis and Synthesis
Venue: arXiv cs.NI 2014
Year: 2014

In this contribution, we establish a model for multichannel cognitive radio networks (CRNs) using the theory of priority queues. This model enables us to conduct a performance analysis in the most general form by the derivation of the probability mass function (PMF) of queue length at the secondary users (SUs). In the second part, a reverse problem is considered to answer the important top-down question of whether a service requirement can be satisfied in a multi-channel CRN knowing the network parameters and traffic situation with respect to the SUs and the primary users (PUs). Terming this problem as the network synthesis, a precise conservation law is obtained, which relates the packet waiting times of both types of users, and based on which the achievable region of the network is also determined. Lastly, by the introduction of a mixed strategy, the conditions for the existence of an optimal trade-off between the interference onto the PUs and the quality-of-service of the SUs is shown, and the optimal mixed strategy is obtained when those conditions are satisfied.