OpenRaiser/Intern-Atlas huggingface dataset:
Branching-time model checking of one-counter processes
Venue: arXiv cs.LO 2009
Year: 2009

One-counter processes (OCPs) are pushdown processes which operate only on a unary stack alphabet. We study the computational complexity of model checking computation tree logic (CTL) over OCPs. A PSPACE upper bound is inherited from the modal mu-calculus for this problem. First, we analyze the periodic behaviour of CTL over OCPs and derive a model checking algorithm whose running time is exponential only in the number of control locations and a syntactic notion of the formula that we call leftward until depth. Thus, model checking fixed OCPs against CTL formulas with a fixed leftward until depth is in P. This generalizes a result of the first author, Mayr, and To for the expression complexity of CTL's fragment EF. Second, we prove that already over some fixed OCP, CTL model checking is PSPACE-hard. Third, we show that there already exists a fixed CTL formula for which model checking of OCPs is PSPACE-hard. To obtain the latter result, we employ two results from complexity theory: (i) Converting a natural number in Chinese remainder presentation into binary presentation is in logspace-uniform NC^1 and (ii) PSPACE is AC^0-serializable. We demonstrate that our approach can be used to obtain further results. We show that model-checking CTL's fragment EF over OCPs is hard for P^NP, thus establishing a matching lower bound and answering an open question of the first author, Mayr, and To. We moreover show that the following problem is hard for PSPACE: Given a one-counter Markov decision process, a set of target states with counter value zero each, and an initial state, to decide whether the probability that the initial state will eventually reach one of the target states is arbitrarily close to 1. This improves a previously known lower bound for every level of the Boolean hierarchy by Brazdil et al.
Anonymization with Worst-Case Distribution-Based Background Knowledge
Venue: arXiv cs.DB 2009
Year: 2009

Background knowledge is an important factor in privacy preserving data publishing. Distribution-based background knowledge is one of the well studied background knowledge. However, to the best of our knowledge, there is no existing work considering the distribution-based background knowledge in the worst case scenario, by which we mean that the adversary has accurate knowledge about the distribution of sensitive values according to some tuple attributes. Considering this worst case scenario is essential because we cannot overlook any breaching possibility. In this paper, we propose an algorithm to anonymize dataset in order to protect individual privacy by considering this background knowledge. We prove that the anonymized datasets generated by our proposed algorithm protects individual privacy. Our empirical studies show that our method preserves high utility for the published data at the same time.
n-Opposition theory to structure debates
Venue: arXiv cs.AI 2009
Year: 2009

2007 was the first international congress on the ?square of oppositions?. A first attempt to structure debate using n-opposition theory was presented along with the results of a first experiment on the web. Our proposal for this paper is to define relations between arguments through a structure of opposition (square of oppositions is one structure of opposition). We will be trying to answer the following questions: How to organize debates on the web 2.0? How to structure them in a logical way? What is the role of n-opposition theory, in this context? We present in this paper results of three experiments (Betapolitique 2007, ECAP 2008, Intermed 2008).
Base Selection and Transmission Synchronization Algorithm in Quantum Cryptography
Venue: arXiv cs.CR 2009
Year: 2009

One Achilles heal of classical cryptographic communication systems is that secret communication can only take place after a key is communicated in secret over a totally secure communication channel. Here comes quantum key distribution which takes advantage of certain phenomena that occur at the subatomic level, so that any attempt by an enemy to obtain the bits in a key not only fails, but gets detected as well. This paper proposes the idea of on algorithm, intended to be a quantum network algorithm named Base Selection and Transmission Synchronization - BSTS, which can realize a perfectly secure communication between two computers.
The Uniformization Process of the Fast Congestion Notification (FN)
Venue: arXiv cs.NI 2009
Year: 2009

Fast Congestion Notification (FN) is one of the proactive queue management mechanisms that practices congestion avoidance to help avoid the beginning of congestion by marking or dropping packets before the routers queue gets full; and exercises congestion control, when congestion avoidance fails, by increasing the rate of packet marking or dropping. Technically, FN avoids the queue overflows by controlling the instantaneous queue size below the optimal queue size, and control congestion by keeping the average arrival rate close to the outgoing link capacity. Upon arrival of each packet, FN uses the instantaneous queue size and the average arrival rate to calculate the packet marking or dropping probability. FN marks or drops packets at fairly regular intervals to avoid long intermarking intervals and clustered packet marks or drops. Too many marked or dropped packets close together can cause global synchronization, and also too long packet intermarking times between marked or dropped packets can cause large queue sizes and congestion. This paper shows how FN controls the queue size, avoids congestion, and reduces global synchronization by uniformizing marked or dropped packet intervals.
On Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids
Venue: arXiv cs.DM 2009
Year: 2009

