OpenRaiser/Intern-Atlas huggingface dataset:
Sequential detection of Markov targets with trajectory estimation
Venue: arXiv cs.IT 2008
Year: 2008

The problem of detection and possible estimation of a signal generated by a dynamic system when a variable number of noisy measurements can be taken is here considered. Assuming a Markov evolution of the system (in particular, the pair signal-observation forms a hidden Markov model), a sequential procedure is proposed, wherein the detection part is a sequential probability ratio test (SPRT) and the estimation part relies upon a maximum-a-posteriori (MAP) criterion, gated by the detection stage (the parameter to be estimated is the trajectory of the state evolution of the system itself). A thorough analysis of the asymptotic behaviour of the test in this new scenario is given, and sufficient conditions for its asymptotic optimality are stated, i.e. for almost sure minimization of the stopping time and for (first-order) minimization of any moment of its distribution. An application to radar surveillance problems is also examined.
An Evolutionary-Based Approach to Learning Multiple Decision Models from Underrepresented Data
Venue: arXiv cs.AI 2008
Year: 2008

The use of multiple Decision Models (DMs) enables to enhance the accuracy in decisions and at the same time allows users to evaluate the confidence in decision making. In this paper we explore the ability of multiple DMs to learn from a small amount of verified data. This becomes important when data samples are difficult to collect and verify. We propose an evolutionary-based approach to solving this problem. The proposed technique is examined on a few clinical problems presented by a small amount of data.
A New Type of Cipher: DICING_csb
Venue: arXiv cs.CR 2008
Year: 2008

In this paper, we will propose a new type of cipher named DICING_csb, which is derived from our previous stream cipher DICING. It has applied a stream of subkey and an encryption form of block ciphers, so it may be viewed as a combinative of stream cipher and block cipher. Hence, the new type of cipher has fast rate like a stream cipher and need no MAC.
Decision Support with Belief Functions Theory for Seabed Characterization
Venue: arXiv cs.AI 2008
Year: 2008

The seabed characterization from sonar images is a very hard task because of the produced data and the unknown environment, even for an human expert. In this work we propose an original approach in order to combine binary classifiers arising from different kinds of strategies such as one-versus-one or one-versus-rest, usually used in the SVM-classification. The decision functions coming from these binary classifiers are interpreted in terms of belief functions in order to combine these functions with one of the numerous operators of the belief functions theory. Moreover, this interpretation of the decision function allows us to propose a process of decisions by taking into account the rejected observations too far removed from the learning data, and the imprecise decisions given in unions of classes. This new approach is illustrated and evaluated with a SVM in order to classify the different kinds of sediment on image sonar.
Sparse power-efficient topologies for wireless ad hoc sensor networks
Venue: arXiv cs.NI 2008
Year: 2008

We study the problem of power-efficient routing for multihop wireless ad hoc sensor networks. The guiding insight of our work is that unlike an ad hoc wireless network, a wireless ad hoc sensor network does not require full connectivity among the nodes. As long as the sensing region is well covered by connected nodes, the network can perform its task. We consider two kinds of geometric random graphs as base interconnection structures: unit disk graphs $\UDG(2,λ)$ and $k$-nearest-neighbor graphs $\NN(2,k)$ built on points generated by a Poisson point process of density $λ$ in $\RR^2$. We provide subgraph constructions for these two models $\US(2,λ)$ and $\NS(2,k)$ and show that there are values $λ_s$ and $k_s$ above which these constructions have the following good properties: (i) they are sparse; (ii) they are power-efficient in the sense that the graph distance is no more than a constant times the Euclidean distance between any pair of points; (iii) they cover the space well; (iv) the subgraphs can be set up easily using local information at each node. We also describe a simple local algorithm for routing packets on these subgraphs. Our constructions also give new upper bounds for the critical values of the parameters $λ$ and $k$ for the models $\UDG(2,λ)$ and $\NN(2,k)$.
Environment Assumptions for Synthesis
Venue: arXiv cs.GT 2008
Year: 2008

The synthesis problem asks to construct a reactive finite-state system from an $ω$-regular specification. Initial specifications are often unrealizable, which means that there is no system that implements the specification. A common reason for unrealizability is that assumptions on the environment of the system are incomplete. We study the problem of correcting an unrealizable specification $ϕ$ by computing an environment assumption $ψ$ such that the new specification $ψ\toϕ$ is realizable. Our aim is to construct an assumption $ψ$ that constrains only the environment and is as weak as possible. We present a two-step algorithm for computing assumptions. The algorithm operates on the game graph that is used to answer the realizability question. First, we compute a safety assumption that removes a minimal set of environment edges from the graph. Second, we compute a liveness assumption that puts fairness conditions on some of the remaining environment edges. We show that the problem of finding a minimal set of fair edges is computationally hard, and we use probabilistic games to compute a locally minimal fairness assumption.
Building Financial Accuracy into Spreadsheets
Venue: arXiv cs.SE 2008
Year: 2008

