OpenRaiser/Intern-Atlas huggingface dataset:
BlenX-based compositional modeling of complex reaction mechanisms
Venue: arXiv cs.CE 2010
Year: 2010

Molecular interactions are wired in a fascinating way resulting in complex behavior of biological systems. Theoretical modeling provides a useful framework for understanding the dynamics and the function of such networks. The complexity of the biological networks calls for conceptual tools that manage the combinatorial explosion of the set of possible interactions. A suitable conceptual tool to attack complexity is compositionality, already successfully used in the process algebra field to model computer systems. We rely on the BlenX programming language, originated by the beta-binders process calculus, to specify and simulate high-level descriptions of biological circuits. The Gillespie's stochastic framework of BlenX requires the decomposition of phenomenological functions into basic elementary reactions. Systematic unpacking of complex reaction mechanisms into BlenX templates is shown in this study. The estimation/derivation of missing parameters and the challenges emerging from compositional model building in stochastic process algebras are discussed. A biological example on circadian clock is presented as a case study of BlenX compositionality.
Optimal Control Strategies in Delayed Sharing Information Structures
Venue: arXiv cs.OH 2010
Year: 2010

The $n$-step delayed sharing information structure is investigated. This information structure comprises of $K$ controllers that share their information with a delay of $n$ time steps. This information structure is a link between the classical information structure, where information is shared perfectly between the controllers, and a non-classical information structure, where there is no "lateral" sharing of information among the controllers. Structural results for optimal control strategies for systems with such information structures are presented. A sequential methodology for finding the optimal strategies is also derived. The solution approach provides an insight for identifying structural results and sequential decomposition for general decentralized stochastic control problems.
Window-Based Greedy Contention Management for Transactional Memory
Venue: arXiv cs.DC 2010
Year: 2010

We consider greedy contention managers for transactional memory for M x N execution windows of transactions with M threads and N transactions per thread. Assuming that each transaction conflicts with at most C other transactions inside the window, a trivial greedy contention manager can schedule them within CN time. In this paper, we show that there are much better schedules. We present and analyze two new randomized greedy contention management algorithms. The first algorithm Offline-Greedy produces a schedule of length O(C + N log(MN)) with high probability, and gives competitive ratio O(log(MN)) for C <= N log(MN). The offline algorithm depends on knowing the conflict graph. The second algorithm Online-Greedy produces a schedule of length O(C log(MN) + N log^2(MN)) with high probability which is only a O(log(NM)) factor worse, but does not require knowledge of the conflict graph. We also give an adaptive version which achieves similar worst-case performance and C is determined on the fly under execution. Our algorithms provide new tradeoffs for greedy transaction scheduling that parameterize window sizes and transaction conflicts within the window.
Redundancy, Deduction Schemes, and Minimum-Size Bases for Association Rules
Venue: arXiv cs.LO 2010
Year: 2010

Association rules are among the most widely employed data analysis methods in the field of Data Mining. An association rule is a form of partial implication between two sets of binary variables. In the most common approach, association rules are parameterized by a lower bound on their confidence, which is the empirical conditional probability of their consequent given the antecedent, and/or by some other parameter bounds such as "support" or deviation from independence. We study here notions of redundancy among association rules from a fundamental perspective. We see each transaction in a dataset as an interpretation (or model) in the propositional logic sense, and consider existing notions of redundancy, that is, of logical entailment, among association rules, of the form "any dataset in which this first rule holds must obey also that second rule, therefore the second is redundant". We discuss several existing alternative definitions of redundancy between association rules and provide new characterizations and relationships among them. We show that the main alternatives we discuss correspond actually to just two variants, which differ in the treatment of full-confidence implications. For each of these two notions of redundancy, we provide a sound and complete deduction calculus, and we show how to construct complete bases (that is, axiomatizations) of absolutely minimum size in terms of the number of rules. We explore finally an approach to redundancy with respect to several association rules, and fully characterize its simplest case of two partial premises.
On Semantic Generalizations of the Bernays-Schönfinkel-Ramsey Class with Finite or Co-finite Spectra
Venue: arXiv cs.LO 2010
Year: 2010

