87 (1) 2008

Special Issue on Membrane Computing - Preface i-ii
A P Systems Flat Form Preserving Step-by-step Behaviour
Roberto Barbuti, Andrea Maggiolo-Schettini, Paolo Milazzo, Simone Tini 1-34
Starting from a compositional operational semantics of transition P Systems we have previously defined, we face the problem of developing an axiomatization that is sound and complete with respect to some behavioural equivalence. To achieve this goal, we propose to transform the systems into a normal form with an equivalent semantics. As a first step, we introduce axioms which allow the transformation of membrane structures into flat membranes. We leave as future work the further step that leads to the wanted normal form.
Implementing Sorting Networks with Spiking Neural P Systems
Rodica Ceterchi, Alexandru Ioan Tomescu 35-48
Spiking neural P systems simulate the behavior of neurons sending signals through axons. Recently, some applications concerning Boolean circuits and sorting algorithms have been proposed. In this paper, we study the ability of such systems to simulate a well known parallel sorting model, sorting networks. First, we construct spiking neural P systems which act as comparators of two values, and then show how to assemble these building blocks according to the topology of a sorting network of N values. In the second part of the paper, we formalize a framework to transform any sorting network into a network composed of comparators which sort n values, 2 < n < N, having the same behaviour as the original sorting network, but using fewer neurons and synapses than the direct simulation. A comparison between the two models proposed here and the sorting model of Ionescu and Sburlan is also given.
Computational Complexity of Simple P Systems
Gabriel Ciobanu, and Andreas Resios 49-59
This paper introduces a new class of membrane systems called simple P systems, and studies their computational complexity. We start by presenting the knapsack problem and its time complexity. Then we study the computational complexity of simple P systems by considering the allocation of resources enabling the parallel application of the rules. We show that the decision version of the resource allocation problem for simple P systems is NP-complete, by using the knapsack problem.
Solving Subset Sum by Spiking Neural P Systems with Pre-computed Resources
Alberto Leporati, Miguel A. Gutiérrez-Naranjo 61-77
Recently the possibility of using spiking neural P systems for solving computationally hard problems has been considered. Such solutions assume that some (possibly exponentially large) pre-computed resources are given in advance, provided that their structure is "regular" and they do not contain neither "hidden information" that simplify the solution of specific instances, nor an encoding of all possible solutions (that is, an exponential amount of information that allows to cheat while solving the instances of the problem). In this paper we continue this research line, and we investigate the possibility of solving numerical NP-complete problems such as Subset Sum. In particular, we first propose a semi-uniform family of spiking neural P systems in which every system solves a specific instance of Subset Sum. Then, we exploit a technique used to calculate Iterated Addition with Boolean circuits to obtain a uniform family of spiking neural P systems in which every system is able to solve any instance of Subset Sum of a fixed size. All the systems here considered are deterministic, and their size generally grows exponentially with respect to the instance size.
On the Computational Efficiency of Polarizationless Recognizer P Systems
with Strong Division and Dissolution
Claudio Zandron, Alberto Leporati, Claudio Ferretti, Giancarlo Mauri,
Mario J. Pérez-Jiménez 79-91
Recognizer P systems with active membranes have proven to be very efficient computing devices, being able to solve NP-complete decision problems in a polynomial time. However such solutions usually exploit many powerful features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong or weak forms of division rules. In this paper we contribute to the study of the computational power of polarizationless recognizer P systems with active membranes. Precisely, we show that such systems are able to solve in polynomial time the NP-complete decision problem 3- sat by using only dissolution rules and a form of strong division for non-elementary membranes, working in the maximallly parallel way.
A Quantum-Inspired Evolutionary Algorithm Based on P systems for Knapsack Problem
Ge-Xiang Zhang, Marian Gheorghe, Chao-Zhong Wu 93-116
This paper introduces an evolutionary algorithm which uses the concepts and principles of the quantum-inspired evolutionary approach and the hierarchical arrangement of the compartments of a P system. The P system framework is also used to formally specify this evolutionary algorithm. Extensive experiments are conducted on a well-known combinatorial optimization problem, the knapsack problem, to test the effectiveness of the approach. These experimental results show that this evolutionary algorithm performs better than quantum-inspired evolutionary algorithms, for certain arrangements of the compartments of the P system structure utilized.
Smaller Universal Spiking Neural P Systems
Xingyi Zhang, Xiangxiang Zeng, Linqiang Pan 117-136
The problem of finding small universal spiking neural P systems was recently investigated by Andrei Paun and Gheorghe Paun, for spiking neural P systems used as devices computing functions and as devices generating sets of numbers. For the first case, a universal spiking neural P system was produced by using 84 neurons for standard rules and using 49 neurons for extended rules. For spiking neural P systems used as generators of sets of numbers, a universal system with standard rules having 76 neurons, and one with extended rules having 50 neurons were obtained. In this paper, we continue the study of small universal spiking neural P systems and we improve in the number of neurons as follows. The small universal spiking neural P systems use 67 neurons for standard rules and 41 neurons for extended rules in the case of computing functions, and 63 neurons for standard rules and 41 neurons for extended rules in the case of generating sets of numbers.

