OpenRaiser/Intern-Atlas huggingface dataset:
Calculation and analysis of solitary waves and kinks in elastic tubes
Venue: arXiv cs.CE 2013
Year: 2013

The paper is devoted to analysis of different models that describe waves in fluid-filled and gas-filled elastic tubes and development of methods of calculation and numerical analysis of solutions with solitary waves and kinks for these models. Membrane model and plate model are used for tube. Two types of solitary waves are found. One-parametric families are stable and may be used as shock structures. Null-parametric solitary waves are unstable. The process of split of such solitary waves is investigated. It may lead to appearance of solutions with kinks. Kink solutions are null-parametric and stable. General theory of reversible shocks is used for analysis of numerical solutions.
Genericity versus expressivity - an exercise in semantic interoperable research information systems for Web Science
Venue: arXiv cs.DL 2013
Year: 2013

The web does not only enable new forms of science, it also creates new possibilities to study science and new digital scholarship. This paper brings together multiple perspectives: from individual researchers seeking the best options to display their activities and market their skills on the academic job market; to academic institutions, national funding agencies, and countries needing to monitor the science system and account for public money spending. We also address the research interests aimed at better understanding the self-organising and complex nature of the science system through researcher tracing, the identification of the emergence of new fields, and knowledge discovery using large-data mining and non-linear dynamics. In particular this paper draws attention to the need for standardisation and data interoperability in the area of research information as an indispensable pre-condition for any science modelling. We discuss which levels of complexity are needed to provide a globally, interoperable, and expressive data infrastructure for research information. With possible dynamic science model applications in mind, we introduce the need for a "middle-range" level of complexity for data representation and propose a conceptual model for research data based on a core international ontology with national and local extensions.
Long Circuits and Large Euler Subgraphs
Venue: arXiv cs.DS 2013
Year: 2013

An undirected graph is Eulerian if it is connected and all its vertices are of even degree. Similarly, a directed graph is Eulerian, if for each vertex its in-degree is equal to its out-degree. It is well known that Eulerian graphs can be recognized in polynomial time while the problems of finding a maximum Eulerian subgraph or a maximum induced Eulerian subgraph are NP-hard. In this paper, we study the parameterized complexity of the following Euler subgraph problems: - Large Euler Subgraph: For a given graph G and integer parameter k, does G contain an induced Eulerian subgraph with at least k vertices? - Long Circuit: For a given graph G and integer parameter k, does G contain an Eulerian subgraph with at least k edges? Our main algorithmic result is that Large Euler Subgraph is fixed parameter tractable (FPT) on undirected graphs. We find this a bit surprising because the problem of finding an induced Eulerian subgraph with exactly k vertices is known to be W[1]-hard. The complexity of the problem changes drastically on directed graphs. On directed graphs we obtained the following complexity dichotomy: Large Euler Subgraph is NP-hard for every fixed k>3 and is solvable in polynomial time for k<=3. For Long Circuit, we prove that the problem is FPT on directed and undirected graphs.
Fully Automated Shape Analysis Based on Forest Automata
Venue: arXiv cs.LO 2013
Year: 2013

Forest automata (FA) have recently been proposed as a tool for shape analysis of complex heap structures. FA encode sets of tree decompositions of heap graphs in the form of tuples of tree automata. In order to allow for representing complex heap graphs, the notion of FA allowed one to provide user-defined FA (called boxes) that encode repetitive graph patterns of shape graphs to be used as alphabet symbols of other, higher-level FA. In this paper, we propose a novel technique of automatically learning the FA to be used as boxes that avoids the need of providing them manually. Further, we propose a significant improvement of the automata abstraction used in the analysis. The result is an efficient, fully-automated analysis that can handle even as complex data structures as skip lists, with the performance comparable to state-of-the-art fully-automated tools based on separation logic, which, however, specialise in dealing with linked lists only.
Improved Complexity Results on $k$-Coloring $P_t$-Free Graphs
Venue: arXiv cs.CC 2013
Year: 2013

