Bisection forAx=λBx with matrices of variable band width

Some extensions of the bisection method and of the inverse vector iteration for the general eigenvalue problemAx=λBx with symmetric matrices are given. A version with restricted pivoting is applied to sparse matricesA andB in which case the decomposition ofA-μB can be performed within an extended envelope with respect to the envelopeA andB. The effect of these refinements is illustrated by an example.     

ANDES: efficient evaluation of NOT-twig queries in relational databases

Despite a large body of work on XPath query processing in relational environment, systematic study of queries containing not-predicates have received little attention in the literature. Particularly, several xml supports of industrial-strength commercial rdbms fail to efficiently evaluate such queries. In this paper, we present an efficient and novel strategy to evaluate not -twig queries in a tree-unaware relational environment. not -twig queries are XPath queries with ancestor–descendant and parent–child axis and contain one or more not-predicates. We propose a novel Dewey-based encoding scheme called Andes (ANcestor Dewey-based Encoding Scheme), which enables us to efficiently filter out elements satisfying a not-predicate by comparing their ancestor group identifiers. In this approach, a set of elements under the same common ancestor at a specific level in the xml tree is assigned same ancestor group identifier. Based on this scheme, we propose a novel sql translation algorithm for not-twig query evaluation. Experiments carried out confirm that our proposed approach built on top of an off-the-shelf commercial rdbms significantly outperforms state-of-the-art relational and native approaches. We also explore the query plans selected by a commercial relational optimizer to evaluate our translated queries in different input cardinality. Such exploration further validates the performance benefits of Andes.     

Local noncuppability in R/M

Given any [c], [a], [d] xxxxxxxxR/M such that [d] ≤ [a] ≤ [c], [a] is locally noncuppable between [c] and [d] if [d] < [a] ≤ [c] and [a] ∨ [b] < [c] for any [b] xxxxxxxxR/M such that [d] ≤ [b] < [c]. It will be shown that given any nonzero [c] xxxxxxxxR/M, there are [a], [d] xxxxxxxxR/M such that [d] < [a] ≤ [c] and [a] is locally noncuppable between [c] and [d].     

PP-Lowness and a Simple Definition of AWPP

Abstract. We show that the counting classes AWPP and APP [FFKL], [L] are more robust than previously thought. Our results identify a sufficient condition for a language to be low for PP, and we show that this condition is at least as weak as other previously studied criteria. We extend a result of Köbler et al. by proving that all sparse co-C ₌ P languages are in APP, and are thus PP-low. Our results also imply that AWPP ?eq APP, and thus APP contains many other established subclasses of PP-low, thereby reducing several different lowness results to membership in APP. We also show that AWPP and APP are Σ ⁰ ₂ -definable classes. Some of our results are reminiscent of amplifying certainty in probabilistic computation.     

A blind digital audio watermarking scheme based on EMD and UISA techniques

