OpenRaiser/Intern-Atlas huggingface dataset:
A semantic space for modeling children's semantic memory
Venue: arXiv cs.CL 2008
Year: 2008

The goal of this paper is to present a model of children's semantic memory, which is based on a corpus reproducing the kinds of texts children are exposed to. After presenting the literature in the development of the semantic memory, a preliminary French corpus of 3.2 million words is described. Similarities in the resulting semantic space are compared to human data on four tests: association norms, vocabulary test, semantic judgments and memory tasks. A second corpus is described, which is composed of subcorpora corresponding to various ages. This stratified corpus is intended as a basis for developmental studies. Finally, two applications of these models of semantic memory are presented: the first one aims at tracing the development of semantic similarities paragraph by paragraph; the second one describes an implementation of a model of text comprehension derived from the Construction-integration model (Kintsch, 1988, 1998) and based on such models of semantic memory.
Uplink Macro Diversity of Limited Backhaul Cellular Network
Venue: arXiv cs.IT 2008
Year: 2008

In this work new achievable rates are derived, for the uplink channel of a cellular network with joint multicell processing, where unlike previous results, the ideal backhaul network has finite capacity per-cell. Namely, the cell sites are linked to the central joint processor via lossless links with finite capacity. The cellular network is abstracted by symmetric models, which render analytical treatment plausible. For this idealistic model family, achievable rates are presented for cell-sites that use compress-and-forward schemes combined with local decoding, for both Gaussian and fading channels. The rates are given in closed form for the classical Wyner model and the soft-handover model. These rates are then demonstrated to be rather close to the optimal unlimited backhaul joint processing rates, already for modest backhaul capacities, supporting the potential gain offered by the joint multicell processing approach. Particular attention is also given to the low-SNR characterization of these rates through which the effect of the limited backhaul network is explicitly revealed. In addition, the rate at which the backhaul capacity should scale in order to maintain the original high-SNR characterization of an unlimited backhaul capacity system is found.
A note on clique-width and tree-width for structures
Venue: arXiv cs.LO 2008
Year: 2008

We give a simple proof that the straightforward generalisation of clique-width to arbitrary structures can be unbounded on structures of bounded tree-width. This can be corrected by allowing fusion of elements.
Control-theoretic dynamic voltage scaling for embedded controllers
Venue: arXiv cs.OS 2008
Year: 2008

For microprocessors used in real-time embedded systems, minimizing power consumption is difficult due to the timing constraints. Dynamic voltage scaling (DVS) has been incorporated into modern microprocessors as a promising technique for exploring the trade-off between energy consumption and system performance. However, it remains a challenge to realize the potential of DVS in unpredictable environments where the system workload cannot be accurately known. Addressing system-level power-aware design for DVS-enabled embedded controllers, this paper establishes an analytical model for the DVS system that encompasses multiple real-time control tasks. From this model, a feedback control based approach to power management is developed to reduce dynamic power consumption while achieving good application performance. With this approach, the unpredictability and variability of task execution times can be attacked. Thanks to the use of feedback control theory, predictable performance of the DVS system is achieved, which is favorable to real-time applications. Extensive simulations are conducted to evaluate the performance of the proposed approach.
Investigating the use of Software Agents to Reduce The Risk of Undetected Errors in Strategic Spreadsheet Applications
Venue: arXiv cs.HC 2008
Year: 2008

There is an overlooked iceberg of problems in end user computing. Spreadsheets are developed by people who are very skilled in their main job function, be it finance, procurement, or production planning, but often have had no formal training in spreadsheet use. IT auditors focus on mainstream information systems but regard spreadsheets as user problems, outside their concerns. Internal auditors review processes, but not the tools that support decision making in these processes. This paper highlights the gaps between risk management and end user awareness in spreadsheet research. In addition the potential benefits of software agent technologies to the management of risk in spreadsheets are explored. This paper discusses the current research into end user computing and spreadsheet use awareness.
Checking the Quality of Clinical Guidelines using Automated Reasoning Tools
Venue: arXiv cs.AI 2008
Year: 2008

Requirements about the quality of clinical guidelines can be represented by schemata borrowed from the theory of abductive diagnosis, using temporal logic to model the time-oriented aspects expressed in a guideline. Previously, we have shown that these requirements can be verified using interactive theorem proving techniques. In this paper, we investigate how this approach can be mapped to the facilities of a resolution-based theorem prover, Otter, and a complementary program that searches for finite models of first-order statements, Mace. It is shown that the reasoning required for checking the quality of a guideline can be mapped to such fully automated theorem-proving facilities. The medical quality of an actual guideline concerning diabetes mellitus 2 is investigated in this way.
On the Security of Liaw et al.'s Scheme
Venue: arXiv cs.CR 2008
Year: 2008

