Narrow Results

In this paper we introduce a fuzzy version of symport/antiport membrane systems. Our fuzzy membrane systems handle possibly inexact copies of reactives and their rules are endowed with threshold functions that determine whether a rule can be applied or not to a given set of objects, depending of the degree of accuracy of these objects to the reactives specified in the rule. We prove that these fuzzy membrane systems generate exactly the recursively enumerable finite-valued fuzzy subsets of ℕ.

We consider tissue P systems with symport/antiport rules and investigate their computational power when using only a (very) small number of symbols and cells. Even when using only one symbol, we need at most six (seven when allowing only one channel between a cell and the environment) cells to generate any recursively enumerable set of natural numbers. On the other hand, with only one cell we can only generate regular sets when using one channel with the environment, whereas one cell with two channels between the cell and the environment obtains computational completeness with five symbols. Between these extreme cases of one symbol and one cell, respectively, there seems to be a trade-off between the number of cells and the number of symbols. For example, for the case of tissue P systems with two channels between a cell and the environment we show that computational completeness can be obtained with two cells and three symbols as well as with three cells and two symbols, respectively. Moreover, we also show that some variants of tissue P systems characterize the families of finite or regular sets of natural numbers.

Operations with membranes are essential both in brane calculi and in membrane computing. In this paper we take four basic operations from brane calculi, pino, exo, mate, drip, we express them in terms of the membrane computing formalism, and then we investigate the computing power of the P systems using the mate, drip operations as unique evolution rules. All operations are controlled by – and make evolve – multisets of protein-objects embedded in the membranes themselves (not contained in the compartments of the cell, as standard in membrane computing; all compartments delimited by membranes are here empty). Somewhat surprisingly, for systems which use the mate, drip operations we obtain the Turing completeness. The power of P systems based on other operations remains to be investigated.

Membrane systems (currently called P systems) are parallel computing devices inspired by the structure and the functioning of living cells. A standard feature of P systems is that each rule is executed in exactly one time unit. Actually, in living cells different chemical reactions might take different times to be executed; moreover, it might be hard to know precisely such time of execution. For this reason, in [7] two models of P systems (time-free and clock-free P systems) have been defined and investigated, where the time of execution of the rules is arbitrary and the output produced by the system is always the same, independently of this time. Preliminary results concerning time-free and clock-free P system have been obtained in [6, 7, 8]. In this paper we continue these investigations by considering different combinations of possible ingredients. In particular, we present the universality of time-free P systems using bi-stable catalysts. Then, we prove that this result implies that is not possible to decide whether an arbitrary bi-stable catalytic P system is time-free. We present several results about time-free evolution-communication P systems, where the computation is a mixed application of evolution and symport/antiport rules. In this case we obtain the universality even by using non-cooperative evolution rules and antiports of weight one. Finally, we formulate several open problems.

We have been developing a general theory of information distance and a paradigm of applying this theory to practical problems.[3, 19, 20] There are several problems associated with this theory. On the practical side, among other problems, the strict requirement of triangle inequality is unrealistic in some applications; on the theoretical side, the universality theorems for normalized information distances were only proved in a weak form. In this paper, we will introduce a complementary theory that resolves or avoids these problems.

This article also serves as a brief expository summary for this area. We will tell the stories about how and why some of the concepts were introduced, recent theoretical developments and interesting applications. These applications include whole genome phylogeny, plagiarism detection, document comparison, music classification, language classification, fetal heart rate tracing, question answering, and a wide range of other data mining tasks.

In this paper we analyze the dynamics of one-dimensional piecewise maps. We show that one-dimensional piecewise affine maps are equivalent to pseudo-billiard or so called “strange billiard” systems. We also show that use of more general classes of functions lead to undecidability of reachability problem for one-dimensional piecewise maps.

In this paper we consider, from the descriptional complexity point of view, a model of computation introduced in [1], namely accepting network of evolutionary processors with filtered connections (ANEPFCs). First we show that for each morphism h : V → W*, with V ∩ W = ∅, one can effectively construct an ANEPFC, of size 6 + |W|, which accepts every input word w and, at the end of the computation on this word, obtains h(w) in its output node. This result can be applied in constructing two different ANEPFCs, with 27 and, respectively, 26 processors, recognizing a given recursively enumerable language. The first architecture, based on the construction of a universal ANEPFC, has the property that only 7 of its 27 processors depend on the accepted language. On the other hand, all the 26 processors of the second architecture depend on the accepted language, but, differently from the first one, this network simulates efficiently (from both time and space perspectives) a nondeterministic Turing machine accepting the given language.

