OpenRaiser/Intern-Atlas huggingface dataset:
Properties of quasi-alphabetic tree bimorphisms
Venue: arXiv cs.CL 2009
Year: 2009

We study the class of quasi-alphabetic relations, i.e., tree transformations defined by tree bimorphisms with two quasi-alphabetic tree homomorphisms and a regular tree language. We present a canonical representation of these relations; as an immediate consequence, we get the closure under union. Also, we show that they are not closed under intersection and complement, and do not preserve most common operations on trees (branches, subtrees, v-product, v-quotient, f-top-catenation). Moreover, we prove that the translations defined by quasi-alphabetic tree bimorphism are exactly products of context-free string languages. We conclude by presenting the connections between quasi-alphabetic relations, alphabetic relations and classes of tree transformations defined by several types of top-down tree transducers. Furthermore, we get that quasi-alphabetic relations preserve the recognizable and algebraic tree languages.
Bounds on the Rate of 2-D Bit-Stuffing Encoders
Venue: arXiv cs.IT 2009
Year: 2009

A method for bounding the rate of bit-stuffing encoders for 2-D constraints is presented. Instead of considering the original encoder, we consider a related one which is quasi-stationary. We use the quasi-stationary property in order to formulate linear requirements that must hold on the probabilities of the constrained arrays that are generated by the encoder. These requirements are used as part of a linear program. The minimum and maximum of the linear program bound the rate of the encoder from below and from above, respectively. A lower bound on the rate of an encoder is also a lower bound on the capacity of the corresponding constraint. For some constraints, our results lead to tighter lower bounds than what was previously known.
Without a 'doubt'? Unsupervised discovery of downward-entailing operators
Venue: arXiv cs.CL 2009
Year: 2009

An important part of textual inference is making deductions involving monotonicity, that is, determining whether a given assertion entails restrictions or relaxations of that assertion. For instance, the statement 'We know the epidemic spread quickly' does not entail 'We know the epidemic spread quickly via fleas', but 'We doubt the epidemic spread quickly' entails 'We doubt the epidemic spread quickly via fleas'. Here, we present the first algorithm for the challenging lexical-semantics problem of learning linguistic constructions that, like 'doubt', are downward entailing (DE). Our algorithm is unsupervised, resource-lean, and effective, accurately recovering many DE operators that are missing from the hand-constructed lists that textual-inference systems currently use.
Exact Indexing for Massive Time Series Databases under Time Warping Distance
Venue: arXiv cs.DB 2009
Year: 2009

Among many existing distance measures for time series data, Dynamic Time Warping (DTW) distance has been recognized as one of the most accurate and suitable distance measures due to its flexibility in sequence alignment. However, DTW distance calculation is computationally intensive. Especially in very large time series databases, sequential scan through the entire database is definitely impractical, even with random access that exploits some index structures since high dimensionality of time series data incurs extremely high I/O cost. More specifically, a sequential structure consumes high CPU but low I/O costs, while an index structure requires low CPU but high I/O costs. In this work, we therefore propose a novel indexed sequential structure called TWIST (Time Warping in Indexed Sequential sTructure) which benefits from both sequential access and index structure. When a query sequence is issued, TWIST calculates lower bounding distances between a group of candidate sequences and the query sequence, and then identifies the data access order in advance, hence reducing a great number of both sequential and random accesses. Impressively, our indexed sequential structure achieves significant speedup in a querying process by a few orders of magnitude. In addition, our method shows superiority over existing rival methods in terms of query processing time, number of page accesses, and storage requirement with no false dismissal guaranteed.
On $[[n,n-4,3]]_{q}$ Quantum MDS Codes for odd prime power $q$
Venue: arXiv cs.IT 2009
Year: 2009

