OpenRaiser/Intern-Atlas huggingface dataset:
Context-Dependent Functions: Narrowing the Realm of Turing's Halting Problem
Venue: arXiv cs.LO 2015
Year: 2015

This paper describes Turing's Halting Problem (HP), and reviews the classic proof that no function exists that can solve HP. The concept of a "Context-Dependent Function" (CDF), whose behavior varies based on seemingly irrelevant changes to a program calling that function, is introduced, and the proof of HP's undecidability is re-examined in light of CDFs. The existence of CDFs is established via a pair of examples of such functions. The conclusion of the proof of HP's undecidability is thus shown to be overly strong, as it doesn't show that no solution to HP exists, but rather that a solution must be a CDF. A higher-level analysis of this work is given, followed by conclusions and comments on future work.
Annotating Cognates and Etymological Origin in Turkic Languages
Venue: arXiv cs.CL 2015
Year: 2015

Turkic languages exhibit extensive and diverse etymological relationships among lexical items. These relationships make the Turkic languages promising for exploring automated translation lexicon induction by leveraging cognate and other etymological information. However, due to the extent and diversity of the types of relationships between words, it is not clear how to annotate such information. In this paper, we present a methodology for annotating cognates and etymological origin in Turkic languages. Our method strives to balance the amount of research effort the annotator expends with the utility of the annotations for supporting research on improving automated translation lexicon induction.
Using Riemannian geometry for SSVEP-based Brain Computer Interface
Venue: arXiv cs.LG 2015
Year: 2015

Riemannian geometry has been applied to Brain Computer Interface (BCI) for brain signals classification yielding promising results. Studying electroencephalographic (EEG) signals from their associated covariance matrices allows a mitigation of common sources of variability (electronic, electrical, biological) by constructing a representation which is invariant to these perturbations. While working in Euclidean space with covariance matrices is known to be error-prone, one might take advantage of algorithmic advances in information geometry and matrix manifold to implement methods for Symmetric Positive-Definite (SPD) matrices. This paper proposes a comprehensive review of the actual tools of information geometry and how they could be applied on covariance matrices of EEG. In practice, covariance matrices should be estimated, thus a thorough study of all estimators is conducted on real EEG dataset. As a main contribution, this paper proposes an online implementation of a classifier in the Riemannian space and its subsequent assessment in Steady-State Visually Evoked Potential (SSVEP) experimentations.
Multi-phase IRC Botnet and Botnet Behavior Detection Model
Venue: arXiv cs.CR 2015
Year: 2015

Botnets are considered one of the most dangerous and serious security threats facing the networks and the Internet. Comparing with the other security threats, botnet members have the ability to be directed and controlled via C&C messages from the botmaster over common protocols such as IRC and HTTP, or even over covert and unknown applications. As for IRC botnets, general security instances like firewalls and IDSes do not provide by themselves a viable solution to prevent them completely. These devices could not differentiate well between the legitimate and malicious traffic of the IRC protocol. So, this paper is proposing an IDS-based and multi-phase IRC botnet and botnet behavior detection model based on C&C responses messages and malicious behaviors of the IRC bots inside the network environment. The proposed model has been evaluated on five network traffic traces from two different network environments (Virtual network and DARPA 2000 Windows NT Attack Data Set). The results show that the proposed model could detect all the infected IRC botnet member(s), state their current status of attack, filter their malicious IRC messages, pass the other normal IRC messages and detect the botnet behavior regardless of the botnet communication protocol with very low false positive rate. The proposed model has been compared with some of the existing and well-known approaches, including BotHunter, BotSniffer and Rishi regarding botnet characteristics taken in each approach. The comparison showed that the proposed model has made a progress on the comparative models by not to rely on a certain time window or specific bot signatures.
Image enhancement in intensity projected multichannel MRI using spatially adaptive directional anisotropic diffusion
Venue: arXiv cs.CV 2015
Year: 2015

Anisotropic Diffusion is widely used for noise reduction with simultaneous preservation of vascular structures in maximum intensity projected (MIP) angiograms. However, extension to minimum intensity projected (mIP) venograms in Susceptibility Weighted Imaging (SWI) poses difficulties due to spatially varying baseline. Here, we introduce a modified version of the directional anisotropic diffusion which allows us to simultaneously reduce the noise and enhance vascular structures reconstructed using both M/mIP angiograms. This method is based on spatial adaptation of the diffusion function, separately in the directions of the gradient, and along those of the minimum and maximum curvatures. The existing approach of directional anisotropic diffusion uses binary switched diffusion function to ensure diffusion along the direction of maximum curvature stopped near the vessel borders. Here, the choice of a threshold for detecting the upper limit of diffusion becomes difficult in the presence of spatially varying baseline. Also, the approach of using vesselness measure to steer the diffusion process results in structural discontinuities due to junction suppression in mIP. The merits of the proposed method include elimination of the need for an apriori choice of a threshold to detect the vessel, and problems due to junction suppression. The proposed method is also extended to multi-channel phase contrast angiogram.
Maximum Sum Rate of Slotted Aloha with Capture
Venue: arXiv cs.IT 2015
Year: 2015