We investigate the spiking neural P systems with communication on request (SNQ P systems) that are devices in the area of neural like P systems abstracting the way in which neurons work and process information. Here we discuss the SNQ P systems using the rule application strategy as defined by Linqiang Pan and collaborators and we are able to improve their result of universality of such systems using two types of spikes. In the current work, we prove that only one type of spikes is sufficient for reaching the computational power of Turing Machines for these devices, bringing closer to implementation such a device. The result holds both in maximum parallel manner application of the rules as well as the maximum-sequentiality application of rules.

The issue of testing invertibility of cellular automata has been often discussed. Constructing invertible automata is very useful for simulating invertible dynamical systems, based on local rules. The computation universality of cellular automata has long been positively resolved, and by showing that any cellular automaton could be simulated by an invertible one having a superior dimension, Toffoli proved that invertible cellular automaton of dimension d≥2 were computation-universal. Morita proved that any invertible Turing Machine could be simulated by a one-dimensional invertible cellular automaton, which proved computation-universality of invertible cellular automata. This article shows how to simulate any Turing Machine by an invertible cellular automaton with no loss of time and gives, as a corollary, an easier proof of this result.

We introduce and study a family of 2D percolation systems which are based on the bond percolation model of the triangular lattice. The system under study has local correlations, however, bonds separated by a few lattice spacings act independently of one another. By avoiding explicit use of microscopic paths, it is first established that the model possesses the typical attributes which are indicative of critical behavior in 2D percolation problems. Subsequently, the so-called Cardy–Carleson functions are demonstrated to satisfy, in the continuum limit, Cardy's formula for crossing probabilities. This extends the results of S. Smirnov to a non-trivial class of critical 2D percolation systems.

This paper proposes a new variant of spiking neural P systems (in short, SNP systems), nonlinear spiking neural P systems (in short, NSNP systems). In NSNP systems, the state of each neuron is denoted by a real number, and a real configuration vector is used to characterize the state of the whole system. A new type of spiking rules, nonlinear spiking rules, is introduced to handle the neuron’s firing, where the consumed and generated amounts of spikes are often expressed by the nonlinear functions of the state of the neuron. NSNP systems are a class of distributed parallel and nondeterministic computing systems. The computational power of NSNP systems is discussed. Specifically, it is proved that NSNP systems as number-generating/accepting devices are Turing-universal. Moreover, we establish two small universal NSNP systems for function computing and number generator, containing 117 neurons and 164 neurons, respectively.

Based on the feature and communication of neurons in animal neural systems, spiking neural P systems (SN P systems) were proposed as a kind of powerful computing model. Considering the length of axons and the information transmission speed on synapses, SN P systems with delay on synapses (SNP-DS systems) are proposed in this work. Unlike the traditional SN P systems, where all the postsynaptic neurons receive spikes at the same instant from their presynaptic neuron, the postsynaptic neurons in SNP-DS systems would receive spikes at different instants, depending on the delay time on the synapses connecting them. It is proved that the SNP-DS systems are universal as number generators. Two small universal SNP-DS systems, with standard or extended rules, are constructed to compute functions, using 56 and 36 neurons, respectively. Moreover, a simulator has been provided, in order to check the correctness of these two SNP-DS systems, thus providing an experimental validation of the universality of the systems designed.

The classic spiking neural P (SN P) systems abstract the real biological neural network into a simple structure based on graphs, where neurons can only communicate on the plane. This study proposes the hypergraph-based numerical spiking neural membrane (HNSNM) systems with novel repartition protocols. Through the introduction of hypergraphs, the HNSNM systems can characterize the high-order relationships among neurons and extend the traditional neuron structure to high-dimensional nonlinear spaces. The HNSNM systems also abstract two biological mechanisms of synapse creation and pruning, and use plasticity rules with repartition protocols to achieve planar, hierarchical and spatial communications among neurons in hypergraph neuron structures. Through imitating register machines, the Turing universality of the HNSNM systems is proved by using them as number generating and accepting devices. A universal HNSNM system consisting of 41 neurons is constructed to compute arbitrary functions. By solving NP-complete problems using the subset sum problem as an example, the computational efficiency and effectiveness of HNSNM systems are verified.

