OpenRaiser/Intern-Atlas huggingface dataset:
Mathematical Model for Transformation of Sentences from Active Voice to Passive Voice
Venue: arXiv cs.CL 2009
Year: 2009

Formal work in linguistics has both produced and used important mathematical tools. Motivated by a survey of models for context and word meaning, syntactic categories, phrase structure rules and trees, an attempt is being made in the present paper to present a mathematical model for structuring of sentences from active voice to passive voice, which is is the form of a transitive verb whose grammatical subject serves as the patient, receiving the action of the verb. For this purpose we have parsed all sentences of a corpus and have generated Boolean groups for each of them. It has been observed that when we take constituents of the sentences as subgroups, the sequences of phrases form permutation roups. Application of isomorphism property yields permutation mapping between the important subgroups. It has resulted in a model for transformation of sentences from active voice to passive voice. A computer program has been written to enable the software developers to evolve grammar software for sentence transformations.
Computing Cylindrical Algebraic Decomposition via Triangular Decomposition
Venue: arXiv cs.SC 2009
Year: 2009

Cylindrical algebraic decomposition is one of the most important tools for computing with semi-algebraic sets, while triangular decomposition is among the most important approaches for manipulating constructible sets. In this paper, for an arbitrary finite set $F \subset {\R}[y_1, ..., y_n]$ we apply comprehensive triangular decomposition in order to obtain an $F$-invariant cylindrical decomposition of the $n$-dimensional complex space, from which we extract an $F$-invariant cylindrical algebraic decomposition of the $n$-dimensional real space. We report on an implementation of this new approach for constructing cylindrical algebraic decompositions.
Sequences close to periodic
Venue: arXiv cs.DM 2009
Year: 2009

The paper is a survey of notions and results related to classical and new generalizations of the notion of a periodic sequence. The topics related to almost periodicity in combinatorics on words, symbolic dynamics, expressibility in logical theories, algorithmic computability, Kolmogorov complexity, number theory, are discussed.
Cooperative Update Exchange in the Youtopia System
Venue: arXiv cs.DB 2009
Year: 2009

Youtopia is a platform for collaborative management and integration of relational data. At the heart of Youtopia is an update exchange abstraction: changes to the data propagate through the system to satisfy user-specified mappings. We present a novel change propagation model that combines a deterministic chase with human intervention. The process is fundamentally cooperative and gives users significant control over how mappings are repaired. An additional advantage of our model is that mapping cycles can be permitted without compromising correctness. We investigate potential harmful interference between updates in our model; we introduce two appropriate notions of serializability that avoid such interference if enforced. The first is very general and related to classical final-state serializability; the second is more restrictive but highly practical and related to conflict-serializability. We present an algorithm to enforce the latter notion. Our algorithm is an optimistic one, and as such may sometimes require updates to be aborted. We develop techniques for reducing the number of aborts and we test these experimentally.
Visual approach for data mining on medical information databases using Fastmap algorithm
Venue: arXiv cs.IR 2009
Year: 2009

The rapid development of tools for acquisition and storage of information has lead to the formation of enormous medical databases. The large quantity of data definitely surpasses the abilities of humans for efficient usage without specialized tools for analysis. The situation is described as rich in data, but poor in information. In order to fill this growing gap, different approaches from the field of Data Mining are applied. These methods perform analysis of large sets of observed data in order to find new dependencies or concise representation of the data, which is more meaningful to humans. One of the possible approaches for discovery of dependencies is the visual approach, in which data is processed and visualized in a way suitable for analysis by a domain expert. This work proposes a visual approach, in which data is processed and visualized in a way suitable for analysis by a domain expert. We design and implement a software solution for visualization of multi-dimensional, classified medical data using the FastMap algorithm for graduate reduction of dimensions. The implementation of the graphical user interface is described in detail since it is the most important factor for the ease of use of these tools by non-professionals in data mining.
What Do Family Caregivers of Alzheimer's Disease Patients Desire in Smart Home Technologies?
Venue: arXiv cs.CY 2009
Year: 2009

Objectives - The authors' aim was to investigate the representations, wishes, and fears of family caregivers (FCs) regarding 14 innovative technologies (IT) for care aiding and burden alleviation, given the severe physical and psychological stress induced by dementia care, and the very slow uptake of these technologies in our society. Methods - A cluster sample survey based on a self-administered questionnaire was carried out on data collected from 270 families of patients with Alzheimer's disease or related disorders, located in the greater Paris area. Multiple Correspondence Analysis was used in addition to usual statistical tests to identify homogenous FCs clusters concerning the appreciation or rejection of the considered technologies. Results - Two opposite clusters were clearly defined: FCs in favor of a substantial use of technology, and those rather or totally hostile. Furthermore the distributions of almost all the answers of appreciations were U shaped. Significant relations were demonstrated between IT appreciation and FC's family or gender statuses (e.g., female FCs appreciated more than male FCs a tracking device for quick recovering of wandering patients: p=0.0025, N=195). Conclusions - The study provides further evidence of the contrasted perception of technology in dementia care at home, and suggests the development of public debates based on rigorous assessment of practices and a strict ethical aim to protect against misuse.
Persistence and Success in the Attention Economy
Venue: arXiv cs.CY 2009
Year: 2009