The sum rate performance of random-access networks crucially depends on the access protocol and receiver structure. Despite extensive studies, how to characterize the maximum sum rate of the simplest version of random access, Aloha, remains an open question. In this paper, a comprehensive study of the sum rate performance of slotted Aloha networks is presented. By extending the unified analytical framework proposed in [20], [21] from the classical collision model to the capture model, the network steady-state point in saturated conditions is derived as a function of the signal-to-interference-plus-noise ratio (SINR) threshold which determines a fundamental tradeoff between the information encoding rate and the network throughput. To maximize the sum rate, both the SINR threshold and backoff parameters of nodes should be properly selected. Explicit expressions of the maximum sum rate and the optimal setting are obtained, which show that similar to the sum capacity of the multiple access channel, the maximum sum rate of slotted Aloha also logarithmically increases with the mean received signal-to-noise ratio (SNR), but the high-SNR slope is only $e^{-1}$. Effects of backoff and power control on the sum rate performance of slotted Aloha networks are further discussed, which shed important light on the practical network design.
All-to-all Broadcast for Vehicular Networks Based on Coded Slotted ALOHA
Venue: arXiv cs.IT 2015
Year: 2015

We propose an uncoordinated all-to-all broadcast protocol for periodic messages in vehicular networks based on coded slotted ALOHA (CSA). Unlike classical CSA, each user acts as both transmitter and receiver in a half-duplex mode. As in CSA, each user transmits its packet several times. The half-duplex mode gives rise to an interesting design trade-off: the more the user repeats its packet, the higher the probability that this packet is decoded by other users, but the lower the probability for this user to decode packets from others. We compare the proposed protocol with carrier sense multiple access with collision avoidance, currently adopted as a multiple access protocol for vehicular networks. The results show that the proposed protocol greatly increases the number of users in the network that reliably communicate with each other. We also provide analytical tools to predict the performance of the proposed protocol.
User Association in Massive MIMO HetNets
Venue: arXiv cs.IT 2015
Year: 2015

Massive MIMO and small cell are both recognized as the key technologies for the future 5G wireless systems. In this paper, we investigate the problem of user association in a heterogeneous network (HetNet) with massive MIMO and small cells, where the macro base station (BS) is equipped with a massive MIMO and the picocell BS's are equipped with regular MIMOs. We first develop centralized user association algorithms with proven optimality, considering various objectives such as rate maximization, proportional fairness, and joint user association and resource allocation. We then model the massive MIMO HetNet as a repeated game, which leads to distributed user association algorithms with proven convergence to the Nash Equilibrium (NE). We demonstrate the efficacy of these optimal schemes by comparison with several greedy algorithms through simulations.
BITS-Tree-An Efficient Data Structure for Segment Storage and Query Processing
Venue: arXiv cs.CG 2015
Year: 2015

In this paper, a new and novel data structure is proposed to dynamically insert and delete segments. Unlike the standard segment trees[3], the proposed data structure permits insertion of a segment with interval range beyond the interval range of the existing tree, which is the interval between minimum and maximum values of the end points of all the segments. Moreover, the number of nodes in the proposed tree is lesser as compared to the dynamic version of the standard segment trees, and is able to answer both stabbing and range queries practically much faster compared to the standard segment trees.
Flexible Content Placement in Cache Networks using Reinforced Counters
Venue: arXiv cs.NI 2015
Year: 2015

In this paper we study the problem of content placement in a cache network. We consider a network where routing of requests is based on random walks. Content placement is done using a novel mechanism referred to as reinforced counters. To each content we associate a counter, which is incremented every time the content is requested, and which is decremented at a fixed rate. We model and analyze this mechanism, tuning its parameters so as to achieve desired performance goals for a single cache or for a cache network. We also show that the optimal static content placement, without reinforced counters, is NP hard under different design goals.
The ModelCC Model-Based Parser Generator
Venue: arXiv cs.FL 2015
Year: 2015