Recently, Liaw et al. proposed a remote user authentication scheme using smartcards. They claimed a number of features of their scheme, e.g. a dictionary of verification tables is not required to authenticate users; users can choose their password freely; mutual authentication is provided between the user and the remote system; the communication cost and the computational cost are very low; users can update their password after the registration phase; a session key agreed by the user and the remote system is generated in every session; and the nonce-based scheme which does not require a timestamp (to solve the serious time synchronization problem) etc. In this paper We show that Liaw et al.'s scheme does not stand with various security requirements and is completely insecure. Keywords: Authentication, Smartcards, Remote system, Attack.
Outage and Local Throughput and Capacity of Random Wireless Networks
Venue: arXiv cs.IT 2008
Year: 2008

Outage probabilities and single-hop throughput are two important performance metrics that have been evaluated for certain specific types of wireless networks. However, there is a lack of comprehensive results for larger classes of networks, and there is no systematic approach that permits the convenient comparison of the performance of networks with different geometries and levels of randomness. The uncertainty cube is introduced to categorize the uncertainty present in a network. The three axes of the cube represent the three main potential sources of uncertainty in interference-limited networks: the node distribution, the channel gains (fading), and the channel access (set of transmitting nodes). For the performance analysis, a new parameter, the so-called {\em spatial contention}, is defined. It measures the slope of the outage probability in an ALOHA network as a function of the transmit probability $p$ at $p=0$. Outage is defined as the event that the signal-to-interference ratio (SIR) is below a certain threshold in a given time slot. It is shown that the spatial contention is sufficient to characterize outage and throughput in large classes of wireless networks, corresponding to different positions on the uncertainty cube. Existing results are placed in this framework, and new ones are derived. Further, interpreting the outage probability as the SIR distribution, the ergodic capacity of unit-distance links is determined and compared to the throughput achievable for fixed (yet optimized) transmission rates.
The Mixing Time of Glauber Dynamics for Colouring Regular Trees
Venue: arXiv cs.CC 2008
Year: 2008

We consider Metropolis Glauber dynamics for sampling proper $q$-colourings of the $n$-vertex complete $b$-ary tree when $3\leq q\leq b/2\ln(b)$. We give both upper and lower bounds on the mixing time. For fixed $q$ and $b$, our upper bound is $n^{O(b/\log b)}$ and our lower bound is $n^{Ω(b/q \log(b))}$, where the constants implicit in the $O()$ and $Ω()$ notation do not depend upon $n$, $q$ or $b$.
Drawing Binary Tanglegrams: An Experimental Evaluation
Venue: arXiv cs.DS 2008
Year: 2008

A binary tanglegram is a pair <S,T> of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics or software engineering, it is required that the individual trees are drawn crossing-free. A natural optimization problem, denoted tanglegram layout problem, is thus to minimize the number of crossings between inter-tree edges. The tanglegram layout problem is NP-hard and is currently considered both in application domains and theory. In this paper we present an experimental comparison of a recursive algorithm of Buchin et al., our variant of their algorithm, the algorithm hierarchy sort of Holten and van Wijk, and an integer quadratic program that yields optimal solutions.
Analysis of a procedure for inserting steganographic data into VoIP calls
Venue: arXiv cs.CR 2008
Year: 2008

The paper concerns performance analysis of a steganographic method, dedicated primarily for VoIP, which was recently filed for patenting under the name LACK. The performance of the method depends on the procedure of inserting covert data into the stream of audio packets. After a brief presentation of the LACK method, the paper focuses on analysis of the dependence of the insertion procedure on the probability distribution of VoIP call duration.
Histograms and Wavelets on Probabilistic Data
Venue: arXiv cs.DB 2008
Year: 2008

There is a growing realization that uncertain information is a first-class citizen in modern database management. As such, we need techniques to correctly and efficiently process uncertain data in database systems. In particular, data reduction techniques that can produce concise, accurate synopses of large probabilistic relations are crucial. Similar to their deterministic relation counterparts, such compact probabilistic data synopses can form the foundation for human understanding and interactive data exploration, probabilistic query planning and optimization, and fast approximate query processing in probabilistic database systems. In this paper, we introduce definitions and algorithms for building histogram- and wavelet-based synopses on probabilistic data. The core problem is to choose a set of histogram bucket boundaries or wavelet coefficients to optimize the accuracy of the approximate representation of a collection of probabilistic tuples under a given error metric. For a variety of different error metrics, we devise efficient algorithms that construct optimal or near optimal B-term histogram and wavelet synopses. This requires careful analysis of the structure of the probability distributions, and novel extensions of known dynamic-programming-based techniques for the deterministic domain. Our experiments show that this approach clearly outperforms simple ideas, such as building summaries for samples drawn from the data distribution, while taking equal or less time.
Fair Access Provisioning through Contention Parameter Adaptation in the IEEE 802.11e Infrastructure Basic Service Set
Venue: arXiv cs.NI 2008
Year: 2008

