OpenRaiser/Intern-Atlas huggingface dataset:
Second-Order Type Isomorphisms Through Game Semantics
Venue: arXiv cs.LO 2007
Year: 2007

The characterization of second-order type isomorphisms is a purely syntactical problem that we propose to study under the enlightenment of game semantics. We study this question in the case of second-order λ$μ$-calculus, which can be seen as an extension of system F to classical logic, and for which we deﬁne a categorical framework: control hyperdoctrines. Our game model of λ$μ$-calculus is based on polymorphic arenas (closely related to Hughes' hyperforests) which evolve during the play (following the ideas of Murawski-Ong). We show that type isomorphisms coincide with the "equality" on arenas associated with types. Finally we deduce the equational characterization of type isomorphisms from this equality. We also recover from the same model Roberto Di Cosmo's characterization of type isomorphisms for system F. This approach leads to a geometrical comprehension on the question of second order type isomorphisms, which can be easily extended to some other polymorphic calculi including additional programming features.
Truecluster matching
Venue: arXiv cs.AI 2007
Year: 2007

Cluster matching by permuting cluster labels is important in many clustering contexts such as cluster validation and cluster ensemble techniques. The classic approach is to minimize the euclidean distance between two cluster solutions which induces inappropriate stability in certain settings. Therefore, we present the truematch algorithm that introduces two improvements best explained in the crisp case. First, instead of maximizing the trace of the cluster crosstable, we propose to maximize a chi-square transformation of this crosstable. Thus, the trace will not be dominated by the cells with the largest counts but by the cells with the most non-random observations, taking into account the marginals. Second, we suggest a probabilistic component in order to break ties and to make the matching algorithm truly random on random data. The truematch algorithm is designed as a building block of the truecluster framework and scales in polynomial time. First simulation results confirm that the truematch algorithm gives more consistent truecluster results for unequal cluster sizes. Free R software is available.
Computing Integer Powers in Floating-Point Arithmetic
Venue: arXiv cs.NA 2007
Year: 2007

We introduce two algorithms for accurately evaluating powers to a positive integer in floating-point arithmetic, assuming a fused multiply-add (fma) instruction is available. We show that our log-time algorithm always produce faithfully-rounded results, discuss the possibility of getting correctly rounded results, and show that results correctly rounded in double precision can be obtained if extended-precision is available with the possibility to round into double precision (with a single rounding).
Motivation, Design, and Ubiquity: A Discussion of Research Ethics and Computer Science
Venue: arXiv cs.GL 2007
Year: 2007

Modern society is permeated with computers, and the software that controls them can have latent, long-term, and immediate effects that reach far beyond the actual users of these systems. This places researchers in Computer Science and Software Engineering in a critical position of influence and responsibility, more than any other field because computer systems are vital research tools for other disciplines. This essay presents several key ethical concerns and responsibilities relating to research in computing. The goal is to promote awareness and discussion of ethical issues among computer science researchers. A hypothetical case study is provided, along with questions for reflection and discussion.
Relating two standard notions of secrecy
Venue: arXiv cs.CR 2007
Year: 2007

Two styles of definitions are usually considered to express that a security protocol preserves the confidentiality of a data s. Reachability-based secrecy means that s should never be disclosed while equivalence-based secrecy states that two executions of a protocol with distinct instances for s should be indistinguishable to an attacker. Although the second formulation ensures a higher level of security and is closer to cryptographic notions of secrecy, decidability results and automatic tools have mainly focused on the first definition so far. This paper initiates a systematic investigation of the situations where syntactic secrecy entails strong secrecy. We show that in the passive case, reachability-based secrecy actually implies equivalence-based secrecy for digital signatures, symmetric and asymmetric encryption provided that the primitives are probabilistic. For active adversaries, we provide sufficient (and rather tight) conditions on the protocol for this implication to hold.
Non-Parametric Field Estimation using Randomly Deployed, Noisy, Binary Sensors
Venue: arXiv cs.IT 2007
Year: 2007

The reconstruction of a deterministic data field from binary-quantized noisy observations of sensors which are randomly deployed over the field domain is studied. The study focuses on the extremes of lack of deterministic control in the sensor deployment, lack of knowledge of the noise distribution, and lack of sensing precision and reliability. Such adverse conditions are motivated by possible real-world scenarios where a large collection of low-cost, crudely manufactured sensors are mass-deployed in an environment where little can be assumed about the ambient noise. A simple estimator that reconstructs the entire data field from these unreliable, binary-quantized, noisy observations is proposed. Technical conditions for the almost sure and integrated mean squared error (MSE) convergence of the estimate to the data field, as the number of sensors tends to infinity, are derived and their implications are discussed. For finite-dimensional, bounded-variation, and Sobolev-differentiable function classes, specific integrated MSE decay rates are derived. For the first and third function classes these rates are found to be minimax order optimal with respect to infinite precision sensing and known noise distribution.
Probabilistic Interval Temporal Logic and Duration Calculus with Infinite Intervals: Complete Proof Systems
Venue: arXiv cs.LO 2007
Year: 2007

The paper presents probabilistic extensions of interval temporal logic (ITL) and duration calculus (DC) with infinite intervals and complete Hilbert-style proof systems for them. The completeness results are a strong completeness theorem for the system of probabilistic ITL with respect to an abstract semantics and a relative completeness theorem for the system of probabilistic DC with respect to real-time semantics. The proposed systems subsume probabilistic real-time DC as known from the literature. A correspondence between the proposed systems and a system of probabilistic interval temporal logic with finite intervals and expanding modalities is established too.
Applying Test-Paradigms in a Generic Tutoring System Concept for Web-based Learning
Venue: arXiv cs.CY 2007
Year: 2007

Realizing test scenarios through a tutoring system involve questions about architecture and didactic methods in such a system. Observing the fact that traditional tutoring systems normally are domain-static, this paper shows investigations for a generic domain-independent tutoring system for utilizing test scenarios in computer-based and web-based environments. Furthermore, test paradigms are analyzed and it is presented an approach for realizing functionality for applying test paradigms in the presented generic tutoring system architecture by an XML-specified language.
Inquiring the Potential of Evoking Small-World Properties for Self-Organizing Communication Networks
Venue: arXiv cs.NI 2007
Year: 2007

Mobile multi-hop ad hoc networks allow establishing local groups of communicating devices in a self-organizing way. However, in a global setting such networks fail to work properly due to network partitioning. Providing that devices are capable of communicating both locally-e.g. using Wi-Fi or Bluetooth-and additionally also with arbitrary remote devices-e.g. using GSM/UMTS links-the objective is to find efficient ways of inter-linking multiple network partitions. Tackling this problem of topology control, we focus on the class of small-world networks that obey two distinguishing characteristics: they have a strong local clustering while still retaining a small average distance between two nodes. This paper reports on results gained investigating the question if small-world properties are indicative for an efficient link management in multiple multi-hop ad hoc network partitions.
Redesigning Computer-based Learning Environments: Evaluation as Communication
Venue: arXiv cs.CY 2007
Year: 2007

In the field of evaluation research, computer scientists live constantly upon dilemmas and conflicting theories. As evaluation is differently perceived and modeled among educational areas, it is not difficult to become trapped in dilemmas, which reflects an epistemological weakness. Additionally, designing and developing a computer-based learning scenario is not an easy task. Advancing further, with end-users probing the system in realistic settings, is even harder. Computer science research in evaluation faces an immense challenge, having to cope with contributions from several conflicting and controversial research fields. We believe that deep changes must be made in our field if we are to advance beyond the CBT (computer-based training) learning model and to build an adequate epistemology for this challenge. The first task is to relocate our field by building upon recent results from philosophy, psychology, social sciences, and engineering. In this article we locate evaluation in respect to communication studies. Evaluation presupposes a definition of goals to be reached, and we suggest that it is, by many means, a silent communication between teacher and student, peers, and institutional entities. If we accept that evaluation can be viewed as set of invisible rules known by nobody, but somehow understood by everybody, we should add anthropological inquiries to our research toolkit. The paper is organized around some elements of the social communication and how they convey new insights to evaluation research for computer and related scientists. We found some technical limitations and offer discussions on how we relate to technology at same time we establish expectancies and perceive others work.
Developing a Collaborative and Autonomous Training and Learning Environment for Hybrid Wireless Networks
Venue: arXiv cs.CY 2007
Year: 2007

With larger memory capacities and the ability to link into wireless networks, more and more students uses palmtop and handheld computers for learning activities. However, existing software for Web-based learning is not well-suited for such mobile devices, both due to constrained user interfaces as well as communication effort required. A new generation of applications for the learning domain that is explicitly designed to work on these kinds of small mobile devices has to be developed. For this purpose, we introduce CARLA, a cooperative learning system that is designed to act in hybrid wireless networks. As a cooperative environment, CARLA aims at disseminating teaching material, notes, and even components of itself through both fixed and mobile networks to interested nodes. Due to the mobility of nodes, CARLA deals with upcoming problems such as network partitions and synchronization of teaching material, resource dependencies, and time constraints.
Duality and Stability Regions of Multi-rate Broadcast and Multiple Access Networks
Venue: arXiv cs.IT 2007
Year: 2007

We characterize stability regions of two-user fading Gaussian multiple access (MAC) and broadcast (BC) networks with centralized scheduling. The data to be transmitted to the users is encoded into codewords of fixed length. The rates of the codewords used are restricted to a fixed set of finite cardinality. With successive decoding and interference cancellation at the receivers, we find the set of arrival rates that can be stabilized over the MAC and BC networks. In MAC and BC networks with average power constraints, we observe that the duality property that relates the MAC and BC information theoretic capacity regions extend to their stability regions as well. In MAC and BC networks with peak power constraints, the union of stability regions of dual MAC networks is found to be strictly contained in the BC stability region.
Evolutionary Mesh Numbering: Preliminary Results
Venue: arXiv cs.NA 2007
Year: 2007

Mesh numbering is a critical issue in Finite Element Methods, as the computational cost of one analysis is highly dependent on the order of the nodes of the mesh. This paper presents some preliminary investigations on the problem of mesh numbering using Evolutionary Algorithms. Three conclusions can be drawn from these experiments. First, the results of the up-to-date method used in all FEM softwares (Gibb's method) can be consistently improved; second, none of the crossover operators tried so far (either general or problem specific) proved useful; third, though the general tendency in Evolutionary Computation seems to be the hybridization with other methods (deterministic or heuristic), none of the presented attempt did encounter any success yet. The good news, however, is that this algorithm allows an improvement over the standard heuristic method between 12% and 20% for both the 1545 and 5453-nodes meshes used as test-bed. Finally, some strange interaction between the selection scheme and the use of problem specific mutation operator was observed, which appeals for further investigation.
Optimal Choice of Threshold in Two Level Processor Sharing
Venue: arXiv cs.NI 2007
Year: 2007

We analyze the Two Level Processor Sharing (TLPS) scheduling discipline with the hyper-exponential job size distribution and with the Poisson arrival process. TLPS is a convenient model to study the benefit of the file size based differentiation in TCP/IP networks. In the case of the hyper-exponential job size distribution with two phases, we find a closed form analytic expression for the expected sojourn time and an approximation for the optimal value of the threshold that minimizes the expected sojourn time. In the case of the hyper-exponential job size distribution with more than two phases, we derive a tight upper bound for the expected sojourn time conditioned on the job size. We show that when the variance of the job size distribution increases, the gain in system performance increases and the sensitivity to the choice of the threshold near its optimal value decreases.
A Methodology for Efficient Space-Time Adapter Design Space Exploration: A Case Study of an Ultra Wide Band Interleaver
Venue: arXiv cs.AR 2007
Year: 2007

This paper presents a solution to efficiently explore the design space of communication adapters. In most digital signal processing (DSP) applications, the overall architecture of the system is significantly affected by communication architecture, so the designers need specifically optimized adapters. By explicitly modeling these communications within an effective graph-theoretic model and analysis framework, we automatically generate an optimized architecture, named Space-Time AdapteR (STAR). Our design flow inputs a C description of Input/Output data scheduling, and user requirements (throughput, latency, parallelism...), and formalizes communication constraints through a Resource Constraints Graph (RCG). The RCG properties enable an efficient architecture space exploration in order to synthesize a STAR component. The proposed approach has been tested to design an industrial data mixing block example: an Ultra-Wideband interleaver.
Stability of boundary measures
Venue: arXiv cs.CG 2007
Year: 2007

We introduce the boundary measure at scale r of a compact subset of the n-dimensional Euclidean space. We show how it can be computed for point clouds and suggest these measures can be used for feature detection. The main contribution of this work is the proof a quantitative stability theorem for boundary measures using tools of convex analysis and geometric measure theory. As a corollary we obtain a stability result for Federer's curvature measures of a compact, allowing to compute them from point-cloud approximations of the compact.
Méthodologie de modélisation et d'implémentation d'adaptateurs spatio-temporels
Venue: arXiv cs.AR 2007
Year: 2007

The re-use of pre-designed blocks is a well-known concept of the software development. This technique has been applied to System-on-Chip (SoC) design whose complexity and heterogeneity are growing. The re-use is made thanks to high level components, called virtual components (IP), available in more or less flexible forms. These components are dedicated blocks: digital signal processing (DCT, FFT), telecommunications (Viterbi, TurboCodes),... These blocks rest on a model of fixed architecture with very few degrees of personalization. This rigidity is particularly true for the communication interface whose orders of acquisition and production of data, the temporal behavior and protocols of exchanges are fixed. The successful integration of such an IP requires that the designer (1) synchronizes the components (2) converts the protocols between "incompatible" blocks (3) temporizes the data to guarantee the temporal constraints and the order of the data. This phase remains however very manual and source of errors. Our approach proposes a formal modeling, based on an original Ressource Compatibility Graph. The synthesis flow is based on a set of transformations of the initial graph to lead to an interface architecture allowing the space-time adaptation of the data exchanges between several components.
WiFi Epidemiology: Can Your Neighbors' Router Make Yours Sick?
Venue: arXiv cs.CR 2007
Year: 2007

In densely populated urban areas WiFi routers form a tightly interconnected proximity network that can be exploited as a substrate for the spreading of malware able to launch massive fraudulent attack and affect entire urban areas WiFi networks. In this paper we consider several scenarios for the deployment of malware that spreads solely over the wireless channel of major urban areas in the US. We develop an epidemiological model that takes into consideration prevalent security flaws on these routers. The spread of such a contagion is simulated on real-world data for geo-referenced wireless routers. We uncover a major weakness of WiFi networks in that most of the simulated scenarios show tens of thousands of routers infected in as little time as two weeks, with the majority of the infections occurring in the first 24 to 48 hours. We indicate possible containment and prevention measure to limit the eventual harm of such an attack.
Approximately-Universal Space-Time Codes for the Parallel, Multi-Block and Cooperative-Dynamic-Decode-and-Forward Channels
Venue: arXiv cs.IT 2007
Year: 2007

Explicit codes are constructed that achieve the diversity-multiplexing gain tradeoff of the cooperative-relay channel under the dynamic decode-and-forward protocol for any network size and for all numbers of transmit and receive antennas at the relays. A particularly simple code construction that makes use of the Alamouti code as a basic building block is provided for the single relay case. Along the way, we prove that space-time codes previously constructed in the literature for the block-fading and parallel channels are approximately universal, i.e., they achieve the DMT for any fading distribution. It is shown how approximate universality of these codes leads to the first DMT-optimum code construction for the general, MIMO-OFDM channel.
Secure Nested Codes for Type II Wiretap Channels
Venue: arXiv cs.IT 2007
Year: 2007

This paper considers the problem of secure coding design for a type II wiretap channel, where the main channel is noiseless and the eavesdropper channel is a general binary-input symmetric-output memoryless channel. The proposed secure error-correcting code has a nested code structure. Two secure nested coding schemes are studied for a type II Gaussian wiretap channel. The nesting is based on cosets of a good code sequence for the first scheme and on cosets of the dual of a good code sequence for the second scheme. In each case, the corresponding achievable rate-equivocation pair is derived based on the threshold behavior of good code sequences. The two secure coding schemes together establish an achievable rate-equivocation region, which almost covers the secrecy capacity-equivocation region in this case study. The proposed secure coding scheme is extended to a type II binary symmetric wiretap channel. A new achievable perfect secrecy rate, which improves upon the previously reported result by Thangaraj et al., is derived for this channel.
Design of optimal convolutional codes for joint decoding of correlated sources in wireless sensor networks
Venue: arXiv cs.IT 2007
Year: 2007

We consider a wireless sensors network scenario where two nodes detect correlated sources and deliver them to a central collector via a wireless link. Differently from the Slepian-Wolf approach to distributed source coding, in the proposed scenario the sensing nodes do not perform any pre-compression of the sensed data. Original data are instead independently encoded by means of low-complexity convolutional codes. The decoder performs joint decoding with the aim of exploiting the inherent correlation between the transmitted sources. Complexity at the decoder is kept low thanks to the use of an iterative joint decoding scheme, where the output of each decoder is fed to the other decoder's input as a-priori information. For such scheme, we derive a novel analytical framework for evaluating an upper bound of joint-detection packet error probability and for deriving the optimum coding scheme. Experimental results confirm the validity of the analytical framework, and show that recursive codes allow a noticeable performance gain with respect to non-recursive coding schemes. Moreover, the proposed recursive coding scheme allows to approach the ideal Slepian-Wolf scheme performance in AWGN channel, and to clearly outperform it over fading channels on account of diversity gain due to correlation of information.
The Domino Problem of the Hyperbolic Plane Is Undecidable
Venue: arXiv cs.CG 2007
Year: 2007

In this paper, we prove that the general tiling problem of the hyperbolic plane is undecidable by proving a slightly stronger version using only a regular polygon as the basic shape of the tiles. The problem was raised by a paper of Raphael Robinson in 1971, in his famous simplified proof that the general tiling problem is undecidable for the Euclidean plane, initially proved by Robert Berger in 1966.
A Robust Linguistic Platform for Efficient and Domain specific Web Content Analysis
Venue: arXiv cs.AI 2007
Year: 2007

Web semantic access in specific domains calls for specialized search engines with enhanced semantic querying and indexing capacities, which pertain both to information retrieval (IR) and to information extraction (IE). A rich linguistic analysis is required either to identify the relevant semantic units to index and weight them according to linguistic specific statistical distribution, or as the basis of an information extraction process. Recent developments make Natural Language Processing (NLP) techniques reliable enough to process large collections of documents and to enrich them with semantic annotations. This paper focuses on the design and the development of a text processing platform, Ogmios, which has been developed in the ALVIS project. The Ogmios platform exploits existing NLP modules and resources, which may be tuned to specific domains and produces linguistically annotated documents. We show how the three constraints of genericity, domain semantic awareness and performance can be handled all together.