OpenRaiser/Intern-Atlas huggingface dataset:
Modular Complexity Analysis for Term Rewriting
Venue: arXiv cs.LO 2014
Year: 2014

All current investigations to analyze the derivational complexity of term rewrite systems are based on a single termination method, possibly preceded by transformations. However, the exclusive use of direct criteria is problematic due to their restricted power. To overcome this limitation the article introduces a modular framework which allows to infer (polynomial) upper bounds on the complexity of term rewrite systems by combining different criteria. Since the fundamental idea is based on relative rewriting, we study how matrix interpretations and match-bounds can be used and extended to measure complexity for relative rewriting, respectively. The modular framework is proved strictly more powerful than the conventional setting. Furthermore, the results have been implemented and experiments show significant gains in power.
Higher Inductive Types as Homotopy-Initial Algebras
Venue: arXiv cs.LO 2014
Year: 2014

Homotopy Type Theory is a new field of mathematics based on the surprising and elegant correspondence between Martin-Lofs constructive type theory and abstract homotopy theory. We have a powerful interplay between these disciplines - we can use geometric intuition to formulate new concepts in type theory and, conversely, use type-theoretic machinery to verify and often simplify existing mathematical proofs. A crucial ingredient in this new system are higher inductive types, which allow us to represent objects such as spheres, tori, pushouts, and quotients. We investigate a variant of higher inductive types whose computational behavior is determined up to a higher path. We show that in this setting, higher inductive types are characterized by the universal property of being a homotopy-initial algebra.
Network Traffic Anomaly Detection
Venue: arXiv cs.CR 2014
Year: 2014

This paper presents a tutorial for network anomaly detection, focusing on non-signature-based approaches. Network traffic anomalies are unusual and significant changes in the traffic of a network. Networks play an important role in today's social and economic infrastructures. The security of the network becomes crucial, and network traffic anomaly detection constitutes an important part of network security. In this paper, we present three major approaches to non-signature-based network detection: PCA-based, sketch-based, and signal-analysis-based. In addition, we introduce a framework that subsumes the three approaches and a scheme for network anomaly extraction. We believe network anomaly detection will become more important in the future because of the increasing importance of network security.
Automata theory in nominal sets
Venue: arXiv cs.LO 2014
Year: 2014

We study languages over infinite alphabets equipped with some structure that can be tested by recognizing automata. We develop a framework for studying such alphabets and the ensuing automata theory, where the key role is played by an automorphism group of the alphabet. In the process, we generalize nominal sets due to Gabbay and Pitts.
Defeating the Eavesdropper: On the Achievable Secrecy Capacity using Reconfigurable Antennas
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider the transmission of confidential messages over slow fading wireless channels in the presence of an eavesdropper. We propose a transmission scheme that employs a single reconfigurable antenna at each of the legitimate partners, whereas the eavesdropper uses a single conventional antenna. A reconfigurable antenna can switch its propagation characteristics over time and thus it perceives different fading channels. It is shown that without channel side information (CSI) at the legitimate partners, the main channel can be transformed into an ergodic regime offering a \textit{secrecy capacity} gain for strict outage constraints. If the legitimate partners have partial or full channel side information (CSI), a sort of selection diversity can be applied boosting the maximum secret communication rate. In this case, fading acts as a friend not a foe.
Approximation Algorithms for Covering and Packing Problems on Paths
Venue: arXiv cs.DS 2014
Year: 2014

Routing and scheduling problems are fundamental problems in combinatorial optimization, and also have many applications. Most variations of these problems are NP-Hard, so we need to use heuristics to solve these problems on large instances, which are fast and yet come close to the optimal value. In this thesis, we study the design and analysis of approximation algorithms for such problems. We focus on two important class of problems. The first is the Unsplittable Flow Problem and some of its variants and the second is the Resource Allocation for Job Scheduling Problem and some of its variants. The first is a packing problem, whereas the second is a covering problem.
Incremental classification using Feature Tree
Venue: arXiv cs.DB 2014
Year: 2014