We theoretically analyze the Cops and Robber Game for the first time in a multidimensional grid. It is shown that for an $n$-dimensional grid, at least $n$ cops are necessary to ensure capture of the robber. We also present a set of cop strategies for which $n$ cops are provably sufficient to catch the robber. Further, for two-dimensional grid, we provide an efficient cop strategy for which the robber is caught even by a single cop under certain conditions.
Design optimization of parallel manipulators for high-speed precision machining applications
Venue: arXiv cs.RO 2009
Year: 2009

The paper proposes an integrated approach to the design optimization of parallel manipulators, which is based on the concept of the workspace grid and utilizes the goal-attainment formulation for the global optimization. To combine the non-homogenous design specification, the developed optimization technique transforms all constraints and objectives into similar performance indices related to the maximum size of the prescribed shape workspace. This transformation is based on the dedicated dynamic programming procedures that satisfy computational requirements of modern CAD. Efficiency of the developed technique is demonstrated via two case studies that deal with optimization of the kinematical and stiffness performances for parallel manipulators of the Orthoglide family.
Efficient and Spontaneous Privacy-Preserving Protocol for Secure Vehicular Communications
Venue: arXiv cs.CR 2009
Year: 2009

This paper introduces an efficient and spontaneous privacy-preserving protocol for vehicular ad-hoc networks based on revocable ring signature. The proposed protocol has three appealing characteristics: First, it offers conditional privacy-preservation: while a receiver can verify that a message issuer is an authorized participant in the system only a trusted authority can reveal the true identity of a message sender. Second, it is spontaneous: safety messages can be authenticated locally, without support from the roadside units or contacting other vehicles. Third, it is efficient by offering fast message authentication and verification, cost-effective identity tracking in case of a dispute, and low storage requirements. We use extensive analysis to demonstrate the merits of the proposed protocol and to contrast it with previously proposed solutions.
Computing the distance distribution of systematic non-linear codes
Venue: arXiv cs.DM 2009
Year: 2009

The most important families of non-linear codes are systematic. A brute-force check is the only known method to compute their weight distribution and distance distribution. On the other hand, it outputs also all closest word pairs in the code. In the black-box complexity model, the check is optimal among closest-pair algorithms. In this paper we provide a Groebner basis technique to compute the weight/distance distribution of any systematic non-linear code. Also our technique outputs all closest pairs. Unlike the check, our method can be extended to work on code families.
Probabilistic Weighted Automata
Venue: arXiv cs.LO 2009
Year: 2009

Nondeterministic weighted automata are finite automata with numerical weights on transitions. They define quantitative languages L that assign to each word w a real number L(w). The value of an infinite word w is computed as the maximal value of all runs over w, and the value of a run as the maximum, limsup, liminf, limit average, or discounted sum of the transition weights. We introduce probabilistic weighted automata, in which the transitions are chosen in a randomized (rather than nondeterministic) fashion. Under almost-sure semantics (resp. positive semantics), the value of a word w is the largest real v such that the runs over w have value at least v with probability 1 (resp. positive probability). We study the classical questions of automata theory for probabilistic weighted automata: emptiness and universality, expressiveness, and closure under various operations on languages. For quantitative languages, emptiness and universality are defined as whether the value of some (resp. every) word exceeds a given threshold. We prove some of these questions to be decidable, and others undecidable. Regarding expressive power, we show that probabilities allow us to define a wide variety of new classes of quantitative languages, except for discounted-sum automata, where probabilistic choice is no more expressive than nondeterminism. Finally, we give an almost complete picture of the closure of various classes of probabilistic weighted automata for the following pointwise operations on quantitative languages: max, min, sum, and numerical complement.
Size Does Matter (in P2P Live Streaming)
Venue: arXiv cs.NI 2009
Year: 2009

Optimal dissemination schemes have previously been studied for peer-to-peer live streaming applications. Live streaming being a delay-sensitive application, fine tuning of dissemination parameters is crucial. In this report, we investigate optimal sizing of chunks, the units of data exchange, and probe sets, the number peers a given node probes before transmitting chunks. Chunk size can have significant impact on diffusion rate (chunk miss ratio), diffusion delay, and overhead. The size of the probe set can also affect these metrics, primarily through the choices available for chunk dissemination. We perform extensive simulations on the so-called random-peer, latest-useful dissemination scheme. Our results show that size does matter, with the optimal size being not too small in both cases.
Qunits: queried units in database search
Venue: arXiv cs.DB 2009
Year: 2009

