OpenRaiser/Intern-Atlas huggingface dataset:
A Cost- Effective Design of Reversible Programmable Logic Array
Venue: arXiv cs.OH 2012
Year: 2012

In the recent era, Reversible computing is a growing field having applications in nanotechnology, optical information processing, quantum networks etc. In this paper, the authors show the design of a cost effective reversible programmable logic array using VHDL. It is simulated on xilinx ISE 8.2i and results are shown. The proposed reversible Programming logic array called RPLA is designed by MUX gate [10] & Feynman gate for 3- inputs, which is able to perform any reversible 3- input logic function or Boolean function. Furthermore the quantized analysis with camparitive finding is shown for the realized RPLA against the existing one. The result shows improvement in the quantum cost and total logical caculation in proposed RPLA.
The Design of GP 2
Venue: arXiv cs.PL 2012
Year: 2012

This papers defines the syntax and semantics of GP 2, a revised version of the graph programming language GP. New concepts are illustrated and explained with example programs. Changes to the first version of GP include an improved type system for labels, a built-in marking mechanism for nodes and edges, a more powerful edge predicate for conditional rule schemata, and functions returning the indegree and outdegree of matched nodes. Moreover, the semantics of the branching and loop statement have been simplified to allow their efficient implementation.
Efficient programs of NPC problems should be length upper-bounded, and a thought experiment to search for them by machine enumeration
Venue: arXiv cs.CC 2012
Year: 2012

This paper proposes a thought experiment to search for efficient bounded algorithms of NPC problems by machine enumeration. The key contributions are: -- On Universal Turing Machines, a program's time complexity should be characterized as: execution time(n) = loading time(n) + running time(n). -- Introduces the concept of bounded algorithms; proposes a comparison based criterion to decide if a bounded algorithm is inefficient; and establishes the length upper bound of efficient bounded programs. -- Introduces the growth rate characteristic function to evaluate program complexity, which is more easily machine checkable based on observations. -- Raises the theoretical question: if there exists any bounded algorithm with polynomial execution time for NPC problems.
Stability Analysis of Path-vector Routing
Venue: arXiv cs.NI 2012
Year: 2012

Most studies on path-vector routing stability have been conducted empirically by means of ad-hoc analysis of BGP data traces. None of them consider prior specification of an analytic method including the use of stability measurement metrics for the systematic analysis of BGP traces and associated meta-processing for determining the local state of the routing system. In this paper, we define a set of metrics that characterize the local stability properties of path-vector routing such as BGP (Border Gateway Protocol). By means of these stability metrics, we propose a method to analyze the effects of BGP policy- and protocol-induced instability on local routers.
Taxonomy and synthesis of Web services querying languages
Venue: arXiv cs.DB 2012
Year: 2012

Most works on Web services has focused on discovery, composition and selection processes of these kinds of services. Other few works were interested in how to represent Web services search queries. However, these queries cannot be processed by ensuring a high level of performance without being adequately represented first. To this end, different query languages were designed. Even so, in the absence of a standard, these languages are quite various. Their diversity makes it difficult choosing the most suitable language. In fact, this language should be able to cover all types of preferences or requirements of clients such as their functional, nonfunctional,temporal or even specific constraints as is the case of geographical or spatial constraints and meet their needs and preferences helping to provide them the best answer. It must also be mutually simple and imposes no restrictions or at least not too many constraints in terms of prior knowledge to use and also provide a formal or semi-formal queries presentation to support their automatic post-processing. A comparative study is eventually established to allow to reveal the advantages and limitations of various existing languages in this context. It is a synthesis of this category of languages discussing their performance level and their capability to respond to various needs related to the Web services research and discovery case. The criterions identified at this stage may, in our opinion, constitute then the main pre-requisite that a language should satisfy to be called perfect or to be a future standard.
ML Decoding Complexity Reduction in STBCs Using Time-Orthogonal Pulse Shaping
Venue: arXiv cs.IT 2012
Year: 2012

Motivated by the recent developments in the Space Shift Keying (SSK) and Spatial Modulation (SM) systems which employ Time-Orthogonal Pulse Shaping (TOPS) filters to achieve transmit diversity gains, we propose TOPS for Space-Time Block Codes (STBC). We show that any STBC whose set of weight matrices partitions into P subsets under the equivalence relation termed as Common Support Relation can be made P -group decodable by properly employing TOPS waveforms across space and time. Furthermore, by considering some of the well known STBCs in the literature we show that the order of their Maximum Likelihood decoding complexity can be greatly reduced by the application of TOPS.
Hybrid FPMS: A New Fairness Protocol Management Scheme for Community Wireless Mesh Networks
Venue: arXiv cs.NI 2012
Year: 2012