Formal languages let us define the textual representation of data with precision. Formal grammars, typically in the form of BNF-like productions, describe the language syntax, which is then annotated for syntax-directed translation and completed with semantic actions. When, apart from the textual representation of data, an explicit representation of the corresponding data structure is required, the language designer has to devise the mapping between the suitable data model and its proper language specification, and then develop the conversion procedure from the parse tree to the data model instance. Unfortunately, whenever the format of the textual representation has to be modified, changes have to propagated throughout the entire language processor tool chain. These updates are time-consuming, tedious, and error-prone. Besides, in case different applications use the same language, several copies of the same language specification have to be maintained. In this paper, we introduce ModelCC, a model-based parser generator that decouples language specification from language processing, hence avoiding many of the problems caused by grammar-driven parsers and parser generators. ModelCC incorporates reference resolution within the parsing process. Therefore, instead of returning mere abstract syntax trees, ModelCC is able to obtain abstract syntax graphs from input strings.
Cloud-Assisted Remote Sensor Network Virtualization for Distributed Consensus Estimation
Venue: arXiv cs.NI 2015
Year: 2015

We develop cloud-assisted remote sensing techniques for enabling distributed consensus estimation of unknown parameters in a given geographic area. We first propose a distributed sensor network virtualization algorithm that searches for, selects, and coordinates Internet-accessible sensors to perform a sensing task in a specific region. The algorithm converges in linearithmic time for large-scale networks, and requires exchanging a number of messages that is at most linear in the number of sensors. Second, we design an uncoordinated, distributed algorithm that relies on the selected sensors to estimate a set of parameters without requiring synchronization among the sensors. Our simulation results show that the proposed algorithm, when compared to conventional ADMM (Alternating Direction Method of Multipliers), reduces communication overhead significantly without compromising the estimation error. In addition, the convergence time, though increases slightly, is still linear as in the case of conventional ADMM.
LATCH: Learned Arrangements of Three Patch Codes
Venue: arXiv cs.CV 2015
Year: 2015

We present a novel means of describing local image appearances using binary strings. Binary descriptors have drawn increasing interest in recent years due to their speed and low memory footprint. A known shortcoming of these representations is their inferior performance compared to larger, histogram based descriptors such as the SIFT. Our goal is to close this performance gap while maintaining the benefits attributed to binary representations. To this end we propose the Learned Arrangements of Three Patch Codes descriptors, or LATCH. Our key observation is that existing binary descriptors are at an increased risk from noise and local appearance variations. This, as they compare the values of pixel pairs; changes to either of the pixels can easily lead to changes in descriptor values, hence damaging its performance. In order to provide more robustness, we instead propose a novel means of comparing pixel patches. This ostensibly small change, requires a substantial redesign of the descriptors themselves and how they are produced. Our resulting LATCH representation is rigorously compared to state-of-the-art binary descriptors and shown to provide far better performance for similar computation and space requirements.
Screen Content Image Segmentation Using Least Absolute Deviation Fitting
Venue: arXiv cs.CV 2015
Year: 2015

We propose an algorithm for separating the foreground (mainly text and line graphics) from the smoothly varying background in screen content images. The proposed method is designed based on the assumption that the background part of the image is smoothly varying and can be represented by a linear combination of a few smoothly varying basis functions, while the foreground text and graphics create sharp discontinuity and cannot be modeled by this smooth representation. The algorithm separates the background and foreground using a least absolute deviation method to fit the smooth model to the image pixels. This algorithm has been tested on several images from HEVC standard test sequences for screen content coding, and is shown to have superior performance over other popular methods, such as k-means clustering based segmentation in DjVu and shape primitive extraction and coding (SPEC) algorithm. Such background/foreground segmentation are important pre-processing steps for text extraction and separate coding of background and foreground for compression of screen content images.
Nested Antichains for WS1S
Venue: arXiv cs.LO 2015
Year: 2015

We propose a novel approach for coping with alternating quantification as the main source of nonelementary complexity of deciding WS1S formulae. Our approach is applicable within the state-of-the-art automata-based WS1S decision procedure implemented, e.g. in MONA. The way in which the standard decision procedure processes quantifiers involves determinization, with its worst case exponential complexity, for every quantifier alternation in the prefix of a formula. Our algorithm avoids building the deterministic automata---instead, it constructs only those of their states needed for (dis)proving validity of the formula. It uses a symbolic representation of the states, which have a deeply nested structure stemming from the repeated implicit subset construction, and prunes the search space by a nested subsumption relation, a generalization of the one used by the so-called antichain algorithms for handling nondeterministic automata. We have obtained encouraging experimental results, in some cases outperforming MONA by several orders of magnitude.
Generalizing Multi-party Contract Signing
Venue: arXiv cs.CR 2015
Year: 2015

