P systems with energy accounting ∗

We consider P systems where each evolution rule “Produces” or “Consumes” some quantity of energy, in amounts which are expressed as integer numbers. In each moment and in each membrane the total energy involved in an evolution step should be positive, but if “Soo much” energy is present in a membrane, then the membrane will be destroyed (dissolved). We show that this feature is rather powerful. In the case of multisets of symbol-objects we find that systems with two membranes and arbitrary energy associated with rules, or with arbitrarily many membranes and a bounded energy associated with rules characterize the recursively enumerable sets of vectors of natural numbers (catalysts and priorities are used). In the case of string-objects we have only proved that the recursively enumerable languages can be generated by systems with arbitrarily many membranes and bounded energy; when bounding the number of membranes and leaving free the quantity of energy associated with each rule we have only generated all matrix languages. Several research topics are also pointed out.     

Sufficient conditions on uniform approximation of multivariatefunctions by general Takagi-Sugeno fuzzy systems with linear ruleconsequent

We have constructively proved a general class of multi-input single-output Takagi-Sugeno (TS) fuzzy systems to be universal approximators. The systems use any types of continuous fuzzy sets, fuzzy logic AND, fuzzy rules with linear rule consequent and the generalized defuzzifier. We first prove that the TS fuzzy systems can uniformly approximate any multivariate polynomial arbitrarily well, and then prove they can also uniformly approximate any multivariate continuous function arbitrarily well. We have derived a formula for computing the minimal upper bounds on the number of fuzzy sets and fuzzy rules necessary to achieve the prespecified approximation accuracy for any given bivariate function. A numerical example is furnished. Our results provide a solid-theoretical basis for fuzzy system applications, particularly as fuzzy controllers and models     

P systems with minimal parallelism

A current research topic in membrane computing is to find more realistic P systems from a biological point of view, and one target in this respect is to relax the condition of using the rules in a maximally parallel way. We contribute in this paper to this issue by considering the minimal parallelism of using the rules: if at least a rule from a set of rules associated with a membrane or a region can be used, then at least one rule from that membrane or region must be used, without any other restriction (e.g., more rules can be used, but we do not care how many). Weak as it might look, this minimal parallelism still leads to universality. We first prove this for the case of symport/antiport rules. The result is obtained both for generating and accepting P systems, in the latter case also for systems working deterministically. Then, we consider P systems with active membranes, and again the usual results are obtained: universality and the possibility to solve NP-complete problems in polynomial time (by trading space for time).     

A note on Parikh maps,abstract languages,and decision problems

We consider formulas similar to Presburger formulas, but extended by allowing the predicate | (for divides), but not allowing universal quantification of the resulting expressions. The solution sets for such formulas are known to be not semilinear, in general. We show that some results concerning decidability questions for classes of languages with effectively constructible semilinear Parikh maps can be extended to languages whose effectively constructible Parikh maps are solutions to these new formulas, which we call “modular”. We suggest that modularity may offer a natural extension of semilinearity, in which many previously established results may remain valid.     

Minimization strategies for maximally parallel multiset rewriting systems

Maximally parallel multiset rewriting systems (MPMRS) give a convenient way to express relations between unstructured objects. The functioning of various computational devices may be expressed in terms of MPMRS (e.g., register machines and many variants of P systems). In particular, this means that MPMRS are Turing universal; however, a direct translation leads to quite a large number of rules. Like for other classes of computationally complete devices, there is a challenge to find a universal system having the smallest number of rules. In this article we present different rule minimization strategies for MPMRS based on encodings and structural transformations. We apply these strategies to the translation of a small universal register machine (Korec (1996) [9]) and we show that there exists a universal MPMRS with 23 rules. Since MPMRS are identical to a restricted variant of P systems with antiport rules, the results we obtained improve previously known results on the number of rules for those systems.     

General SISO Takagi-Sugeno fuzzy systems with linear ruleconsequent are universal approximators