Students learning how to apply spreadsheets to accounting problems are not always well served by the built-in financial functions. Problems can arise because of differences between UK and US practice, through anomalies in the functions themselves, and because the promptings of Wizards' engender an attitude of filling in the blanks on the screen, and hoping for the best. Some examples of these problems are described, and suggestions are presented for ways of improving the situation. Principally, it is suggested that spreadsheet prompts and 'Help' screens should offer integrated guidance, covering some aspects of financial practice, as well as matters of spreadsheet technique.
On the Capacity of Wireless Multicast Networks
Venue: arXiv cs.IT 2008
Year: 2008

The problem of maximizing the average rate in a multicast network subject to a coverage constraint (minimum quality of service) is studied. Assuming the channel state information is available only at the receiver side and single antenna nodes, the highest expected rate achievable by a random user in the network, called expected typical rate, is derived in two scenarios: hard coverage constraint and soft coverage constraint. In the first case, the coverage is expressed in terms of the outage probability, while in the second case, the expected rate should satisfy certain minimum requirement. It is shown that the optimum solution in both cases (achieving the highest expected typical rate for given coverage requirements) is achieved by an infinite layer superposition code for which the optimum power allocation among the different layers is derived. For the MISO case, a suboptimal coding scheme is proposed, which is shown to be asymptotically optimal, when the number of transmit antennas grows at least logarithmically with the number of users in the network.
Optimal Coding for the Erasure Channel with Arbitrary Alphabet Size
Venue: arXiv cs.IT 2008
Year: 2008

An erasure channel with a fixed alphabet size $q$, where $q \gg 1$, is studied. It is proved that over any erasure channel (with or without memory), Maximum Distance Separable (MDS) codes achieve the minimum probability of error (assuming maximum likelihood decoding). Assuming a memoryless erasure channel, the error exponent of MDS codes are compared with that of random codes and linear random codes. It is shown that the envelopes of all these exponents are identical for rates above the critical rate. Noting the optimality of MDS codes, it is concluded that both random codes and linear random codes are exponentially optimal, whether the block sizes is larger or smaller than the alphabet size.
Exact Matrix Completion via Convex Optimization
Venue: arXiv cs.IT 2008
Year: 2008

We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen? We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys m >= C n^{1.2} r log n for some positive numerical constant C, then with very high probability, most n by n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show that objects other than signals and images can be perfectly reconstructed from very limited information.
Rock mechanics modeling based on soft granulation theory
Venue: arXiv cs.AI 2008
Year: 2008

This paper describes application of information granulation theory, on the design of rock engineering flowcharts. Firstly, an overall flowchart, based on information granulation theory has been highlighted. Information granulation theory, in crisp (non-fuzzy) or fuzzy format, can take into account engineering experiences (especially in fuzzy shape-incomplete information or superfluous), or engineering judgments, in each step of designing procedure, while the suitable instruments modeling are employed. In this manner and to extension of soft modeling instruments, using three combinations of Self Organizing Map (SOM), Neuro-Fuzzy Inference System (NFIS), and Rough Set Theory (RST) crisp and fuzzy granules, from monitored data sets are obtained. The main underlined core of our algorithms are balancing of crisp(rough or non-fuzzy) granules and sub fuzzy granules, within non fuzzy information (initial granulation) upon the open-close iterations. Using different criteria on balancing best granules (information pockets), are obtained. Validations of our proposed methods, on the data set of in-situ permeability in rock masses in Shivashan dam, Iran have been highlighted.
On White-box Cryptography and Obfuscation
Venue: arXiv cs.CR 2008
Year: 2008

We study the relationship between obfuscation and white-box cryptography. We capture the requirements of any white-box primitive using a \emph{White-Box Property (WBP)} and give some negative/positive results. Loosely speaking, the WBP is defined for some scheme and a security notion (we call the pair a \emph{specification}), and implies that w.r.t. the specification, an obfuscation does not leak any ``useful'' information, even though it may leak some ``useless'' non-black-box information. Our main result is a negative one - for most interesting programs, an obfuscation (under \emph{any} definition) cannot satisfy the WBP for every specification in which the program may be present. To do this, we define a \emph{Universal White-Box Property (UWBP)}, which if satisfied, would imply that under \emph{whatever} specification we conceive, the WBP is satisfied. We then show that for every non-approximately-learnable family, there exist (contrived) specifications for which the WBP (and thus, the UWBP) fails. On the positive side, we show that there exists an obfuscator for a non-approximately-learnable family that achieves the WBP for a certain specification. Furthermore, there exists an obfuscator for a non-learnable (but approximately-learnable) family that achieves the UWBP. Our results can also be viewed as formalizing the distinction between ``useful'' and ``useless'' non-black-box information.
La fiabilité des informations sur le web
Venue: arXiv cs.IR 2008
Year: 2008

