Wyniki wyszukiwania - BazTech

1

Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete

Křivka Zbyněk, Meduna Alexander

Fundamenta Informaticae

|

2021

|

Vol. 179, nr 4

361--384

EN

This paper investigates the reduction of scattered context grammars with respect to the number of non-context-free productions. It proves that every recursively enumerable language is generated by a scattered context grammar that has no more than one non-context-free production. An open problem is formulated.

2

Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars

Fernau Henning, Kuppusamy Lakshmanan, Oladele Rufus O., Raman Indhumathi

Fundamenta Informaticae

|

2021

|

Vol. 181, nr 2-3

189--211

EN

A simple semi-conditional (SSC) grammar is a form of regulated rewriting system where the derivations are controlled either by a permitting string alone or by a forbidden string alone and this condition is specified in the rule. The maximum length i (j, resp.) of the permitting (forbidden, resp.) strings serves as a measure of descriptional complexity known as the degree of such grammars. In addition to the degree, the numbers of nonterminals and of conditional rules are also counted into the descriptional complexity measures of these grammars. We improve on some previously obtained results on the computational completeness of SSC grammars by minimizing the number of nonterminals and / or the number of conditional rules for a given degree (i, j). More specifically we prove, using a refined analysis of a normal form for type-0 grammars due to Geffert, that every recursively enumerable language is generated by an SSC grammar of (i) degree (2, 1) with eight conditional rules and nine nonterminals, (ii) degree (3, 1) with seven conditional rules and seven nonterminals (iii) degree (4, 1) with six conditional rules and seven nonterminals and (iv) degree (4, 1) with eight conditional rules and six nonterminals.

3

Random Context and Semi-conditional Insertion-deletion Systems

Ivanov S., Verlan S.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

127--144

EN

In this article we introduce the operations of insertion and deletion working in random context and semi-conditional modes. We show that conditional application of insertion and deletion rules strictly increases the computational power. In the case of semi-conditional insertion-deletion systems, context-free insertion and deletion rules of one symbol are sufficient to achieve computational completeness. In the random context case, our results expose asymmetry between the computational power of insertion and deletion rules: semi-conditional systems of size (2, 0, 0; 1, 1, 0) (with context-free two-symbol insertion rules, and one-symbol deletion rules with one-symbol left context) are computationally complete, while systems of size (1, 1, 0; 2, 0, 0) (and, more generally, of size (1, 1, 0; p, 1, 1)) are not.

4

Partial Halting and Minimal Parallelism Based on Arbitrary Rule Partitions

Alhazov A., Oswald M., Freund R., Verlan S.

Fundamenta Informaticae

|

2009

|

Vol. 91, nr 1

17-34

EN

We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if not for all membranes a rule is applicable anymore at the same time, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for several variants of P systems using membrane rules with permitting contexts and working in different transition modes, especially for minimal parallelism. Both partial halting and minimal parallelism are based on an arbitrary set of subsets from the set of rules assigned to the membranes.

5

(Tissue) P Systems with Unit Rules and Energy Assigned to Membranes

Alhazov A., Freund R., Leporati A., Oswald M., Zandron C.

Fundamenta Informaticae

|

2006

|

Vol. 74, nr 4

391-408

EN

We introduce a new variant of membrane systems where the rules are directly assigned to membranes and, moreover, every membrane carries an energy value that can be changed during a computation by objects passing through the membrane. The result of a successful computation is considered to be the distribution of energy values carried by the membranes. We show that for systems working in the sequential mode with a kind of priority relation on the rules we already obtain universal computational power. When omitting the priority relation, we obtain a characterization of the family of Parikh sets of languages generated by context-free matrix grammars. On the other hand, when using the maximally parallel mode, we do not need a priority relation to obtain computational completeness. Finally, we introduce the corresponding model of tissue P systems with energy assigned to the membrane of each cell and objects moving from one cell to another one in the environment as well as being able to change the energy of a cell when entering or leaving the cell. In each derivation step, only one object may pass through the membrane of each cell. When using priorities on the rules in the sequential mode (where in each derivation step only one cell is affected) as well as without priorities in the maximally parallel mode (where in each derivation step all cells possible are affected) we again obtain computational completeness, whereas without priorities on the rules in the sequential mode we only get a characterization of the family of Parikh sets of languages generated by context-free matrix grammars.

6

Contextual P Systems

Krithivasan K., Madhu M.

Fundamenta Informaticae

|

2002

|

Vol. 49, nr 1-3

179-189

EN

Generally, in P systems with string-objects one uses the Chomsky way of rewriting for processing the objects. In this paper we consider the contextual way of handling string-objects in P systems. We introduce some variants of contextual grammars and prove that contextual P systems with rules corresponding to these variants are more powerful than ordinary contextual grammars and their variants. We also show that one-sided contextual P systems with right-sided erased contexts and insertion contextual P systems with right-sided erased contexts are computationally complete.