Takagi-Sugeno (TS) fuzzy systems have been employed as fuzzy controllers and fuzzy models in successfully solving difficult control and modeling problems in practice. Virtually all the TS fuzzy systems use linear rule consequent. At present, there exist no results (qualitative or quantitative) to answer the fundamentally important question that is especially critical to TS fuzzy systems as fuzzy controllers and models, “Are TS fuzzy systems with linear rule consequent universal approximators?” If the answer is yes, then how can they be constructed to achieve prespecified approximation accuracy and what are the sufficient renditions on systems configuration? In this paper, we provide answers to these questions for a general class of single-input single-output (SISO) fuzzy systems that use any type of continuous input fuzzy sets, TS fuzzy rules with linear consequent and a generalized defuzzifier containing the widely used centroid defuzzifier as a special case. We first constructively prove that this general class of SISO TS fuzzy systems can uniformly approximate any polynomial arbitrarily well and then prove, by utilizing the Weierstrass approximation theorem, that the general TS fuzzy systems can uniformly approximate any continuous function with arbitrarily high precision. Furthermore, we have derived a formula as part of sufficient conditions for the fuzzy approximation that can compute the minimal upper bound on the number of input fuzzy sets and rules needed for any given continuous function and prespecified approximation error bound, An illustrative numerical example is provided     

Membrane Systems with Marked Membranes

Membrane computing is a biologically inspired computational paradigm. Motivated by brane calculi we investigate membrane systems which differ from conventional membrane systems by the following features: (1) biomolecules (proteins) can move through the regions of the systems, and can attach onto (and de-attach from) membranes, and (2) membranes can evolve depending on the attached molecules. The evolution of membranes is performed by using rules that are motivated by the operation of pinocytosis (the pino rule) and the operation of cellular dripping (the drip rule) that take place in living cells. We show that such membrane systems are computationally universal. We also show that if only the second feature is used then one can generate at least the family of Parikh images of the languages generated by programmed grammars without appearance checking (which contains non-semilinear sets of vectors). If, moreover, the use of pino/drip rules is non-cooperative (i.e., not dependent on the proteins attached to membranes), then one generates a family of sets of vectors that is strictly included in the family of semilinear sets of vectors. We also consider a number of decision problems concerning reachability of configurations and boundness.     

Abstract geometrical computation 4: Small Turing universal signal machines

This paper provides several very small signal machines able to perform any computation—in the classical understanding—generated from Turing machines, cellular automata and cyclic tag systems. A halting universal signal machine with 13 meta-signals and 21 collision rules is presented (resp. 15 and 24 for a robust version). If infinitely many signals are allowed to be present in the initial configuration, five meta-signals and seven collision rules are enough to achieve non-halting weak universality (resp. six and nine for a robust version).     

Spiking neural P systems with extended rules: universality and languages

We consider spiking neural P systems with rules allowed to introduce zero, one, or more spikes at the same time. The motivation comes both from constructing small universal systems and from generating strings; previous results from these areas are briefly recalled. Then, the computing power of the obtained systems is investigated, when considering them as number generating and as language generating devices. In the first case, a simpler proof of universality is obtained, while in the latter case we find characterizations of finite and recursively enumerable languages (without using any squeezing mechanism, as it was necessary in the case of standard rules). The relationships with regular languages are also investigated.     

Decision problems concerning thinness and slenderness of formal languages

A language L is called thin if for almost all n there is at most one word of length n in L. A language L is called slender if there is a positive integer k such that for any n there are at most k words of length n in L. The notions of Parikh thin and Parikh slender languages are defined similarly by counting the words with the same Parikh vectors instead of the words of the same length. In this paper we discuss decision problems concerning these four properties. It is shown that all four properties are decidable for bounded semilinear languages but undecidable for DT0L languages. As a consequence all these problems are decidable for context-free languages. Received 9 June 1997 / 3 December 1997     

Commutative grammars