For each odd prime power $q$, let $4 \leq n\leq q^{2}+1$. Hermitian self-orthogonal $[n,2,n-1]$ codes over $GF(q^{2})$ with dual distance three are constructed by using finite field theory. Hence, $[[n,n-4,3]]_{q}$ quantum MDS codes for $4 \leq n\leq q^{2}+1$ are obtained.
On the Complexity of Branching-Time Logics
Venue: arXiv cs.LO 2009
Year: 2009

We classify the complexity of the satisfiability problem for extensions of CTL and UB. The extensions we consider are Boolean combinations of path formulas, fairness properties, past modalities, and forgettable past. Our main result shows that satisfiability for CTL with all these extensions is still in 2-EXPTIME, which strongly contrasts with the nonelementary complexity of CTL* with forgettable past. We give a complete classification of combinations of these extensions, yielding a dichotomy between extensions with 2-EXPTIME-complete and those with EXPTIME-complete complexity. In particular, we show that satisfiability for the extension of UB with forgettable past is complete for 2-EXPTIME, contradicting a claim for a stronger logic in the literature. The upper bounds are established with the help of a new kind of pebble automata.
From Artifacts to Aggregations: Modeling Scientific Life Cycles on the Semantic Web
Venue: arXiv cs.DL 2009
Year: 2009

In the process of scientific research, many information objects are generated, all of which may remain valuable indefinitely. However, artifacts such as instrument data and associated calibration information may have little value in isolation; their meaning is derived from their relationships to each other. Individual artifacts are best represented as components of a life cycle that is specific to a scientific research domain or project. Current cataloging practices do not describe objects at a sufficient level of granularity nor do they offer the globally persistent identifiers necessary to discover and manage scholarly products with World Wide Web standards. The Open Archives Initiative's Object Reuse and Exchange data model (OAI-ORE) meets these requirements. We demonstrate a conceptual implementation of OAI-ORE to represent the scientific life cycles of embedded networked sensor applications in seismology and environmental sciences. By establishing relationships between publications, data, and contextual research information, we illustrate how to obtain a richer and more realistic view of scientific practices. That view can facilitate new forms of scientific research and learning. Our analysis is framed by studies of scientific practices in a large, multi-disciplinary, multi-university science and engineering research center, the Center for Embedded Networked Sensing (CENS).
Stability Properties of Networks with Interacting TCP Flows
Venue: arXiv cs.NI 2009
Year: 2009

The equilibrium distributions of a Markovian model describing the interaction of several classes of permanent connections in a network are analyzed. It has been introduced by Graham and Robert. For this model each of the connections has a self-adaptive behavior in that its transmission rate along its route depends on the level of congestion of the nodes on its route. It has been shown that the invariant distributions are determined by the solutions of a fixed point equation in a finite dimensional space. In this paper, several examples of these fixed point equations are studied. The topologies investigated are rings, trees and a linear network, with various sets of routes through the nodes.
RPO, Second-order Contexts, and Lambda-calculus
Venue: arXiv cs.PL 2009
Year: 2009

First, we extend Leifer-Milner RPO theory, by giving general conditions to obtain IPO labelled transition systems (and bisimilarities) with a reduced set of transitions, and possibly finitely branching. Moreover, we study the weak variant of Leifer-Milner theory, by giving general conditions under which the weak bisimilarity is a congruence. Then, we apply such extended RPO technique to the lambda-calculus, endowed with lazy and call by value reduction strategies. We show that, contrary to process calculi, one can deal directly with the lambda-calculus syntax and apply Leifer-Milner technique to a category of contexts, provided that we work in the framework of weak bisimilarities. However, even in the case of the transition system with minimal contexts, the resulting bisimilarity is infinitely branching, due to the fact that, in standard context categories, parametric rules such as the beta-rule can be represented only by infinitely many ground rules. To overcome this problem, we introduce the general notion of second-order context category. We show that, by carrying out the RPO construction in this setting, the lazy observational equivalence can be captured as a weak bisimilarity equivalence on a finitely branching transition system. This result is achieved by considering an encoding of lambda-calculus in Combinatory Logic.
Coding cells of digital spaces: a framework to write generic digital topology algorithms
Venue: arXiv cs.DM 2009
Year: 2009

