OpenRaiser/Intern-Atlas huggingface dataset:
Predicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairs
Venue: arXiv cs.CE 2001
Year: 2001

The paper investigates the computational problem of predicting RNA secondary structures. The general belief is that allowing pseudoknots makes the problem hard. Existing polynomial-time algorithms are heuristic algorithms with no performance guarantee and can only handle limited types of pseudoknots. In this paper we initiate the study of predicting RNA secondary structures with a maximum number of stacking pairs while allowing arbitrary pseudoknots. We obtain two approximation algorithms with worst-case approximation ratios of 1/2 and 1/3 for planar and general secondary structures,respectively. For an RNA sequence of $n$ bases, the approximation algorithm for planar secondary structures runs in $O(n^3)$ time while that for the general case runs in linear time. Furthermore, we prove that allowing pseudoknots makes it NP-hard to maximize the number of stacking pairs in a planar secondary structure. This result is in contrast with the recent NP-hard results on psuedoknots which are based on optimizing some general and complicated energy functions.
Using a Support-Vector Machine for Japanese-to-English Translation of Tense, Aspect, and Modality
Venue: arXiv cs.CL 2001
Year: 2001

This paper describes experiments carried out using a variety of machine-learning methods, including the k-nearest neighborhood method that was used in a previous study, for the translation of tense, aspect, and modality. It was found that the support-vector machine method was the most precise of all the methods tested.
A Logic Programming Approach to Knowledge-State Planning: Semantics and Complexity
Venue: arXiv cs.AI 2001
Year: 2001

We propose a new declarative planning language, called K, which is based on principles and methods of logic programming. In this language, transitions between states of knowledge can be described, rather than transitions between completely described states of the world, which makes the language well-suited for planning under incomplete knowledge. Furthermore, it enables the use of default principles in the planning process by supporting negation as failure. Nonetheless, K also supports the representation of transitions between states of the world (i.e., states of complete knowledge) as a special case, which shows that the language is very flexible. As we demonstrate on particular examples, the use of knowledge states may allow for a natural and compact problem representation. We then provide a thorough analysis of the computational complexity of K, and consider different planning problems, including standard planning and secure planning (also known as conformant planning) problems. We show that these problems have different complexities under various restrictions, ranging from NP to NEXPTIME in the propositional case. Our results form the theoretical basis for the DLV^K system, which implements the language K on top of the DLV logic programming system.
Exact Complexity of the Winner Problem for Young Elections
Venue: arXiv cs.CC 2001
Year: 2001

In 1977, Young proposed a voting scheme that extends the Condorcet Principle based on the fewest possible number of voters whose removal yields a Condorcet winner. We prove that both the winner and the ranking problem for Young elections is complete for the class of problems solvable in polynomial time by parallel access to NP. Analogous results for Lewis Carroll's 1876 voting scheme were recently established by Hemaspaandra et al. In contrast, we prove that the winner and ranking problems in Fishburn's homogeneous variant of Carroll's voting scheme can be solved efficiently by linear programming.
Faster Algorithm of String Comparison
Venue: arXiv cs.DS 2001
Year: 2001

In many applications, it is necessary to determine the string similarity. Edit distance[WF74] approach is a classic method to determine Field Similarity. A well known dynamic programming algorithm [GUS97] is used to calculate edit distance with the time complexity O(nm). (for worst case, average case and even best case) Instead of continuing with improving the edit distance approach, [LL+99] adopted a brand new approach-token-based approach. Its new concept of token-base-retain the original semantic information, good time complex-O(nm) (for worst, average and best case) and good experimental performance make it a milestone paper in this area. Further study indicates that there is still room for improvement of its Field Similarity algorithm. Our paper is to introduce a package of substring-based new algorithms to determine Field Similarity. Combined together, our new algorithms not only achieve higher accuracy but also gain the time complexity O(knm) (k<0.75) for worst case, O(*n) where <6 for average case and O(1) for best case. Throughout the paper, we use the approach of comparative examples to show higher accuracy of our algorithms compared to the one proposed in [LL+99]. Theoretical analysis, concrete examples and experimental result show that our algorithms can significantly improve the accuracy and time complexity of the calculation of Field Similarity. [US97] D. Guseld. Algorithms on Strings, Trees and Sequences, in Computer Science and Computational Biology. [LL+99] Mong Li Lee, Cleansing data for mining and warehousing, In Proceedings of the 10th International Conference on Database and Expert Systems Applications (DEXA99), pages 751-760,August 1999. [WF74] R. Wagner and M. Fisher, The String to String Correction Problem, JACM 21 pages 168-173, 1974.
Ultrametric Distance in Syntax
Venue: arXiv cs.CL 2001
Year: 2001

