OpenRaiser/Intern-Atlas huggingface dataset:
Symbolic Implementation of Connectors in BIP
Venue: arXiv cs.SE 2009
Year: 2009

BIP is a component framework for constructing systems by superposing three layers of modeling: Behavior, Interaction, and Priority. Behavior is represented by labeled transition systems communicating through ports. Interactions are sets of ports. A synchronization between components is possible through the interactions specified by a set of connectors. When several interactions are possible, priorities allow to restrict the non-determinism by choosing an interaction, which is maximal according to some given strict partial order. The BIP component framework has been implemented in a language and a tool-set. The execution of a BIP program is driven by a dedicated engine, which has access to the set of connectors and priority model of the program. A key performance issue is the computation of the set of possible interactions of the BIP program from a given state. Currently, the choice of the interaction to be executed involves a costly exploration of enumerative representations for connectors. This leads to a considerable overhead in execution times. In this paper, we propose a symbolic implementation of the execution model of BIP, which drastically reduces this overhead. The symbolic implementation is based on computing boolean representation for components, connectors, and priorities with an existing BDD package.
Strong Spatial Mixing for Binary Markov Random Fields
Venue: arXiv cs.IT 2009
Year: 2009

Gibbs distribution of binary Markov random fields on a sparse on average graph is considered in this paper. The strong spatial mixing is proved under the condition that the `external field' is uniformly large or small. Such condition on `external field' is meaningful in physics.
Checkpointing vs. Migration for Post-Petascale Machines
Venue: arXiv cs.DC 2009
Year: 2009

We craft a few scenarios for the execution of sequential and parallel jobs on future generation machines. Checkpointing or migration, which technique to choose?
Variants of Constrained Longest Common Subsequence
Venue: arXiv cs.DS 2009
Year: 2009

In this work, we consider a variant of the classical Longest Common Subsequence problem called Doubly-Constrained Longest Common Subsequence (DC-LCS). Given two strings s1 and s2 over an alphabet A, a set C_s of strings, and a function Co from A to N, the DC-LCS problem consists in finding the longest subsequence s of s1 and s2 such that s is a supersequence of all the strings in Cs and such that the number of occurrences in s of each symbol a in A is upper bounded by Co(a). The DC-LCS problem provides a clear mathematical formulation of a sequence comparison problem in Computational Biology and generalizes two other constrained variants of the LCS problem: the Constrained LCS and the Repetition-Free LCS. We present two results for the DC-LCS problem. First, we illustrate a fixed-parameter algorithm where the parameter is the length of the solution. Secondly, we prove a parameterized hardness result for the Constrained LCS problem when the parameter is the number of the constraint strings and the size of the alphabet A. This hardness result also implies the parameterized hardness of the DC-LCS problem (with the same parameters) and its NP-hardness when the size of the alphabet is constant.
NP-completeness of Certain Sub-classes of the Syndrome Decoding Problem
Venue: arXiv cs.CR 2009
Year: 2009

The problem of Syndrome Decoding was proven to be NP-complete in 1978 and, since then, quite a few cryptographic applications have had their security rely on the (provable) difficulty of solving some instances of it. However, in most cases, the instances to be solved follow some specific constraint: the target weight is a function of the dimension and length of the code. In these cases, is the Syndrome Decoding problem still NP-complete? This is the question that this article intends to answer.
Steinitz Theorems for Orthogonal Polyhedra
Venue: arXiv cs.CG 2009
Year: 2009

We define a simple orthogonal polyhedron to be a three-dimensional polyhedron with the topology of a sphere in which three mutually-perpendicular edges meet at each vertex. By analogy to Steinitz's theorem characterizing the graphs of convex polyhedra, we find graph-theoretic characterizations of three classes of simple orthogonal polyhedra: corner polyhedra, which can be drawn by isometric projection in the plane with only one hidden vertex, xyz polyhedra, in which each axis-parallel line through a vertex contains exactly one other vertex, and arbitrary simple orthogonal polyhedra. In particular, the graphs of xyz polyhedra are exactly the bipartite cubic polyhedral graphs, and every bipartite cubic polyhedral graph with a 4-connected dual graph is the graph of a corner polyhedron. Based on our characterizations we find efficient algorithms for constructing orthogonal polyhedra from their graphs.
Constructing Optimal Authentication Codes with Perfect Multi-fold Secrecy
Venue: arXiv cs.CR 2009
Year: 2009

We establish a construction of optimal authentication codes achieving perfect multi-fold secrecy by means of combinatorial designs. This continues the author's work (ISIT 2009) and answers an open question posed therein. As an application, we present the first infinite class of optimal codes that provide two-fold security against spoofing attacks and at the same time perfect two- fold secrecy.
Conceptual Model for Communication
Venue: arXiv cs.NI 2009
Year: 2009