A graph is $H$-free if it does not contain an induced subgraph isomorphic to $H$. We denote by $P_k$ and $C_k$ the path and the cycle on $k$ vertices, respectively. In this paper, we prove that 4-COLORING is NP-complete for $P_7$-free graphs, and that 5-COLORING is NP-complete for $P_6$-free graphs. These two results improve all previous results on $k$-coloring $P_t$-free graphs, and almost complete the classification of complexity of $k$-COLORING $P_t$-free graphs for $k\ge 4$ and $t\ge 1$, leaving as the only missing case 4-COLORING $P_6$-free graphs. We expect that 4-COLORING is polynomial time solvable for $P_6$-free graphs; in support of this, we describe a polynomial time algorithm for 4-COLORING $P_6$-free graphs which are also $P$-free, where $P$ is the graph obtained from $C_4$ by adding a new vertex and making it adjacent to exactly one vertex on the $C_4$.
Multi-Label Classifier Chains for Bird Sound
Venue: arXiv cs.LG 2013
Year: 2013

Bird sound data collected with unattended microphones for automatic surveys, or mobile devices for citizen science, typically contain multiple simultaneously vocalizing birds of different species. However, few works have considered the multi-label structure in birdsong. We propose to use an ensemble of classifier chains combined with a histogram-of-segments representation for multi-label classification of birdsong. The proposed method is compared with binary relevance and three multi-instance multi-label learning (MIML) algorithms from prior work (which focus more on structure in the sound, and less on structure in the label sets). Experiments are conducted on two real-world birdsong datasets, and show that the proposed method usually outperforms binary relevance (using the same features and base-classifier), and is better in some cases and worse in others compared to the MIML algorithms.
Solving the minimum sum coloring problem via binary quadratic programming
Venue: arXiv cs.DS 2013
Year: 2013

In recent years, binary quadratic programming (BQP) has been successively applied to solve several combinatorial optimization problems. We consider in this paper a study of using the BQP model to solve the minimum sum coloring problem (MSCP). For this purpose, we recast the MSCP with a quadratic model which is then solved via a recently proposed Path Relinking (PR) algorithm designed for the general BQP. Based on a set of MSCP benchmark instances, we investigate the performance of this solution approach compared with existing methods.
Dealing with natural language interfaces in a geolocation context
Venue: arXiv cs.CL 2013
Year: 2013

In the geolocation field where high-level programs and low-level devices coexist, it is often difficult to find a friendly user inter- face to configure all the parameters. The challenge addressed in this paper is to propose intuitive and simple, thus natural lan- guage interfaces to interact with low-level devices. Such inter- faces contain natural language processing and fuzzy represen- tations of words that facilitate the elicitation of business-level objectives in our context.
A Competitive Strategy for Distance-Aware Online Shape Allocation
Venue: arXiv cs.DS 2013
Year: 2013

We consider the following online allocation problem: Given a unit square S, and a sequence of numbers n_i between 0 and 1, with partial sum bounded by 1; at each step i, select a region C_i of previously unassigned area n_i in S. The objective is to make these regions compact in a distance-aware sense: minimize the maximum (normalized) average Manhattan distance between points from the same set C_i. Related location problems have received a considerable amount of attention; in particular, the problem of determining the "optimal shape of a city", i.e., allocating a single n_i has been studied. We present an online strategy, based on an analysis of space-filling curves; for continuous shapes, we prove a factor of 1.8092, and 1.7848 for discrete point sets.
The varifold representation of non-oriented shapes for diffeomorphic registration
Venue: arXiv cs.CG 2013
Year: 2013