We present the station-based unfair access problem among the uplink and the downlink stations in the IEEE 802.11e infrastructure Basic Service Set (BSS) when the default settings of the Enhanced Distributed Channel Access (EDCA) parameters are used. We discuss how the transport layer protocol characteristics alleviate the unfairness problem. We design a simple, practical, and standard-compliant framework to be employed at the Access Point (AP) for fair and efficient access provisioning. A dynamic measurement-based EDCA parameter adaptation block lies in the core of this framework. The proposed framework is unique in the sense that it considers the characteristic differences of Transmission Control Protocol (TCP) and User Datagram Protocol (UDP) flows and the coexistence of stations with varying bandwidth or Quality-of-Service (QoS) requirements. Via simulations, we show that our solution provides short- and long-term fair access for all stations in the uplink and downlink employing TCP and UDP flows with non-uniform packet rates in a wired-wireless heterogeneous network. In the meantime, the QoS requirements of coexisting real-time flows are also maintained.
From a set of parts to an indivisible whole. Part III: Holistic space of multi-object relations
Venue: arXiv cs.OH 2008
Year: 2008

The previously described methodology for hierarchical grouping of objects through iterative averaging has been used for simulation of cooperative interactions between objects of a system with the purpose of investigation of the conformational organization of the system. Interactions between objects were analyzed within the space of an isotropic field of one of the objects (drifter). Such an isotropic field of an individual object can be viewed as a prototype of computer ego. It allows visualization of a holistic space of multi-object relations (HSMOR) which has a complex structure depending on the number of objects, their mutual arrangement in space, and the type of metric used for assessment of (dis)similarities between the objects. In the course of computer simulation of cooperative interactions between the objects, only those points of the space were registered which corresponded to transitions in hierarchical grouping. Such points appeared to aggregate into complex spatial structures determining a unique internal organization of a respective HSMOR. We describe some of the peculiarities of such structures, referred to by us as attractor membranes, and discuss their properties. We also demonstrate the peculiarities of the changing of intergroup similarities which occurs when a drifter infinitely moves away from the fixed objects.
Feedback Scheduling: An Event-Driven Paradigm
Venue: arXiv cs.OS 2008
Year: 2008

Embedded computing systems today increasingly feature resource constraints and workload variability, which lead to uncertainty in resource availability. This raises great challenges to software design and programming in multitasking environments. In this paper, the emerging methodology of feedback scheduling is introduced to address these challenges. As a closed-loop approach to resource management, feedback scheduling promises to enhance the flexibility and resource efficiency of various software programs through dynamically distributing available resources among concurrent tasks based on feedback information about the actual usage of the resources. With emphasis on the behavioral design of feedback schedulers, we describe a general framework of feedback scheduling in the context of real-time control applications. A simple yet illustrative feedback scheduling algorithm is given. From a programming perspective, we describe how to modify the implementation of control tasks to facilitate the application of feedback scheduling. An event-driven paradigm that combines time-triggered and event-triggered approaches is proposed for programming of the feedback scheduler. Simulation results argue that the proposed event-driven paradigm yields better performance than time-triggered paradigm in dynamic environments where the workload varies irregularly and unpredictably.
The Improvement of the Bound on Hash Family
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we study the bound on three kinds of hash family using the Singleton bound. To $ε-U(N; n, m)$ hash family, in the caes of $n>m^2>1$ and $1\geqε\geq ε_1(n, m)$, we get that the new bound is better. To $ε-\bigtriangleup U(N; n, m)$ hash family, in the case of $n>m>1$ and $1\geqε\geqε_3(n,m)$, the new bound is better. To $ε-SU(N; n, m)$ hash family, in the case of $n>2^m>2$ and $1\geqε\geq ε_4(n, m)$, we get that the new bound is better.
Bits through ARQs
Venue: arXiv cs.IT 2008
Year: 2008