87 (2) 2008

Cellular Automata: Theory and Application in Artificial Intelligence - Preface i-ii
Exploring Cycle Structures of Additive Cellular Automata
Niloy Ganguly, Biplab K. Sikdar, P. Pal Chaudhuri 137-154
This paper reports the complete characterization of additive cellular automaton (ACA) that employs xor and xnor logic to realize its next state function. Compared to linear cellular automaton (LCA) [], which employs only xor logic in its next state function, an ACA displays much more wider varieties of state transition behavior leading to enhanced computing power. An analytical framework is developed to characterize the cyclic vector subspaces of an ACA that can be derived from careful analysis of the vector subspaces covered by the LCA. A scheme is proposed to explore the ACA structures having different state transition behavior than that of its LCA counterpart. The reported theoretical analysis justifies the nature of differences.
A New Time-Optimum Synchronization Algorithm for Rectangle Arrays
Hiroshi Umeo, Hiroki Uchino 155-164
The firing squad synchronization problem on cellular automata has been studied extensively for more than forty years, and a rich variety of synchronization algorithms have been proposed so far. In the present paper, we propose a new optimum-time algorithm for synchronizing two-dimensional cellular automata. The algorithm can synchronize any two-dimensional rectangle array of size m ×n in optimum m + n + max(m, n)- 3 steps. A partial implementation of the algorithm for small cellular arrays is also given.
Radial View of Continuous Cellular Automata
Paola Flocchini, Vladimir Cezar 165-183
Continuous cellular automata (or coupled map lattices) are cellular automata where the state of the cells are real values in [0,1] and the local transition rule is a real function.
The classical observation medium for cellular automata, whether Boolean or continuous, is the space-time diagram, where successive rows correspond to successive configurations in time.
In this paper we introduce a different way to visualize the evolution of continuous cellular automata called Radial Representation and we employ it to observe a particular class of continuous cellular automata called fuzzy cellular automata (FCA), where the local rule is the "fuzzification" of the disjunctive normal form that describes the local rule of the corresponding Boolean cellular automata.
Our new visualization method reveals interesting dynamics that are not easily observable with the space-time diagram. In particular, it allows us to detect the quick emergence of spatial correlations among cells and to observe that all circular FCA from random initial configurations appear to converge towards an asymptotic periodic behavior. We propose an empirical classification of FCA based on the length of the observed periodic behavior: interestingly, all the minimum periods that we observe are of lengths one, two, four, or n (where n is the size of a configuration).
Different Types of Linear Fuzzy Cellular Automata and their Applications
Subhasree Basu, Sumita Basu 185-205
A linear array of interconnected fuzzy automaton is called linear fuzzy cellular automaton. It is shown that the language class of linear fuzzy cellular automata strictly contains the language class of linear cellular automata. This justifies the wide spread use of linear fuzzy cellular automaton as is evident from the literature.
In this paper a special type of cellular automaton (CA) model is investigated. This CA model computes effect due to interaction of neighboring cells and effect due to external disturbance on the cells simultaneously. The transition due to both the effects may be represented by a single function which is the composition of two functions. Further it is shown that the class of language accepted by linear hybrid fuzzy cellular automata is included in the class of language accepted by linear hybrid fuzzy cellular automata with external input(HFCAI). HFCAI is useful for computing growth in evolutionary systems which are also affected by external cause.
A Neuro-Genetic Framework for Pattern Recognition in Complex Systems
Stefania Bandini, Leonardo Vanneschi, Andrew Wuensche, Alessandro Bahgat Shehata 207-226
This paper presents a general framework to automatically generate rules that produce given spatial patterns in complex systems. The proposed framework integrates Genetic Algorithms with Artificial Neural Networks or Support Vector Machines. Here, it is tested on a well known 3-values, 6-neighbors, k-totalistic cellular automata rule called the "burning paper" rule. Results are encouraging and should pave the way for the use of the proposed framework in real-life complex systems models.
Cellular Automata Based Design of Cost Optimal Steel Building Frames
Debashis Moitra, S. Dhar, J.M. Mallick, S. Sadhu, Biplab K. Sikdar 227-245
This work proposes graceful application of cellular automata (CA) to address a well known design problem in civil engineering. A large number of design alternatives exists regarding the choice of bracing pattern and the placing of braces in a tall steel building frame. The target is to find a cost optimal steel structure through proper placing of braces. In the conventional design procedure, based on the principles of structural engineering, an extremely large number of design alternatives exists, making it nearly impossible to arrive at an appropriate design of the bracing system that may lead to optimum design of the entire structure. The proposed design scheme, developed around the GF(2³) CA, offers better alternatives and an easier way to arrive at the near-optimum solution in zero time. The GF(2³) CA, defined in Galois extension field, suits the modeling of different braces that are conventionally considered for designing multi-storied steel building frames. A CA state on the other hand, corresponds to bracing pattern of a storey and can be tuned to achieve the desired solution. The exhaustive experimental results point to the fact that the proposed CA based approach is most effective, while considering the design of tall building frames, and can reuse a design for scalability.
Lava Flow Hazard Evaluation Through Cellular Automata and Genetic Algorithms:
an Application to Mt Etna Volcano
Rocco Rongo, William Spataro, Donato D'Ambrosio, Maria Vittoria Avolio, Giuseppe A. Trunfio, Salvatore Di Gregorio 247-268
A hybrid technique based on Cellular Automata and Genetic Algorithms has been used for modeling lava flows on Mt Etna volcano (Italy). In particular, a Parallel Master-Slave Genetic Algorithm has been applied to evolve a two dimensional Cellular Automata model for "aa"-type lava flows, typical of the considered study area. Specifically, the 2001 Etnean Nicolosi case study has been considered for model calibration, while a subsequent validation phase has been performed by considering further events occurred in the same area. Results have confirmed both the goodness of the cellular automata simulation model and of the genetic algorithm employed for its calibration. An application concerning hazard evaluation has been subsequently performed on a vast area of the volcano, regarding different types of vulnerability assessments. Results have pointed out the validity of the methodology and its usefulness for Civil Defence purposes.