Keyword search against structured databases has become a popular topic of investigation, since many users find structured queries too hard to express, and enjoy the freedom of a ``Google-like'' query box into which search terms can be entered. Attempts to address this problem face a fundamental dilemma. Database querying is based on the logic of predicate evaluation, with a precisely defined answer set for a given query. On the other hand, in an information retrieval approach, ranked query results have long been accepted as far superior to results based on boolean query evaluation. As a consequence, when keyword queries are attempted against databases, relatively ad-hoc ranking mechanisms are invented (if ranking is used at all), and there is little leverage from the large body of IR literature regarding how to rank query results. Our proposal is to create a clear separation between ranking and database querying. This divides the problem into two parts, and allows us to address these separately. The first task is to represent the database, conceptually, as a collection of independent ``queried units'', or ``qunits'', each of which represents the desired result for some query against the database. The second task is to evaluate keyword queries against a collection of qunits, which can be treated as independent documents for query purposes, thereby permitting the use of standard IR techniques. We provide insights that encourage the use of this query paradigm, and discuss preliminary investigations into the efficacy of a qunits-based framework based on a prototype implementation.
Sailing the Information Ocean with Awareness of Currents: Discovery and Application of Source Dependence
Venue: arXiv cs.DB 2009
Year: 2009

The Web has enabled the availability of a huge amount of useful information, but has also eased the ability to spread false information and rumors across multiple sources, making it hard to distinguish between what is true and what is not. Recent examples include the premature Steve Jobs obituary, the second bankruptcy of United airlines, the creation of Black Holes by the operation of the Large Hadron Collider, etc. Since it is important to permit the expression of dissenting and conflicting opinions, it would be a fallacy to try to ensure that the Web provides only consistent information. However, to help in separating the wheat from the chaff, it is essential to be able to determine dependence between sources. Given the huge number of data sources and the vast volume of conflicting data available on the Web, doing so in a scalable manner is extremely challenging and has not been addressed by existing work yet. In this paper, we present a set of research problems and propose some preliminary solutions on the issues involved in discovering dependence between sources. We also discuss how this knowledge can benefit a variety of technologies, such as data integration and Web 2.0, that help users manage and access the totality of the available information from various sources.
Capturing Data Uncertainty in High-Volume Stream Processing
Venue: arXiv cs.DB 2009
Year: 2009

We present the design and development of a data stream system that captures data uncertainty from data collection to query processing to final result generation. Our system focuses on data that is naturally modeled as continuous random variables. For such data, our system employs an approach grounded in probability and statistical theory to capture data uncertainty and integrates this approach into high-volume stream processing. The first component of our system captures uncertainty of raw data streams from sensing devices. Since such raw streams can be highly noisy and may not carry sufficient information for query processing, our system employs probabilistic models of the data generation process and stream-speed inference to transform raw data into a desired format with an uncertainty metric. The second component captures uncertainty as data propagates through query operators. To efficiently quantify result uncertainty of a query operator, we explore a variety of techniques based on probability and statistical theory to compute the result distribution at stream speed. We are currently working with a group of scientists to evaluate our system using traces collected from the domains of (and eventually in the real systems for) hazardous weather monitoring and object tracking and monitoring.
The Case for RodentStore, an Adaptive, Declarative Storage System
Venue: arXiv cs.DB 2009
Year: 2009

Recent excitement in the database community surrounding new applications?analytic, scientific, graph, geospatial, etc.?has led to an explosion in research on database storage systems. New storage systems are vital to the database community, as they are at the heart of making database systems perform well in new application domains. Unfortunately, each such system also represents a substantial engineering effort including a great deal of duplication of mechanisms for features such as transactions and caching. In this paper, we make the case for RodentStore, an adaptive and declarative storage system providing a high-level interface for describing the physical representation of data. Specifically, RodentStore uses a declarative storage algebra whereby administrators (or database design tools) specify how a logical schema should be grouped into collections of rows, columns, and/or arrays, and the order in which those groups should be laid out on disk. We describe the key operators and types of our algebra, outline the general architecture of RodentStore, which interprets algebraic expressions to generate a physical representation of the data, and describe the interface between RodentStore and other parts of a database system, such as the query optimizer and executor. We provide a case study of the potential use of RodentStore in representing dense geospatial data collected from a mobile sensor network, showing the ease with which different storage layouts can be expressed using some of our algebraic constructs and the potential performance gains that a RodentStore-built storage system can offer.
The Case for a Structured Approach to Managing Unstructured Data
Venue: arXiv cs.DB 2009
Year: 2009

