Tag: Natural Computing

A synthetic genetic circuit whose signal-response curve is temperature-tunable from band-detection to sigmoidal behaviour

Abstract  Programming new cellular functions by using synthetic gene circuits is a key goal in synthetic biology, and an important element
of this process is the ability to couple to the information processing systems of the host cell using …

Abstract  Programming new cellular functions by using synthetic gene circuits is a key goal in synthetic biology, and an important element
of this process is the ability to couple to the information processing systems of the host cell using synthetic systems with
various signal-response characteristics. Here, we present a synthetic gene system in Escherichia coli whose signal-response curve may be tuned from band detection (strongest response within a band of input concentrations) to
a switch-like sigmoidal response, simply by altering the temperature. This change from a band-detection response to a sigmoidal
response has not previously been implemented. The system allows investigation of a range of signal-response behaviours with
minimal effort: a single system, once inserted into the cells, provides a range of response curves without any genetic alterations
or replacement with other systems. By altering its output, the system may couple to other synthetic or natural genetic circuits,
and thus serve as a useful modular component. A mathematical model has also been developed which captures the essential qualitative
behaviours of the circuit.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9167-3
  • Authors
    • Sangram Bagh, University of Toronto Mississauga Department of Chemical and Physical Sciences, Institute for Optical Sciences 3359 Mississauga Rd. N Mississauga ON L5L 1C6 Canada
    • David R. McMillen, University of Toronto Mississauga Department of Chemical and Physical Sciences, Institute for Optical Sciences 3359 Mississauga Rd. N Mississauga ON L5L 1C6 Canada

On the regularity of circular splicing languages: a survey and new developments

Abstract  
Circular splicing has been introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with
linear splicing. In this paper we focus on the relationship between regular circular lan…

Abstract  

Circular splicing has been introduced to model a specific recombinant behaviour of circular DNA, continuing the investigation initiated with
linear splicing. In this paper we focus on the relationship between regular circular languages and languages generated by finite circular splicing systems. We survey the known results towards a characterization of the intersection between these two classes and provide new contributions
on the open problem of finding this characterization. First, we exhibit a non-regular circular language generated by a circular simple system thus disproving a known result in this area. Then we give new results related to a restrictive class of circular splicing
systems, the marked systems. Precisely, we review in a graph theoretical setting the recently obtained characterization of marked systems generating
regular circular languages. In particular, we define a slight variant of marked systems, that is the g-marked systems, and we introduce the graph associated with a g-marked system. We show that a g-marked system generates a regular circular
language if and only if its associated graph is a cograph. Furthermore, we prove that the class of g-marked systems generating regular circular languages is closed under a complement
operation applied to systems. We also prove that marked systems with self-splicing generate only regular circular languages.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9155-7
  • Authors
    • Paola Bonizzoni, Università degli Studi di Milano-Bicocca Dipartimento di Informatica Sistemistica e Comunicazione Viale Sarca 336 20126 Milano Italy
    • Clelia De Felice, Università di Salerno Dipartimento di Informatica ed Applicazioni 84084 Fisciano SA Italy
    • Gabriele Fici, Università di Salerno Dipartimento di Informatica ed Applicazioni 84084 Fisciano SA Italy
    • Rosalba Zizza, Università di Salerno Dipartimento di Informatica ed Applicazioni 84084 Fisciano SA Italy

Transducer generated arrays of robotic nano-arms

Abstract  We consider sets of two-dimensional arrays, called here transducer generated languages, obtained by iterative applications
of transducers (finite state automata with output). Each transducer generates a set of blocks of symbols suc…

Abstract  

We consider sets of two-dimensional arrays, called here transducer generated languages, obtained by iterative applications
of transducers (finite state automata with output). Each transducer generates a set of blocks of symbols such that the bottom
row of a block is an input string accepted by the transducer and, by iterative application of the transducer, each row of
the block is an output of the transducer on the preceding row. We show how these arrays can be implemented through molecular
assembly of triple crossover DNA molecules. Such assembly could serve as a scaffold for arranging molecular robotic arms capable
of simultaneous movements. We observe that transducer generated languages define a class of languages which is a proper subclass
of recognizable picture languages, but it contains the class of all factorial local two-dimensional languages. By taking the
average growth rate of the number of blocks in the language as a measure of its complexity, we further observe that arrays
with high complexity patterns can be generated in this way.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9157-5
  • Authors
    • Egor Dolzhenko, University of South Florida Department of Mathematics and Statistics Tampa FL 33620 USA
    • Nataša Jonoska, University of South Florida Department of Mathematics and Statistics Tampa FL 33620 USA
    • Nadrian C. Seeman, New York University Chemistry Department New York NY 10003 USA