In this paper, we address the problem of orientation that naturally arises when representing shapes like curves or surfaces as currents. In the field of computational anatomy, the framework of currents has indeed proved very efficient to model a wide variety of shapes. However, in such approaches, orientation of shapes is a fundamental issue that can lead to several drawbacks in treating certain kind of datasets. More specifically, problems occur with structures like acute pikes because of canceling effects of currents or with data that consists in many disconnected pieces like fiber bundles for which currents require a consistent orientation of all pieces. As a promising alternative to currents, varifolds, introduced in the context of geometric measure theory by F. Almgren, allow the representation of any non-oriented manifold (more generally any non-oriented rectifiable set). In particular, we explain how varifolds can encode numerically non-oriented objects both from the discrete and continuous point of view. We show various ways to build a Hilbert space structure on the set of varifolds based on the theory of reproducing kernels. We show that, unlike the currents' setting, these metrics are consistent with shape volume (theorem 4.1) and we derive a formula for the variation of metric with respect to the shape (theorem 4.2). Finally, we propose a generalization to non-oriented shapes of registration algorithms in the context of Large Deformations Metric Mapping (LDDMM), which we detail with a few examples in the last part of the paper.
Evaluating Web Content Quality via Multi-scale Features
Venue: arXiv cs.IR 2013
Year: 2013

Web content quality measurement is crucial to various web content processing applications. This paper will explore multi-scale features which may affect the quality of a host, and develop automatic statistical methods to evaluate the Web content quality. The extracted properties include statistical content features, page and host level link features and TFIDF features. The experiments on ECML/PKDD 2010 Discovery Challenge data set show that the algorithm is effective and feasible for the quality tasks of multiple languages, and the multi-scale features have different identification ability and provide good complement to each other for most tasks.
Counting people from above: Airborne video based crowd analysis
Venue: arXiv cs.CV 2013
Year: 2013

Crowd monitoring and analysis in mass events are highly important technologies to support the security of attending persons. Proposed methods based on terrestrial or airborne image/video data often fail in achieving sufficiently accurate results to guarantee a robust service. We present a novel framework for estimating human count, density and motion from video data based on custom tailored object detection techniques, a regression based density estimate and a total variation based optical flow extraction. From the gathered features we present a detailed accuracy analysis versus ground truth measurements. In addition, all information is projected into world coordinates to enable a direct integration with existing geo-information systems. The resulting human counts demonstrate a mean error of 4% to 9% and thus represent a most efficient measure that can be robustly applied in security critical services.
Sequent Calculi with procedure calls
Venue: arXiv cs.LO 2013
Year: 2013

In this paper, we introduce two focussed sequent calculi, LKp(T) and LK+(T), that are based on Miller-Liang's LKF system for polarised classical logic. The novelty is that those sequent calculi integrate the possibility to call a decision procedure for some background theory T, and the possibility to polarise literals "on the fly" during proof-search. These features are used in our other works to simulate the DPLL(T) procedure as proof-search in the extension of LKp(T) with a cut-rule. In this report we therefore prove cut-elimination in LKp(T). Contrary to what happens in the empty theory, the polarity of literals affects the provability of formulae in presence of a theory T. On the other hand, changing the polarities of connectives does not change the provability of formulae, only the shape of proofs. In order to prove this, we introduce a second sequent calculus, LK+(T) that extends LKp(T) with a relaxed focussing discipline, but we then show an encoding of LK+(T) back into the more restrictive system LK(T). We then prove completeness of LKp(T) (and therefore of LK+(T)) with respect to first-order reasoning modulo the ground propositional lemmas of the background theory T .
Expressibility in the Lambda Calculus with mu
Venue: arXiv cs.PL 2013
Year: 2013