Motivated by model-theoretic properties of the BSR class, we present a family of semantic classes of FO formulae with finite or co-finite spectra over a relational vocabulary Σ. A class in this family is denoted EBS_Σ(σ), where σis a subset of Σ. Formulae in EBS_Σ(σ) are preserved under substructures modulo a bounded core and modulo re-interpretation of predicates outside σ. We study properties of the family EBS_Σ= {EBS_Σ(σ) | σ\subseteq Σ}, e.g. classes in EBS_Σare spectrally indistinguishable, EBS_Σ(Σ) is semantically equivalent to BSR over Σ, and EBS_Σ(\emptyset) is the set of all FO formulae over Σwith finite or co-finite spectra. Furthermore, (EBS_Σ, \subseteq) forms a lattice isomorphic to the powerset lattice (\wp(Σ), \subseteq). This gives a natural semantic generalization of BSR as ascending chains in (EBS_Σ, \subseteq). Many well-known FO classes are semantically subsumed by EBS_Σ(Σ) or EBS_Σ(\emptyset). Our study provides alternative proofs of interesting results like the Loś-Tarski Theorem and the semantic subsumption of the Löwenheim class with equality by BSR. We also present a syntactic sub-class of EBS_Σ(σ) called EDP_Σ(σ) and give an expression for the size of the bounded cores of models of EDP_Σ(σ) formulae. We show that the EDP_Σ(σ) classes also form a lattice structure. Finally, we study some closure properties and applications of the classes presented.
Nonparametric Estimation and On-Line Prediction for General Stationary Ergodic Sources
Venue: arXiv cs.IT 2010
Year: 2010

We proposed a learning algorithm for nonparametric estimation and on-line prediction for general stationary ergodic sources. We prepare histograms each of which estimates the probability as a finite distribution, and mixture them with weights to construct an estimator. The whole analysis is based on measure theory. The estimator works whether the source is discrete or continuous. If it is stationary ergodic, then the measure theoretically given Kullback-Leibler information divided by the sequence length $n$ converges to zero as $n$ goes to infinity. In particular, for continuous sources, the method does not require existence of a probability density function.
Pebbling and Branching Programs Solving the Tree Evaluation Problem
Venue: arXiv cs.CC 2010
Year: 2010

We study restricted computation models related to the Tree Evaluation Problem}. The TEP was introduced in earlier work as a simple candidate for the (*very*) long term goal of separating L and LogDCFL. The input to the problem is a rooted, balanced binary tree of height h, whose internal nodes are labeled with binary functions on [k] = {1,...,k} (each given simply as a list of k^2 elements of [k]), and whose leaves are labeled with elements of [k]. Each node obtains a value in [k] equal to its binary function applied to the values of its children, and the output is the value of the root. The first restricted computation model, called Fractional Pebbling, is a generalization of the black/white pebbling game on graphs, and arises in a natural way from the search for good upper bounds on the size of nondeterministic branching programs (BPs) solving the TEP - for any fixed h, if the binary tree of height h has fractional pebbling cost at most p, then there are nondeterministic BPs of size O(k^p) solving the height h TEP. We prove a lower bound on the fractional pebbling cost of d-ary trees that is tight to within an additive constant for each fixed d. The second restricted computation model we study is a semantic restriction on (non)deterministic BPs solving the TEP - Thrifty BPs. Deterministic (resp. nondeterministic) thrifty BPs suffice to implement the best known algorithms for the TEP, based on black (resp. fractional) pebbling. In earlier work, for each fixed h a lower bound on the size of deterministic thrifty BPs was proved that is tight for sufficiently large k. We give an alternative proof that achieves the same bound for all k. We show the same bound still holds in a less-restricted model, and also that gradually weaker lower bounds can be obtained for gradually weaker restrictions on the model.
On Analysis and Evaluation of Multi-Sensory Cognitive Learning of a Mathematical Topic Using Artificial Neural Networks
Venue: arXiv cs.NE 2010
Year: 2010

This piece of research belongs to the field of educational assessment issue based upon the cognitive multimedia theory. Considering that theory; visual and auditory material should be presented simultaneously to reinforce the retention of a mathematical learned topic, a carefully computer-assisted learning (CAL) module is designed for development of a multimedia tutorial for our suggested mathematical topic. The designed CAL module is a multimedia tutorial computer package with visual and/or auditory material. So, via suggested computer package, Multi-Sensory associative memories and classical conditioning theories are practically applicable at an educational field (a children classroom). It is noticed that comparative practical results obtained are interesting for field application of CAL package with and without associated teacher's voice. Finally, the presented study highly recommends application of a novel teaching trend aiming to improve quality of children mathematical learning performance.
Network Coding-Aware Queue Management for TCP Flows over Coded Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

We are interested in unicast traffic over wireless networks that employ constructive inter-session network coding, including single-hop and multi-hop schemes. In this setting, TCP flows do not fully exploit the network coding opportunities due to their bursty behavior and due to the fact that TCP is agnostic to the underlying network coding. In order to improve the performance of TCP flows over coded wireless networks, we take the following steps. First, we formulate the problem as network utility maximization and we present a distributed solution. Second, mimicking the structure of the optimal solution, we propose a "network-coding aware" queue management scheme (NCAQM) at intermediate nodes; we make no changes to TCP or to the MAC protocol (802.11). We demonstrate, via simulation, that NCAQM significantly improves TCP performance compared to TCP over baseline schemes.
Threshold rules for online sample selection
Venue: arXiv cs.DS 2010
Year: 2010