Node cooperation during packet forwarding operations is critically important for fair resource utilization in Community Wireless Mesh Networks (CoWMNs). In a CoWMN, node cooperation is achieved by using fairness protocols specifically designed to detect and isolate malicious nodes, discourage unfair behavior, and encourage node participation in forwarding packets. In general, these protocols can be split into two groups: Incentive-based ones, which are managed centrally, and use credit allocation schemes. In contrast, reputation-based protocols that are decentralized, and rely on information exchange among neighboring nodes. Centrally managed protocols inevitably suffer from scalability problems. The decentralized, reputation-based protocols lacks in detection capability, suffer from false detections and error propagation compared to the centralized, incentive-based protocols. In this study, we present a new fairness protocol management scheme, called Hybrid FPMS that captures the superior detection capability of incentive-based fairness protocols without the scalability problems inherently expected from a centralized management scheme as a network's size and density grows. Simulation results show that Hybrid FPMS is more efficient than the current centralized approach and significantly reduces the network delays and overhead.
Chain Rotations: a New Look at Tree Distance
Venue: arXiv cs.DS 2012
Year: 2012

As well known the rotation distance D(S,T) between two binary trees S, T of n vertices is the minimum number of rotations of pairs of vertices to transform S into T. We introduce the new operation of chain rotation on a tree, involving two chains of vertices, that requires changing exactly three pointers in the data structure as for a standard rotation, and define the corresponding chain distance C(S,T). As for D(S,T), no polynomial time algorithm to compute C(S,T) is known. We prove a constructive upper bound and an analytical lower bound on C(S,T) based on the number of maximal chains in the two trees. In terms of n we prove the general upper bound C(S,T)<= n-1 and we show that there are pairs of trees for which this bound is tight. No similar result is known for D(S,T) where the best upper and lower bounds are 2n-6 and 5n/3-4 respectively.
Optimizing I/O for Big Array Analytics
Venue: arXiv cs.DB 2012
Year: 2012

Big array analytics is becoming indispensable in answering important scientific and business questions. Most analysis tasks consist of multiple steps, each making one or multiple passes over the arrays to be analyzed and generating intermediate results. In the big data setting, I/O optimization is a key to efficient analytics. In this paper, we develop a framework and techniques for capturing a broad range of analysis tasks expressible in nested-loop forms, representing them in a declarative way, and optimizing their I/O by identifying sharing opportunities. Experiment results show that our optimizer is capable of finding execution plans that exploit nontrivial I/O sharing opportunities with significant savings.
Multi-model-based Access Control in Construction Projects
Venue: arXiv cs.MA 2012
Year: 2012

During the execution of large scale construction projects performed by Virtual Organizations (VO), relatively complex technical models have to be exchanged between the VO members. For linking the trade and transfer of these models, a so-called multi-model container format was developed. Considering the different skills and tasks of the involved partners, it is not necessary for them to know all the models in every technical detailing. Furthermore, the model size can lead to a delay in communication. In this paper an approach is presented for defining model cut-outs according to the current project context. Dynamic dependencies to the project context as well as static dependencies on the organizational structure are mapped in a context-sensitive rule. As a result, an approach for dynamic filtering of multi-models is obtained which ensures, together with a filtering service, that the involved VO members get a simplified view of complex multi-models as well as sufficient permissions depending on their tasks.
Towards a Formal Model of Privacy-Sensitive Dynamic Coalitions
Venue: arXiv cs.MA 2012
Year: 2012

The concept of dynamic coalitions (also virtual organizations) describes the temporary interconnection of autonomous agents, who share information or resources in order to achieve a common goal. Through modern technologies these coalitions may form across company, organization and system borders. Therefor questions of access control and security are of vital significance for the architectures supporting these coalitions. In this paper, we present our first steps to reach a formal framework for modeling and verifying the design of privacy-sensitive dynamic coalition infrastructures and their processes. In order to do so we extend existing dynamic coalition modeling approaches with an access-control-concept, which manages access to information through policies. Furthermore we regard the processes underlying these coalitions and present first works in formalizing these processes. As a result of the present paper we illustrate the usefulness of the Abstract State Machine (ASM) method for this task. We demonstrate a formal treatment of privacy-sensitive dynamic coalitions by two example ASMs which model certain access control situations. A logical consideration of these ASMs can lead to a better understanding and a verification of the ASMs according to the aspired specification.
Mechanism Design for Base Station Association and Resource Allocation in Downlink OFDMA Network
Venue: arXiv cs.IT 2012
Year: 2012