A variety of idealized models of communication systems exist, and all may have something in common. Starting with Shannons communication model and ending with the OSI model, this paper presents progressively more advanced forms of modeling of communication systems by tying communication models together based on the notion of flow. The basic communication process is divided into different spheres (sources, channels, and destinations), each with its own five interior stages, receiving, processing, creating, releasing, and transferring of information. The flow of information is ontologically distinguished from the flow of physical signals, accordingly, Shannons model, network based OSI models, and TCP IP are redesigned.
Sequential Clustering based Facial Feature Extraction Method for Automatic Creation of Facial Models from Orthogonal Views
Venue: arXiv cs.CV 2009
Year: 2009

Multiview 3D face modeling has attracted increasing attention recently and has become one of the potential avenues in future video systems. We aim to make more reliable and robust automatic feature extraction and natural 3D feature construction from 2D features detected on a pair of frontal and profile view face images. We propose several heuristic algorithms to minimize possible errors introduced by prevalent nonperfect orthogonal condition and noncoherent luminance. In our approach, we first extract the 2D features that are visible to both cameras in both views. Then, we estimate the coordinates of the features in the hidden profile view based on the visible features extracted in the two orthogonal views. Finally, based on the coordinates of the extracted features, we deform a 3D generic model to perform the desired 3D clone modeling. Present study proves the scope of resulted facial models for practical applications like face recognition and facial animation.
A Reliable and Fault Tolerant Routing for Optical WDM Networks
Venue: arXiv cs.NI 2009
Year: 2009

In optical WDM networks, since each lightpath can carry a huge mount of traffic, failures may seriously damage the end user applications. Hence fault tolerance becomes an important issue on these networks. The light path which carries traffic during normal operation is called as primary path. The traffic is rerouted on a backup path in case of a failure. In this paper we propose to design a reliable and fault tolerant routing algorithm for establishing primary and backup paths. In order to establish the primary path, this algorithm uses load balancing in which link cost metrics are estimated based on the current load of the links. In backup path setup, the source calculates the blocking probability through the received feedback from the destination by sending a small fraction of probe packets along the existing paths. It then selects the optimal light path with the lowest blocking probability. Based on the simulation results, we show that the reliable and fault tolerant routing algorithm reduces the blocking probability and latency while increasing the throughput and channel utilization.
A Digital Guitar Tuner
Venue: arXiv cs.SD 2009
Year: 2009

The objective of this paper is to understand the critical parameters that need to be addressed while designing a guitar tuner. The focus of the design lies in developing a suitable algorithm to accurately detect the fundamental frequency of a plucked guitar string from its frequency spectrum. A userfriendly graphical interface is developed using Matlab to allow any user to easily tune his guitar using the developed program.
A novel approach for implementing Steganography with computing power obtained by combining Cuda and Matlab
Venue: arXiv cs.CR 2009
Year: 2009

With the current development of multiprocessor systems, strive for computing data on such processor have also increased exponentially. If the multi core processors are not fully utilized, then even though we have the computing power the speed is not available to the end users for their respective applications. In accordance to this, the users or application designers also have to design newer applications taking care of the computing infrastructure available within. Our approach is to use the CUDA (Compute Unified Device Architecture) as backend and MATLAB as the front end to design an application for implementing steganography. Steganography is the term used for hiding information in the cover object like Image, Audio or Video data. As the computing required for multimedia data is much more than the text information, we have been successful in implementing image Steganography with the help of technology for the next generation.
Shoulder Surfing attack in graphical password authentication
Venue: arXiv cs.CR 2009
Year: 2009

Information and computer security is supported largely by passwords which are the principle part of the authentication process. The most common computer authentication method is to use alphanumerical username and password which has significant drawbacks. To overcome the vulnerabilities of traditional methods, visual or graphical password schemes have been developed as possible alternative solutions to text based scheme. A potential drawback of graphical password schemes is that they are more vulnerable to shoulder surfing than conventional alphanumeric text passwords. When users input their passwords in a public place, they may be at risk of attackers stealing their password. An attacker can capture a password by direct observation or by recording the individuals authentication session. This is referred to as shouldersurfing and is a known risk, of special concern when authenticating in public places. In this paper we will present a survey on graphical password schemes from 2005 till 2009 which are proposed to be resistant against shoulder surfing attacks.
An Efficient Admission Control Algorithm for Load Balancing In Hierarchical Mobile IPv6 Networks
Venue: arXiv cs.NI 2009
Year: 2009