We consider the following sample selection problem. We observe in an online fashion a sequence of samples, each endowed by a quality. Our goal is to either select or reject each sample, so as to maximize the aggregate quality of the subsample selected so far. There is a natural trade-off here between the rate of selection and the aggregate quality of the subsample. We show that for a number of such problems extremely simple and oblivious "threshold rules" for selection achieve optimal tradeoffs between rate of selection and aggregate quality in a probabilistic sense. In some cases we show that the same threshold rule is optimal for a large class of quality distributions and is thus oblivious in a strong sense.
Modelling and Verification of Multiple UAV Mission Using SMV
Venue: arXiv cs.LO 2010
Year: 2010

Model checking has been used to verify the correctness of digital circuits, security protocols, communication protocols, as they can be modelled by means of finite state transition model. However, modelling the behaviour of hybrid systems like UAVs in a Kripke model is challenging. This work is aimed at capturing the behaviour of an UAV performing cooperative search mission into a Kripke model, so as to verify it against the temporal properties expressed in Computation Tree Logic (CTL). SMV model checker is used for the purpose of model checking.
Profile Popularity in a Business-oriented Online Social Network
Venue: arXiv cs.CY 2010
Year: 2010

Analysing Online Social Networks (OSN), voluntarily maintained and automatically exploitable databases of electronic personal information, promises a wealth of insight into their users' behavior, interest, and utilization of these currently predominant services on the Internet. To understand popularity in OSN, we monitored a large sample of profiles from a highly popular network for three months, and analysed the relation between profile properties and their impression frequency. Evaluating the data indicates a strong relation between both the number of accepted contacts and the diligence of updating contacts versus the frequency of requests for a profile. Counter intuitively, the overall activity, gender, as well as participation span of users have no remarkable impact on their profile's popularity.
Unsupervised Supervised Learning II: Training Margin Based Classifiers without Labels
Venue: arXiv cs.LG 2010
Year: 2010

Many popular linear classifiers, such as logistic regression, boosting, or SVM, are trained by optimizing a margin-based risk function. Traditionally, these risk functions are computed based on a labeled dataset. We develop a novel technique for estimating such risks using only unlabeled data and the marginal label distribution. We prove that the proposed risk estimator is consistent on high-dimensional datasets and demonstrate it on synthetic and real-world data. In particular, we show how the estimate is used for evaluating classifiers in transfer learning, and for training classifiers with no labeled data whatsoever.
A definable number which cannot be approximated algorithmically
Venue: arXiv cs.CC 2010
Year: 2010

The Turing machine (TM) and the Church thesis have formalized the concept of computable number, this allowed to display non-computable numbers. This paper defines the concept of number "approachable" by a TM and shows that some (if not all) known non-computable numbers are approachable by TMs. Then an example of a number not approachable by a TM is given.
Polychronous Interpretation of Synoptic, a Domain Specific Modeling Language for Embedded Flight-Software
Venue: arXiv cs.PL 2010
Year: 2010

The SPaCIFY project, which aims at bringing advances in MDE to the satellite flight software industry, advocates a top-down approach built on a domain-specific modeling language named Synoptic. In line with previous approaches to real-time modeling such as Statecharts and Simulink, Synoptic features hierarchical decomposition of application and control modules in synchronous block diagrams and state machines. Its semantics is described in the polychronous model of computation, which is that of the synchronous language Signal.
Text Region Extraction from Business Card Images for Mobile Devices
Venue: arXiv cs.CV 2010
Year: 2010

Designing a Business Card Reader (BCR) for mobile devices is a challenge to the researchers because of huge deformation in acquired images, multiplicity in nature of the business cards and most importantly the computational constraints of the mobile devices. This paper presents a text extraction method designed in our work towards developing a BCR for mobile devices. At first, the background of a camera captured image is eliminated at a coarse level. Then, various rule based techniques are applied on the Connected Components (CC) to filter out the noises and picture regions. The CCs identified as text are then binarized using an adaptive but light-weight binarization technique. Experiments show that the text extraction accuracy is around 98% for a wide range of resolutions with varying computation time and memory requirements. The optimum performance is achieved for the images of resolution 1024x768 pixels with text extraction accuracy of 98.54% and, space and time requirements as 1.1 MB and 0.16 seconds respectively.
On the Secure Degrees-of-Freedom of the Multiple-Access-Channel
Venue: arXiv cs.IT 2010
Year: 2010

