32641172
Learning Strategies Using Decision Lists
This paper presents a new technique for improving the efficiency of problem solvers by using trace data. The learning schema of this kind is usually called speedup learning. Although this learning paradigm has been formalized by [Nat89] based on the Probably Approximately Correct Learning model[Val84], his algorithm does not use operator sequence information of traces at all. We give a new algorithm which makes use of operator sequence information, and its effectiveness is shown by experiments in several domains. We also show theoretical backgrounds of the algorithm.
40461039
Learning local languages and its application to protein /spl alpha/-chain identification
Concerns an efficient algorithm for learning in the limit a special type of regular language called a locally testable language from positive data, and its application to identifying the protein /spl alpha/-chain region in amino acid sequences. First, we present a linear-time algorithm that, given a locally testable language, learns (identifies) its deterministic finite state automaton in the limit from only positive data. This provides a practical and efficient learning method for a specific domain of symbolic analysis. We then describe several experimental results using the learning algorithm. Following a theoretical observation which strongly suggests that a certain type of amino acid sequence can be expressed by a locally testable language, we apply the learning algorithm to identifying the protein /spl alpha/-chain region in amino acid sequences for hemoglobin. Experimental scores show an overall success rate of 95% correct identification for positive data and 96% for negative data.<<ETX>>
28066504
Multiple splicing systems and the universal computability
We propose a new extension of splicing systems, called multiple splicing systems, based on a kind of logic grammars. First, we introduce a class of Elementary formal systems, called simple H-form EFS, and show that its generative power is equivalent to the class of basic splicing systems (the original Head's splicing system) and is more adequate as representation device for formal languages. Next, we gradually extend the simple class of EFSs and get a very natural extension of splicing systems, multiple splicing systems. We show that multiple splicing systems have universal computability.
36727244
Horn Clause Computation by Self-assembly of DNA Molecules
Kobayashi proposed Horn clause computation by DNA molecules, which is more suitable for expressing complex algorithms than other models for DNA computing. This paper describes a new implementation of Horn clause computation by DNA. It employs branching DNA molecules for representing Horn clauses. As derivations are realized by self-assembly of such molecules, the implementation requires only a constant number of laboratory operations. Furthermore, it deals with firstorder Horn clauses with some restrictions. In order to realize first-order logic, we implement variable substitutions by string tiling proposed by Winfree, et al. As we show the computational power of a Horn clause program in our model, we give another proof that a polynomial number of operations using self-assembly of DNA molecules can compute any problem in NP.
39613508
A Magic Pot : Self-assembly Computation Revisited
Molecular computing is a novel computing paradigm recently emerged from groundbreaking wet lab experiments by Adleman in 1994. His experimental work marks a potential capability and feasibility of "one pot" computing with molecules for solving hard problems of practical size.This paper concerns a molecular computing paradigm based on "self-assembly" and "screening mechanism". After a brief getting back to and reviewing Adleman's original work, we propose a new molecular implementation method based on length-only encoding, which leads us to much simpler molecular implementation techniques to solve graph problems.With two examples, we demonstrate the effectiveness of the molecular implementation method for one pot computing based on self-assembly: one is Nondeterministic Finite Automaton Pot and the other Hamiltonian Path Problem Pot.
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.
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.
11284896
Semantic Wiki as a Lightweight Knowledge Management System
Since its birth in 1995, Wiki has become more and more popular This paper presents a Semantic Wiki, a Wiki extended to include the ideas of Semantic Web The proposed Semantic Wiki uses a simple Wiki syntax to write labeled links which represent RDF triples By enabling the writing of labeled links, Semantic Wiki may provide an easy-to-use and flexible environment for an integrated management of content and metadata, so that Semantic Wiki may be used as a lightweight knowledge management system.