Phrase structure trees have a hierarchical structure. In many subjects, most notably in Taxonomy such tree structures have been studied using ultrametrics. Here syntactical hierarchical phrase trees are subject to a similar analysis, which is much siompler as the branching structure is more readily discernible and switched. The occurence of hierarchical structure elsewhere in linguistics is mentioned. The phrase tree can be represented by a matrix and the elements of the matrix can be represented by triangles. The height at which branching occurs is not prescribed in previous syntatic models, but it is by using the ultrametric matrix. The ambiguity of which branching height to choose is resolved by postulating that branching occurs at the lowest height available. An ultrametric produces a measure of the complexity of sentences: presumably the complexity of sentence increases as a language is aquired so that this can be tested. A All ultrametric triangles are equilateral or isocles, here it is shown that X structur implies that there are no equilateral triangles. Restricting attention to simple syntax a minium ultrametric distance between lexical categories is calculatex. This ultrametric distance is shown to be different than the matrix obtasined from feaures. It is shown that the definition of c-commabnd can be replaced by an equivalent ultrametric definition. The new definition invokes a minimum distance between nodes and this is more aesthetically satisfing than previouv varieties of definitions. From the new definition of c-command follows a new definition of government.
Reconciliation of a Quantum-Distributed Gaussian Key
Venue: arXiv cs.CR 2002
Year: 2002

Two parties, Alice and Bob, wish to distill a binary secret key out of a list of correlated variables that they share after running a quantum key distribution protocol based on continuous-spectrum quantum carriers. We present a novel construction that allows the legitimate parties to get equal bit strings out of correlated variables by using a classical channel, with as few leaked information as possible. This opens the way to securely correcting non-binary key elements. In particular, the construction is refined to the case of Gaussian variables as it applies directly to recent continuous-variable protocols for quantum key distribution.
Flipping Cubical Meshes
Venue: arXiv cs.CG 2002
Year: 2002

We define and examine flip operations for quadrilateral and hexahedral meshes, similar to the flipping transformations previously used in triangular and tetrahedral mesh generation.
Dense point sets have sparse Delaunay triangulations
Venue: arXiv cs.CG 2002
Year: 2002

The spread of a finite set of points is the ratio between the longest and shortest pairwise distances. We prove that the Delaunay triangulation of any set of n points in R^3 with spread D has complexity O(D^3). This bound is tight in the worst case for all D = O(sqrt{n}). In particular, the Delaunay triangulation of any dense point set has linear complexity. We also generalize this upper bound to regular triangulations of k-ply systems of balls, unions of several dense point sets, and uniform samples of smooth surfaces. On the other hand, for any n and D=O(n), we construct a regular triangulation of complexity Omega(nD) whose n vertices have spread D.
The performance of the batch learner algorithm
Venue: arXiv cs.LG 2002
Year: 2002

We analyze completely the convergence speed of the \emph{batch learning algorithm}, and compare its speed to that of the memoryless learning algorithm and of learning with memory. We show that the batch learning algorithm is never worse than the memoryless learning algorithm (at least asymptotically). Its performance \emph{vis-a-vis} learning with full memory is less clearcut, and depends on certain probabilistic assumptions.
Long Proteins with Unique Optimal Foldings in the H-P Model
Venue: arXiv cs.CG 2002
Year: 2002

It is widely accepted that (1) the natural or folded state of proteins is a global energy minimum, and (2) in most cases proteins fold to a unique state determined by their amino acid sequence. The H-P (hydrophobic-hydrophilic) model is a simple combinatorial model designed to answer qualitative questions about the protein folding process. In this paper we consider a problem suggested by Brian Hayes in 1998: what proteins in the two-dimensional H-P model have unique optimal (minimum energy) foldings? In particular, we prove that there are closed chains of monomers (amino acids) with this property for all (even) lengths; and that there are open monomer chains with this property for all lengths divisible by four.
Learning to Play Games in Extensive Form by Valuation
Venue: arXiv cs.LG 2002
Year: 2002

A valuation for a player in a game in extensive form is an assignment of numeric values to the players moves. The valuation reflects the desirability moves. We assume a myopic player, who chooses a move with the highest valuation. Valuations can also be revised, and hopefully improved, after each play of the game. Here, a very simple valuation revision is considered, in which the moves made in a play are assigned the payoff obtained in the play. We show that by adopting such a learning process a player who has a winning strategy in a win-lose game can almost surely guarantee a win in a repeated game. When a player has more than two payoffs, a more elaborate learning procedure is required. We consider one that associates with each move the average payoff in the rounds in which this move was made. When all players adopt this learning procedure, with some perturbations, then, with probability 1, strategies that are close to subgame perfect equilibrium are played after some time. A single player who adopts this procedure can guarantee only her individually rational payoff.
Model-Based Software Engineering and Ada: Synergy for the Development of Safety-Critical Systems
Venue: arXiv cs.SE 2002
Year: 2002