This paper proposes a concise coding of the cells of n-dimensional finite regular grids. It induces a simple, generic and efficient framework for implementing classical digital topology data structures and algorithms. Discrete subsets of multidimensional images (e.g. regions, digital surfaces, cubical cell complexes) have then a common and compact representation. Moreover, algorithms have a straightforward and efficient implementation, which is independent from the dimension or sizes of digital images. We illustrate that point with generic hypersurface boundary extraction algorithms by scanning or tracking. This framework has been implemented and basic operations as well as the presented applications have been benchmarked.
What Does Artificial Life Tell Us About Death?
Venue: arXiv cs.AI 2009
Year: 2009

Short philosophical essay
Fragments of first-order logic over infinite words
Venue: arXiv cs.FL 2009
Year: 2009

We give topological and algebraic characterizations as well as language theoretic descriptions of the following subclasses of first-order logic FO[<] for omega-languages: Sigma_2, FO^2, the intersection of FO^2 and Sigma_2, and Delta_2 (and by duality Pi_2 and the intersection of FO^2 and Pi_2). These descriptions extend the respective results for finite words. In particular, we relate the above fragments to language classes of certain (unambiguous) polynomials. An immediate consequence is the decidability of the membership problem of these classes, but this was shown before by Wilke and Bojanczyk and is therefore not our main focus. The paper is about the interplay of algebraic, topological, and language theoretic properties.
Feynman Algorithm Implementation for Comparison with Euler in a Uniform Elastic Two-Layer 2D and 3D Object Dynamic Deformation Framework in OpenGL with GUI
Venue: arXiv cs.GR 2009
Year: 2009

We implement for comparative purposes the Feynman algorithm within a C++-based framework for two-layer uniform facet elastic object for real-time softbody simulation based on physics modeling methods. To facilitate the comparison, we implement initial timing measurements on the same hardware against that of Euler integrator in the softbody framework by varying different algorithm parameters. Due to a relatively large number of such variations we implement a GLUI-based user-interface to allow for much more finer control over the simulation process at real-time, which was lacking completely in the previous versions of the framework. We show our currents results based on the enhanced framework. The two-layered elastic object consists of inner and outer elastic mass-spring surfaces and compressible internal pressure. The density of the inner layer can be set differently from the density of the outer layer; the motion of the inner layer can be opposite to the motion of the outer layer. These special features, which cannot be achieved by a single layered object, result in improved imitation of a soft body, such as tissue's liquid non-uniform deformation. The inertial behavior of the elastic object is well illustrated in environments with gravity and collisions with walls, ceiling, and floor. The collision detection is defined by elastic collision penalty method and the motion of the object is guided by the Ordinary Differential Equation computation. Users can interact with the modeled objects, deform them, and observe the response to their action in real-time and we provide an extensible framework and its implementation for comparative studies of different physical-based modeling and integration algorithm implementations.
Activités collectives et instrumentation. Étude de pratiques dans l'enseignement supérieur
Venue: arXiv cs.CY 2009
Year: 2009

This article presents the results of a study which concerns Instrumented Collective Learning Situations (ICLS) used in higher education and according to different actors's point of view (instructional designer and tutor). Considered actors have been involved in ICLS conception or in their use with students. We determine several forms of ICLS (in terms of scenario, tools, kind of activity) and what educational approaches are adopted by educational actors in their practices. We detail the results of our study, mainly by highlighting the "home-made" approach of the actors, that is based on an opportunist and pragmatic use of available tools in order to fit into the educational contexts.
Fracture numérique chez les seniors du 4eme age. Observation d'une acculturation technique
Venue: arXiv cs.CY 2009
Year: 2009