A fundamental problem in dynamic frequency reuse is that the cognitive radio is ignorant of the amount of interference it inflicts on the primary license holder. A model for such a situation is proposed and analyzed. The primary sends packets across an erasure channel and employs simple ACK/NAK feedback (ARQs) to retransmit erased packets. Furthermore, its erasure probabilities are influenced by the cognitive radio's activity. While the cognitive radio does not know these interference characteristics, it can eavesdrop on the primary's ARQs. The model leads to strategies in which the cognitive radio adaptively adjusts its input based on the primary's ARQs thereby guaranteeing the primary exceeds a target packet rate. A relatively simple strategy whereby the cognitive radio transmits only when the primary's empirical packet rate exceeds a threshold is shown to have interesting universal properties in the sense that for unknown time-varying interference characteristics, the primary is guaranteed to meet its target rate. Furthermore, a more intricate version of this strategy is shown to be capacity-achieving for the cognitive radio when the interference characteristics are time-invariant.
Flexible Time-Triggered Sampling in Smart Sensor-Based Wireless Control Systems
Venue: arXiv cs.NI 2008
Year: 2008

Wireless control systems (WCSs) often have to operate in dynamic environments where the network traffic load may vary unpredictably over time. The sampling in sensors is conventionally time triggered with fixed periods. In this context, only worse-than-possible quality of control (QoC) can be achieved when the network is underloaded, while overloaded conditions may significantly degrade the QoC, even causing system instability. This is particularly true when the bandwidth of the wireless network is limited and shared by multiple control loops. To address these problems, a flexible time-triggered sampling scheme is presented in this work. Smart sensors are used to facilitate dynamic adjustment of sampling periods, which enhances the flexibility and resource efficiency of the system based on time-triggered sampling. Feedback control technology is exploited for adapting sampling periods in a periodic manner. The deadline miss ratio in each control loop is maintained at/around a desired level, regardless of workload variations. Simulation results show that the proposed sampling scheme is able to deal with dynamic and unpredictable variations in network traffic load. Compared to conventional time-triggered sampling, it leads to much better QoC in WCSs operating in dynamic environments.
Local Read-Write Operations in Sensor Networks
Venue: arXiv cs.OS 2008
Year: 2008

Designing protocols and formulating convenient programming units of abstraction for sensor networks is challenging due to communication errors and platform constraints. This paper investigates properties and implementation reliability for a \emph{local read-write} abstraction. Local read-write is inspired by the class of read-modify-write operations defined for shared-memory multiprocessor architectures. The class of read-modify-write operations is important in solving consensus and related synchronization problems for concurrency control. Local read-write is shown to be an atomic abstraction for synchronizing neighborhood states in sensor networks. The paper compares local read-write to similar lightweight operations in wireless sensor networks, such as read-all, write-all, and a transaction-based abstraction: for some optimistic scenarios, local read-write is a more efficient neighborhood operation. A partial implementation is described, which shows that three outcomes characterize operation response: success, failure, and cancel. A failure response indicates possible inconsistency for the operation result, which is the result of a timeout event at the operation's initiator. The paper presents experimental results on operation performance with different timeout values and situations of no contention, with some tests also on various neighborhood sizes.
Perfect Derived Propagators
Venue: arXiv cs.AI 2008
Year: 2008

When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear equations both with and without coefficients? Constraint variants are ubiquitous: implementing them requires considerable (if not prohibitive) effort and decreases maintainability, but will deliver better performance. This paper shows how to use variable views, previously introduced for an implementation architecture, to derive perfect propagator variants. A model for views and derived propagators is introduced. Derived propagators are proved to be indeed perfect in that they inherit essential properties such as correctness and domain and bounds consistency. Techniques for systematically deriving propagators such as transformation, generalization, specialization, and channeling are developed for several variable domains. We evaluate the massive impact of derived propagators. Without derived propagators, Gecode would require 140000 rather than 40000 lines of code for propagators.
Cardinality heterogeneities in Web service composition: Issues and solutions
Venue: arXiv cs.SE 2008
Year: 2008

Data exchanges between Web services engaged in a composition raise several heterogeneities. In this paper, we address the problem of data cardinality heterogeneity in a composition. Firstly, we build a theoretical framework to describe different aspects of Web services that relate to data cardinality, and secondly, we solve this problem by developing a solution for cardinality mediation based on constraint logic programming.
An adaptive routing strategy for packet delivery in complex networks
Venue: arXiv cs.NI 2008
Year: 2008

We present an efficient routing approach for delivering packets in complex networks. On delivering a message from a node to a destination, a node forwards the message to a neighbor by estimating the waiting time along the shortest path from each of its neighbors to the destination. This projected waiting time is dynamical in nature and the path through which a message is delivered would be adapted to the distribution of messages in the network. Implementing the approach on scale-free networks, we show that the present approach performs better than the shortest-path approach and another approach that takes into account of the waiting time only at the neighboring nodes. Key features in numerical results are explained by a mean field theory. The approach has the merit that messages are distributed among the nodes according to the capabilities of the nodes in handling messages.