87 (3-4) 2008

Characterizing DNA Bond Shapes Using Trajectories
Michael Domaratzki 269-285
We consider the use of DNA trajectories to characterize DNA bond shapes. This is an extension of recent work on the bond-free properties of a language. Using a new definition of bond-freeness, we show that we can increase the types of DNA bond shapes which are expressible. This is motivated by the types of bond shapes frequently found in DNA computing.
We examine the algebraic properties of sets of DNA trajectories. In particular, we consider rotation of trajectories and weakening of the bonding conditions expressed by a set of DNA trajectories. We also consider decidability results for bond-freeness with respect to our definition.
Is Timed Branching Bisimilarity a Congruence Indeed?
Wan Fokkink, Jun Pang, Anton Wijs 287-311
We show that timed branching bisimilarity as defined by Van der Zwaag [17] and Baeten and Middelburg [2] is not an equivalence relation, in case of a dense time domain. We propose an adaptation based on Van der Zwaag's definition, and prove that the resulting timed branching bisimilarity is an equivalence indeed. Furthermore, we prove that in case of a discrete time domain, Van der Zwaag's definition and our adaptation coincide. Finally, we prove that a rooted version of timed branching bisimilarity is a congruence over a basic timed process algebra containing parallelism, successful termination and deadlock.
New Bit Reduction of Vector Quantization Using Block Prediction and Relative Addressing
Yu-Chen Hu, Piyu Tsai, Chun-Chi Lo 313-329
A low bit rate image coding scheme based on vector quantization is proposed. In this scheme, the block prediction coding and the relative addressing techniques are employed to cut down the required bit rate of vector quantization. In block prediction coding, neighboring encoded blocks are taken to compress the current block if a high degree of similarity between them is existed. In the relative addressing technique, the redundancy among neighboring indices are exploited to reduce the bit rate. From the results, it is shown that the proposed scheme significantly reduces the bit rate of VQ while keeping good image quality of compressed images.
Complete Process Semantics of Petri Nets
Gabriel Juhás, Robert Lorenz, Sebastian Mauser 331-365
In the first part of this paper we extend the semantical framework proposed in [22] for process and causality semantics of Petri nets by an additional aim, firstly mentioned in the habilitation thesis [15]. The aim states that causality semantics deduced from process nets should be complete w.r.t. step semantics of a Petri net in the sense that each causality structure which is enabled w.r.t. step semantics corresponds to some process net.
In the second part of this paper we examine several process semantics of different Petri net classes w.r.t. this aim. While it is well known that it is satisfied by the process semantics of place/transition Petri nets (p/t-nets), we show in particular that the process semantics of p/t-nets with weighted inhibitor arcs (PTI-nets) proposed in [22] does not satisfy the aim. We develop a modified process semantics of PTI-nets fulfilling the aim of completeness and also all remaining axioms of the semantical framework. Finally, we sketch results in literature concerning the aim of completeness for process definitions of various further Petri net classes.
The paper is a revised and extended version of the conference paper [18].
sPBC: A Markovian Extension of Petri Box Calculus with Immediate Multiactions
Hermenegilda Macià, Valentín Valero, Fernando Cuartero, M. Carmen Ruiz 367-406
Petri Box Calculus (PBC) is an algebraic model for the description of concurrent systems and sPBC (stochastic Petri Box Calculus) is a Markovian extension of that model. In this paper we add immediate multiactions to sPBC in order to increase the description power of this language. Thus, we both have timed multiactions that follow an exponential distribution, and multiactions that do not require any time and can be immediately executed. The denotational semantics of this model is based on a special class of GSPN (Generalized Stochastic Petri Nets), called gs-boxes .
On Descriptional Complexity of Partially Parallel Grammars
Tomás Masopust, Alexander Meduna 407-415
This paper presents some new results concerning the descriptional complexity of partially parallel grammars. Specifically, it proves that every recursively enumerable language is generated (i) by a four-nonterminal scattered context grammar with no more than four non-context-free productions, (ii) by a two-nonterminal multisequential grammar with no more than two selectors, or (iii) by a three-nonterminal multicontinuous grammar with no more than two selectors.
A New Probabilistic Approach for Fractal Based Image Compression
Suman K. Mitra, Malay K. Kundu, C.A. Murthy, Bhargab B. Bhattacharya, Tinku Acharya 417-433
Approximation of an image by the attractor evolved through iterations of a set of contractive maps is usually known as fractal image compression. The set of maps is called iterated function system (IFS). Several algorithms, with different motivations, have been suggested towards the solution of this problem. But, so far, the theory of IFS with probabilities, in the context of image compression, has not been explored much. In the present article we have proposed a new technique of fractal image compression using the theory of IFS and probabilities. In our proposed algorithm, we have used a multiscaling division of the given image up to a predetermined level or up to that level at which no further division is required. At each level, the maps and the corresponding probabilities are computed using the gray value information contained in that image level and in the image level higher to that level. A fine tuning of the algorithm is still to be done. But, the most interesting part of the proposed technique is its extreme fastness in image encoding. It can be looked upon as one of the solutions to the problem of huge computational cost for obtaining fractal code of images.
Algorithmic Approach to Devaney Chaos in Shift Spaces
Piotr Oprocha 435-446
Among the class of sofic shifts Devaney chaos is equivalent to topological transitivity. The aim of this paper is to study possibilities of detection of this phenomena when a right-resolving graph presentation of a sofic shift is given. We show that Devaney chaos detection is co-NP-hard problem and point out some possible improvements of algorithms known from the literature.
Fast VQ Codebook Generation Method Using Codeword Stability Check and Finite State Concept
Piyu Tsai, Yu-Chen Hu, Hsiu-Lien Yeh 447-463
The codebook design in the vector quantization scheme is important because it affects the image quality of the encoded image. The Linde-Buzo-Gray (LBG) codebook generation algorithm is well known and a popular choice among codebook users. However, a heavy computational complexity is consumed for the iteratively clustering process in the LBG algorithm. In this paper, the similarity of codewords in consecutive rounds of the LBG algorithm is exploited to reduce the computational complexity.
By checking the stability of codewords, the status of each codeword in the codebook can be determined. Only the unstable codewords are refined to generate the new codebook. The proposed method can be further improved by cooperating with the finite state technique. Experimental results show that the computational complexity of the proposed method is reduced to about 4% of the LBG algorithm while achieving a slightly worse image quality.
Automatic Unsupervised Segmentation Methods for MRI Based on Modified Fuzzy C-Means
Kai Xiao, Sooi Hock Ho, Aboul ella Hassanien 465-481
Robust User Password Change Scheme based on the Elliptic Curve Cryptosystem
Eun-Jun Yoon, Kee-Young Yoo 483-492
In this paper, an efficient user password change scheme based on the elliptic curve discrete logarithm problem (ECDLP)is presented. In contrast to the existing password change schemes using a server's public key, the proposed scheme can securely update user passwords without a complicated process and server's public key, and also provides explicit key auth