Very old people accumulate the "handicaps": social, physical, psychological or cognitive. Various research thus developed to determine there waiting and needs and also to see the benefit possibly produced by technologies (called ?gerontechnology?) on their living conditions. The object of this article is to present the numerical service offer to very old perople and to see how it takes part in a social justice according to the definition of Rawls (principle of equal freedom, principle of equal opportunity in the access). The adoption, the use and the benefit of technology are analyzed in a theoretical way through a state of the art and in an experimental way through a qualitative and quantitative investigation carried out with a population of very old people. We propose to identify dynamic technological acceptance of old people according to the TAM'S (Technology Acceptance Model) of Davis adapted by (Hamner and Qazi, 2008).
Semi-Myopic Sensing Plans for Value Optimization
Venue: arXiv cs.AI 2009
Year: 2009

We consider the following sequential decision problem. Given a set of items of unknown utility, we need to select one of as high a utility as possible (``the selection problem''). Measurements (possibly noisy) of item values prior to selection are allowed, at a known cost. The goal is to optimize the overall sequential decision process of measurements and selection. Value of information (VOI) is a well-known scheme for selecting measurements, but the intractability of the problem typically leads to using myopic VOI estimates. In the selection problem, myopic VOI frequently badly underestimates the value of information, leading to inferior sensing plans. We relax the strict myopic assumption into a scheme we term semi-myopic, providing a spectrum of methods that can improve the performance of sensing plans. In particular, we propose the efficiently computable method of ``blinkered'' VOI, and examine theoretical bounds for special cases. Empirical evaluation of ``blinkered'' VOI in the selection problem with normally distributed item values shows that is performs much better than pure myopic VOI.
A General Notion of Useful Information
Venue: arXiv cs.CC 2009
Year: 2009

In this paper we introduce a general framework for defining the depth of a sequence with respect to a class of observers. We show that our general framework captures all depth notions introduced in complexity theory so far. We review most such notions, show how they are particular cases of our general depth framework, and review some classical results about the different depth notions.
Some Considerations on Universality
Venue: arXiv cs.CC 2009
Year: 2009

The paper puts into discussion the concept of universality, in particular for structures not of the power of Turing computability. The question arises if for such structures a universal structure of the same kind exists or not. For that the construction of universal Turing machines and those with some constraints are presented in some detail.
Busy beavers gone wild
Venue: arXiv cs.LO 2009
Year: 2009

We show some incompleteness results a la Chaitin using the busy beaver functions. Then, with the help of ordinal logics, we show how to obtain a theory in which the values of the busy beaver functions can be provably established and use this to reveal a structure on the provability of the values of these functions.
On acceptance conditions for membrane systems: characterisations of L and NL
Venue: arXiv cs.CC 2009
Year: 2009

In this paper we investigate the affect of various acceptance conditions on recogniser membrane systems without dissolution. We demonstrate that two particular acceptance conditions (one easier to program, the other easier to prove correctness) both characterise the same complexity class, NL. We also find that by restricting the acceptance conditions we obtain a characterisation of L. We obtain these results by investigating the connectivity properties of dependency graphs that model membrane system computations.
Complexity through the Observation of Simple Systems
Venue: arXiv cs.CC 2009
Year: 2009

We survey work on the paradigm called "computing by observing." Its central feature is that one considers the behavior of an evolving system as the result of a computation. To this end an observer records this behavior. It has turned out that the observed behavior of computationally simple systems can be very complex, when an appropriate observer is used. For example, a restricted version of context-free grammars with regular observers suffices to obtain computational completeness. As a second instantiation presented here, we apply an observer to sticker systems. Finally, some directions for further research are proposed.
A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
Venue: arXiv cs.DS 2009
Year: 2009