The challenge of managing unstructured data represents perhaps the largest data management opportunity for our community since managing relational data. And yet we are risking letting this opportunity go by, ceding the playing field to other players, ranging from communities such as AI, KDD, IR, Web, and Semantic Web, to industrial players such as Google, Yahoo, and Microsoft. In this essay we explore what we can do to improve upon this situation. Drawing on the lessons learned while managing relational data, we outline a structured approach to managing unstructured data. We conclude by discussing the potential implications of this approach to managing other kinds of non-relational data, and to the identify of our field.
Cooperative Transmission for a Vector Gaussian Parallel Relay Network
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we consider a parallel relay network where two relays cooperatively help a source transmit to a destination. We assume the source and the destination nodes are equipped with multiple antennas. Three basic schemes and their achievable rates are studied: Decode-and-Forward (DF), Amplify-and-Forward (AF), and Compress-and-Forward (CF). For the DF scheme, the source transmits two private signals, one for each relay, where dirty paper coding (DPC) is used between the two private streams, and a common signal for both relays. The relays make efficient use of the common information to introduce a proper amount of correlation in the transmission to the destination. We show that the DF scheme achieves the capacity under certain conditions. We also show that the CF scheme is asymptotically optimal in the high relay power limit, regardless of channel ranks. It turns out that the AF scheme also achieves the asymptotic optimality but only when the relays-to-destination channel is full rank. The relative advantages of the three schemes are discussed with numerical results.
Deterministic approximation for the cover time of trees
Venue: arXiv cs.DS 2009
Year: 2009

We present a deterministic algorithm that given a tree T with n vertices, a starting vertex v and a slackness parameter epsilon > 0, estimates within an additive error of epsilon the cover and return time, namely, the expected time it takes a simple random walk that starts at v to visit all vertices of T and return to v. The running time of our algorithm is polynomial in n/epsilon, and hence remains polynomial in n also for epsilon = 1/n^{O(1)}. We also show how the algorithm can be extended to estimate the expected cover (without return) time on trees.
Navigation in tilings of the hyperbolic plane and possible applications
Venue: arXiv cs.CG 2009
Year: 2009

This paper introduces a method of navigation in a large family of tilings of the hyperbolic plane and looks at the question of possible applications in the light of the few ones which were already obtained.
A Survey on Service Composition Middleware in Pervasive Environments
Venue: arXiv cs.SE 2009
Year: 2009

The development of pervasive computing has put the light on a challenging problem: how to dynamically compose services in heterogeneous and highly changing environments? We propose a survey that defines the service composition as a sequence of four steps: the translation, the generation, the evaluation, and finally the execution. With this powerful and simple model we describe the major service composition middleware. Then, a classification of these service composition middleware according to pervasive requirements - interoperability, discoverability, adaptability, context awareness, QoS management, security, spontaneous management, and autonomous management - is given. The classification highlights what has been done and what remains to do to develop the service composition in pervasive environments.
Embedded Sensor System for Early Pathology Detection in Building Construction
Venue: arXiv cs.NI 2009
Year: 2009

Structure pathology detection is an important security task in building construction, which is performed by an operator by looking manually for damages on the materials. This activity could be dangerous if the structure is hidden or difficult to reach. On the other hand, embedded devices and wireless sensor networks (WSN) are becoming popular and cheap, enabling the design of an alternative pathology detection system to monitor structures based on these technologies. This article introduces a ZigBee WSN system, intending to be autonomous, easy to use and with low power consumption. Its functional parts are fully discussed with diagrams, as well as the protocol used to collect samples from sensor nodes. Finally, several tests focused on range and power consumption of our prototype are shown, analysing whether the results obtained were as expected or not.
Logic with Verbs
Venue: arXiv cs.AI 2009
Year: 2009

The aim of this paper is to introduce a logic in which nouns and verbs are handled together as a deductive reasoning, and also to observe the relationship between nouns and verbs as well as between logics and conversations.
Weblog Clustering in Multilinear Algebra Perspective
Venue: arXiv cs.IR 2009
Year: 2009

This paper describes a clustering method to group the most similar and important weblogs with their descriptive shared words by using a technique from multilinear algebra known as PARAFAC tensor decomposition. The proposed method first creates labeled-link network representation of the weblog datasets, where the nodes are the blogs and the labels are the shared words. Then, 3-way adjacency tensor is extracted from the network and the PARAFAC decomposition is applied to the tensor to get pairs of node lists and label lists with scores attached to each list as the indication of the degree of importance. The clustering is done by sorting the lists in decreasing order and taking the pairs of top ranked blogs and words. Thus, unlike standard co-clustering methods, this method not only groups the similar blogs with their descriptive words but also tends to produce clusters of important blogs and descriptive words.