Category: Uncategorized

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

Beyond evolutionary trees

Abstract  In Computational Biology, the notion of phylogeny has become synonymous with tree-like evolution. Recent advances in the Life
Sciences have suggested that evolution has a much more diverse course. In this paper we will survey some …

Abstract  

In Computational Biology, the notion of phylogeny has become synonymous with tree-like evolution. Recent advances in the Life
Sciences have suggested that evolution has a much more diverse course. In this paper we will survey some of the models that
have been proposed to overcome the limitations of using phylogenies to represent evolutionary histories.

  • Content Type Journal Article
  • DOI 10.1007/s11047-009-9156-6
  • Authors
    • Gianluca Della Vedova, Università degli Studi di Milano-Bicocca Dipartimento di Statistica Milano Italy
    • Riccardo Dondi, Università degli Studi di Bergamo Dipartimento di Scienze dei Linguaggi, della Comunicazione e degli Studi Culturali Bergamo Italy
    • Tao Jiang, University of California at Riverside Department of Computer Science Riverside CA USA
    • Giulio Pavesi, Università degli Studi di Milano Dipartimento di Informatica e Comunicazione Milano Italy
    • Yuri Pirola, Università degli Studi di Milano-Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Milano Italy
    • Lusheng Wang, City University of Hong Kong Department of Computer Science Kowloon Hong Kong

Journal Publication versus Conference Contribution?

In a recent issue of the Communications of the ACM, Moshe Vardi discusses the pros and cons of journal archival publications versus conference contributions. The upshot of his statement, which points to two recent contributions to the viewpoint columns…

In a recent issue of the Communications of the ACM, Moshe Vardi discusses the pros and cons of journal archival publications versus conference contributions. The upshot of his statement, which points to two recent contributions to the viewpoint columns of the journal [1], [2] is that perhaps it is time for Computer Scientists to shift emphasis away from conference and workshop contributions, and start publishing in journal as all other sciences do. A lively discussion followed, see among others, the opinion piece of Lance Fortnow.

As an editor myself of Genetic Programming and Evolvable Machines I have always wondered why it would be more attractive for people in our discipline to publish in conference venues than in archival journals. Are there not enough journals to allow for scientific progress? Or is there a dire need to communicate with colleagues in spatial co-location? Well, to my mind, none of the two! We are not the types of people that wanted to discuss our results to extreme length. Our conferences and workshops usually operate under tight time constraints, and one to three questions is about the average a presenter receives, anything else would eat into the next presenter’s time and is discouraged. Also, the number of journals now accepting work from our field has grown over the years to a very reasonable number so that there is no shortage of places where quality work could find a home.

What is it then, that makes us submit and publish so much at conferences? Possible explanations are the existence of deadlines and the incremental nature of much of the work published. The existence of deadlines is a valuable selection pressure in our hectic times where everything is under the dictate of time-driven priorities. It can only be mimicked by journals through the introduction of regular “special issues” which also come with this requirement, and usually are successful in attracting work. As for the second possible explanation, I’d like to cite from [1] on the pitfalls of program committee work: “And arguably it is the more innovative papers that suffer because they are time consuming to read and understand, so they are the most likely to be either completely misunderstood or underappreciated by an increasingly error-prone process.” So while innovative work has a harder time at conferences, “our culture creates more units to review with a lower density of new ideas.” It is not only that we get to review smaller pieces of work, we are also more busy, with all the workshops and conferences that make us look at these papers. “Genuinely innovative papers that have issues, but could have been conditionally accepted, are all too often rejected in this climate of negativism. So the less ambitious, but well-executed work trumps what could have been the more exciting result.” Those would have to be revised and revised and revised again, and there is no time to do this for conferences. Journal articles, on the other hand, can be worked on for a long time, if need be, and there is no time pressure except for the fact that delays could be unbearable and make results obsolete.

In the end, however, it is the impact of the work that counts most. And it is my experience that a carefully edited journal paper is worth the effort, as it produces impact on a scale that conference papers have diffulty to achieve.

[1] K. Birman and F.B. Schneider. Comm. ACM, 52(5) 2009, p. 34
[2] J. Crowcroft, S. Keshav, and N. McKeown, Comm. ACM, 52(1) 2009, p. 27

Additional awards at GECCO-2009

There were several awards presented at the GECCO-2009 conference aside from the Human-Competitive Results Awards (Humies) awards about which Wolfgang posted previously, and for which I’ve listed the other winners below. Of particular interest to reader…