In recent years, stream data have become an immensely growing area of research for the database, computer science and data mining communities. Stream data is an ordered sequence of instances. In many applications of data stream mining data can be read only once or a small number of times using limited computing and storage capabilities. Some of the issues occurred in classifying stream data that have significant impact in algorithm development are size of database, online streaming, high dimensionality and concept drift. The concept drift occurs when the properties of the historical data and target variable change over time abruptly in such a case that the predictions will become inaccurate as time passes. In this paper the framework of incremental classification is proposed to solve the issues for the classification of stream data. The Trie structure based incremental feature tree, Trie structure based incremental FP (Frequent Pattern) growth tree and tree based incremental classification algorithm are introduced in the proposed framework.
Backtracking algorithms for service selection
Venue: arXiv cs.DC 2014
Year: 2014

In this paper, we explore the automation of services' compositions. We focus on the service selection problem. In the formulation that we consider, the problem's inputs are constituted by a behavioral composition whose abstract services must be bound to concrete ones. The objective is to find the binding that optimizes the {\it utility} of the composition under some services level agreements. We propose a complete solution. Firstly, we show that the service selection problem can be mapped onto a Constraint Satisfaction Problem (CSP). The benefit of this mapping is that the large know-how in the resolution of the CSP can be used for the service selection problem. Among the existing techniques for solving CSP, we consider the backtracking. Our second contribution is to propose various backtracking-based algorithms for the service selection problem. The proposed variants are inspired by existing heuristics for the CSP. We analyze the runtime gain of our framework over an intuitive resolution based on exhaustive search. Our last contribution is an experimental evaluation in which we demonstrate that there is an effective gain in using backtracking instead of some comparable approaches. The experiments also show that our proposal can be used for finding in real time, optimal solutions on small and medium services' compositions.
A Cellular Automata based Optimal Edge Detection Technique using Twenty-Five Neighborhood Model
Venue: arXiv cs.CV 2014
Year: 2014

Cellular Automata (CA) are common and most simple models of parallel computations. Edge detection is one of the crucial task in image processing, especially in processing biological and medical images. CA can be successfully applied in image processing. This paper presents a new method for edge detection of binary images based on two dimensional twenty five neighborhood cellular automata. The method considers only linear rules of CA for extraction of edges under null boundary condition. The performance of this approach is compared with some existing edge detection techniques. This comparison shows that the proposed method to be very promising for edge detection of binary images. All the algorithms and results used in this paper are prepared in MATLAB.
Combining finite and continuous solvers
Venue: arXiv cs.AI 2014
Year: 2014

Combining efficiency with reliability within CP systems is one of the main concerns of CP developers. This paper presents a simple and efficient way to connect Choco and Ibex, two CP solvers respectively specialised on finite and continuous domains. This enables to take advantage of the most recent advances of the continuous community within Choco while saving development and maintenance resources, hence ensuring a better software quality.
Quantile Representation for Indirect Immunofluorescence Image Classification
Venue: arXiv cs.CV 2014
Year: 2014

In the diagnosis of autoimmune diseases, an important task is to classify images of slides containing several HEp-2 cells. All cells from one slide share the same label, and by classifying cells from one slide independently, some information on the global image quality and intensity is lost. Considering one whole slide as a collection (a bag) of feature vectors, however, poses the problem of how to handle this bag. A simple, and surprisingly effective, approach is to summarize the bag of feature vectors by a few quantile values per feature. This characterizes the full distribution of all instances, thereby assuming that all instances in a bag are informative. This representation is particularly useful when each bag contains many feature vectors, which is the case in the classification of the immunofluorescence images. Experiments on the classification of indirect immunofluorescence images show the usefulness of this approach.
Reasoning about Games via a First-order Modal Model Checking Approach
Venue: arXiv cs.LO 2014
Year: 2014