In this paper, a new perceptual spread spectrum audio watermarking scheme is discussed. The watermark embedding process is performed in the Empirical Mode Decomposition (EMD) domain, and the hybrid watermark extraction process is based on the combination of EMD and ISA (Independent Subspace Analysis) techniques, followed by the generic detection system, i.e. inverse perceptual filter, predictor filter and correlation based detector. Since the EMD decomposes the audio signal into several oscillating components–the intrinsic mode functions (IMF)–the watermark information can be inserted in more than one IMF, using spread spectrum modulation, allowing hence the increase of the insertion capacity. The imperceptibility of the inserted data is ensured by the use of a psychoacoustical model. The blind extraction of the watermark signal, from the received watermarked audio, consists in the separation of the watermark from the IMFs of the received audio signal. The separation is achieved by a new proposed under-determined ISA method, here referred to as UISA. The proposed hybrid watermarking system was applied to the SQAM (Sound Quality Assessment Material) audio database (Available at http://sound.media.mit.edu/mpeg4/audio/sqam/) and proved to have efficient detection performances in terms of Bit Error Rate (BER) compared to a generic perceptual spread spectrum watermarking system. The perceptual quality of the watermarked audio was objectively assessed using the PEMO-Q (Tool for objective perceptual assessment of audio quality) algorithm. Also, using our technique, we can extract the different watermarks without using any information of original signal or the inserted watermark. Experimental results exhibit that the transparency and high robustness of the watermarked audio can be achieved simultaneously with a substantial increase of the amount of information transmitted. A reliability of 1.8 10^???4 (against 1.5 10^???2 for the generic system), for a bit rate of 400 bits/s, can be achieved when the channel is not disturbed.     

Query reverse engineering

In this paper, we introduce a new problem termed query reverse engineering (QRE). Given a database \(D\) and a result table \(T\) —the output of some known or unknown query \(Q\) on \(D\) —the goal of QRE is to reverse-engineer a query \(Q'\) such that the output of query \(Q'\) on database \(D\) (denoted by \(Q'(D)\) ) is equal to \(T\) (i.e., \(Q(D)\) ). The QRE problem has useful applications in database usability, data analysis, and data security. In this work, we propose a data-driven approach, TALOS for Tree-based classifier with At Least One Semantics, that is based on a novel dynamic data classification formulation and extend the approach to efficiently support the three key dimensions of the QRE problem: whether the input query is known/unknown, supporting different query fragments, and supporting multiple database versions.     

Outlier detection from large distributed databases

In this paper, we present an innovative system, coined as DISTROD (a.k.a DISTRibuted Outlier Detector), for detecting outliers, namely abnormal instances or observations, from multiple large distributed databases. DISTROD is able to effectively detect the so-called global outliers from distributed databases that are consistent with those produced by the centralized detection paradigm. DISTROD is equipped with a number of optimization/boosting strategies which empower it to significantly enhance its speed performance and reduce its communication overhead. Experimental evaluation demonstrates the good performance of DISTROD in terms of speed and communication overhead.     

Invariant-Free Clausal Temporal Resolution

Resolution is a well-known proof method for classical logics that is well suited for mechanization. The most fruitful approach in the literature on temporal logic, which was started with the seminal paper of M. Fisher, deals with Propositional Linear-time Temporal Logic (PLTL) and requires to generate invariants for performing resolution on eventualities. The methods and techniques developed in that approach have also been successfully adapted in order to obtain a clausal resolution method for Computation Tree Logic (CTL), but invariant handling seems to be a handicap for further extension to more general branching temporal logics. In this paper, we present a new approach to applying resolution to PLTL. The main novelty of our approach is that we do not generate invariants for performing resolution on eventualities. Hence, we say that the approach presented in this paper is invariant-free. Our method is based on the dual methods of tableaux and sequents for PLTL that we presented in a previous paper. Our resolution method involves translation into a clausal normal form that is a direct extension of classical CNF. We first show that any PLTL-formula can be transformed into this clausal normal form. Then, we present our temporal resolution method, called trs-resolution, that extends classical propositional resolution. Finally, we prove that trs-resolution is sound and complete. In fact, it finishes for any input formula deciding its satisfiability, hence it gives rise to a new decision procedure for PLTL.     

OXPath: A language for scalable data extraction, automation, and crawling on the deep web

The evolution of the web has outpaced itself: A growing wealth of information and increasingly sophisticated interfaces necessitate automated processing, yet existing automation and data extraction technologies have been overwhelmed by this very growth. To address this trend, we identify four key requirements for web data extraction, automation, and (focused) web crawling: (1) interact with sophisticated web application interfaces, (2) precisely capture the relevant data to be extracted, (3) scale with the number of visited pages, and (4) readily embed into existing web technologies. We introduce OXPath as an extension of XPath for interacting with web applications and extracting data thus revealed—matching all the above requirements. OXPath’s page-at-a-time evaluation guarantees memory use independent of the number of visited pages, yet remains polynomial in time. We experimentally validate the theoretical complexity and demonstrate that OXPath’s resource consumption is dominated by page rendering in the underlying browser. With an extensive study of sublanguages and properties of OXPath, we pinpoint the effect of specific features on evaluation performance. Our experiments show that OXPath outperforms existing commercial and academic data extraction tools by a wide margin.     

Crystal: Integrating Structured Queries into a Tactic Language

We present the language CRStL (Control Rule Strategy Language, pronounce “crystal”) to formulate mathematical reasoning techniques as proof strategies in the context of the proof assistant Ωmega. The language is arranged in two levels, a query language to access mathematical knowledge maintained in development graphs, and a strategy language to annotate the results of these queries with further control information. The two-leveled structure of the language allows the specification of proof techniques in a declarative way. We present the syntax and semantics of CRStL and illustrate its use by examples.     

A Quantum Characterization Of NP

In this article, we introduce a new complexity class called PQMA _log(2). Informally, this is the class of languages for which membership has a logarithmic-size quantum proof with perfect completeness and soundness, which is polynomially close to 1 in a context where the verifier is provided a proof with two unentangled parts. We then show that PQMA _log(2) =? NP. For this to be possible, it is important, when defining the class, not to give too much power to the verifier. This result, when compared to the fact that QMA _log =? BQP, gives us new insight into the power of quantum information and the impact of entanglement.     

Comparing variants of strategic ability: how uncertainty and memory influence general properties of games

Alternating-time temporal logic (ATL) is a modal logic that allows to reason about agents’ abilities in game-like scenarios. Semantic variants of ATL are usually built upon different assumptions about the kind of game that is played, including capabilities of agents (perfect vs. imperfect information, perfect vs. imperfect memory, etc.). ATL has been studied extensively in previous years; however, most of the research focused on model checking. Studies of other decision problems (e.g., satisfiability) and formal meta-properties of the logic (like axiomatization or expressivity) have been relatively scarce, and mostly limited to the basic variant of ATL where agents possess perfect information and perfect memory. In particular, a comparison between different semantic variants of the logic is largely left untouched. In this paper, we show that different semantics of ability in ATL give rise to different validity sets. The issue is important for several reasons. First, many logicians identify a logic with its set of true sentences. As a consequence, we prove that different notions of ability induce different strategic logics. Secondly, we show that different concepts of ability induce different general properties of games. Thirdly, the study can be seen as the first systematic step towards satisfiability-checking algorithms for ATL with imperfect information. We introduce sophisticated unfoldings of models and prove invariance results that are an important technical contribution to formal analysis of strategic logics.     

An implicit GTS allocation mechanism in IEEE 802.15.4 for time-sensitive wireless sensor networks: theory and practice

Timeliness guarantee is an important feature of the recently standardized IEEE 802.15.4 protocol, turning it quite appealing for Wireless Sensor Network (WSN) applications under timing constraints. When operating in beacon-enabled mode, this protocol allows nodes with real-time requirements to allocate Guaranteed Time Slots (GTS) in the contention-free period. The protocol natively supports explicit GTS allocation, i.e. a node allocates a number of time slots in each superframe for exclusive use. The limitation of this explicit GTS allocation is that GTS resources may quickly disappear, since a maximum of seven GTSs can be allocated in each superframe, preventing other nodes to benefit from guaranteed service. Moreover, the GTS may be underutilized, resulting in wasted bandwidth. To overcome these limitations, this paper proposes i-GAME, an implicit GTS Allocation Mechanism in beacon-enabled IEEE 802.15.4 networks. The allocation is based on implicit GTS allocation requests, taking into account the traffic specifications and the delay requirements of the flows. The i-GAME approach enables the use of one GTS by multiple nodes, still guaranteeing that all their (delay, bandwidth) requirements are satisfied. For that purpose, we propose an admission control algorithm that enables to decide whether to accept a new GTS allocation request or not, based not only on the remaining time slots, but also on the traffic specifications of the flows, their delay requirements and the available bandwidth resources. We show that our approach improves the bandwidth utilization as compared to the native explicit allocation mechanism defined in the IEEE 802.15.4 standard. We also present some practical considerations for the implementation of i-GAME, ensuring backward compatibility with the IEEE 801.5.4 standard with only minor add-ons. Finally, an experimental evaluation on a real system that validates our theoretical analysis and demonstrates the implementation of i-GAME is also presented.     

The Alexander Method — A technique for the processing of recursive axioms in deductive databases

We propose a technique for handling recursive axioms in deductive databases. More precisely, we solve the following problem: Given a relational query including virtual relations defined from axioms (Horn clauses, with variables in the conclusion predefined in the hypotheses), which can be recursive, how to translate this query into arelational program, i. e. a set of relational operations concerning only real relations (not virtual). Our solution has the following properties:

? the program to evaluate the query always terminates,

? the relational program is produced by a pure compilation of a source query and of the axioms, and is independent of the data values (there is no run-time),

? the relational operations are optimized: theyfocus towards the computation of the query, without needless computations.

As far as we know, the Alexander Method is the first solution exhibiting all these properties. This work is partly funded by Esprit Project 112 (KIMS).     

Contraction-Free Linear Depth Sequent Calculi for Intuitionistic Propositional Logic with the Subformula Property and Minimal Depth Counter-Models

In this paper we present LSJ, a contraction-free sequent calculus for Intuitionistic propositional logic whose proofs are linearly bounded in the length of the formula to be proved and satisfy the subformula property. We also introduce a sequent calculus RJ for intuitionistic unprovability with the same properties of LSJ. We show that from a refutation of RJ of a sequent σ we can extract a Kripke counter-model for σ. Finally, we provide a procedure that given a sequent σ returns either a proof of σ in LSJ or a refutation in RJ such that the extracted counter-model is of minimal depth.     

MPaaS: Mobility prediction as a service in telecom cloud

Mobile applications and services relying on mobility prediction have recently spurred lots of interest. In this paper, we propose mobility prediction based on cellular traces as an infrastructural level service of telecom cloud. Mobility Prediction as a Service (MPaaS) embeds mobility mining and forecasting algorithms into a cloud-based user location tracking framework. By empowering MPaaS, the hosted 3rd-party and value-added services can benefit from online mobility prediction. Particularly we took Mobility-aware Personalization and Predictive Resource Allocation as key features to elaborate how MPaaS drives new fashion of mobile cloud applications. Due to the randomness of human mobility patterns, mobility predicting remains a very challenging task in MPaaS research. Our preliminary study observed collective behavioral patterns (CBP) in mobility of crowds, and proposed a CBP-based mobility predictor. MPaaS system equips a hybrid predictor fusing both CBP-based scheme and Markov-based predictor to provide telecom cloud with large-scale mobility prediction capacity.     

Efficient processing of k-hop reachability queries

We study the problem of answering k -hop reachability queries in a directed graph, i.e., whether there exists a directed path of length $k$ , from a source query vertex to a target query vertex in the input graph. The problem of $k$ -hop reachability is a general problem of the classic reachability (where $k=\infty $ ). Existing indexes for processing classic reachability queries, as well as for processing shortest path distance queries, are not applicable or not efficient for processing $k$ -hop reachability queries. We propose an efficient index for processing $k$ -hop reachability queries. Our experimental results on a wide range of real datasets show that our method is efficient and scalable in terms of both index construction and query processing.     

Reasoning about temporal properties of rational play

This article is about defining a suitable logic for expressing classical game theoretical notions. We define an extension of alternating-time temporal logic (ATL) that enables us to express various rationality assumptions of intelligent agents. Our proposal, the logic ATLP (ATL with plausibility) allows us to specify sets of rational strategy profiles in the object language, and reason about agents’ play if only these strategy profiles were allowed. For example, we may assume the agents to play only Nash equilibria, Pareto-optimal profiles or undominated strategies, and ask about the resulting behaviour (and outcomes) under such an assumption. The logic also gives rise to generalized versions of classical solution concepts through characterizing patterns of payoffs by suitably parameterized formulae of ATLP. We investigate the complexity of model checking ATLP for several classes of formulae: It ranges from $\Delta_{\mathbf{3}}^{\mathbf{P}}$ to PSPACE in the general case and from $\Delta_{\mathbf{3}}^{\mathbf{P}}$ to $\Delta_{\mathbf{4}}^{\mathbf{P}}$ for the most interesting subclasses, and roughly corresponds to solving extensive games with imperfect information.