OpenRaiser/Intern-Atlas huggingface dataset:
Symmetric Groups and Quotient Complexity of Boolean Operations
Venue: arXiv cs.FL 2013
Year: 2013

The quotient complexity of a regular language L is the number of left quotients of L, which is the same as the state complexity of L. Suppose that L and L' are binary regular languages with quotient complexities m and n, and that the transition semigroups of the minimal deterministic automata accepting L and L' are the symmetric groups S_m and S_n of degrees m and n, respectively. Denote by o any binary boolean operation that is not a constant and not a function of one argument only. For m,n >= 2 with (m,n) not in {(2,2),(3,4),(4,3),(4,4)} we prove that the quotient complexity of LoL' is mn if and only either (a) m is not equal to n or (b) m=n and the bases (ordered pairs of generators) of S_m and S_n are not conjugate. For (m,n)\in {(2,2),(3,4),(4,3),(4,4)} we give examples to show that this need not hold. In proving these results we generalize the notion of uniform minimality to direct products of automata. We also establish a non-trivial connection between complexity of boolean operations and group theory.
TSP Tours in Cubic Graphs: Beyond 4/3
Venue: arXiv cs.DS 2013
Year: 2013

After a sequence of improvements Boyd, Sitters, van der Ster, and Stougie proved that any 2-connected graph whose n vertices have degree 3, i.e., a cubic 2-connected graph, has a Hamiltonian tour of length at most (4/3)n, establishing in particular that the integrality gap of the subtour LP is at most 4/3 for cubic 2-connected graphs and matching the conjectured value of the famous 4/3 conjecture. In this paper we improve upon this result by designing an algorithm that finds a tour of length (4/3 - 1/61236)n, implying that cubic 2-connected graphs are among the few interesting classes of graphs for which the integrality gap of the subtour LP is strictly less than 4/3. With the previous result, and by considering an even smaller epsilon, we show that the integrality gap of the TSP relaxation is at most 4/3 - epsilon, even if the graph is not 2-connected (i.e. for cubic connected graphs), implying that the approximability threshold of the TSP in cubic graphs is strictly below 4/3. Finally, using similar techniques we show, as an additional result, that every Barnette graph admits a tour of length at most (4/3 - 1/18)n.
Named entity recognition using conditional random fields with non-local relational constraints
Venue: arXiv cs.CL 2013
Year: 2013

We begin by introducing the Computer Science branch of Natural Language Processing, then narrowing the attention on its subbranch of Information Extraction and particularly on Named Entity Recognition, discussing briefly its main methodological approaches. It follows an introduction to state-of-the-art Conditional Random Fields under the form of linear chains. Subsequently, the idea of constrained inference as a way to model long-distance relationships in a text is presented, based on an Integer Linear Programming representation of the problem. Adding such relationships to the problem as automatically inferred logical formulas, translatable into linear conditions, we propose to solve the resulting more complex problem with the aid of Lagrangian relaxation, of which some technical details are explained. Lastly, we give some experimental results.
A State Of the Art Report on Research in Multiple RGB-D sensor Setups
Venue: arXiv cs.CV 2013
Year: 2013

That the Microsoft Kinect, an RGB-D sensor, transformed the gaming and end consumer sector has been anticipated by the developers. That it also impacted in rigorous computer vision research has probably been a surprise to the whole community. Shortly before the commercial deployment of its successor, Kinect One, the research literature fills with resumees and state-of-the art papers to summarize the development over the past 3 years. This particular report describes significant research projects which have built on sensoring setups that include two or more RGB-D sensors in one scene.
Finding Dominators via Disjoint Set Union
Venue: arXiv cs.DS 2013
Year: 2013