A hallmark of the attention economy is the competition for the attention of others. Thus people persistently upload content to social media sites, hoping for the highly unlikely outcome of topping the charts and reaching a wide audience. And yet, an analysis of the production histories and success dynamics of 10 million videos from \texttt{YouTube} revealed that the more frequently an individual uploads content the less likely it is that it will reach a success threshold. This paradoxical result is further compounded by the fact that the average quality of submissions does increase with the number of uploads, with the likelihood of success less than that of playing a lottery.
Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we consider recovery of jointly sparse multichannel signals from incomplete measurements. Several approaches have been developed to recover the unknown sparse vectors from the given observations, including thresholding, simultaneous orthogonal matching pursuit (SOMP), and convex relaxation based on a mixed matrix norm. Typically, worst-case analysis is carried out in order to analyze conditions under which the algorithms are able to recover any jointly sparse set of vectors. However, such an approach is not able to provide insights into why joint sparse recovery is superior to applying standard sparse reconstruction methods to each channel individually. Previous work considered an average case analysis of thresholding and SOMP by imposing a probability model on the measured signals. In this paper, our main focus is on analysis of convex relaxation techniques. In particular, we focus on the mixed l_2,1 approach to multichannel recovery. We show that under a very mild condition on the sparsity and on the dictionary characteristics, measured for example by the coherence, the probability of recovery failure decays exponentially in the number of channels. This demonstrates that most of the time, multichannel sparse recovery is indeed superior to single channel methods. Our probability bounds are valid and meaningful even for a small number of signals. Using the tools we develop to analyze the convex relaxation method, we also tighten the previous bounds for thresholding and SOMP.
Optimal Supervisory Control Synthesis
Venue: arXiv cs.IT 2009
Year: 2009

The place invariant method is well known as an elegant way to construct a Petri net controller. It is possible to use the constraint for preventing forbidden states. But in general case, the number forbidden states can be very large giving a great number of control places. In this paper is presented a systematic method to reduce the size and the number of constraints. This method is applicable for safe and conservative Petri nets giving a maximally permissive controller.
A statistical mechanical interpretation of algorithmic information theory III: Composite systems and fixed points
Venue: arXiv cs.IT 2009
Year: 2009

The statistical mechanical interpretation of algorithmic information theory (AIT, for short) was introduced and developed by our former works [K. Tadaki, Local Proceedings of CiE 2008, pp.425-434, 2008] and [K. Tadaki, Proceedings of LFCS'09, Springer's LNCS, vol.5407, pp.422-440, 2009], where we introduced the notion of thermodynamic quantities, such as partition function Z(T), free energy F(T), energy E(T), and statistical mechanical entropy S(T), into AIT. We then discovered that, in the interpretation, the temperature T equals to the partial randomness of the values of all these thermodynamic quantities, where the notion of partial randomness is a stronger representation of the compression rate by means of program-size complexity. Furthermore, we showed that this situation holds for the temperature itself as a thermodynamic quantity, namely, for each of all the thermodynamic quantities above, the computability of its value at temperature T gives a sufficient condition for T in (0,1) to be a fixed point on partial randomness. In this paper, we develop the statistical mechanical interpretation of AIT further and pursue its formal correspondence to normal statistical mechanics. The thermodynamic quantities in AIT are defined based on the halting set of an optimal computer, which is a universal decoding algorithm used to define the notion of program-size complexity. We show that there are infinitely many optimal computers which give completely different sufficient conditions in each of the thermodynamic quantities in AIT. We do this by introducing the notion of composition of computers into AIT, which corresponds to the notion of composition of systems in normal statistical mechanics.
A New Key-Agreement-Protocol
Venue: arXiv cs.CR 2009
Year: 2009

A new 4-pass Key-Agreement Protocol is presented. The security of the protocol mainly relies on the existence of a (polynomial-computable) One-Way-Function and the supposed computational hardness of solving a specific system of equations.
Towards an explanatory and computational theory of scientific discovery
Venue: arXiv cs.GL 2009
Year: 2009