Trace monoids with idempotent generators and measure-only quantum automata

Abstract  In this paper, we analyze a model of 1-way quantum automaton where only measurements are allowed (
MON
-1qfa). The automaton works on a compatibility alphabet

(S, E)
of observables and its probabilistic behavior is a formal ser…

Abstract  

In this paper, we analyze a model of 1-way quantum automaton where only measurements are allowed (
MON
-1qfa). The automaton works on a compatibility alphabet

(S, E)

of observables and its probabilistic behavior is a formal series on the free partially commutative monoid

FI(S, E)

with idempotent generators. We prove some properties of this class of formal series and we apply the results to analyze the
class

LMO(S, E)

of languages recognized by
MON
-1qfa’s with isolated cut point. In particular, we prove that

LMO(S, E)

is a boolean algebra of recognizable languages with finite variation, and that

LMO(S, E)

is properly contained in the recognizable languages, with the exception of the trivial case of complete commutativity.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9154-8
  • Authors
    • Alberto Bertoni, Università degli Studi di Milano Dipartimento di Scienze dell’Informazione via Comelico 39 20135 Milano Italy
    • Carlo Mereghetti, Università degli Studi di Milano Dipartimento di Scienze dell’Informazione via Comelico 39 20135 Milano Italy
    • Beatrice Palano, Università degli Studi di Milano Dipartimento di Scienze dell’Informazione via Comelico 39 20135 Milano Italy

Deterministic and stochastic P systems for modelling cellular processes

Abstract  This paper presents two approaches based on metabolic and stochastic P systems, together with their associated analysis methods,
for modelling biological systems and illustrates their use through two case studies.

Content Type…

Abstract  

This paper presents two approaches based on metabolic and stochastic P systems, together with their associated analysis methods,
for modelling biological systems and illustrates their use through two case studies.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9158-4
  • Authors
    • Marian Gheorghe, The University of Sheffield Department of Computer Science Regent Court, Portobello Street Sheffield S1 4DP UK
    • Vincenzo Manca, The University of Verona Department of Computer Science Strada Le Grazie 15 37134 Verona Italy
    • Francisco J. Romero-Campero, The University of Nottingham School of Computer Science Jubilee Campus Nottingham NG8 1BB UK

Robust self-assembly of graphs

Abstract  Self-assembly is a process in which small building blocks interact autonomously to form larger structures. A recently studied
model of self-assembly is the Accretive Graph Assembly Model whereby an edge-weighted graph is assembled …

Abstract  

Self-assembly is a process in which small building blocks interact autonomously to form larger structures. A recently studied
model of self-assembly is the Accretive Graph Assembly Model whereby an edge-weighted graph is assembled one vertex at a time
starting from a designated seed vertex. The weight of an edge specifies the magnitude of attraction (positive weight) or repulsion
(negative weight) between adjacent vertices. It is feasible to add a vertex to the assembly if the total attraction minus repulsion of the already built neighbors exceeds a certain threshold,
called the assembly temperature. This model naturally generalizes the extensively studied Tile Assembly Model. A natural question
in graph self-assembly is to determine whether or not there exists a sequence of feasible vertex additions to realize the
entire graph. However, even when it is feasible to realize the assembly, not much can be inferred about its likelihood of
realization in practice due to the uncontrolled nature of the self-assembly process. Motivated by this, we introduce the robust self-assembly problem where the goal is to determine if every possible sequence of feasible vertex additions leads to the
completion of the assembly. We show that the robust self-assembly problem is co-NP-complete even on planar graphs with two
distinct edge weights. We then examine the tractability of the robust self-assembly problem on a natural subclass of planar
graphs, namely grid graphs. We identify structural conditions that determine whether or not a grid graph can be robustly self-assembled,
and give poly-time algorithms to determine this for several interesting cases of the problem. Finally, we also show that the
problem of counting the number of feasible orderings that lead to the completion of an assembly is #P-complete.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9149-5
  • Authors
    • Stanislav Angelov, Google, Inc. New York NY 10011 USA
    • Sanjeev Khanna, University of Pennsylvania Department of Computer and Information Science, School of Engineering and Applied Sciences Philadelphia PA 19104 USA
    • Mirkó Visontai, University of Pennsylvania Department of Mathematics, School of Arts and Sciences Philadelphia PA 19104 USA

On spiking neural P systems

Abstract  This work deals with several aspects concerning the formal verification of SN P systems and the computing power of some variants.
A methodology based on the information given by the transition diagram associated with an SN P system…

Abstract  