The problem of finding dominators in a directed graph has many important applications, notably in global optimization of computer code. Although linear and near-linear-time algorithms exist, they use sophisticated data structures. We develop an algorithm for finding dominators that uses only a "static tree" disjoint set data structure in addition to simple lists and maps. The algorithm runs in near-linear or linear time, depending on the implementation of the disjoint set data structure. We give several versions of the algorithm, including one that computes loop nesting information (needed in many kinds of global code optimization) and that can be made self-certifying, so that the correctness of the computed dominators is very easy to verify.
BloSEn: Blog Search Engine Based On Post Concept Clustering
Venue: arXiv cs.IR 2013
Year: 2013

This paper focuses on building a blog search engine which doesn't focus only on keyword search but includes extended search capabilities. It also incorporates the blog-post concept clustering which is based on the category extracted from the blog post semantic content analysis. The proposed approach is titled as "BloSen (Blog Search Engine)". It involves in extracting the posts from blogs and parsing them to extract the blog elements and store them as fields in a document format. Inverted index is being built on the fields of the documents. Search is induced on the index and requested query is processed based on the documents so far made from blog posts. It currently focuses on Blogger and Wordpress hosted blogs since both these hosting services are the most popular ones in the blogosphere. The proposed BloSen model is experimented with a prototype implementation and the results of the experiments with the user's relevance cumulative metric value of 95.44% confirms the efficiency of the proposed model.
C2MS: Dynamic Monitoring and Management of Cloud Infrastructures
Venue: arXiv cs.DC 2013
Year: 2013

Server clustering is a common design principle employed by many organisations who require high availability, scalability and easier management of their infrastructure. Servers are typically clustered according to the service they provide whether it be the application(s) installed, the role of the server or server accessibility for example. In order to optimize performance, manage load and maintain availability, servers may migrate from one cluster group to another making it difficult for server monitoring tools to continuously monitor these dynamically changing groups. Server monitoring tools are usually statically configured and with any change of group membership requires manual reconfiguration; an unreasonable task to undertake on large-scale cloud infrastructures. In this paper we present the Cloudlet Control and Management System (C2MS); a system for monitoring and controlling dynamic groups of physical or virtual servers within cloud infrastructures. The C2MS extends Ganglia - an open source scalable system performance monitoring tool - by allowing system administrators to define, monitor and modify server groups without the need for server reconfiguration. In turn administrators can easily monitor group and individual server metrics on large-scale dynamic cloud infrastructures where roles of servers may change frequently. Furthermore, we complement group monitoring with a control element allowing administrator-specified actions to be performed over servers within service groups as well as introduce further customized monitoring metrics. This paper outlines the design, implementation and evaluation of the C2MS.
New Approach for Prediction Pre-cancer via Detecting Mutated in Tumor Protein P53
Venue: arXiv cs.CE 2013
Year: 2013

Tumor protein P53 is believed to be involved in over half of human cancers cases, the prediction of malignancies plays essential roles not only in advance detection for cancer, but also in discovering effective prevention and treatment of cancer, till now there isn't approach be able in prediction the mutated in tumor protein P53 which is caused high ratio of human cancers like breast, Blood, skin, liver, lung, bladder etc. This research proposed a new approach for prediction pre-cancer via detection malignant mutations in tumor protein P53 using bioinformatics tools like FASTA, BLAST, CLUSTALW and TP53 databases worldwide. Implement and apply this new approach of prediction pre-cancer through mutations at tumor protein P53 shows an effective result when used more specific parameters/features to extract the prediction result that means when the user increase the number of filters of the results which obtained from the database gives more specific diagnosis and classify, addition that the detecting pre-cancer via prediction mutated tumor protein P53 will reduces a person's cancers in the future by avoiding exposure to toxins, radiation or monitoring themselves at older ages by change their food, environment, even the pace of living. Also that new approach of prediction pre-cancer will help if there is any treatment can give for that person to therapy the mutated tumor protein P53. Index Terms (Normal Homology TP53 gene, Tumor Protein P53, Oncogene Labs, GC and AT content, FASTA, BLAST, ClustalW)
A Mathematical Model, Implementation and Study of a Swarm System
Venue: arXiv cs.RO 2013
Year: 2013