We propose an explanatory and computational theory of transformative discoveries in science. The theory is derived from a recurring theme found in a diverse range of scientific change, scientific discovery, and knowledge diffusion theories in philosophy of science, sociology of science, social network analysis, and information science. The theory extends the concept of structural holes from social networks to a broader range of associative networks found in science studies, especially including networks that reflect underlying intellectual structures such as co-citation networks and collaboration networks. The central premise is that connecting otherwise disparate patches of knowledge is a valuable mechanism of creative thinking in general and transformative scientific discovery in particular.
Intent expression using eye robot for mascot robot system
Venue: arXiv cs.RO 2009
Year: 2009

An intent expression system using eye robots is proposed for a mascot robot system from a viewpoint of humatronics. The eye robot aims at providing a basic interface method for an information terminal robot system. To achieve better understanding of the displayed information, the importance and the degree of certainty of the information should be communicated along with the main content. The proposed intent expression system aims at conveying this additional information using the eye robot system. Eye motions are represented as the states in a pleasure-arousal space model. Changes in the model state are calculated by fuzzy inference according to the importance and degree of certainty of the displayed information. These changes influence the arousal-sleep coordinates in the space that corresponds to levels of liveliness during communication. The eye robot provides a basic interface for the mascot robot system that is easy to be understood as an information terminal for home environments in a humatronics society.
A 3-approximation algorithm for computing a parsimonious first speciation in the gene duplication model
Venue: arXiv cs.DM 2009
Year: 2009

We consider the following problem: from a given set of gene families trees on a set of genomes, find a first speciation, that splits these genomes into two subsets, that minimizes the number of gene duplications that happened before this speciation. We call this problem the Minimum Duplication Bipartition Problem. Using a generalization of the Minimum Edge-Cut Problem, known as Submodular Function Minimization, we propose a polynomial time and space 3-approximation algorithm for the Minimum Duplication Bipartition Problem.
CP-logic: A Language of Causal Probabilistic Events and Its Relation to Logic Programming
Venue: arXiv cs.AI 2009
Year: 2009

This papers develops a logical language for representing probabilistic causal laws. Our interest in such a language is twofold. First, it can be motivated as a fundamental study of the representation of causal knowledge. Causality has an inherent dynamic aspect, which has been studied at the semantical level by Shafer in his framework of probability trees. In such a dynamic context, where the evolution of a domain over time is considered, the idea of a causal law as something which guides this evolution is quite natural. In our formalization, a set of probabilistic causal laws can be used to represent a class of probability trees in a concise, flexible and modular way. In this way, our work extends Shafer's by offering a convenient logical representation for his semantical objects. Second, this language also has relevance for the area of probabilistic logic programming. In particular, we prove that the formal semantics of a theory in our language can be equivalently defined as a probability distribution over the well-founded models of certain logic programs, rendering it formally quite similar to existing languages such as ICL or PRISM. Because we can motivate and explain our language in a completely self-contained way as a representation of probabilistic causal laws, this provides a new way of explaining the intuitions behind such probabilistic logic programs: we can say precisely which knowledge such a program expresses, in terms that are equally understandable by a non-logician. Moreover, we also obtain an additional piece of knowledge representation methodology for probabilistic logic programs, by showing how they can express probabilistic causal laws.
Joint Opportunistic Scheduling in Multi-Cellular Systems
Venue: arXiv cs.NI 2009
Year: 2009

We address the problem of multiuser scheduling with partial channel information in a multi-cell environment. The scheduling problem is formulated jointly with the ARQ based channel learning process and the intercell interference mitigating cell breathing protocol. The optimal joint scheduling policy under various system constraints is established. The general problem is posed as a generalized Restless Multiarmed Bandit process and the notion of indexability is studied. We conjecture, with numerical support, that the multicell multiuser scheduling problem is indexable and obtain a partial structure of the index policy.
First Person Singular
Venue: arXiv cs.OH 2009
Year: 2009

Brian Rotman argues that (one) "mind" and (one) "god" are only conceivable, literally, because of (alphabetic) literacy, which allowed us to designate each of these ghosts as an incorporeal, speaker-independent "I" (or, in the case of infinity, a notional agent that goes on counting forever). I argue that to have a mind is to have the capacity to feel. No one can be sure which organisms feel, hence have minds, but it seems likely that one-celled organisms and plants do not, whereas animals do. So minds originated before humans and before language --hence, a fortiori, before writing, whether alphabetic or ideographic.
Inferring Dynamic Bayesian Networks using Frequent Episode Mining
Venue: arXiv cs.LG 2009
Year: 2009