Multi-party contract signing (MPCS) protocols allow a group of signers to exchange signatures on a predefined contract. Previous approaches considered either completely linear protocols or fully parallel broadcasting protocols. We introduce the new class of DAG MPCS protocols which combines parallel and linear execution and allows for parallelism even within a signer role. This generalization is useful in practical applications where the set of signers has a hierarchical structure, such as chaining of service level agreements and subcontracting. Our novel DAG MPCS protocols are represented by directed acyclic graphs and equipped with a labeled transition system semantics. We define the notion of abort-chaining sequences and prove that a DAG MPCS protocol satisfies fairness if and only if it does not have an abort-chaining sequence. We exhibit several examples of optimistic fair DAG MPCS protocols. The fairness of these protocols follows from our theory and has additionally been verified with our automated tool. We define two complexity measures for DAG MPCS protocols, related to execution time and total number of messages exchanged. We prove lower bounds for fair DAG MPCS protocols in terms of these measures.
On cyclic codes over $\mathbb{Z}_q+u\mathbb{Z}_q$
Venue: arXiv cs.IT 2015
Year: 2015

Let $R=\mathbb{Z}_q+u\mathbb{Z}_q$, where $q=p^s$ and $u^2=0$. In this paper, some structural properties of cyclic codes over the ring $R$ are considered. A necessary and sufficient condition for cyclic codes over the ring $R$ to be free is obtained and a BCH-type bound on the minimum Hamming distance for them is also given.
RDF Validation Requirements - Evaluation and Logical Underpinning
Venue: arXiv cs.LO 2015
Year: 2015

There are many case studies for which the formulation of RDF constraints and the validation of RDF data conforming to these constraint is very important. As a part of the collaboration with the W3C and the DCMI working groups on RDF validation, we identified major RDF validation requirements and initiated an RDF validation requirements database which is available to contribute at http://purl.org/net/rdf-validation. The purpose of this database is to collaboratively collect case studies, use cases, requirements, and solutions regarding RDF validation. Although, there are multiple constraint languages which can be used to formulate RDF constraints (associated with these requirements), there is no standard way to formulate them. This paper serves to evaluate to which extend each requirement is satisfied by each of these constraint languages. We take reasoning into account as an important pre-validation step and therefore map constraints to DL in order to show that each constraint can be mapped to an ontology describing RDF constraints generically.
Sequence-based Detection of Sleeping Cell Failures in Mobile Networks
Venue: arXiv cs.NI 2015
Year: 2015

This article presents an automatic malfunction detection framework based on data mining approach to analysis of network event sequences. The considered environment is Long Term Evolution (LTE) for Universal Mobile Telecommunication System (UMTS) with sleeping cell caused by random access channel failure. Sleeping cell problem means unavailability of network service without triggered alarm. The proposed detection framework uses N-gram analysis for identification of abnormal behavior in sequences of network events. These events are collected with Minimization of Drive Tests (MDT) functionality standardized in LTE. Further processing applies dimensionality reduction, anomaly detection with k-nearest neighbor, cross-validation, post-processing techniques and efficiency evaluation. Different anomaly detection approaches proposed in this paper are compared against each other with both classic data mining metrics, such as F-score and receiver operating characteristic curves, and a newly proposed heuristic approach. Achieved results demonstrate that the suggested method can be used in modern performance monitoring systems for reliable, timely and automatic detection of random access channel sleeping cells.
A One-Dimensional Physically Universal Cellular Automaton
Venue: arXiv cs.FL 2015
Year: 2015

Physical universality of a cellular automaton was defined by Janzing in 2010 as the ability to implement an arbitrary transformation of spatial patterns. In 2014, Schaeffer gave a construction of a two-dimensional physically universal cellular automaton. We construct a one-dimensional version of the automaton.
Numerical modelling of sandstone uniaxial compression test using a mix-mode cohesive fracture model
Venue: arXiv cs.CE 2015
Year: 2015

A mix-mode cohesive fracture model considering tension, compression and shear material behaviour is presented, which has wide applications to geotechnical problems. The model considers both elastic and inelastic displacements. Inelastic displacement comprises fracture and plastic displacements. The norm of inelastic displacement is used to control the fracture behaviour. Meantime, a failure function describing the fracture strength is proposed. Using the internal programming FISH, the cohesive fracture model is programmed into a hybrid distinct element algorithm as encoded in Universal Distinct Element Code (UDEC). The model is verified through uniaxial tension and direct shear tests. The developed model is then applied to model the behaviour of a uniaxial compression test on Gosford sandstone. The modelling results indicate that the proposed cohesive fracture model is capable of simulating combined failure behaviour applicable to rock.