A discrete Gelfand–Tsetlin pattern is a configuration of particles in ℤ². The particles are arranged in a finite number of consecutive rows, numbered from the bottom. There is one particle on the first row, two particles on the second row, three particles on the third row, etc., and particles on adjacent rows satisfy an interlacing constraint. We consider the uniform probability measure on the set of all discrete Gelfand–Tsetlin patterns of a fixed size where the particles on the top row are in deterministic positions. This measure arises naturally as an equivalent description of the uniform probability measure on the set of all tilings of certain polygons with lozenges. We prove a determinantal structure, and calculate the correlation kernel. We consider the asymptotic behavior of the system as the size increases under the assumption that the empirical distribution of the deterministic particles on the top row converges weakly. We consider the asymptotic "shape" of such systems. We provide parameterizations of the asymptotic boundaries and investigate the local geometric properties of the resulting curves. We show that the boundary can be partitioned into natural sections which are determined by the behavior of the roots of a function related to the correlation kernel. This paper should be regarded as a companion piece to the paper [E. Duse and A. Metcalfe, Asymptotic geometry of discrete interlaced patterns: Part II, in preparation], in which we resolve some of the remaining issues. Both of these papers serve as background material for the papers [E. Duse and A. Metcalfe, Universal edge fluctuations of discrete interlaced particle systems, in preparation; E. Duse and K. Johansson and A. Metcalfe, Cusp Airy process of discrete interlaced particle systems, in preparation], in which we examine the edge asymptotic behavior.

Universality of ratios of cumulants depends on the minor changes in the definition of time.

The two-dimensional antiferromagnetic spin-1 Ising model with positive biquadratic interaction is simulated on a cellular automaton which based on the Creutz cellular automaton for square lattice. Phase diagrams characterizing phase transition of the model are presented for a comparison with those obtained from other calculations. We confirm the existence of the intermediate phase observed in previous works for some values of J/K and D/K. The values of the static critical exponents (β, γ and ν) are estimated within the framework of the finite-size scaling theory for D/K<2J/K. Although the results are compatible with the universal Ising critical behavior in the region of D/K<2J/K-4, the model does not exhibit any universal behavior in the interval 2J/K-4<D/K<2J/K.

Critical properties of hulls of directed spiral percolation clusters are studied on the square and triangular lattices in two dimensions (2D). The hull fractal dimension (d_H) and some of the critical exponents associated with different moments of the hull size distribution function of the anisotropic DSP clusters are reported here. The values of d_H and other critical exponents are found the same within error bars on both the lattices. The universality of the hull's critical exponents then holds true between the square and triangular lattices in 2D unlike the cluster's critical exponents which exhibit a breakdown of universality. The hull fractal dimension (d_H ≈ 1.46) is also found close to 4/3 and away from 7/4, that of ordinary percolation cluster hull. A new conjecture is proposed for d_H in terms of two connectivity length exponents (ν_‖ and ν_⊥) of the anisotropic clusters generated here. The values of d_H and other critical exponents obtained here are very close to that of the spiral percolation cluster hull. The hull properties of the DSP clusters are then mostly determined by the rotational constraint and almost independent of the directional constraint present in the model.

The sand-pile models exhibit a great diversity of behavioral patterns. The average height as a function on time points out the variety of the sand-pile's criticality. We define the classes of universality for the sand-piles in terms of the spectrum of the average height. The definition, in particular, distinguishes two classes with Manna's and Bak et al. sand-piles as the typical representatives. The one-parametric family of the models investigated in this paper develops a crossover between the classes and introduces the infinite quantity of other sand-pile's classes. The parameter is the number of grains that any unstable cell transfers to its neighbors. The sand-piles admit a certain normalization generating unified laws. The spectral approach increases the precision of the universalities from our size distribution analysis. The latter describes the sand-piles' typical distribution, sets the correspondence between the sand-piles with small and large parameter values, but fails to determine their diversity.

Directed spiral percolation (DSP) is a new percolation model with crossed external bias fields. Since percolation is a model of disorder, the effect of external bias fields on the properties of disordered systems can be studied numerically using DSP. In DSP, the bias fields are an in-plane directional field (E) and a field of rotational nature (B) applied perpendicular to the plane of the lattice. The critical properties of DSP clusters are studied here varying the direction of E field and intensities of both E and B fields in two-dimensions. The system shows interesting and unusual critical behavior at the percolation threshold. Not only the DSP model is found to belong in a new universality class compared to that of other percolation models but also the universality class remains invariant under the variation of E field direction. Varying the intensities of the E and B fields, a crossover from DSP to other percolation models has been studied. A phase diagram of the percolation models is obtained as a function of intensities of the bias fields E and B.

This paper proposes a universal constructor implemented on a self-timed cellular automaton, which is a particular type of asynchronous cellular automaton. Our construction utilizes the asynchronous nature of the underlying cellular automaton in a direct way, as a result of which it is simpler than the conventional construction based on the simulation of a synchronous cellular automaton by an asynchronous cellular automaton. Our model employs 39 rotation-invariant rules and the state of each cell is encoded by 8 bits.