In this work, we present a logic based on first-order CTL, namely Game Analysis Logic (GAL), in order to reason about games. We relate models and solution concepts of Game Theory as models and formulas of GAL, respectively. Precisely, we express extensive games with perfect in- formation as models of GAL, and Nash equilibrium and subgame perfect equilibrium by means of formulas of GAL. From a practical point of view, we provide a GAL model checker in order to analyze games automatically. We use our model checker in at least two directions: to find solution con- cepts of Game Theory; and, to analyze players that are based on standard algorithms of the AI community, such as the minimax procedure.
A Three-Phase Search Approach for the Quadratic Minimum Spanning Tree Problem
Venue: arXiv cs.DS 2014
Year: 2014

Given an undirected graph with costs associated with each edge as well as each pair of edges, the quadratic minimum spanning tree problem (QMSTP) consists of determining a spanning tree of minimum total cost. This problem can be used to model many real-life network design applications, in which both routing and interference costs should be considered. For this problem, we propose a three-phase search approach named TPS, which integrates 1) a descent-based neighborhood search phase using two different move operators to reach a local optimum from a given starting solution, 2) a local optima exploring phase to discover nearby local optima within a given regional search area, and 3) a perturbation-based diversification phase to jump out of the current regional search area. Additionally, we introduce dedicated techniques to reduce the neighborhood to explore and streamline the neighborhood evaluations. Computational experiments based on hundreds of representative benchmarks show that TPS produces highly competitive results with respect to the best performing approaches in the literature by improving the best known results for 31 instances and matching the best known results for the remaining instances only except two cases. Critical elements of the proposed algorithms are analyzed.
WiFiPos: An In/Out-Door Positioning Tool
Venue: arXiv cs.NI 2014
Year: 2014

Geographical location solutions have a wide diversity of applications, ranging from emergency services to access to tourist and entertainment services. GPS (Global Positioning System) is the most widely used system for outdoor areas. Since it requires a direct line of sight with the satellites, it cannot be used indoors. For indoor positioning, the most commonly used technology to calculate the position of mobile devices is Wi-Fi. In this article, we present a positioning tool called WiFiPos based on Wi-Fi signal processing. This tool uses different variations of the Fingerprint technique to analyze the performance and accuracy of the system both indoors and outdoors.
Use of Dynamical Systems Modeling to Hybrid Cloud Database
Venue: arXiv cs.DB 2014
Year: 2014

In the article, an experiment is aimed at clarifying the transfer efficiency of the database in the cloud infrastructure. The system was added to the control unit, which has guided the database search in the local part or in the cloud. It is shown that the time data acquisition remains unchanged as a result of modification. Suggestions have been made about the use of the theory of dynamic systems to hybrid cloud database. The present work is aimed at attracting the attention of spe-cialists in the field of cloud database to the apparatus control theory. The experiment presented in this article allows the use of the description of the known methods for solving important practical problems.
Programming plantation lines on driverless tractors
Venue: arXiv cs.CE 2014
Year: 2014

Recent advances in Agricultural Engineering include image processing, robotics and geographic information systems (GIS). Some tasks are still accomplished manually, like drawing plantation lines that optimize productivity. Herewith we present an algorithm to find the optimal plantation lines in linear time. The algorithm is based upon classical results of Geometry which enabled a source code with only 573 lines. We have implemented it in Matlab for sugar cane, and it can be easily adapted to other crops like coffee, maize and soy.
PUC-Logic
Venue: arXiv cs.LO 2014
Year: 2014