This work deals with several aspects concerning the formal verification of SN P systems and the computing power of some variants.
A methodology based on the information given by the transition diagram associated with an SN P system is presented. The analysis
of the diagram cycles codifies invariants formulae which enable us to establish the soundness and completeness of the system
with respect to the problem it tries to resolve. We also study the universality of asynchronous and sequential SN P systems
and the capability these models have to generate certain classes of languages. Further, by making a slight modification to
the standard SN P systems, we introduce a new variant of SN P systems with a special I/O mode, called SN P modules, and study their computing power. It is demonstrated that, as string language acceptors and transducers, SN P modules can
simulate several types of computing devices such as finite automata, a-finite transducers, and systolic trellis automata.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9159-3
  • Authors
    • Oscar H. Ibarra, University of California Department of Computer Science Santa Barbara CA 93106 USA
    • Mario J. Pérez-Jiménez, University of Seville Department of Computer Science and AI Sevilla Spain
    • Takashi Yokomori, Waseda University Department of Mathematics, Faculty of Education and Integrated Arts and Sciences 1-6-1 Nishi-waseda, Shinjuku-ku Tokyo 169-8050 Japan

Computing with energy and chemical reactions

Abstract  Taking inspiration from some laws of Nature—energy transformation and chemical reactions—we consider two different paradigms
of computation in the framework of Membrane Computing. We first study the computational power of energ…

Abstract  

Taking inspiration from some laws of Nature—energy transformation and chemical reactions—we consider two different paradigms
of computation in the framework of Membrane Computing. We first study the computational power of energy-based P systems, a
model of membrane systems where a fixed amount of energy is associated with each object and the rules transform objects by
manipulating their energy. We show that if we assign local priorities to the rules, then energy-based P systems are as powerful
as Turing machines; otherwise, they can be simulated by vector addition systems, and hence are not universal. Then, we consider
stochastic membrane systems where computations are performed through chemical networks. We show how molecular species and
chemical reactions can be used to describe and simulate the functioning of Fredkin gates and circuits. We conclude the paper
with some research topics related to computing with energy-based P systems and with chemical reactions.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9160-x
  • Authors
    • Alberto Leporati, Università degli Studi di Milano – Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336 20126 Milano Italy
    • Daniela Besozzi, Università degli Studi di Milano Dipartimento di Informatica e Comunicazione Via Comelico 39 20135 Milano Italy
    • Paolo Cazzaniga, Università degli Studi di Milano – Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336 20126 Milano Italy
    • Dario Pescini, Università degli Studi di Milano – Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336 20126 Milano Italy
    • Claudio Ferretti, Università degli Studi di Milano – Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Viale Sarca 336 20126 Milano Italy

Preface

Preface
Content Type Journal ArticleDOI 10.1007/s11047-009-9161-9Authors
Paola Bonizzoni, Milan ItalyGheorghe Paun, Bucharest RomaniaGrzegorz Rozenberg, Leiden The NetherlandsClaudio Zandron, Milan Italy

Journal Natural ComputingOnline ISSN 1…

Preface

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9161-9
  • Authors
    • Paola Bonizzoni, Milan Italy
    • Gheorghe Paun, Bucharest Romania
    • Grzegorz Rozenberg, Leiden The Netherlands
    • Claudio Zandron, Milan Italy

All-optical binary flip-flop with the help of Terahertz Optical Asymmetric Demultiplexer

Abstract  The memory device is very important as they store various values either temporary or permanently. Optical flip-flop memories
form a fundamental building block for all-optical packet switches in the next generation communication net…

Abstract  The memory device is very important as they store various values either temporary or permanently. Optical flip-flop memories
form a fundamental building block for all-optical packet switches in the next generation communication networks. All-optical
flip-flop memory with the help of Terahertz Optical Asymmetric Demultiplexer (TOAD) is proposed and described. Principles
and possibilities of all-optical circuits for TOAD based S–R, J–K, D and T flip-flop are reported. Numerical simulation confirming
described method is also given in this paper.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9162-8
  • Authors
    • Goutam Kumar Maity, Calcutta Institute of Technology Uluberia, Howrah West Bengal India
    • Tanay Chattopadhyay, College of Engineering and Management Department of Physics Kolaghat KTPP Township, Midnapur (East) 721171 West Bengal India
    • Dilip Kumar Gayen, College of Engineering and Management Department of Computer Science Kolaghat KTPP Township, Midnapur (East) 721171 West Bengal India
    • Chinmoy Taraphdar, Bankura Christian College Department of Physics Bankura West Bengal India
    • Anup Kumar Maiti, College of Engineering and Management Department of Physics Kolaghat KTPP Township, Midnapur (East) 721171 West Bengal India
    • Santi Prasad Maity, Bengal Engineering College and Science University Department of Information Technology Shibpur, Howrah West Bengal India
    • Jitendra Nath Roy, College of Engineering and Management Department of Physics Kolaghat KTPP Township, Midnapur (East) 721171 West Bengal India