There were several awards presented at the GECCO-2009 conference aside from the Human-Competitive Results Awards (Humies) awards about which Wolfgang posted previously, and for which I’ve listed the other winners below. Of particular interest to readers of this blog may be the Best Paper awards from each of the technical tracks; these are generally awarded for exciting new results, several of which may soon be appearing in more complete form in our field’s journals. In addition, this year was the first year of the SIGEVO GECCO Impact Award, for the papers with the most citations from the GECCO conference 10 years ago.
Congratulations to all of the winners!
2009 SIGEVO GECCO Impact Awards, for the papers with the most citations from GECCO 1999
M. Pelikan, D. Goldberg, E. Cantu-Paz: “BOA: The Bayesian Optimization Algorithm”
Citations: 447
S. Hofmeyer, S. Forrest: “Immunity by Design: An Artificial Immune System”
Citations: 212
Humies BRONZE MEDALS
Perez, Olague: “Evolutionary Learning of Local Descriptor Operators for Object Recognition”
AND Hauptpman, Elyasay, Sipper, Karman: “GP to Evolve Solvers for the Rush Hour Problem”
Humies SILVER MEDAL
Shahzad, Zahid, Farooq, Khayam: “GA+PSO for User ID on Smart Phones”
Humies GOLD MEDAL
Forrest, Le Goues, Nguyen, Weimer: “GP for Automated Software Repair”
2009 GECCO Best Paper Awards
Ant Colony Optimization and Swarm Intelligence: “Parallel Shared Memory Strategies for Ant-Based Optimization Algorithms” by T. Bui, T. Nguyen, J. R. Rizzo Jr.
Artificial Life, Evolutionary Robotics, Adaptive Behavior, Evolvable Hardware: “How Novelty Search Escapes the Deceptive Trap of Learning to Learn” by S. Risi, S. D. Vanderbleek, C. E. Hughes, K. O. Stanley
Bioinformatics and Computational Biology Modeling: “Evolutionary Fitness for DNA Motif Discovery” by S. Rahmann, T. Marschall, F. Behler, O. Kramer
Combinatorial Optimization and Metaheuristics: “Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem” by S. Kratsch, F. Neumann
Estimation of Distribution Algorithms: “EDA-RL: Estimation of Distribution Algorithms for Reinforcement Learning Problems” by H. Handa
AND
“Approximating the Search Distribution to the Selection Distribution in EDAs” by S. I. Valdez-Peña, A. Hernández-Aguirre, S. Botello-Rionda
Evolution Strategies and Evolutionary Programming: “Efficient Natural Evolution Strategies” by Y. Sun, D. Wierstra, T. Schaul, J. Schmidhuber
Evolutionary Multiobjective Optimization: “Multiplicative Approximations and the Hypervolume Indicator” by T. Friedrich, C. Horoba, F. Neumann
Generative and Developmental Systems: “The Sensitivity of HyperNEAT to Different Geometric Representations of a Problem” by J. Clune, C. Ofria, R. T. Pennock
Genetic Algorithms: “Tunneling Between Optima: Partition Crossover for the Traveling Salesman Problem” by D. Whitley, A. Howe, D. Hains
Genetic Programming: “A Genetic Programming Approach to Automated Software Repair” by S. Forrest, T.V. Nguyen, W. Weimer, C. Le Goues
Genetics-Based Machine Learning: “Learning Sensorimotor Control Structures with XCSF” by M. V. Butz, G. K. M. Pedersen, P. O. Stalph
AND
“New Entropy Model for Extraction of Structural Information from XCS Population” by W. K. Park, J. C. Oh
Parallel Evolutionary Systems: “Strategies to Minimise the Total Run Time of Cyclic Graph Based Genetic Programming with GPUs” by T. E. Lewis, G. D. Magoulas
Real World Applications: “Optimizing Low-Discrepancy Sequences with an Evolutionary Algorithm” by F.-M. De Rainville, C. Gagné, O. Teytaud, D. Laurendeau
Search Based Software Engineering: “Software Project Planning for Robustness and Completion Time in the Presence of Uncertainty using Multi Objective Search Based Software Engineering” by S. Gueorguiev, M. Harman, G. Antoniol
Theory: “Dynamic Evolutionary Optimisation: An Analysis of Frequency and Magnitude of Change” by P. Rohlfshagen. P. K. Lehre, X. Yao
GECCO Graduate Student Workshop: “Learnable Evolution Model Performance Impaired by Binary Tournament Survival Selection” by M. Coletti (George Mason University)

An LCS Review for Beginners and Non-Computer Scientists.

I am pleased to share with you that the Journal of Artificial Evolution and Applications has recently published my LCS Review paper entitled, “Learning Classifier Systems: A Complete Introduction, Review, and Roadmap”. I wrote this from the perspective of a non-computer scientist, to introduce the basic LCS concept, as well as the variation represented in different LCS implementations that have been tasked to different problem domains. It was my goal and hope that this review might provide a reasonable starting point for outsiders interested in understanding or getting involved in the LCS community. This paper may be viewed using the following link: Thanks! I enjoyed listening to the many excellent GBML talks given at GECCO this year.

http://www.hindawi.com/journals/jaea/aip.736398.pdf