International Journal of Foundations of Computer Science

Spiking neural P systems were introduced in the end of the year 2005, in the aim of incorporating in membrane computing the idea of working with unique objects ("spikes"), encoding the information in the time elapsed between consecutive spikes sent from a cell/neuron to another cell/neuron. More than one dozen of papers where written in the meantime, clarifying many of the basic properties of these devices, especially related to their computing power.

The present paper quickly surveys the basic ideas and the basic results, presenting a complete to-date bibliography, and also giving a completing result related to the normal forms possible for spiking neural P systems: we prove that the indegree of such systems (the maximal number of incoming synapses of neurons) can be bounded by 2 without losing the computational completeness.

A series of research topics and open problems are formulated.

We consider the problem of decontaminating a network infected by a mobile virus. The goal is to perform the task using as small a team of antiviral agents as possible, avoiding recontamination of disinfected areas. In all the existing literature, it is assumed that the immunity level of a decontaminated site is nil; that is, a decontaminated node, in absence of an antiviral agent on site, may be re-contaminated by any infected neighbour. The network decontamination problem is studied here under a new model of immunity to recontamination: we consider the case when a decontaminated vertex, after the cleaning agent has gone, will become recontaminated only if a majority of its neighbours are infected. We study the impact that the presence of local immunity has on the number of antiviral agents necessary to decontaminate the entire network. We establish both lower and upper bounds on the number cleaners in the case of (multidimensional) toroidal meshes, graphs of vertex degree at most three (e.g., cubic graphs, binary trees, etc.), and of tree networks. In all cases the established bounds are tight. All upper-bound proofs are constructive; i.e., we exhibit decontamination protocol achieving the claimed bound. We also analyze the total number of moves performed by the agents, and establish tight bounds in some cases.

In recent works for high performance computing, computation with DNA strands, that is, DNA computing, has considerable attention as one of non-silicon based computing. In this paper, we propose three procedures for computing the maximum of n binary numbers of m bits, which are represented with O(mn) DNA strands. The first procedure computes the maximum of the binary numbers in O(m) steps using O(n) kinds of DNA strands. The second and third procedures also compute the maximum in O(log n) and O(1) steps using O(mn) and O(mn²) kinds of DNA strands, respectively.

Active replication has been widely explored to achieve fault tolerance and to improve system availability, especially in service oriented applications. In this paper we explore software diversity-based active replication in the context of advanced simulation systems, with the aim at improving the timeliness for the production of simulation output. Our proposal is framed by the High-Level-Architecture (HLA), namely a middleware based standard for simulation package interoperability, and results in the design and implementation of an Active Replication Management Layer (ARML) targeted to off-the-shelf SMP computing systems. This layer can be interposed in between each simulator instance and the underlying HLA middleware component, in order to support the execution of diversity-based active replicas of a same simulation package in a totally transparent manner. Beyond presenting the replication framework and the design/implementation of ARML, we also report the results of an experimental evaluation on a case study, quantifying the benefits from our proposal in terms of both simulation execution speed and performance guarantees vs tunable software parameters. (Free software releases of ARML can be found at the URL ).

An "n choose k" counter (C(n,k) counter for short) is a counter which lists all n-bit numbers with (n - k) 0's and k 1's. The C(n,k) counters have applications to solving combinatorial optimization problems and image processing. The main contribution of this work is to present an efficient hardware implementation of the C(n,k) counter. In some applications, C(n,k) counters are used only for small k. The second contribution is to show more efficient implementations that support C(n,k) counters only for small k. We evaluate the performance of our new implementation and known implementations in terms of the number of used slices and the clock frequency for the Xilinx VirtexII family FPGA XC2V3000-4. Although the theoretical analysis shows that our implementation is not the best, it runs in higher clock frequency using fewer number of slices than the other implementations.

Sense of direction is a property of the edge-labeling of a network whose availability facilitates computations and often decreases their complexity. In this paper we consider the problem of providing a sense of direction to an anonymous, unoriented torus. The edges of the torus are initially labeled arbitrarily, and they have to be relabeled with a classical compass sense of direction.

We first describe an algorithm where the relabeling of the edges is performed by a mobile agent that carries a token. The algorithm is optimal both in terms of number of tokens (with no tokens the task cannot be performed), and in terms of number of moves. We then show that the same technique can be used to orient the torus in the classical message-passing environment, thus obtaining an orientation algorithm that improves all the existing ones in this setting.

In this paper we consider a network where an intruder is moving "contaminating" the nodes it passes by, and we focus on the problem of decontaminating such a network by a team of mobile agents.

The contamination/decontamination process has the following asynchronous dynamics: when the team is deployed all nodes are assumed to be contaminated, when an agent transits on a node, it will clean the node, when the node is left with no agent, the node will be recontaminated as soon as at least one of its neighbours is contaminated.

We study the problem in asynchronous chordal ring networks and in tori. We consider two variations of the model: one where agents have only local knowledge, the other in which they have "visibility", i.e., they can "see" the state of their neighbouring nodes.

We first derive lower bounds on the minimum number of agents necessary for the decontamination. In the case of chordal rings we show that the number of agents necessary to perform the cleaning does not depend on the size of the network; in fact it is linear in the length of the longest chord (provided that it is not too long). In the case of a torus, the minimum number of agents is equal to 2 · h, where h is the smallest dimension.

We then propose optimal strategies for decontamination and we analyse the number of moves and the time complexity of the decontamination algorithms, showing that the visibility assumption allows us to decrease substantially both complexity measures. Another advantage of the "visibility model" is that agents move independently and autonomously without requiring any coordination.

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables.

In this paper, we present a process algebra aimed at modelling PKI-based systems. The new language, SPIKY, extends the spi-calculus by adding primitives for the retrieval of certified/uncertified public keys as well as private keys belonging to users of the PKI-based system. SPIKY also formalises the notion of process ownership by PKI users, which is necessary in controlling the semantics of the key retrieval capabilities. We also construct a static analysis for SPIKY that captures the property of term substitutions resulting from message-passing and PKI/cryptographic operations. This analysis is shown to be safe and computable. Finally, we use the analysis to define the term secrecy and peer participation properties for a couple of examples of authentication protocols.

In the unbounded version of the range assignment problem for all-to-all communication in 1D, a set of n radio-stations are placed arbitrarily on a line; the objective is to assign ranges to these radio-stations such that each of them can communicate with the others (using at most n - 1 hops) and the total power consumption is minimum. A simple incremental algorithm for this problem is proposed which produces optimum solution in O(n³) time and O(n²) space. This is an improvement in the running time by a factor of n over the best known existing algorithm for the same problem.

It is well known that a solution for the Firing Squad Synchronization Problem (FSSP) takes time 2n - 1, n being the number of soldiers. It is also known that a solution on a square of n × n soldiers takes the same time. The main result of this paper is a new solution for the FSSP on networks shaped as squares. Our solution is optimal in two aspects: it is communication optimal (the so-called 1-bit solution) and is also time optimal, as it takes 2n - 1 time. It is also used as a building block to construct a very efficient solution on the square torus. Our approach applies also to linearly shaped networks and yields on the ring almost optimal time & communication solutions. In particular, for the square torus with n rows and rings of n processors, if n is even our solution is time & communication optimal. Otherwise, it is communication-optimal but does not match the lower bound on the time of a synchronization just by 1 time unit.

We approximate factorial languages by languages with finite antidictionaries. Let s and m be positive integers with s ≤ m. We construct a language of complexity Θ(n^s), and a sequence of languages with finite antidictionaries, each of those having the complexity Θ(n^m), such that this sequence converges to the original language.