PART 1. Special Issue – Language Theory in BiocomputingNo Access

ON THE DESCRIPTIONAL COMPLEXITY OF ACCEPTING NETWORKS OF EVOLUTIONARY PROCESSORS WITH FILTERED CONNECTIONS

CEZARA DRĂGOI

LIAFA, Universite Paris Diderot - Paris 7, Paris, Case 7014, 75205 Cedex 13, France

Faculty of Mathematics and Computer Science, University of Bucharest, Bucharest, Str. Academiei 14, 010014, Romania

Search for more papers by this author

and

FLORIN MANEA

Faculty of Mathematics and Computer Science, University of Bucharest, Bucharest, Str. Academiei 14, 010014, Romania

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0129054108006170Cited by:5 (Source: Crossref)

Abstract

In this paper we consider, from the descriptional complexity point of view, a model of computation introduced in [1], namely accepting network of evolutionary processors with filtered connections (ANEPFCs). First we show that for each morphism h : V → W*, with V ∩ W = ∅, one can effectively construct an ANEPFC, of size 6 + |W|, which accepts every input word w and, at the end of the computation on this word, obtains h(w) in its output node. This result can be applied in constructing two different ANEPFCs, with 27 and, respectively, 26 processors, recognizing a given recursively enumerable language. The first architecture, based on the construction of a universal ANEPFC, has the property that only 7 of its 27 processors depend on the accepted language. On the other hand, all the 26 processors of the second architecture depend on the accepted language, but, differently from the first one, this network simulates efficiently (from both time and space perspectives) a nondeterministic Turing machine accepting the given language.

The authors acknowledge partial support from the Romanian Ministry of Education and Research (PN-II Program, Project GlobalComp - Models, semantics, logics and technologies for global computing).

Keywords:

References

C. Drăgoi, F. Manea and V. Mitrana, J. UCS 13(11), 1598 (2007). Google Scholar
L. Errico and C. Jesshope, Towards a new architecture for symbolic processing, Artificial Intelligence and Information-Control Systems of Robots 94 (World Scientific, Singapore, 1994) pp. 31–40. Google Scholar
S. Fahlman, G. Hinton and T. Seijnowski, Massively parallel architectures for AI: NETL, THISTLE and Boltzmann Machines, Proc. AAAI National Conf. on AI (William Kaufman, Los Altos, 1983) pp. 109–113. Google Scholar
J. Hartmanis, P. M. Lewis II and R. E. Stearns, Hierarchies of memory limited computations, Proc. 6th Annual IEEE Symp. on Switching Circuit Theory and Logical Design (1965) pp. 179–190. Google Scholar
J. Hartmanis and R. E. Stearns, Trans. Amer. Math. Soc. 117, 533 (1965), DOI: 10.2307/1994208. Google Scholar
W. Hillis , The Connection Machine ( MIT Press , Cambridge , 1985 ) . Google Scholar
F. Manea, C. Martin-Vide and V. Mitrana, Math. Struct. Comp. Sci. 17, 753 (2007), DOI: 10.1017/S0960129507006202. Crossref, Web of Science, Google Scholar
F. Manea, C. Martin-Vide and V. Mitrana, ENTCS 135, 95 (2005). Google Scholar
F. Manea and V. Mitrana, Inform. Process. Lett. 103, 112 (2007), DOI: 10.1016/j.ipl.2007.03.001. Crossref, Web of Science, Google Scholar
M. Margenstern, V. Mitrana and M. Perez-Jimenez, Accepting hybrid networks of evolutionary systems, DNA 10, LNCS 3384 (Springer-Verlag, Berlin, 2005) pp. 235–246. Google Scholar
C. Martín-Vide and V. Mitrana, Molecular Computational Models: Unconventional Approaches (Idea Group Publishing, Hershey, 2005) pp. 78–114. Crossref, Google Scholar
C. H. Papadimitriou , Computational Complexity ( Addison-Wesley , 1994 ) . Google Scholar
D. Sankoffet al., Proc. Natl. Acad. Sci. USA 89, 6575 (1992), DOI: 10.1073/pnas.89.14.6575. Crossref, Web of Science, Google Scholar