Name
Abstract | ||
|---|---|---|
In this paper we show that some aspects of networks of evolutionary processors can be normalized or simplified without loosing generative power. More precisely, we show that one can use very small finite automata for the control of the communication. We first prove that the networks with evolutionary processors remain computationally complete if one restricts the control automata to have only one state, but underlying graphs of the networks have no fixed structure and the rules are applied in three different modes. Moreover, we show that networks where the rules are applied arbitrary, and all the automata for control have one state, cannot generate all recursively enumerable languages. Finally, we show that one can generate all recursively enumerable languages by complete networks, where the rules are applied arbitrary, but the automata for control have at most two states. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-21341-0_14 | UC |
Keywords | Field | DocType |
control automaton,recursively enumerable language,generative power,complete network,fixed structure,normal form,underlying graph,small finite automaton,different mode,evolutionary processor | Generative power,Discrete mathematics,Graph,Normalization (statistics),Formal language,Automaton,Recursively enumerable language,Theoretical computer science,Finite-state machine,Regular language,Mathematics | Conference |
Citations | PageRank | References |
3 | 0.42 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jürgen Dassow | 1 | 530 | 118.27 |
| Florin Manea | 2 | 372 | 58.12 |
| Bianca Truthe | 3 | 159 | 28.57 |