We address a problem connected to the unfolding semantics of functional programming languages: give a useful characterization of those infinite lambda-terms that are lambda_{letrec}-expressible in the sense that they arise as infinite unfoldings of terms in lambda_{letrec}, the lambda-calculus with letrec. We provide two characterizations, using concepts we introduce for infinite lambda-terms: regularity, strong regularity, and binding-capturing chains. It turns out that lambda_{letrec}-expressible infinite lambda-terms form a proper subclass of the regular infinite lambda-terms. In this paper we establish these characterizations only for expressibility in lambda_{mu}, the lambda-calculus with explicit mu-recursion. We show that for all infinite lambda-terms T the following are equivalent: (i): T is lambda_{mu}-expressible; (ii): T is strongly regular; (iii): T is regular, and it only has finite binding-capturing chains. We define regularity and strong regularity for infinite lambda-terms as two different generalizations of regularity for infinite first-order terms: as the existence of only finitely many subterms that are defined as the reducts of two rewrite relations for decomposing lambda-terms. These rewrite relations act on infinite lambda-terms furnished with a marked prefix of abstractions for collecting decomposed lambda-abstractions and keeping the terms closed under decomposition. They differ in how vacuous abstractions in the prefix are removed. This report accompanies the article with the same title for the proceedings of the conference RTA 2013, and mainly differs from that by providing the proof of the characterization of lambda_{mu}-expressibility with binding-capturing chains.
A O(c^k n) 5-Approximation Algorithm for Treewidth
Venue: arXiv cs.DS 2013
Year: 2013

We give an algorithm that for an input n-vertex graph G and integer k>0, in time 2^[O(k)]n either outputs that the treewidth of G is larger than k, or gives a tree decomposition of G of width at most 5k+4. This is the first algorithm providing a constant factor approximation for treewidth which runs in time single-exponential in k and linear in n. Treewidth based computations are subroutines of numerous algorithms. Our algorithm can be used to speed up many such algorithms to work in time which is single-exponential in the treewidth and linear in the input size.
Operational characterization of scattered MCFLs -- Technical Report
Venue: arXiv cs.FL 2013
Year: 2013

We give a Kleene-type operational characterization of Muller context-free languages (MCFLs) of well-ordered and scattered words.
Remote Homology Detection in Proteins Using Graphical Models
Venue: arXiv cs.CE 2013
Year: 2013

Given the amino acid sequence of a protein, researchers often infer its structure and function by finding homologous, or evolutionarily-related, proteins of known structure and function. Since structure is typically more conserved than sequence over long evolutionary distances, recognizing remote protein homologs from their sequence poses a challenge. We first consider all proteins of known three-dimensional structure, and explore how they cluster according to different levels of homology. An automatic computational method reasonably approximates a human-curated hierarchical organization of proteins according to their degree of homology. Next, we return to homology prediction, based only on the one-dimensional amino acid sequence of a protein. Menke, Berger, and Cowen proposed a Markov random field model to predict remote homology for beta-structural proteins, but their formulation was computationally intractable on many beta-strand topologies. We show two different approaches to approximate this random field, both of which make it computationally tractable, for the first time, on all protein folds. One method simplifies the random field itself, while the other retains the full random field, but approximates the solution through stochastic search. Both methods achieve improvements over the state of the art in remote homology detection for beta-structural protein folds.
Optimizing Cost, Delay, Packet Loss and Network Load in AODV Routing Protocol
Venue: arXiv cs.NI 2013
Year: 2013

AODV is Ad-hoc On-Demand Distance Vector.A mobile ad-hoc network is a self-configuring network of mobile devices connected by wireless. MANET does not have any fixed infrastructure. The device in a MANET is free to move in any direction and will form the connection as per the requirement of the network. Due to changing topology maintenance of factors like Packet loss, End to End Delay, Number of hops, delivery ratio and controlling the network load is of great challenge. This paper mainly concentrates on reducing the factors such as cost, End-to-End Delay, Network Load and Packet loss in AODV routing protocol. The NS-2 is used for the simulation purpose.
Route-Based Detection of Conflicting ATC Clearances on Airports
Venue: arXiv cs.SY 2013
Year: 2013