We consider a resource management problem in a multi-cell downlink OFDMA network, whereby the goal is to find the optimal per base station resource allocation and user-base station assignment. The users are assumed to be strategic/selfish who have private information on downlink channel states and noise levels. To induce truthfulness among the users as well as to enhance the spectrum efficiency, the resource management strategy needs to be both incentive compatible and efficient. However, due to the mixed (discrete and continuous) nature of resource management in this context, the implementation of any incentive compatible mechanism that maximizes the system throughput is NP-hard. We consider the dominant strategy implementation of an approximately optimal resource management scheme via a computationally tractable mechanism. The proposed mechanism is decentralized and dynamic. More importantly, it ensures the truthfulness of the users and it implements a resource allocation solution that yields at least 1/2 of the optimal throughput. Simulations are provided to illustrate the effectiveness of the performance of the proposed mechanism.
Combining Deduction Modulo and Logics of Fixed-Point Definitions
Venue: arXiv cs.LO 2012
Year: 2012

Inductive and coinductive specifications are widely used in formalizing computational systems. Such specifications have a natural rendition in logics that support fixed-point definitions. Another useful formalization device is that of recursive specifications. These specifications are not directly complemented by fixed-point reasoning techniques and, correspondingly, do not have to satisfy strong monotonicity restrictions. We show how to incorporate a rewriting capability into logics of fixed-point definitions towards additionally supporting recursive specifications. In particular, we describe a natural deduction calculus that adds a form of "closed-world" equality - a key ingredient to supporting fixed-point definitions - to deduction modulo, a framework for extending a logic with a rewriting layer operating on formulas. We show that our calculus enjoys strong normalizability when the rewrite system satisfies general properties and we demonstrate its usefulness in specifying and reasoning about syntax-based descriptions. The integration of closed-world equality into deduction modulo leads us to reconfigure the elimination principle for this form of equality in a way that, for the first time, resolves issues regarding the stability of finite proofs under reduction.
Background subtraction based on Local Shape
Venue: arXiv cs.CV 2012
Year: 2012

We present a novel approach to background subtraction that is based on the local shape of small image regions. In our approach, an image region centered on a pixel is mod-eled using the local self-similarity descriptor. We aim at obtaining a reliable change detection based on local shape change in an image when foreground objects are moving. The method first builds a background model and compares the local self-similarities between the background model and the subsequent frames to distinguish background and foreground objects. Post-processing is then used to refine the boundaries of moving objects. Results show that this approach is promising as the foregrounds obtained are com-plete, although they often include shadows.
A Corpus-based Evaluation of a Domain-specific Text to Knowledge Mapping Prototype
Venue: arXiv cs.CL 2012
Year: 2012

The aim of this paper is to evaluate a Text to Knowledge Mapping (TKM) Prototype. The prototype is domain-specific, the purpose of which is to map instructional text onto a knowledge domain. The context of the knowledge domain is DC electrical circuit. During development, the prototype has been tested with a limited data set from the domain. The prototype reached a stage where it needs to be evaluated with a representative linguistic data set called corpus. A corpus is a collection of text drawn from typical sources which can be used as a test data set to evaluate NLP systems. As there is no available corpus for the domain, we developed and annotated a representative corpus. The evaluation of the prototype considers two of its major components- lexical components and knowledge model. Evaluation on lexical components enriches the lexical resources of the prototype like vocabulary and grammar structures. This leads the prototype to parse a reasonable amount of sentences in the corpus. While dealing with the lexicon was straight forward, the identification and extraction of appropriate semantic relations was much more involved. It was necessary, therefore, to manually develop a conceptual structure for the domain to formulate a domain-specific framework of semantic relations. The framework of semantic relationsthat has resulted from this study consisted of 55 relations, out of which 42 have inverse relations. We also conducted rhetorical analysis on the corpus to prove its representativeness in conveying semantic. Finally, we conducted a topical and discourse analysis on the corpus to analyze the coverage of discourse by the prototype.
A Fuzzy Model for Analogical Problem Solving
Venue: arXiv cs.AI 2012
Year: 2012

In this paper we develop a fuzzy model for the description of the process of Analogical Reasoning by representing its main steps as fuzzy subsets of a set of linguistic labels characterizing the individuals' performance in each step and we use the Shannon- Wiener diversity index as a measure of the individuals' abilities in analogical problem solving. This model is compared with a stochastic model presented in author's earlier papers by introducing a finite Markov chain on the steps of the process of Analogical Reasoning. A classroom experiment is also presented to illustrate the use of our results in practice.
The Role of Vertex Consistency in Sampling-based Algorithms for Optimal Motion Planning
Venue: arXiv cs.RO 2012
Year: 2012

