VASZIL , György

We present a characterization of context-free languages in terms of a restricted class of P automata (P systems accepting strings of symbols using symport/antiport communication rules). The characterization is based on the form of the rules used by the system.

We show how P automata having a finite description and working with a finite object-alphabet can be used to describe languages over countably infinite alphabets. We propose to relate the language classes characterized by different types of P automata to some of the existing characterizations of language classes over infinite alphabets, and give...

We study the computational power of generalized P colony automata and show how it is in uenced by the capacity of the system (the number of objects inside the cells of the colony) and the types of programs which are allowed to be used (restricted and unrestricted com-tape and all-tape programs, or programs allowing any kinds of rules).

Membrane systems are nature motivated computational models inspired by certain basic features of biological cells and their membranes. They are examples of the chemical computational paradigm which describes computation in terms of chemical solutions where molecules interact according to rules de ning their reaction capabilities. Chemical...

We introduce a new acceptance mode for APCol systems (Automaton-like P colonies), variants of P colonies where the environment of the agents is given by a string and during functioning the agents change their own states and process the string similarly to automata. In case of the standard variant, the string is accepted if it can be reduced to...

We investigate the possibility of the deterministic parsing (that is, parsing without backtracking) of languages characterized by (generalized) P colony automata. We de ne a class of P colony automata satisfying a property which resembles the LL(k) property of context-free grammars, and study the possibility of parsing the...

Deterministic one-way Turing machines with sublinear space bounds are systematically studied. We distinguish among the notions of strong, weak, and restricted space bounds. The latter is motivated by the study of P automata. The space available on the work tape depends on the number of input symbols read so far, instead of the entire input. The...

Deterministic one-way Turing machines with sublinear space bounds are systematically studied. We distinguish among the notions of strong, weak, and restricted space bounds. The latter is motivated by the study of P automata. The space available on the work tape depends on the number of input symbols read so far, instead of the entire input. The...

We show how to implement the DBSCAN clustering algorithm (Density Based Spatial Clustering of Applications with Noise) on membrane systems using evolution rules with promoters and priorities.

We investigate the relationship of time Petri nets and di erent variants of membrane systems. First we show that the added feature of \time" in time Petri nets makes it possible to simulate the maximal parallel rule application of membrane systems without introducing maximal parallelism to the Petri net semantics, then we de ne local time P...

We present a transformation of membrane systems, possibly with pro- moter/inhibitor rules, priority relations, and membrane dissolution, into formulas of the chemical calculus such that terminating computations of membranes correspond to terminating reduction sequences of formulas and vice versa. In the end, the same result can be extracted...

We introduce some variants of P systems that mimic the behaviour of social networks and illustrate some of the characteristics of them. Other concepts related to social networks are discussed and suitable classes of P systems are suggested. A simple example shows the capabilities of such a P system where the intensity of the communication is...

It is known that P systems with symport/antiport rules simulate the register machines, i.e., they are computationally complete. Hence, due to the existence of universal register machines, there exist computationally complete subclasses of symport/antiport P systems with a number of rules limited by a constant. However, there was no...

We study two very simple variants of P colonies: systems with only one object inside the cells, and systems with insertion-deletion programs, so called P colonies with senders and consumers. We show that both of these extremely simple types of systems are able to compute any recursively enumerable set of vectors of non-negative integers.

We introduce the concept of a P colony automaton, an automata-like con- struct combining properties of finite automata and P colonies. We present some preliminary results on the accepting power of several variants of these extremely simple language recognizing devices, and propose problems for future research.

We continue the investigations on exploring the connection between membrane systems and time Petri nets already commenced in [4] by extending membrane systems with promoters/inhibitors, membrane dissolution and priority for rules compared to the simple symbol-object membrane system. By constructing the simulating Petri net, we retain one of the...

This paper proposes and preliminarily investigates the possibility of transforming a configuration (membrane structure and multisets of symbol-objects present in the compartments of this membrane structure) of a P system into another configuration, by means of a given set of rules acting both on the membranes and on the multisets of objects....