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.
32287187
Sticker systems with complex structures
Abstract In this paper, we propose a variant of sticker systems which uses molecules with complex structures. Since the original sticker systems (Paun et al. (1998) [2, 8]) working on double strands of DNA have been studied as a formal model for self-assembly in DNA computing, we extend the sticker systems to working on more complex (higher-order) structures of DNA molecules. The advantage of sticker systems with complex structures is that augmented with weak codings we can obtain the characterization of recursively enumerable languages by using only sticking (hybridization) operations for complex molecules, while the usual sticker systems require more complicated operations such as the simultaneous use of couples of dominoes or coherent computations besides morphisms.
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.
207106066
Families of Noncounting Languages and Their Learnability from Positive Data
This paper introduces some subclasses of noncounting languages and presents some results on the learnability of the classes from positive data. We first establish several relationships among the language classes introduced and the class of reversible languages. Especially, we introduce the 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. We show its close relation to the class of reversible languages. We then study on the relationship between the closure of the Boolean operations and the learnability in the limit from positive data only. Further, we explore the learnability question of some subclasses of noncounting languages in the model of identification in the limit from positive data. In particular, we show that, for each k, l≥1, (k, l)-CLTS is identifiable in the limit from positive data using reversible automata with the conjectures updated in polynomial time. Some possible applications of the result are also briefly discussed.
62399989
Proceedings of the 8th international conference on Grammatical Inference: algorithms and applications
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.
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.
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.
3026036
Towards a Semantic Wiki-Based Japanese Biodictionary
This paper describes an on-going project to develop and maintain a web-based Japanese Biodictionary within a Semantic Wiki environment. For the development of the dictionary, MediaWiki is extended to enable the writing of labeled links that represent RDF triples. The extension enables Semantic Wiki to provide not only collaborative environment for experts in various biol- ogy fields to create and edit the dictionary, but also the navigation support to manage relations between terms. Using a simple wiki syntax, people can de- velop and maintain the dictionary visually and easily.
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.