In this paper we introduce "hybrid" Max 2-CSP formulas consisting of "simple clauses", namely conjunctions and disjunctions of pairs of variables, and general 2-variable clauses, which can be any integer-valued functions of pairs of boolean variables. This allows an algorithm to use both efficient reductions specific to AND and OR clauses, and other powerful reductions that require the general CSP setting. We use new reductions introduced here, and recent reductions such as "clause-learning" and "2-reductions" generalized to our setting's mixture of simple and general clauses. Parametrizing an instance by the fraction p of non-simple clauses, we give an exact (exponential-time) algorithm that is the fastest known polynomial-space algorithm for p=0 (which includes the well-studied Max 2-Sat problem but also instances with arbitrary mixtures of AND and OR clauses); the only efficient algorithm for mixtures of AND, OR, and general integer-valued clauses; and tied for fastest for general Max 2-CSP (p=1). Since a pure 2-Sat input instance may be transformed to a general CSP instance in the course of being solved, the algorithm's efficiency and generality go hand in hand. Our algorithm analysis and optimization are a variation on the familiar measure-and-conquer approach, resulting in an optimizing mathematical program that is convex not merely quasi-convex, and thus can be solved efficiently and with a certificate of optimality. We produce a family of running-time upper-bound formulas, each optimized for instances with a particular value of p but valid for all instances.
Spanning connectivity games
Venue: arXiv cs.GT 2009
Year: 2009

The Banzhaf index, Shapley-Shubik index and other voting power indices measure the importance of a player in a coalitional game. We consider a simple coalitional game called the spanning connectivity game (SCG) based on an undirected, unweighted multigraph, where edges are players. We examine the computational complexity of computing the voting power indices of edges in the SCG. It is shown that computing Banzhaf values and Shapley-Shubik indices is #P-complete for SCGs. Interestingly, Holler indices and Deegan-Packel indices can be computed in polynomial time. Among other results, it is proved that Banzhaf indices can be computed in polynomial time for graphs with bounded treewidth. It is also shown that for any reasonable representation of a simple game, a polynomial time algorithm to compute the Shapley-Shubik indices implies a polynomial time algorithm to compute the Banzhaf indices. As a corollary, computing the Shapley value is #P-complete for simple games represented by the set of minimal winning coalitions, Threshold Network Flow Games, Vertex Connectivity Games and Coalitional Skill Games.
Neighbor-Specific BGP: More Flexible Routing Policies While Improving Global Stability
Venue: arXiv cs.NI 2009
Year: 2009

Please Note: This document was written to summarize and facilitate discussion regarding (1) the benefits of changing the way BGP selects routes to selecting the most preferred route allowed by export policies, or more generally, to selecting BGP routes on a per-neighbor basis, (2) the safety condition that guarantees global routing stability under the Neighbor-Specific BGP model, and (3) ways of deploying this model in practice. A paper presenting the formal model and proof of the stability conditions was published at SIGMETRICS 2009 and is available online.
The Two-Tap Input-Erasure Gaussian Channel and its Application to Cellular Communications
Venue: arXiv cs.IT 2009
Year: 2009

This paper considers the input-erasure Gaussian channel. In contrast to the output-erasure channel where erasures are applied to the output of a linear time-invariant (LTI) system, here erasures, known to the receiver, are applied to the inputs of the LTI system. Focusing on the case where the input symbols are independent and identically distributed (i.i.d)., it is shown that the two channels (input- and output-erasure) are equivalent. Furthermore, assuming that the LTI system consists of a two-tap finite impulse response (FIR) filter, and using simple properties of tri-diagonal matrices, an achievable rate expression is presented in the form of an infinite sum. The results are then used to study the benefits of joint multicell processing (MCP) over single-cell processing (SCP) in a simple linear cellular uplink, where each mobile terminal is received by only the two nearby base-stations (BSs). Specifically, the analysis accounts for ergodic shadowing that simultaneously blocks the mobile terminal (MT) signal from being received by the two BS. It is shown that the resulting ergodic per-cell capacity with optimal MCP is equivalent to that of the two-tap input-erasure channel. Finally, the same cellular uplink is addressed by accounting for dynamic user activity, which is modelled by assuming that each MT is randomly selected to be active or to remain silent throughout the whole transmission block. For this alternative model, a similar equivalence results to the input-erasure channel are reported.