Motivation: Several different threads of research have been proposed for modeling and mining temporal data. On the one hand, approaches such as dynamic Bayesian networks (DBNs) provide a formal probabilistic basis to model relationships between time-indexed random variables but these models are intractable to learn in the general case. On the other, algorithms such as frequent episode mining are scalable to large datasets but do not exhibit the rigorous probabilistic interpretations that are the mainstay of the graphical models literature. Results: We present a unification of these two seemingly diverse threads of research, by demonstrating how dynamic (discrete) Bayesian networks can be inferred from the results of frequent episode mining. This helps bridge the modeling emphasis of the former with the counting emphasis of the latter. First, we show how, under reasonable assumptions on data characteristics and on influences of random variables, the optimal DBN structure can be computed using a greedy, local, algorithm. Next, we connect the optimality of the DBN structure with the notion of fixed-delay episodes and their counts of distinct occurrences. Finally, to demonstrate the practical feasibility of our approach, we focus on a specific (but broadly applicable) class of networks, called excitatory networks, and show how the search for the optimal DBN structure can be conducted using just information from frequent episodes. Application on datasets gathered from mathematical models of spiking neurons as well as real neuroscience datasets are presented. Availability: Algorithmic implementations, simulator codebases, and datasets are available from our website at http://neural-code.cs.vt.edu/dbn
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications
Venue: arXiv cs.CC 2009
Year: 2009

First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time exact solutions. Next, we consider the following general capacitated set cover problem. There is given a set of elements with real weights and a family S of sets of elements. One can use a set if it is a subset of one of the sets on our lists and the sum of weights is at most one. The goal is to cover all the elements with the allowed sets.<br>We show that any polynomial-time algorithm that approximates the un-capacitated version of the set cover problem with ratio r can be converted to an approximation algorithm for the capacitated version with ratio r + 1.357.In particular, the composition of these two results yields a polynomial-time approximation algorithm for the problem of covering a set of customers represented by a weighted n-point set with a minimum number of antennas of variable angular range and fixed capacity with ratio 2.357. Finally, we provide a PTAS for the dual problem where the number of sets (e.g., antennas) to use is fixed and the task is to minimize the maximum set load, in case the sets correspond to line intervals or arcs.
Source Coding with a Side Information "Vending Machine"
Venue: arXiv cs.IT 2009
Year: 2009

We study source coding in the presence of side information, when the system can take actions that affect the availability, quality, or nature of the side information. We begin by extending the Wyner-Ziv problem of source coding with decoder side information to the case where the decoder is allowed to choose actions affecting the side information. We then consider the setting where actions are taken by the encoder, based on its observation of the source. Actions may have costs that are commensurate with the quality of the side information they yield, and an overall per-symbol cost constraint may be imposed. We characterize the achievable tradeoffs between rate, distortion, and cost in some of these problem settings. Among our findings is the fact that even in the absence of a cost constraint, greedily choosing the action associated with the `best' side information is, in general, sub-optimal. A few examples are worked out.
Reliable Identification of RFID Tags Using Multiple Independent Reader Sessions
Venue: arXiv cs.IT 2009
Year: 2009

Radio Frequency Identification (RFID) systems are gaining momentum in various applications of logistics, inventory, etc. A generic problem in such systems is to ensure that the RFID readers can reliably read a set of RFID tags, such that the probability of missing tags stays below an acceptable value. A tag may be missing (left unread) due to errors in the communication link towards the reader e.g. due to obstacles in the radio path. The present paper proposes techniques that use multiple reader sessions, during which the system of readers obtains a running estimate of the probability to have at least one tag missing. Based on such an estimate, it is decided whether an additional reader session is required. Two methods are proposed, they rely on the statistical independence of the tag reading errors across different reader sessions, which is a plausible assumption when e.g. each reader session is executed on different readers. The first method uses statistical relationships that are valid when the reader sessions are independent. The second method is obtained by modifying an existing capture-recapture estimator. The results show that, when the reader sessions are independent, the proposed mechanisms provide a good approximation to the probability of missing tags, such that the number of reader sessions made, meets the target specification. If the assumption of independence is violated, the estimators are still useful, but they should be corrected by a margin of additional reader sessions to ensure that the target probability of missing tags is met.
Effective Bounds for P-Recursive Sequences
Venue: arXiv cs.SC 2009
Year: 2009

We describe an algorithm that takes as input a complex sequence $(u_n)$ given by a linear recurrence relation with polynomial coefficients along with initial values, and outputs a simple explicit upper bound $(v_n)$ such that $|u_n| \leq v_n$ for all $n$. Generically, the bound is tight, in the sense that its asymptotic behaviour matches that of $u_n$. We discuss applications to the evaluation of power series with guaranteed precision.
Subshifts, Languages and Logic
Venue: arXiv cs.DM 2009
Year: 2009

We study the Monadic Second Order (MSO) Hierarchy over infinite pictures, that is tilings. We give a characterization of existential MSO in terms of tilings and projections of tilings. Conversely, we characterise logic fragments corresponding to various classes of infinite pictures (subshifts of finite type, so?c subshifts).