Wyniki wyszukiwania - BazTech

1

On State-Synchronized Automata Systems

Meduna A., Kučera J.

Schedae Informaticae

|

2015

|

Vol. 24

221--237

EN

In this paper, we introduce a new kind of automata systems, called state-synchronized automata systems of degree n. In general, they consists of n pushdown automata, referred to as their components. These systems can perform a computation step provided that the concatenation of the current states of all their components belongs to a prescribed control language. As its main result, the paper demonstrates that these systems characterize the family of recursively enumerable languages. In fact, this characterization is demostrated in both deterministic and nondeterministic versions of these systems. Restricting their components, these systems provides less computational power.

2

On Networks of Evolutionary Processors with Nodes of Two Types

Alhazov A., Martin-Vide C., Truthe B., Dassow J., Rogozhin Y.

Fundamenta Informaticae

|

2009

|

Vol. 91, nr 1

1-15

EN

We discuss the power of networks of evolutionary processors where only two types of nodes are allowed. We prove that (up to an intersection with a monoid) every recursively enumerable language can be generated by a network with one deletion and one insertion node. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficient. Networks with an arbitrary number of insertion and substitution nodes only generate context-sensitive languages, and (up to an intersection with a monoid) every context-sensitive language can be generated by a network with one substitution node and one insertion node. All results are optimal with respect to the number of nodes.

3

On Characterizing Recursively Enumerable Languages by Insertion Grammars

Mutyam M., Krithivasan K., Reddy A. S.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

317--324

EN

Insertion grammars have been introduced in [1] and their computational power has been studied in several places. In [7] it is proved that insertion grammars with weight at least 7 can characterize recursively enumerable languages (modulo a weak coding and an inverse morphism), and the question was formulated whether or not this result can be improved. In this paper, we come up with a positive answer to this question, by decreasing the weight of the insertion grammar used to 5. We also give a characterization of recursively enumerable languages in terms of right quotients of insertion languages.

4

Further Results on Contextual and Rewriting P Systems

Krishna S. N., Rama R., Ramesh H.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

241-253

EN

In this paper, we continue the study of contextual and rewriting P systems. In contextual P systems, we improve a universality result avoiding the extended feature and by using rules of small weight. In rewriting P systems, we have two (rather surprising) universality results, both of them using three membranes, for non-extended systems with replicated rewriting and with leftmost rewriting, respectively.

5

One-Turn Regulated Pushdown Automata and Their Reduction

Meduna A., Kolar D.

Fundamenta Informaticae

|

2002

|

Vol. 51, nr 4

399-405

EN

This paper discusses some simple and natural restrictions of regulated pushdown automata, whose moves are regulated by some control languages. Most importantly, it studies one-turn regulated pushdown automata and proves that they characterize the family of recursively enumerable languages. In fact, this characterization holds even for atomic one-turn regulated pushdown automata of a reduced size. This result is established in terms of acceptance by final state and empty pushdown, acceptance by final state, and acceptance by empty pushdown.

6

On the Power of P Systems with DNA-Worm-Objects

Maté J.L., Rodriguez-Patón A., Silva A.

Fundamenta Informaticae

|

2002

|

Vol. 49, nr 1-3

229-239

EN

We introduce a variant of P systems with string-objects - called worm-objects - inspired in the DNA computing area. These systems work with multisets of string-objects processed by splitting, mutation, replication and recombination. This model is simpler (we eliminate the replication operation) and more realistic (the recombination operation is changed by the simpler one of suffix-prefix or head-tail concatenation developed in the DNA computing framework) than the previous one. The result of a computation is the set of strings sent out of the system. We work with multisets of strings but we generate languages instead of sets of numbers. We prove that, without priority among rules or other control mechanisms, (1) these P systems with at most three membranes can generate all recursively enumerable languages, (2) with non-decreasing length mutation and splitting rules, three membranes are enough to generate the family of context-sensitive languages, and (3) with these restricted types of splitting and mutation rules, four membranes can generate the family of recursively enumerable languages.

7

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.

8

On synchronization in P systems

Paun G., Yu S

Fundamenta Informaticae

|

1999

|

Vol. 38, Nr 4

397-410

EN

The P systems were recently introduced as distributed parallel computing models of a biochemical type. Multisets of objects are placed in a hierarchical structure of membranes and they evolve according to given rules, which are applied in a synchronous manner: at each step, all objects which can evolve, from all membranes, must evolve. We consider here the case when this restriction is removed. As expected, unsynchronized systems (even using catalysts) are weaker than the synchronized ones, providing that no priority relation among rules is considered. The power of P systems is not diminished when a priority is used and, moreover, the catalysts can change their states, among two possible states for each catalyst.