In hierarchical Mobile IPv6 networks, Mobility Anchor Point (MAP) may become a single point of bottleneck as it handles more and more mobile nodes (MNs). A number of schemes have been proposed to achieve load balancing among different MAPs. However, signaling reduction is still imperfect because these schemes also avoid the effect of the number of CNs. Also only the balancing of MN is performed, but not the balancing of the actual traffic load, since CN of each MN may be different. This paper proposes an efficient admission control algorithm along with a replacement mechanism for HMIPv6 networks. The admission control algorithm is based on the number of serving CNs and achieves actual load balancing among MAPs. Moreover, a replacement mechanism is introduced to decrease the new MN blocking probability and the handoff MN dropping probability. By simulation results, we show that, the handoff delay and packet loss are reduced in our scheme, when compared with the standard HMIPv6 based handoff.
Short Term Load Forecasting Using Multi Parameter Regression
Venue: arXiv cs.NE 2009
Year: 2009

Short Term Load forecasting in this paper uses input data dependent on parameters such as load for current hour and previous two hours, temperature for current hour and previous two hours, wind for current hour and previous two hours, cloud for current hour and previous two hours. Forecasting will be of load demand for coming hour based on input parameters at that hour. In this paper we are using multiparameter regression method for forecasting which has error within tolerable range. Algorithms implementing these forecasting techniques have been programmed using MATLAB and applied to the case study. Other methodologies in this area are ANN, Fuzzy and Evolutionary Algorithms for which investigations are under process. Adaptive multiparameter regression for load forecasting, in near future will be possible.
Location Update Accuracy in Human Tracking system using Zigbee modules
Venue: arXiv cs.HC 2009
Year: 2009

A location and tracking system becomes very important to our future world of pervasive computing. An algorithm for accurate location information is being incorporated in the human walking model and in the blind human walking model. We want to implement an accurate location tracking mechanism using Zigbee along with GPS, we have incorporated Markov chain algorithm for establishing accuracy. Normal Human and blind human walking steps were actually taken in the known environment within our campus and the Markov chain algorithm was used for smoothening the stepwise variation in location updates. A comparison module is also implemented to show the difference between normal human and blind human walking step variations. This accuracy is used for designing a blind tracking device so that the device can be used by the blind for finding the path without obstacles. We present a system level approach to localizing and tracking Human and blind users on a basis of different sources of location information [GPS plus Zigbee]. The system can be applied outdoors especially for avoiding accidents, GPS as the source of location data. Performance evaluation shows that the system is accurate and it is a future path finding device with service for the blind.
Abstract Milling with Turn Costs
Venue: arXiv cs.CC 2009
Year: 2009

The Abstract Milling problem is a natural and quite general graph-theoretic model for geometric milling problems. Given a graph, one asks for a walk that covers all its vertices with a minimum number of turns, as specified in the graph model by a 0/1 turncost function fx at each vertex x giving, for each ordered pair of edges (e,f) incident at x, the turn cost at x of a walk that enters the vertex on edge e and departs on edge f. We describe an initial study of the parameterized complexity of the problem. Our main positive result shows that Abstract Milling, parameterized by: number of turns, treewidth and maximum degree, is fixed-parameter tractable, We also show that Abstract Milling parameterized by (only) the number of turns and the pathwidth, is hard for W[1] -- one of the few parameterized intractability results for bounded pathwidth.
Clusters and Maps of Science Journals Based on Bi-connected Graphs in the Journal Citation Reports
Venue: arXiv cs.DL 2009
Year: 2009

The aggregated journal-journal citation matrix derived from the Journal Citation Reports 2001 can be decomposed into a unique subject classification by using the graph-analytical algorithm of bi-connected components. This technique was recently incorporated in software tools for social network analysis. The matrix can be assessed in terms of its decomposability using articulation points which indicate overlap between the components. The articulation points of this set did not exhibit a next-order network of 'general science' journals. However, the clusters differ in size and in terms of the internal density of their relations. A full classification of the journals is provided in an Appendix. The clusters can also be extracted and mapped for the visualization.
Automatic creation of urban velocity fields from aerial video
Venue: arXiv cs.CV 2009
Year: 2009

In this paper, we present a system for modelling vehicle motion in an urban scene from low frame-rate aerial video. In particular, the scene is modelled as a probability distribution over velocities at every pixel in the image. We describe the complete system for acquiring this model. The video is captured from a helicopter and stabilized by warping the images to match an orthorectified image of the area. A pixel classifier is applied to the stabilized images, and the response is segmented to determine car locations and orientations. The results are fed in to a tracking scheme which tracks cars for three frames, creating tracklets. This allows the tracker to use a combination of velocity, direction, appearance, and acceleration cues to keep only tracks likely to be correct. Each tracklet provides a measurement of the car velocity at every point along the tracklet's length, and these are then aggregated to create a histogram of vehicle velocities at every pixel in the image. The results demonstrate that the velocity probability distribution prior can be used to infer a variety of information about road lane directions, speed limits, vehicle speeds and common trajectories, and traffic bottlenecks, as well as providing a means of describing environmental knowledge about traffic rules that can be used in tracking.
Energy Efficient Scheduling via Partial Shutdown
Venue: arXiv cs.DS 2009
Year: 2009