The work reported in this paper is motivated towards the development of a mathematical model for swarm systems based on macroscopic primitives. A pattern formation and transformation model is proposed. The pattern transformation model comprises two general methods for pattern transformation, namely a macroscopic transformation and mathematical transformation method. The problem of transformation is formally expressed and four special cases of transformation are considered. Simulations to confirm the feasibility of the proposed models and transformation methods are presented. Comparison between the two transformation methods is also reported.
Modelling Complexity for Policy: Opportunities and Challenges
Venue: arXiv cs.MA 2013
Year: 2013

This chapter reviews the purpose and use of models from the field of complex systems and, in particular, the implications of trying to use models to understand or make decisions within complex situations, such as policy makers usually face. A discussion of the different dimensions one can formalise situations, the different purposes for models and the different kinds of relationship they can have with the policy making process, is followed by an examination of the compromises forced by the complexity of the target issues. Several modelling approaches from complexity science are briefly described, with notes as to their abilities and limitations. These approaches include system dynamics, network theory, information theory, cellular automata, and agent-based modelling. Some examples of policy models are presented and discussed in the context of the previous analysis. Finally we conclude by outlining some of the major pitfalls facing those wishing to use such models for policy evaluation.
Robust Adaptive Control for Circadian Dynamics: Poincare Approach to Backstepping Method
Venue: arXiv cs.SY 2013
Year: 2013

A mathematical model of the circadian dynamics in the form of Van der Pol equation with an external force as a control is investigated. The combination of backstepping method and differential-topological techniques based on the Poincare's ideas is used. The robust model identification adaptive control for a specific adaptation law is designed.
Socially-Optimal Design of Service Exchange Platforms with Imperfect Monitoring
Venue: arXiv cs.GT 2013
Year: 2013

In service exchange platforms, anonymous users exchange services with each other: clients request services and are matched to servers who provide services. Because providing good-quality services requires effort, in any single interaction a server will have no incentive to exert effort and will shirk. We show that if current servers will later become clients and want good-quality services, shirking can be eliminated by rating protocols, which maintain ratings for each user, prescribe behavior in each client-server interaction, and update ratings based on whether observed/reported behavior conforms with prescribed behavior. The rating protocols proposed are the first to achieve social optimum even when observation/reporting is imperfect (quality is incorrectly assessed/reported or reports are lost). The proposed protocols are remarkably simple, requiring only binary ratings and three possible prescribed behaviors. Key to the efficacy of the proposed protocols is that they are nonstationary, and tailor prescriptions to both current and past rating distributions.
Quality of Service Games for Spectrum Sharing
Venue: arXiv cs.NI 2013
Year: 2013

Today's wireless networks are increasingly crowded with an explosion of wireless users, who have greater and more diverse quality of service (QoS) demands than ever before. However, the amount of spectrum that can be used to satisfy these demands remains finite. This leads to a great challenge for wireless users to effectively share the spectrum to achieve their QoS requirements. This paper presents a game theoretic model for spectrum sharing, where users seek to satisfy their QoS demands in a distributed fashion. Our spectrum sharing model is quite general, because we allow different wireless channels to provide different QoS, depending upon their channel conditions and how many users are trying to access them. Also, users can be highly heterogeneous, with different QoS demands, depending upon their activities, hardware capabilities, and technology choices. Under such a general setting, we show that it is NP hard to find a spectrum allocation which satisfies the maximum number of users' QoS requirements in a centralized fashion. We also show that allowing users to self-organize through distributed channel selections is a viable alternative to the centralized optimization, because better response updating is guaranteed to reach a pure Nash equilibria in polynomial time. By bounding the price of anarchy, we demonstrate that the worst case pure Nash equilibrium can be close to optimal, when users and channels are not very heterogenous. We also extend our model by considering the frequency spatial reuse, and consider the user interactions as a game upon a graph where players only contend with their neighbors. We prove that better response updating is still guaranteed to reach a pure Nash equilibrium in this more general spatial QoS satisfaction game.
Handy Annotations within Oracle 10g
Venue: arXiv cs.DB 2013
Year: 2013