Motion planning problems have been studied by both the robotics and the controls research communities for a long time, and many algorithms have been developed for their solution. Among them, incremental sampling-based motion planning algorithms, such as the Rapidly-exploring Random Trees (RRTs), and the Probabilistic Road Maps (PRMs) have become very popular recently, owing to their implementation simplicity and their advantages in handling high-dimensional problems. Although these algorithms work very well in practice, the quality of the computed solution is often not good, i.e., the solution can be far from the optimal one. A recent variation of RRT, namely the RRT* algorithm, bypasses this drawback of the traditional RRT algorithm, by ensuring asymptotic optimality as the number of samples tends to infinity. Nonetheless, the convergence rate to the optimal solution may still be slow. This paper presents a new incremental sampling-based motion planning algorithm based on Rapidly-exploring Random Graphs (RRG), denoted RRT# (RRT "sharp") which also guarantees asymptotic optimality but, in addition, it also ensures that the constructed spanning tree of the geometric graph is consistent after each iteration. In consistent trees, the vertices which have the potential to be part of the optimal solution have the minimum cost-come-value. This implies that the best possible solution is readily computed if there are some vertices in the current graph that are already in the goal region. Numerical results compare with the RRT* algorithm.
On the Manipulability of Voting Systems: Application to Multi-Carrier Networks
Venue: arXiv cs.NI 2012
Year: 2012

Today, Internet involves many actors who are making revenues on it (operators, companies, service providers,...). It is therefore important to be able to make fair decisions in this large-scale and highly competitive economical ecosystem. One of the main issues is to prevent actors from manipulating the natural outcome of the decision process. For that purpose, game theory is a natural framework. In that context, voting systems represent an interesting alternative that, to our knowledge, has not yet been considered. They allow competing entities to decide among different options. Strong theoretical results showed that all voting systems are susceptible to be manipulated by one single voter, except for some "degenerated" and non-acceptable cases. However, very little is known about how much a voting system is manipulable in practical scenarios. In this paper, we investigate empirically the use of voting systems for choosing end-to-end paths in multi-carrier networks, analyzing their manipulability and their economical efficiency. We show that one particular system, called \Single Transferable Vote (STV), is largely more resistant to manipulability than the natural system which tries to get the economical optimum. Moreover, STV manages to select paths close to the economical optimum, whether the participants try to cheat or not.
Proxy dynamic delegation in grid gateway
Venue: arXiv cs.CR 2012
Year: 2012

Nowadays one of the main obstacles the research comes up against is the difficulty in accessing the required computational resources. Grid is able to offer the user a wide set of resources, even if they are often too hard to exploit for non expert end user. Use simplification has today become a common practice in the access and utilization of Cloud, Grid, and data center resources. With the launch of L-GRID gateway, we introduced a new way to deal with Grid portals. L-GRID is an extremely light portal developed in order to access the EGI Grid infrastructure via Web, allowing users to submit their jobs from whatever Web browser in a few minutes, without any knowledge about the underlying Grid infrastructure.
Mppsocgen: A framework for automatic generation of mppsoc architecture
Venue: arXiv cs.DC 2012
Year: 2012

Automatic code generation is a standard method in software engineering since it improves the code consistency and reduces the overall development time. In this context, this paper presents a design flow for automatic VHDL code generation of mppSoC (massively parallel processing System-on-Chip) configuration. Indeed, depending on the application requirements, a framework of Netbeans Platform Software Tool named MppSoCGEN was developed in order to accelerate the design process of complex mppSoC. Starting from an architecture parameters design, VHDL code will be automatically generated using parsing method. Configuration rules are proposed to have a correct and valid VHDL syntax configuration. Finally, an automatic generation of Processor Elements and network topologies models of mppSoC architecture will be done for Stratix II device family. Our framework improves its flexibility on Netbeans 5.5 version and centrino duo Core 2GHz with 22 Kbytes and 3 seconds average runtime. Experimental results for reduction algorithm validate our MppSoCGEN design flow and demonstrate the efficiency of generated architectures.
Indices to Quantify the Ranking of Arabic Journals and Research Output
Venue: arXiv cs.DL 2012
Year: 2012

I propose two simple indices to classify journals, published in Arabic language, and different researchers. These indices depend upon the known impact factor and h-index. The new indices give an easy way to judge the rank of any journal (output of any researcher) without looking for other journals (output of other researchers).
A Market for Unbiased Private Data: Paying Individuals According to their Privacy Attitudes
Venue: arXiv cs.CY 2012
Year: 2012

Since there is, in principle, no reason why third parties should not pay individuals for the use of their data, we introduce a realistic market that would allow these payments to be made while taking into account the privacy attitude of the participants. And since it is usually important to use unbiased samples to obtain credible statistical results, we examine the properties that such a market should have and suggest a mechanism that compensates those individuals that participate according to their risk attitudes. Equally important, we show that this mechanism also benefits buyers, as they pay less for the data than they would if they compensated all individuals with the same maximum fee that the most concerned ones expect.
$λ$-Scale, a lambda calculus for spaces with dilations
Venue: arXiv cs.LO 2012
Year: 2012

$λ$-Scale is an enrichment of lambda calculus which is adapted to emergent algebras. It can be used therefore in metric spaces with dilations.