In this paper we outline a software development process for safety-critical systems that aims at combining some of the specific strengths of model-based development with those of programming language based development using safety-critical subsets of Ada. Model-based software development and model-based test case generation techniques are combined with code generation techniques and tools providing a transition from model to code both for a system itself and for its test cases. This allows developers to combine domain-oriented, model-based techniques with source code based validation techniques, as required for conformity with standards for the development of safety-critical software, such as the avionics standard RTCA/DO-178B. We introduce the AutoFocus and Validator modeling and validation toolset and sketch its usage for modeling, test case generation, and code generation in a combined approach, which is further illustrated by a simplified leading edge aerospace model with built-in fault tolerance.
The Deductive Database System LDL++
Venue: arXiv cs.DB 2002
Year: 2002

This paper describes the LDL++ system and the research advances that have enabled its design and development. We begin by discussing the new nonmonotonic and nondeterministic constructs that extend the functionality of the LDL++ language, while preserving its model-theoretic and fixpoint semantics. Then, we describe the execution model and the open architecture designed to support these new constructs and to facilitate the integration with existing DBMSs and applications. Finally, we describe the lessons learned by using LDL++ on various tested applications, such as middleware and datamining.
Steady State Resource Allocation Analysis of the Stochastic Diffusion Search
Venue: arXiv cs.AI 2002
Year: 2002

This article presents the long-term behaviour analysis of Stochastic Diffusion Search (SDS), a distributed agent-based system for best-fit pattern matching. SDS operates by allocating simple agents into different regions of the search space. Agents independently pose hypotheses about the presence of the pattern in the search space and its potential distortion. Assuming a compositional structure of hypotheses about pattern matching agents perform an inference on the basis of partial evidence from the hypothesised solution. Agents posing mutually consistent hypotheses about the pattern support each other and inhibit agents with inconsistent hypotheses. This results in the emergence of a stable agent population identifying the desired solution. Positive feedback via diffusion of information between the agents significantly contributes to the speed with which the solution population is formed. The formulation of the SDS model in terms of interacting Markov Chains enables its characterisation in terms of the allocation of agents, or computational resources. The analysis characterises the stationary probability distribution of the activity of agents, which leads to the characterisation of the solution population in terms of its similarity to the target pattern.
Small Strictly Convex Quadrilateral Meshes of Point Sets
Venue: arXiv cs.CG 2002
Year: 2002

In this paper, we give upper and lower bounds on the number of Steiner points required to construct a strictly convex quadrilateral mesh for a planar point set. In particular, we show that $3{\lfloor\frac{n}{2}\rfloor}$ internal Steiner points are always sufficient for a convex quadrilateral mesh of $n$ points in the plane. Furthermore, for any given $n\geq 4$, there are point sets for which $\lceil\frac{n-3}{2}\rceil-1$ Steiner points are necessary for a convex quadrilateral mesh.
Logic program specialisation through partial deduction: Control issues
Venue: arXiv cs.PL 2002
Year: 2002

Program specialisation aims at improving the overall performance of programs by performing source to source transformations. A common approach within functional and logic programming, known respectively as partial evaluation and partial deduction, is to exploit partial knowledge about the input. It is achieved through a well-automated application of parts of the Burstall-Darlington unfold/fold transformation framework. The main challenge in developing systems is to design automatic control that ensures correctness, efficiency, and termination. This survey and tutorial presents the main developments in controlling partial deduction over the past 10 years and analyses their respective merits and shortcomings. It ends with an assessment of current achievements and sketches some remaining research challenges.
Nonmonotonic Logics and Semantics
Venue: arXiv cs.AI 2002
Year: 2002

Tarski gave a general semantics for deductive reasoning: a formula a may be deduced from a set A of formulas iff a holds in all models in which each of the elements of A holds. A more liberal semantics has been considered: a formula a may be deduced from a set A of formulas iff a holds in all of the "preferred" models in which all the elements of A hold. Shoham proposed that the notion of "preferred" models be defined by a partial ordering on the models of the underlying language. A more general semantics is described in this paper, based on a set of natural properties of choice functions. This semantics is here shown to be equivalent to a semantics based on comparing the relative "importance" of sets of models, by what amounts to a qualitative probability measure. The consequence operations defined by the equivalent semantics are then characterized by a weakening of Tarski's properties in which the monotonicity requirement is replaced by three weaker conditions. Classical propositional connectives are characterized by natural introduction-elimination rules in a nonmonotonic setting. Even in the nonmonotonic setting, one obtains classical propositional logic, thus showing that monotonicity is not required to justify classical propositional connectives.
Expected Qualitative Utility Maximization
Venue: arXiv cs.GT 2002
Year: 2002