Online IR tools have to take into account new phenomena linked to the appearance of blogs, wiki and other collaborative publications. Among these collaborative sites, Wikipedia represents a crucial source of information. However, the quality of this information has been recently questionned. A better knowledge of the contributors' behaviors should help users navigate through information whose quality may vary from one source to another. In order to explore this idea, we present an analysis of the role of different types of contributors in the control of the publication of conflictual articles.
Pattern-based Model-to-Model Transformation: Long Version
Venue: arXiv cs.SE 2008
Year: 2008

We present a new, high-level approach for the specification of model-to-model transformations based on declarative patterns. These are (atomic or composite) constraints on triple graphs declaring the allowed or forbidden relationships between source and target models. In this way, a transformation is defined by specifying a set of triple graph constraints that should be satisfied by the result of the transformation. The description of the transformation is then compiled into lower-level operational mechanisms to perform forward or backward transformations, as well as to establish mappings between two existent models. In this paper we study one of such mechanisms based on the generation of operational triple graph grammar rules. Moreover, we exploit deduction techniques at the specification level to generate more specialized constraints (preserving the specification semantics) reflecting pattern dependencies, from which additional rules can be derived. This is an extended version of the paper submitted to ICGT'08, with additional definitions and proofs.
New Construction of 2-Generator Quasi-Twisted Codes
Venue: arXiv cs.IT 2008
Year: 2008

Quasi-twisted (QT) codes are a generalization of quasi-cyclic (QC) codes. Based on consta-cyclic simplex codes, a new explicit construction of a family of 2-generator quasi-twisted (QT) two-weight codes is presented. It is also shown that many codes in the family meet the Griesmer bound and therefore are length-optimal. New distance-optimal binary QC [195, 8, 96], [210, 8, 104] and [240, 8, 120] codes, and good ternary QC [208, 6, 135] and [221, 6, 144] codes are also obtained by the construction.
Canonical calculi with (n,k)-ary quantifiers
Venue: arXiv cs.LO 2008
Year: 2008

Propositional canonical Gentzen-type systems, introduced in 2001 by Avron and Lev, are systems which in addition to the standard axioms and structural rules have only logical rules in which exactly one occurrence of a connective is introduced and no other connective is mentioned. A constructive coherence criterion for the non-triviality of such systems was defined and it was shown that a system of this kind admits cut-elimination iff it is coherent. The semantics of such systems is provided using two-valued non-deterministic matrices (2Nmatrices). In 2005 Zamansky and Avron extended these results to systems with unary quantifiers of a very restricted form. In this paper we substantially extend the characterization of canonical systems to (n,k)-ary quantifiers, which bind k distinct variables and connect n formulas, and show that the coherence criterion remains constructive for such systems. Then we focus on the case of k∈{0,1} and for a canonical calculus G show that it is coherent precisely when it has a strongly characteristic 2Nmatrix, which in turn is equivalent to admitting strong cut-elimination.
GuiLiner: A Configurable and Extensible Graphical User Interface for Scientific Analysis and Simulation Software
Venue: arXiv cs.HC 2008
Year: 2008

The computer programs most users interact with daily are driven by a graphical user interface (GUI). However, many scientific applications are used with a command line interface (CLI) for the ease of development and increased flexibility this mode provides. Scientific application developers would benefit from being able to provide a GUI easily for their CLI programs, thus retaining the advantages of both modes of interaction. GuiLiner is a generic, extensible and flexible front-end designed to ``host'' a wide variety of data analysis or simulation programs. Scientific application developers who produce a correctly formatted XML file describing their program's options and some of its documentation can immediately use GuiLiner to produce a carefully implemented GUI for their analysis or simulation programs.
Directional Cross Diamond Search Algorithm for Fast Block Motion Estimation
Venue: arXiv cs.CV 2008
Year: 2008

In block-matching motion estimation (BMME), the search patterns have a significant impact on the algorithm's performance, both the search speed and the search quality. The search pattern should be designed to fit the motion vector probability (MVP) distribution characteristics of the real-world sequences. In this paper, we build a directional model of MVP distribution to describe the directional-center-biased characteristic of the MVP distribution and the directional characteristics of the conditional MVP distribution more exactly based on the detailed statistical data of motion vectors of eighteen popular sequences. Three directional search patterns are firstly designed by utilizing the directional characteristics and they are the smallest search patterns among the popular ones. A new algorithm is proposed using the horizontal cross search pattern as the initial step and the horizontal/vertical diamond search pattern as the subsequent step for the fast BMME, which is called the directional cross diamond search (DCDS) algorithm. The DCDS algorithm can obtain the motion vector with fewer search points than CDS, DS or HEXBS while maintaining the similar or even better search quality. The gain on speedup of DCDS over CDS or DS can be up to 54.9%. The simulation results show that DCDS is efficient, effective and robust, and it can always give the faster search speed on different sequences than other fast block-matching algorithm in common use.
On convergence-sensitive bisimulation and the embedding of CCS in timed CCS
Venue: arXiv cs.LO 2008
Year: 2008