Commutative grammars are a formalism for generating bags, equivalent to vector addition systems and Petri nets. Known results are recalled and new one are presented on reachability and boundedness. In particular some subclasses of commutative grammars are introduced which admit a positive answer to these problems, and generate semilinear languages. Finally the equivalence, via Parikh mapping, of commutative and matrix grammars is proven.     

Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems

We give “syntactic’’ characterizations of context-sensitive languages (CSLs) in terms of some restricted models of symport/antiport P systems. These are the first such characterizations of CSLs in terms of P systems. In particular, we show the following for any language L over a binary alphabet:

(1)

Let m   be any integer ≥1$\ge 1$. Then L is a CSL if and only if it can be accepted by a restricted symport/antiport P system with m membranes and multiple number of symbols (objects). Moreover, holding the number of membranes at m, there is an infinite hierarchy in computational power (within the class of binary CSLs) with respect to the number of symbols.     

Unexpected universality results for three classes of P systems with symport/antiport

Symport and antiport are biological ways of transporting molecules through membranesin ``collaborating' pairs; in the case of symport the two molecules pass in the same direction, in the case of antiport the two molecules pass in opposite directions. Here we first survey the results about the computing power of membrane systems (P systems) using only symport/antiport rules (hence these systems compute by communication only), then we consider a recently introduced, way of defining the result of a computation in a membrane system: looking for the trace of certain objects in their movement through membranes. Rather unexpected, in this way we get characterizations of recursively enumerable languages by means of membrane systems with symport/antiport which work with multisets of objects (note the qualitative difference between the data structure used by computations – multisets: no ordering– and the data structure of the output – strings: linear ordering). A similar remark holds true for the case of analysing P systems, which work in an automata-like manner: the sequence of certain distinguished objects taken from the environment during acomputation is the string recognized by the computation. We also survey universality results from this area, with sketched proofs. Some open problems are also formulated. This revised version was published online in June 2006 with corrections to the Cover Date.     

Engineering model transformations with transML

Model transformation is one of the pillars of model-driven engineering (MDE). The increasing complexity of systems and modelling languages has dramatically raised the complexity and size of model transformations as well. Even though many transformation languages and tools have been proposed in the last few years, most of them are directed to the implementation phase of transformation development. In this way, even though transformations should be built using sound engineering principles—just like any other kind of software—there is currently a lack of cohesive support for the other phases of the transformation development, like requirements, analysis, design and testing. In this paper, we propose a unified family of languages to cover the life cycle of transformation development enabling the engineering of transformations. Moreover, following an MDE approach, we provide tools to partially automate the progressive refinement of models between the different phases and the generation of code for several transformation implementation languages.     

Necessary conditions on minimal system configuration for general MISO Mamdani fuzzy systems as universal approximators

Recent studies have shown that both Mamdani-type and Takagi-Sugeno-type fuzzy systems are universal approximators in that they can uniformly approximate continuous functions defined on compact domains with arbitrarily high approximation accuracy. In this paper, we investigate necessary conditions for general multiple-input single-output (MISO) Mamdani fuzzy systems as universal approximators with as minimal system configuration as possible. The general MISO fuzzy systems employ almost arbitrary continuous input fuzzy sets, arbitrary singleton output fuzzy sets, arbitrary fuzzy rules, product fuzzy logic AND, and the generalized defuzzifier containing the popular centroid defuzzifier as a special case. Our necessary conditions are developed under the practically sensible assumption that only a finite set of extrema of the multivariate continuous function to be approximated is available. We have first revealed a decomposition property of the general fuzzy systems: A r-input fuzzy system can always be decomposed to the sum of r simpler fuzzy systems where the first system has only one input variable, the second one two input variables, and the last one r input variables. Utilizing this property, we have derived some necessary conditions for the fuzzy systems to be universal approximators with minimal system configuration. The conditions expose the strength as well as limitation of the fuzzy approximation: (1) only a small number of fuzzy rules may be needed to uniformly approximate multivariate continuous functions that have a complicated formulation but a relatively small number of extrema; and (2) the number of fuzzy rules must be large in order to approximate highly oscillatory continuous functions. A numerical example is given to demonstrate our new results.     