We present a logic for Proximity-based Understanding of Conditionals (PUC-Logic) that unifies the Counterfactual and Deontic logics proposed by David Lewis. We also propose a natural deduction system (PUC-ND) associated to this new logic. This inference system is proven to be sound, complete, normalizing and decidable. The relative completeness for the $\boldsymbol{V}$ and $\boldsymbol{CO}$ logics is shown to emphasize the unified approach over the work of Lewis.
Homeland Defense and Security Universal Interface Software (HDUIS) Protocol Communication Gateway UIS Protocol Enhancements, Alterations and Attachments
Venue: arXiv cs.CY 2014
Year: 2014

The Universal Interface Software(UIS) Protocol was a Theater Missile Defense Gateway Protocol which linked the Strategic Defense Initiative(SDI) Architecture Killer Satellite Software Protocol to the National Test Bed Simulation Software Protocol to enable neural network shock loop operation when ICBMS were approaching the SDI Shield. A Gateway Software is required for Homeland Defense and Security Systems to communicate the sensor information from hardware and software boxes at airports and government buildings and other locations to the Global Information Grid(GIG). Therefore, a Homeland Defense and Security UIS(HDSUIS) Protocol is achieved by UIS conversion to HDSUIS for Thresholds Stabilization and GIG and terrorist sensor Enhancements, Homeland Defense and Security Lagrangian equation and GIG simulation facility timing chart Alterations, and two Catastrophe Theory Protocol Attachments to the UIS Geometric software structure inner cube. This UIS Protocol conversion to the HDSUIS Protocol will track and provide a Congestion Controlled, i.e.,prevention of deadlock and livelock, communication of (1) Shoe bombers and copycat shoe bombers, (2) deeply buried and imbedded boxes with explosives, (3) damage to lase1 equipment, (4) shoulder missile fired armament, and (5) surface to air missiles from their sensor equipment to the Global Information Grid with Theater Missile Defense Characteristics. The Homeland Defense and Security GNNO(Geometric Neural Network Overlay) Protocol will be derived as a conversion of the UIS GNNO Protocol.
Performance Improvement of OFDM System Using Iterative Signal Clipping With Various Window Techniques for PAPR Reduction
Venue: arXiv cs.IT 2014
Year: 2014

OFDM signals demonstrates high fluctuations termed as Peak to Average Power Ratio (PAPR).The problem of OFDM is the frequent occurrence of high Peaks in the time domain signal which in turn reduces the efficiency of transmit high power amplifier.In this paper we discussed clipping and filtering technique which is easy to implement and reduces the amount of PAPR by clipping the peak of the maximum power signal.This technique clips the OFDM signal to a predefined threshold and uses a filter to eliminate the out-of-band radiation.Moreover, analysis of PAPR is given by varying different filters.The study is focused to reduce PAPR by iterative clipping and filtering method. The symbol error rate performances for different modulation techniques have been countered.Each clipping noise sample is multiplied by a window function(e.g.Hanning,Kaiser, or Hamming) to suppress the out-of-band noise.It is shown that clipping and different filtering techniques for improvement in the SER performance and provides further reduction in PAPR.
How Fast Can We Multiply Large Integers on an Actual Computer?
Venue: arXiv cs.CC 2014
Year: 2014

We provide two complexity measures that can be used to measure the running time of algorithms to compute multiplications of long integers. The random access machine with unit or logarithmic cost is not adequate for measuring the complexity of a task like multiplication of long integers. The Turing machine is more useful here, but fails to take into account the multiplication instruction for short integers, which is available on physical computing devices. An interesting outcome is that the proposed refined complexity measures do not rank the well known multiplication algorithms the same way as the Turing machine model.
Foundation for Frequent Pattern Mining Algorithms Implementation
Venue: arXiv cs.DB 2014
Year: 2014