This paper describes practical observations during the Database system Lab. Oracle 10g DBMS is used in the data base system lab and performed SQL queries based many concepts like Data Definition Language Commands (DDL), Data Modification Language Commands ((DML), Views, Integrity Constraints, Aggregate functions, Joins and Abstract type . While performing practical during the lab session, many problems occurred, in order to solve them many text books and websites referred but could not obtain expected help from them. Even though by spending much time in the database labs with Oracle 10g, tried in numerous ways, as a final point expected output is achieved. This paper describes annotations which were experimentally proved in the Database lab.
Improved Decoding Algorithms for Reed-Solomon Codes
Venue: arXiv cs.IT 2013
Year: 2013

In coding theory, Reed-Solomon codes are one of the most well-known and widely used classes of error-correcting codes. In this thesis we study and compare two major strategies known for their decoding procedure, the Peterson-Gorenstein-Zierler (PGZ) and the Berlekamp-Massey (BM) decoder, in order to improve existing decoding algorithms and propose faster new ones. In particular we study a modified version of the PGZ decoder, which we will call the fast Peterson-Gorenstein-Zierler (fPGZ) decoding algorithm. This improvement was presented in 1997 by exploiting the Hankel structure of the syndrome matrix. In this thesis we show that the fPGZ decoding algorithm can be seen as a particular case of the BM one. Indeed we prove that the intermediate outcomes obtained in the implementation of fPGZ are a subset of those of the BM decoding algorithm. In this way, we also uncover the existing relationship between the leading principal minors of syndrome matrix and the discrepancies computed by the BM algorithm. Finally, thanks to the study done on the structure of the syndrome matrix and its leading principal minors, we improve the error value computation in both the decoding strategies studied (specifically we prove new error value formulas for the fPGZ and the BM decoding algorithm) and moreover we state a new iterative formulation of the PGZ decoder well suited to a parallel implementation on integrated microchips. Thus using techniques of linear algebra we obtain a parallel decoding algorithm for Reed-Solomon codes with an O(e) computational time complexity, where e is the number of errors which occurred, although a fairly large number of elementary circuit elements is needed.
Treating clitics with minimalist grammars
Venue: arXiv cs.CL 2013
Year: 2013

We propose an extension of Stabler's version of clitics treatment for a wider coverage of the French language. For this, we present the lexical entries needed in the lexicon. Then, we show the recognition of complex syntactic phenomena as (left and right) dislo- cation, clitic climbing over modal and extraction from determiner phrase. The aim of this presentation is the syntax-semantic interface for clitics analyses in which we will stress on clitic climbing over verb and raising verb.
Consensus and Coherence in Fractal Networks
Venue: arXiv cs.SY 2013
Year: 2013

We consider first and second order consensus algorithms in networks with stochastic disturbances. We quantify the deviation from consensus using the notion of network coherence, which can be expressed as an $H_2$ norm of the stochastic system. We use the setting of fractal networks to investigate the question of whether a purely topological measure, such as the fractal dimension, can capture the asymptotics of coherence in the large system size limit. Our analysis for first-order systems is facilitated by connections between first-order stochastic consensus and the global mean first passage time of random walks. We then show how to apply similar techniques to analyze second-order stochastic consensus systems. Our analysis reveals that two networks with the same fractal dimension can exhibit different asymptotic scalings for network coherence. Thus, this topological characterization of the network does not uniquely determine coherence behavior. The question of whether the performance of stochastic consensus algorithms in large networks can be captured by purely topological measures, such as the spatial dimension, remains open.
Localized Iterative Methods for Interpolation in Graph Structured Data
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, we present two localized graph filtering based methods for interpolating graph signals defined on the vertices of arbitrary graphs from only a partial set of samples. The first method is an extension of previous work on reconstructing bandlimited graph signals from partially observed samples. The iterative graph filtering approach very closely approximates the solution proposed in the that work, while being computationally more efficient. As an alternative, we propose a regularization based framework in which we define the cost of reconstruction to be a combination of smoothness of the graph signal and the reconstruction error with respect to the known samples, and find solutions that minimize this cost. We provide both a closed form solution and a computationally efficient iterative solution of the optimization problem. The experimental results on the recommendation system datasets demonstrate effectiveness of the proposed methods.
Case Adaptation with Qualitative Algebras
Venue: arXiv cs.AI 2013
Year: 2013

This paper proposes an approach for the adaptation of spatial or temporal cases in a case-based reasoning system. Qualitative algebras are used as spatial and temporal knowledge representation languages. The intuition behind this adaptation approach is to apply a substitution and then repair potential inconsistencies, thanks to belief revision on qualitative algebras. A temporal example from the cooking domain is given. (The paper on which this extended abstract is based was the recipient of the best paper award of the 2012 International Conference on Case-Based Reasoning.)
Distributed firewalls and IDS interoperability checking based on a formal approach
Venue: arXiv cs.NI 2013
Year: 2013

To supervise and guarantee a network security, the administrator uses different security components, such as firewalls, IDS and IPS. For a perfect interoperability between these components, they must be configured properly to avoid misconfiguration between them. Nevertheless, the existence of a set of anomalies between filtering rules and alerting rules, particularly in distributed multi-component architectures is very likely to degrade the network security. The main objective of this paper is to check if a set of security components are interoperable. A case study using a firewall and an IDS as examples will illustrate the usefulness of our approach.
A quantum lower bound for distinguishing random functions from random permutations
Venue: arXiv cs.CC 2013
Year: 2013

The problem of distinguishing between a random function and a random permutation on a domain of size $N$ is important in theoretical cryptography, where the security of many primitives depend on the problem's hardness. We study the quantum query complexity of this problem, and show that any quantum algorithm that solves this problem with bounded error must make $Ω(N^{1/5}/\log N)$ queries to the input function. Our lower bound proof uses a combination of the Collision Problem lower bound and Ambainis's adversary theorem.
Value-chain oriented identification of indicators to establish a comprehensive process improvement framework
Venue: arXiv cs.OH 2013
Year: 2013

The process development and optimization potential needs to be driven by the individial coporate value chain. The identification of this specific value chain and the related indicators is essential to limit the scope of any analysis and optimization to the core business The process framework consisting of clearly defined value chain, the related processes and the corresponding indicators is a pre-requisite for a meaningful and efficient process analysis and continuous process optimization.
Exact Algorithm for Graph Homomorphism and Locally Injective Graph Homomorphism
Venue: arXiv cs.DM 2013
Year: 2013

For graphs $G$ and $H$, a homomorphism from $G$ to $H$ is a function $φ\colon V(G) \to V(H)$, which maps vertices adjacent in $G$ to adjacent vertices of $H$. A homomorphism is locally injective if no two vertices with a common neighbor are mapped to a single vertex in $H$. Many cases of graph homomorphism and locally injective graph homomorphism are NP-complete, so there is little hope to design polynomial-time algorithms for them. In this paper we present an algorithm for graph homomorphism and locally injective homomorphism working in time $\mathcal{O}^*((b + 2)^{|V(G)|})$, where $b$ is the bandwidth of the complement of $H$.
An MDS code associated to an elliptic curve
Venue: arXiv cs.IT 2013
Year: 2013

We will construct an MDS(= the most distance separable) code $C$ which admits a decomposition such that every factor is still MDS. An effective way of decoding will be also discussed.