We propose a notion of convergence-sensitive bisimulation that is built just over the notions of (internal) reduction and of (static) context. In the framework of timed CCS, we characterise this notion of `contextual' bisimulation via the usual labelled transition system. We also remark that it provides a suitable semantic framework for a fully abstract embedding of untimed processes into timed ones. Finally, we show that the notion can be refined to include sensitivity to divergence.
Significant Diagnostic Counterexamples in Probabilistic Model Checking
Venue: arXiv cs.LO 2008
Year: 2008

This paper presents a novel technique for counterexample generation in probabilistic model checking of Markov Chains and Markov Decision Processes. (Finite) paths in counterexamples are grouped together in witnesses that are likely to provide similar debugging information to the user. We list five properties that witnesses should satisfy in order to be useful as debugging aid: similarity, accuracy, originality, significance, and finiteness. Our witnesses contain paths that behave similar outside strongly connected components. This papers shows how to compute these witnesses by reducing the problem of generating counterexamples for general properties over Markov Decision Processes, in several steps, to the easy problem of generating counterexamples for reachability properties over acyclic Markov Chains.
The Separation of Duty with Privilege Calculus
Venue: arXiv cs.CR 2008
Year: 2008

This paper presents Privilege Calculus (PC) as a new approach of knowledge representation for Separation of Duty (SD) in the view of process and intents to improve the reconfigurability and traceability of SD. PC presumes that the structure of SD should be reduced to the structure of privilege and then the regulation of system should be analyzed with the help of forms of privilege.
An Identity Based Strong Bi-Designated Verifier (t, n) Threshold Proxy Signature Scheme
Venue: arXiv cs.CR 2008
Year: 2008

Proxy signature schemes have been invented to delegate signing rights. The paper proposes a new concept of Identify Based Strong Bi-Designated Verifier threshold proxy signature (ID-SBDVTPS) schemes. Such scheme enables an original signer to delegate the signature authority to a group of 'n' proxy signers with the condition that 't' or more proxy signers can cooperatively sign messages on behalf of the original signer and the signatures can only be verified by any two designated verifiers and that they cannot convince anyone else of this fact.
Control-Scheduling Codesign: A Perspective on Integrating Control and Computing
Venue: arXiv cs.OH 2008
Year: 2008

Despite rapid evolution, embedded computing systems increasingly feature resource constraints and workload uncertainties. To achieve much better system performance in unpredictable environments than traditional design approaches, a novel methodology, control-scheduling codesign, is emerging in the context of integrating feedback control and real-time computing. The aim of this work is to provide a better understanding of this emerging methodology and to spark new interests and developments in both the control and computer science communities. The state of the art of control-scheduling codesign is captured. Relevant research efforts in the literature are discussed under two categories, i.e., control of computing systems and codesign for control systems. Critical open research issues on integrating control and computing are also outlined.
The Lotus-Eater Attack
Venue: arXiv cs.NI 2008
Year: 2008

Many protocols for distributed and peer-to-peer systems have the feature that nodes will stop providing service for others once they have received a certain amount of service. Examples include BitTorent's unchoking policy, BAR Gossip's balanced exchanges, and threshold strategies in scrip systems. An attacker can exploit this by providing service in a targeted way to prevent chosen nodes from providing service. While such attacks cannot be prevented, we discuss techniques that can be used to limit the damage they do. These techniques presume that a certain number of processes will follow the recommended protocol, even if they could do better by ``gaming'' the system.
Full Abstraction for a Recursively Typed Lambda Calculus with Parallel Conditional
Venue: arXiv cs.LO 2008
Year: 2008

We define the syntax and reduction relation of a recursively typed lambda calculus with a parallel case-function (a parallel conditional). The reduction is shown to be confluent. We interpret the recursive types as information systems in a restricted form, which we call prime systems. A denotational semantics is defined with this interpretation. We define the syntactical normal form approximations of a term and prove the Approximation Theorem: The semantics of a term equals the limit of the semantics of its approximations. The proof uses inclusive predicates (logical relations). The semantics is adequate with respect to the observation of Boolean values. It is also fully abstract in the presence of the parallel case-function.