As with the development of the IT technologies, the amount of accumulated data is also increasing. Thus the role of data mining comes into picture. Association rule mining becomes one of the significant responsibilities of descriptive technique which can be defined as discovering meaningful patterns from large collection of data. The frequent pattern mining algorithms determine the frequent patterns from a database. Mining frequent itemset is very fundamental part of association rule mining. Many algorithms have been proposed from last many decades including majors are Apriori, Direct Hashing and Pruning, FP-Growth, ECLAT etc. The aim of this study is to analyze the existing techniques for mining frequent patterns and evaluate the performance of them by comparing Apriori and DHP algorithms in terms of candidate generation, database and transaction pruning. This creates a foundation to develop newer algorithm for frequent pattern mining.
The Generalized Statistical Complexity of PolSAR Data
Venue: arXiv cs.IT 2014
Year: 2014

This paper presents and discusses the use of a new feature for PolSAR imagery: the Generalized Statistical Complexity. This measure is able to capture the disorder of the data by means of the entropy, as well as its departure from a reference distribution. The latter component is obtained by measuring a stochastic distance between two models: the $\mathcal G^0$ and the Gamma laws. Preliminary results on the intensity components of AIRSAR image of San Francisco are encouraging.
Design of Locally E-management System for Technical Education Foundation- Erbil
Venue: arXiv cs.CY 2014
Year: 2014

Until now, there is no e-management and automation necessary for the operations or procedures of the departments in the Technical Education Foundation Erbil, and the foundation like any other organization in Kurdistan region is not connected to the network, because there is not infrastructure for that purpose. To solve this problem, comes the proposal DLMS4TEF, which requirements are divided into hardware and software, as hardware will need Fast-Ethernet (LAN) technology to connect the departments of the Foundation via Client-Server network later, when an infrastructure is established for e-governments or e-management, it may be extended to the campus network. The software is represented by installing windows server to implement the proposal design of DLMS4TEF, PHP script is used as web programming that supports the server, where as the HTML and JavaScript are used to support the client side. The dynamic DLMS4TEF will be based on relational database, which is created by using MySQL, to support processing hundreds of queries per second, and the Kurdish Unicode to support Kurdish fonts of GUI's, Moreover, for security DLMS4TEF allows each department in the Foundation to enter its own section and prevent accessing other sections by using HTAccessible program which allows the user to access by using his IP address and his computer only. The important conclusions and advantages of applying DLMS4TEF are making backup to DLMS4TEF's databases using the option (zipped) which allows them to reach the size of (3%) of the original database size, sufficient security techniques, through achieving levels of security, hidden access to the administrator section, and finally DLMS4TEF, when compared with the traditional methods and project of Oman, shows the same efficiency of some, if not better, features of Oman. Keywords- E-management, Client-Server network, Fast-Ethernet, PHP, MySQL
Tactical Fixed Job Scheduling with Spread-Time Constraints
Venue: arXiv cs.DS 2014
Year: 2014

We address the tactical fixed job scheduling problem with spread-time constraints. In such a problem, there are a fixed number of classes of machines and a fixed number of groups of jobs. Jobs of the same group can only be processed by machines of a given set of classes. All jobs have their fixed start and end times. Each machine is associated with a cost according to its machine class. Machines have spread-time constraints, with which each machine is only available for $L$ consecutive time units from the start time of the earliest job assigned to it. The objective is to minimize the total cost of the machines used to process all the jobs. For this strongly NP-hard problem, we develop a branch-and-price algorithm, which solves instances with up to $300$ jobs, as compared with CPLEX, which cannot solve instances of $100$ jobs. We further investigate the influence of machine flexibility by computational experiments. Our results show that limited machine flexibility is sufficient in most situations.
Amortised Resource Analysis and Typed Polynomial Interpretations (extended version)
Venue: arXiv cs.LO 2014
Year: 2014

We introduce a novel resource analysis for typed term rewrite systems based on a potential-based type system. This type system gives rise to polynomial bounds on the innermost runtime complexity. We relate the thus obtained amortised resource analysis to polynomial interpretations and obtain the perhaps surprising result that whenever a rewrite system R can be well-typed, then there exists a polynomial interpretation that orients R. For this we adequately adapt the standard notion of polynomial interpretations to the typed setting.