A $K$-user secure Gaussian Multiple-Access-Channel (MAC) with an external eavesdropper is considered in this paper. An achievable rate region is established for the secure discrete memoryless MAC. The secrecy sum capacity of the degraded Gaussian MIMO MAC is proven using Gaussian codebooks. For the non-degraded Gaussian MIMO MAC, an algorithm inspired by interference alignment technique is proposed to achieve the largest possible total Secure-Degrees-of-Freedom (S-DoF). When all the terminals are equipped with a single antenna, Gaussian codebooks have shown to be inefficient in providing a positive S-DoF. Instead, a novel secure coding scheme is proposed to achieve a positive S-DoF in the single antenna MAC. This scheme converts the single-antenna system into a multiple-dimension system with fractional dimensions. The achievability scheme is based on the alignment of signals into a small sub-space at the eavesdropper, and the simultaneous separation of the signals at the intended receiver. Tools from the field of Diophantine Approximation in number theory are used to analyze the probability of error in the coding scheme. It is proven that the total S-DoF of $\frac{K-1}{K}$ can be achieved for almost all channel gains. For the other channel gains, a multi-layer coding scheme is proposed to achieve a positive S-DoF. As a function of channel gains, therefore, the achievable S-DoF is discontinued.
Compress-and-Forward Performance in Low-SNR Relay Channels
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we study the Gaussian relay channels in the low signal-to-noise ratio (SNR) regime with the time-sharing compress-and-forward (CF) scheme, where at each time slot all the nodes keep silent at the first fraction of time and then transmit with CF at a higher peak power in the second fraction. Such a silent vs. active two-phase relay scheme is preferable in the low-SNR regime. With this setup, the upper and lower bounds on the minimum energy per bit required over the relay channel are established under both full-duplex and half-duplex relaying modes. In particular, the lower bound is derived by applying the max-flow min-cut capacity theorem; the upper bound is established with the aforementioned time-sharing CF scheme, and is further minimized by letting the active phase fraction decrease to zero at the same rate as the SNR value. Numerical results are presented to validate the theoretical results.
Properties of the Discrete Pulse Transform for Multi-Dimensional Arrays
Venue: arXiv cs.CV 2010
Year: 2010

This report presents properties of the Discrete Pulse Transform on multi-dimensional arrays introduced by the authors two or so years ago. The main result given here in Lemma 2.1 is also formulated in a paper to appear in IEEE Transactions on Image Processing. However, the proof, being too technical, was omitted there and hence it appears in full in this publication.
Precise Request Tracing and Performance Debugging for Multi-tier Services of Black Boxes
Venue: arXiv cs.DC 2010
Year: 2010

As more and more multi-tier services are developed from commercial components or heterogeneous middleware without the source code available, both developers and administrators need a precise request tracing tool to help understand and debug performance problems of large concurrent services of black boxes. Previous work fails to resolve this issue in several ways: they either accept the imprecision of probabilistic correlation methods, or rely on knowledge of protocols to isolate requests in pursuit of tracing accuracy. This paper introduces a tool named PreciseTracer to help debug performance problems of multi-tier services of black boxes. Our contributions are two-fold: first, we propose a precise request tracing algorithm for multi-tier services of black boxes, which only uses application-independent knowledge; secondly, we present a component activity graph abstraction to represent causal paths of requests and facilitate end-to-end performance debugging. The low overhead and tolerance of noise make PreciseTracer a promising tracing tool for using on production systems.
PhoenixCloud: Provisioning Resources for Heterogeneous Cloud Workloads
Venue: arXiv cs.DC 2010
Year: 2010

As more and more service providers choose Cloud platforms, a resource provider needs to provision resources and supporting runtime environments (REs) for heterogeneous workloads in different scenarios. Previous work fails to resolve this issue in several ways: (1) it fails to pay attention to diverse RE requirements, and does not enable creating coordinated REs on demand; (2) few work investigates coordinated resource provisioning for heterogeneous workloads. In this paper, our contributions are three-fold: (1) we present an RE agreement that expresses diverse RE requirements, and build an innovative system PhoenixCloud that enables a resource provider to create REs on demand according to RE agreements; (2) we propose two coordinated resource provisioning solutions for heterogeneous workloads in two typical Cloud scenarios: first, a large organization operates a private Cloud for two heterogeneous workloads; second, a large organization or two service providers running heterogeneous workloads revert to a public Cloud; and (3) A comprehensive evaluation has been performed in experiments. For typical workload traces of parallel batch jobs and Web services, our experiments show that: a) In the first Cloud scenario, when the throughput is almost same like that of a dedicated cluster system, our solution decreases the configuration size of cluster by about 40%; b) in the second scenario, our solution decreases not only the total resource consumption, but also the peak resource consumption maximally to 31% with respect to that of EC2 + RightScale solution.
Levels of Undecidability in Infinitary Rewriting: Normalization and Reachability
Venue: arXiv cs.LO 2010
Year: 2010

In [EGZ09] it has been shown that infinitary strong normalization (SNi) is Pi-1-1-complete. Suprisingly, it turns out that infinitary weak normalization (WNi) is a harder problem, being Pi-1-2-complete, and thereby strictly higher in the analytical hierarchy.