A model for decision making that generalizes Expected Utility Maximization is presented. This model, Expected Qualitative Utility Maximization, encompasses the Maximin criterion. It relaxes both the Independence and the Continuity postulates. Its main ingredient is the definition of a qualitative order on nonstandard models of the real numbers and the consideration of nonstandard utilities. Expected Qualitative Utility Maximization is characterized by an original weakening of von Neumann-Morgenstern's postulates. Subjective probabilities may be defined from those weakened postulates, as Anscombe and Aumann did from the original postulates. Subjective probabilities are numbers, not matrices as in the Subjective Expected Lexicographic Utility approach. JEL no.: D81 Keywords: Utility Theory, Non-Standard Utilities, Qualitative Decision Theory
A note on Darwiche and Pearl
Venue: arXiv cs.AI 2002
Year: 2002

It is shown that Darwiche and Pearl's postulates imply an interesting property, not noticed by the authors.
Nonstandard numbers for qualitative decision making
Venue: arXiv cs.GT 2002
Year: 2002

The consideration of nonstandard models of the real numbers and the definition of a qualitative ordering on those models provides a generalization of the principle of maximization of expected utility. It enables the decider to assign probabilities of different orders of magnitude to different events or to assign utilities of different orders of magnitude to different outcomes. The properties of this generalized notion of rationality are studied in the frameworks proposed by von Neumann and Morgenstern and later by Anscombe and Aumann. It is characterized by an original weakening of their postulates in two different situations: nonstandard probabilities and standard utilities on one hand and standard probabilities and nonstandard utilities on the other hand. This weakening concerns both Independence and Continuity. It is orthogonal with the weakening proposed by lexicographic orderings.
The logical meaning of Expansion
Venue: arXiv cs.AI 2002
Year: 2002

The Expansion property considered by researchers in Social Choice is shown to correspond to a logical property of nonmonotonic consequence relations that is the {\em pure}, i.e., not involving connectives, version of a previously known weak rationality condition. The assumption that the union of two definable sets of models is definable is needed for the soundness part of the result.
Covariance Plasticity and Regulated Criticality
Venue: arXiv cs.NE 2002
Year: 2002

We propose that a regulation mechanism based on Hebbian covariance plasticity may cause the brain to operate near criticality. We analyze the effect of such a regulation on the dynamics of a network with excitatory and inhibitory neurons and uniform connectivity within and across the two populations. We show that, under broad conditions, the system converges to a critical state lying at the common boundary of three regions in parameter space; these correspond to three modes of behavior: high activity, low activity, oscillation.
Representing and Aggregating Conflicting Beliefs
Venue: arXiv cs.AI 2002
Year: 2002

We consider the two-fold problem of representing collective beliefs and aggregating these beliefs. We propose modular, transitive relations for collective beliefs. They allow us to represent conflicting opinions and they have a clear semantics. We compare them with the quasi-transitive relations often used in Social Choice. Then, we describe a way to construct the belief state of an agent informed by a set of sources of varying degrees of reliability. This construction circumvents Arrow's Impossibility Theorem in a satisfactory manner. Finally, we give a simple set-theory-based operator for combining the information of multiple agents. We show that this operator satisfies the desirable invariants of idempotence, commutativity, and associativity, and, thus, is well-behaved when iterated, and we describe a computationally effective way of computing the resulting belief state.
Active Virtual Network Management Prediction: Complexity as a Framework for Prediction, Optimization, and Assurance
Venue: arXiv cs.CC 2002
Year: 2002

Research into active networking has provided the incentive to re-visit what has traditionally been classified as distinct properties and characteristics of information transfer such as protocol versus service; at a more fundamental level this paper considers the blending of computation and communication by means of complexity. The specific service examined in this paper is network self-prediction enabled by Active Virtual Network Management Prediction. Computation/communication is analyzed via Kolmogorov Complexity. The result is a mechanism to understand and improve the performance of active networking and Active Virtual Network Management Prediction in particular. The Active Virtual Network Management Prediction mechanism allows information, in various states of algorithmic and static form, to be transported in the service of prediction for network management. The results are generally applicable to algorithmic transmission of information. Kolmogorov Complexity is used and experimentally validated as a theory describing the relationship among algorithmic compression, complexity, and prediction accuracy within an active network. Finally, the paper concludes with a complexity-based framework for Information Assurance that attempts to take a holistic view of vulnerability analysis.