Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2015

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: random context conditions

Sortuj według:

Ogranicz wyniki do:

On the Power of Accepting Networks of Evolutionary Processors with Special Topologies and Random Context Filters

Dassow J., Manea F., Truthe B.

Fundamenta Informaticae

2015

Vol. 136, nr 1/2

1--35

In this paper, we approach the problemof accepting all recursively enumerable languages by accepting networks of evolutionary processors (ANEPs, for short) with a fixed architecture. More precisely, we show that every recursively enumerable language can be accepted by an ANEP with an underlying graph in the form of a star with 13 nodes or by an ANEP with an underlying grid with 13 × 4 = 52 nodes as well as by ANEPs having underlying graphs in the form of a chain, a ring, or a wheel with 29 nodes each. In all these cases, the size and form as well as the general working strategy of the constructed networks do not depend on the accepted language; only the rewriting rules and the filters associated to each node of the networks depend on this language. Noteworthy is also the fact that the filtering process is implemented using random context conditions only. Our results answer problems which were left open in a paper published by J. Dassow and F. Manea at the conference on Descriptional Complexity of Formal Systems (DCFS) 2010 and improve a result published by B. Truthe at the conference on Non-Classical Models of Automata and Applications (NCMA) 2013.