29272698
Monad as Modality
Abstract In 1989, Eugenio Moggi proposed a categorical framework for program semantics based on the notion of a strong monad. He showed that various kinds of computation can be modeled in his framework. On the other hand, strong monads are not suited for the categorical semantics of traditional modal logics. According to these observations, Moggi thought that the CurryHoward correspondence would not hold between programs and constructive proofs in modal logics. However, contrary to his view, we can show that proofs in a certain kind of modal logics are actually considered as programs. In this paper, first we shall introduce the notion of an l-strong monad which is a generalization of strong monads. Using this new notion, we can generalize Moggi's semantics-preserving soundness and completeness with respect to his equational logic. Next we shall show that l-strong monads give a sound and complete semantics of a constructive version of S4 modal logic. Finally, we present a method to extract a monad-based imperative functional program from a proof in the modal logic. Interestingly, this method can also be understood in terms of l-strong monads.
8742017
Two Extensions of PX system
Abstract Two extensions of PX system will be discussed. The extensions are ctPX (catch/throw PX) and mvPX (multiple values PX). ctPX is a PX system extended with Nakano's catch/throw logic. ctPX enables to extract LISP programs with catch/throw mechanism form natural proofs. mvPX is a PX system which uses multiple values rather than lists to keep a finite sequences of data. Programs extracted by ctPX are more efficient than the ones by the original PX.
28922785
Realizability Interpretation of Generalized Inductive Definitions
Generalized inductive definitions give a way of defining a predicate as the least solution P of the equation [email protected]?A[P] where a predicate variable P may occur in a formula A[P] positively. This paper gives aq-realizability interpretation of generalized inductive definitions and proves the soundness of the interpretation.
38554897
Tree Adjoining Grammars for RNA Structure Prediction
In this paper, we are concerned with identifying a subclass of tree adjoining grammars (TAGs) that is suitable for the application to modeling and predicting RNA secondary structures. The goal of this paper is twofold: For the purpose of applying to the RNA secondary structure prediction problem, we first introduce a special subclass of TAGs and develop a fast parsing algorithm for the subclass, together with some of its language theoretic characterizations. Then, based on the algorithm, we develop a prediction system and demonstrate the effectiveness of the system by presenting some experimental results obtained from biological data, where free energy evaluation selection for parse trees is incorporated into the algorithm.
16146948
Learning Concatenations of Locally Testable Languages from Positive Data
This paper introduces the class of concatenations of locally testable languages and its subclasses, and presents some results on the learnability of the classes from positive data. We first establish several relationships among the language classes introduced, and give a sufficient condition for a concatenation operation to preserve finite elasticity of a language class C. Then we show that, for each k, the class CLT≤ k, a subclass of concatenations of locally testable languages, is identifiable in the limit from positive data. Further, we introduce a notion of local parsability, and define a class (k, l)-CLTS, which is a subclass of the class of concatenations of strictly locally testable languages. Then, for each k, l ≥ 1, (k, l)-CLTS is proved to be identifiable in the limit from positive data using reversible automata with the conjectures updated in polynomial time. Some possible applications of this result are also briefly discussed.
39030523
Efficient Algorithm for Testing Structure Freeness of Finite Set of Biomolecular Sequences
In this paper we will focus on the structure freeness test problem of finite sets of sequences. The result is an extension of Andronescu's algorithm which can be applied to the sequence design of various DNA computing experiments. We will first give a general algorithm for this problem which runs in O(n5) time. Then, we will give an evaluation method for sequence design system, which requires O(n5) time for precomputation, and O(n4) time and O(n5) space for each evaluation of sequence sets. The authors believe that this result will give an important progress of efficient sequence design systems.
30034887
Horn Clause Computation with DNA Molecules
In this paper, we will propose Horn clause computation as an underlying computational framework of DNA computer. Horn clause program is a subclass of the formulas of first order logic and has close relation to PROLOG language. The computational power of Horn clauses was discussed in (Tärnland, 1977) and it was shown that a finite set of Horn clauses is computationally equivalent to Turing Machine. Furthermore, it should be noted that Horn programs are adequate for representing nondeterministic computation. Thus, its parallel implementation with huge number of molecules might have possibility to overcome the computational power of conventional computers. It should also be noted that the clear logical semantics of Horn programs might enable us to accept it as a higher-level programming language of DNA computer. The aim of this paper is to propose an experimental method for implementing deduction with a subclass of Horn programs, called simple Horn programs. The computational power of this model is theoretically investigated and demonstrated with some applications to NP-complete problems.