Networks of evolutionary processors: computationally complete normal forms

Networks of evolutionary processors (NEPs, for short) form a bio-inspired language generating computational model that was shown to be equivalent to the model of phrase-structure grammars. In this paper, we analyse different restricted variants of NEPs that preserve the computational power of the general model. We prove that any recursively enumerable language can be generated by a NEP where the derivation rules can be applied at arbitrarily chosen positions, the control of the communication is done by finite automata with at most three states, and either the rule sets are singletons or the underlying graph is a complete graph. If one uses networks with arbitrary underlying graphs and allows the additional application of insertions and deletions only to the right-most or the to left-most position of the derived words for some nodes, then we only need automata with only one state to control the communication in the network. Clearly, this result is optimal; moreover, finite automata with two states are necessary and sufficient in order to generate all the recursively enumerable languages when the derivation rules can be applied only at arbitrarily chosen positions.     

DNA Computing Based on Splicing: The Existence of Universal Computers

We prove that splicing systems with finite components and certain controls on their work are computationally complete (they can simulate any Turing Machine); moreover, there are universal splicing systems (systems with all components fixed which can simulate any given splicing system, when an encoding of the particular system is added—as a program—to the universal system). Splicing systems are based on the splicing operation which is a model for DNA recombination. Informally, a prefix of a word is catenated to a suffix of another word, thus yielding a (possibly) new word. Cutting occurs at specific sites which correspond to specific sequences in DNA strands as they can be recognized by restriction enzymes. When no additional control is assumed, splicing systems with finitely many starting words (axioms) and finitely many splicing rules are known to characterize only regular languages (those recognized by finite automata ). However, when a splicing rule is allowed to be used (1)\hskip .5em only in the presence of certain symbols (``catalyst') or (2)\hskip .5em only in the absence of certain symbols (``inhibitors'), then we can characterize the recursively enumerable languages (recognized by Turing Machines ); the same result is obtained when counting the number of copies of (some of) the words used. From the proofs, we also infer the existence of universal (hence programmable) splicing systems. Received August 1997, and in final form March 1998.     

Toward a knowledge-to-text controlled natural language of isiZulu

The language isiZulu belongs to the Nguni group of languages, which also include isiXhosa, isiNdebele and siSwati. Of the four Nguni languages, isiZulu is the most dominant language in South Africa, which is spoken by 22.7 % of the country’s 51.8 million population. However, isiZulu (and even more so the other Nguni languages) still remains an under-resourced language for software applications. In this article we focus on controlled natural languages for structured knowledge-to-text viewed from a potential utility for verbalising business rules and OWL ontologies. IsiZulu grammar—and by extension, all Bantu languages—shows that a template-based approach is infeasible. This is due to, mainly, the noun class system, the agglutination and verb conjugation with concords for each noun class. We present verbalisation patterns for existential and universal quantification, taxonomic subsumption, axioms with simple properties, and basic cases of negation. Based on the preliminary user assessment of the patterns, selected ones are refined into algorithms for verbalisation to generate correct isiZulu sentences, which have been evaluated.     

Computationally universal P systems without priorities: two catalysts are sufficient

The original model of P systems with symbol objects introduced by Păun was shown to be computationally universal, provided that catalysts and priorities of rules are used. By reduction via register machines Sosík and Freund proved that the priorities may be omitted from the model without loss of computational power. Freund, Oswald, and Sosík considered several variants of P systems with catalysts (but without priorities) and investigated the number of catalysts needed for these specific variants to be computationally universal. It was shown that for the classic model of P systems with the minimal number of two membranes the number of catalysts can be reduced from six to five; using the idea of final states the number of catalysts could even be reduced to four. In this paper we are able to reduce the number of catalysts again: two catalysts are already sufficient. For extended P systems we even need only one membrane and two catalysts. For the (purely) catalytic systems considered by Ibarra only three catalysts are already enough.