Motivated by issues of saving energy in data centers we define a collection of new problems referred to as "machine activation" problems. The central framework we introduce considers a collection of $m$ machines (unrelated or related) with each machine $i$ having an {\em activation cost} of $a_i$. There is also a collection of $n$ jobs that need to be performed, and $p_{i,j}$ is the processing time of job $j$ on machine $i$. We assume that there is an activation cost budget of $A$ -- we would like to {\em select} a subset $S$ of the machines to activate with total cost $a(S) \le A$ and {\em find} a schedule for the $n$ jobs on the machines in $S$ minimizing the makespan (or any other metric). For the general unrelated machine activation problem, our main results are that if there is a schedule with makespan $T$ and activation cost $A$ then we can obtain a schedule with makespan $\makespanconstant T$ and activation cost $\costconstant A$, for any $ε>0$. We also consider assignment costs for jobs as in the generalized assignment problem, and using our framework, provide algorithms that minimize the machine activation and the assignment cost simultaneously. In addition, we present a greedy algorithm which only works for the basic version and yields a makespan of $2T$ and an activation cost $A (1+\ln n)$. For the uniformly related parallel machine scheduling problem, we develop a polynomial time approximation scheme that outputs a schedule with the property that the activation cost of the subset of machines is at most $A$ and the makespan is at most $(1+ε) T$ for any $ε>0$.
Topological Properties of an Exponential Random Geometric Graph Process
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we consider a one-dimensional random geometric graph process with the inter-nodal gaps evolving according to an exponential AR(1) process, which may serve as a mobile wireless network model. The transition probability matrix and stationary distribution are derived for the Markov chains in terms of network connectivity and the number of components. We characterize an algorithm for the hitting time regarding disconnectivity. In addition, we also study topological properties for static snapshots. We obtain the degree distributions as well as asymptotic precise bounds and strong law of large numbers for connectivity threshold distance and the largest nearest neighbor distance amongst others. Both closed form results and limit theorems are provided.
Detection of Denial of Service Attacks against Domain Name System Using Neural Networks
Venue: arXiv cs.CR 2009
Year: 2009

In this paper we introduce an intrusion detection system for Denial of Service (DoS) attacks against Domain Name System (DNS). Our system architecture consists of two most important parts: a statistical preprocessor and a neural network classifier. The preprocessor extracts required statistical features in a shorttime frame from traffic received by the target name server. We compared three different neural networks for detecting and classifying different types of DoS attacks. The proposed system is evaluated in a simulated network and showed that the best performed neural network is a feed-forward backpropagation with an accuracy of 99%.
Parsing of part-of-speech tagged Assamese Texts
Venue: arXiv cs.CL 2009
Year: 2009

A natural language (or ordinary language) is a language that is spoken, written, or signed by humans for general-purpose communication, as distinguished from formal languages (such as computer-programming languages or the "languages" used in the study of formal logic). The computational activities required for enabling a computer to carry out information processing using natural language is called natural language processing. We have taken Assamese language to check the grammars of the input sentence. Our aim is to produce a technique to check the grammatical structures of the sentences in Assamese text. We have made grammar rules by analyzing the structures of Assamese sentences. Our parsing program finds the grammatical errors, if any, in the Assamese sentence. If there is no error, the program will generate the parse tree for the Assamese sentence
Document Searching System based on Natural Language Query Processing for Vietnam Open Courseware Library
Venue: arXiv cs.IR 2009
Year: 2009

The necessary of buiding the searching system being able to support users expressing their searching by natural language queries is very important and opens the researching direction with many potential. It combines the traditional methods of information retrieval and the researching of Question Answering (QA). In this paper, we introduce a searching system built by us for searching courses on the Vietnam OpenCourseWare Program (VOCW). It can be considered as the first tool to be able to perform the user's Vietnamese questions. The experiment results are rather good when we evaluate this system on the precision
Quantitative Safety: Linking Proof-Based Verification with Model Checking for Probabilistic Systems
Venue: arXiv cs.LO 2009
Year: 2009

This paper presents a novel approach for augmenting proof-based verification with performance-style analysis of the kind employed in state-of-the-art model checking tools for probabilistic systems. Quantitative safety properties usually specified as probabilistic system invariants and modeled in proof-based environments are evaluated using bounded model checking techniques. Our specific contributions include the statement of a theorem that is central to model checking safety properties of proof-based systems, the establishment of a procedure; and its full implementation in a prototype system (YAGA) which readily transforms a probabilistic model specified in a proof-based environment to its equivalent verifiable PRISM model equipped with reward structures. The reward structures capture the exact interpretation of the probabilistic invariants and can reveal succinct information about the model during experimental investigations. Finally, we demonstrate the novelty of the technique on a probabilistic library case study.