IJFCS hosts in October 2008 a special issue on Language Theory in Biocomputing (edited by Michael Domaratzki and Kai Salomaa). I have submitted a paper for this issue, it was accepted, and now it was published. Here it is a brief description:
On the Descriptional Complexity of Accepting Networks of Evolutionary Processors With Filtered Connections, written together with Cezara Dragoi.
Abstract: In this paper we consider, from the descriptional complexity point of view, a model of computation introduced in [Accepting Networks of Evolutionary Processors With Filtered Connections", C. Dragoi, F. Manea V. Mitrana, Journal of Universal Computer Science, vol. 13, no. 11, pg. 1598 -- 1614, Springer], namely accepting network of evolutionary processors with filtered connections (ANEPFC). First we show that for each morphism h, defined on V with values in 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.
On the Descriptional Complexity of Accepting Networks of Evolutionary Processors With Filtered Connections, written together with Cezara Dragoi.
Abstract: In this paper we consider, from the descriptional complexity point of view, a model of computation introduced in [Accepting Networks of Evolutionary Processors With Filtered Connections", C. Dragoi, F. Manea V. Mitrana, Journal of Universal Computer Science, vol. 13, no. 11, pg. 1598 -- 1614, Springer], namely accepting network of evolutionary processors with filtered connections (ANEPFC). First we show that for each morphism h, defined on V with values in 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.