Runway incursions are among the most serious safety concerns in air traffic control. Traditional A-SMGCS level 2 safety systems detect runway incursions with the help of surveillance information only. In the context of SESAR, complementary safety systems are emerging that also use other information in addition to surveillance, and that aim at warning about potential runway incursions at earlier points in time. One such system is "conflicting ATC clearances", which processes the clearances entered by the air traffic controller into an electronic flight strips system and cross-checks them for potentially dangerous inconsistencies. The cross-checking logic may be implemented directly based on the clearances and on surveillance data, but this is cumbersome. We present an approach that instead uses ground routes as an intermediate layer, thereby simplifying the core safety logic.
Logging safely in public spaces using color PINs
Venue: arXiv cs.HC 2013
Year: 2013

Nowadays, we are increasingly logging on many different Internet sites to access private data like emails or photos remotely stored in the clouds. This makes us all the more concerned with digital identity theft and passwords being stolen either by key loggers or shoulder-surfing attacks. Quite surprisingly, the current bottleneck of computer security when logging for authentication is the User Interface (UI): How can we enter safely secret passwords when concealed spy cameras or key loggers may be recording the login session? Logging safely requires to design a secure Human Computer Interface (HCI) robust to those attacks. We describe a novel method and system based on entering secret ID passwords by means of associative secret UI passwords that provides zero-knowledge to observers. We demonstrate the principles using a color Personal Identification Numbers (PINs) login system and describes its various extensions.
Unifying the Linear Time-Branching Time Spectrum of Process Semantics
Venue: arXiv cs.LO 2013
Year: 2013

Van Glabbeek's linear time-branching time spectrum is one of the most relevant work on comparative study on process semantics, in which semantics are partially ordered by their discrimination power. In this paper we bring forward a refinement of this classification and show how the process semantics can be dealt with in a uniform way: based on the very natural concept of constrained simulation we show how we can classify the spectrum in layers; for the families lying in the same layer we show how to obtain in a generic way equational, observational, logical and operational characterizations; relations among layers are also very natural and differences just stem from the constraint imposed on the simulations that rule the layers. Our methodology also shows how to achieve a uniform treatment of semantic preorders and equivalences.
Third Party Privacy Preserving Protocol for Perturbation Based Classification of Vertically Fragmented Data Bases
Venue: arXiv cs.CR 2013
Year: 2013

Privacy is become major issue in distributed data mining. In the literature we can found many proposals of privacy preserving which can be divided into two major categories that is trusted third party and multiparty based privacy protocols. In case of trusted third party models the conventional asymmetric cryptographic based techniques will be used and in case of multi party based protocols data perturbed to make sure no other party to understand original data. In order to enhance security features by combining strengths of both models in this paper, we propose to use data perturbed techniques in third party privacy preserving protocol to conduct the classification on vertically fragmented data bases. Specially, we present a method to build Naive Bayes classification from the disguised and decentralized databases. In order to perform classification we propose third party protocol for secure computations. We conduct experiments to compare the accuracy of our Naive Bayes with the one built from the original undisguised data. Our results show that although the data are disguised and decentralized, our method can still achieve fairly high accuracy.
Robust error correction for real-valued signals via message-passing decoding and spatial coupling
Venue: arXiv cs.IT 2013
Year: 2013

We revisit the error correction scheme of real-valued signals when the codeword is corrupted by gross errors on a fraction of entries and a small noise on all the entries. Combining the recent developments of approximate message passing and the spatially-coupled measurement matrix in compressed sensing we show that the error correction and its robustness towards noise can be enhanced considerably. We discuss the performance in the large signal limit using previous results on state evolution, as well as for finite size signals through numerical simulations. Even for relatively small sizes, the approach proposed here outperforms convex-relaxation-based decoders.
An implementation of the relational k-means algorithm
Venue: arXiv cs.LG 2013
Year: 2013

A C# implementation of a generalized k-means variant called relational k-means is described here. Relational k-means is a generalization of the well-known k-means clustering method which works for non-Euclidean scenarios as well. The input is an arbitrary distance matrix, as opposed to the traditional k-means method, where the clustered objects need to be identified with vectors.