It's been a while since the last post regarding my research work (also since my last post, generally speaking), thus here are a few words about the papers I co-authored lately.
Some Remarks on Superposition Based on Watson-Crick-like Complementarity, written together with Victor Mitrana and Jose Sempere. This paper was accepted at DLT 2009.
Abstract: In this note we solve a problem previously left open, namely we show that the iterated superposition of a regular language is regular. The proof of this result is based on two facts: (i) the iterated superposition of a language equals the restricted iterated superposition of the same language, (ii) the sequence of applying iteratively the restricted superposition can be precisely defined. We then define the restricted superposition distance between a word and a language and prove that this distance can be computed in time O(n^2 f(n)), where the language is accepted in time O(f(n)) on the unit cost RAM model. Finally, we briefly discuss the necessity of the n^2 factor for the classes of regular and context-free languages.
Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections, written together with Remco Loos and Victor Mitrana. The paper was accepted at DCFS 2009.
Abstract: In this paper, we present some results regarding the size complexity of Accepting Networks of Evolutionary Processors with Filtered Connections (ANEPFCs). We show that there are universal ANEPFCs of size 10, by devising a method for simulating 2-Tag Systems. This result significantly improves the known upper bound for the size of universal ANEPFCs which is 18. We also propose a new, computationally and descriptionally efficient simulation of nondeterministic Turing machines by ANEPFCs. More precisely, due to space limitations we informally describe how ANEPFCs with 16 nodes can simulate in O(f(n)) time any nondeterministic Turing machine of time complexity f(n). Thus the known upper bound for the number of nodes in a network simulating an arbitrary Turing machine is decreased from 26 to 16.
Filter Position in Networks of Evolutionary Processors Does Not Matter, written together with Paolo Bottoni, Anna Labella, Victor Mitrana and Jose Sempere. This paper was accepted at DNA 2009.
Abstract: In this paper we give a direct proof of the fact that the computational power of networks of evolutionary processors and that of networks of evolutionary processors with filtered connections is the same. It was previously shown that both are equivalent to Turing machines, but here we propose here a direct simulation of one device by the other.
Combinatorial Queries and Updates on Partial Words, written together with Adrian Diaconu and Catalin Tiseanu (two of my students). The paper was accepted at FCT 2009. I am particularly proud of this work, since it is the first time I co-author a paper with some of my students. Also, I am happy that it was accepted at a conference with a good tradition, such as FCT.
Abstract: In this paper we define four combinatorial queries on partial words, asking if a factor of a partial word is a k-repetition, k-free, overlap-free, and primitive, respectively. We show how a given partial word can be preprocessed efficiently in order to answer each of these queries in constant time. Also, we define an update operation for partial words: add a new symbol at the rightmost end of a given partial word; further, we show that the data structures obtained during the preprocessing mentioned above can be updated efficiently in order to still be able to answer all the combinatorial queries, for the updated word, in constant time.
Networks of Evolutionary Picture Processors with Filtered Connections, written together with Paolo Bottoni, Anna Labella, Victor Mitrana and Jose Sempere. This paper was accepted at UC 2009.
Abstract: In this paper we simplify the model of computation of evolutionary picture processors, by moving the filters from the nodes to the edges. Each edge is now viewed as a two-way channel such that input and output filters, respectively, of the two nodes connected by the edge coincide. Thus, the possibility of controlling the computation in such networks seems to be diminished. In spite of this observation all the results concerning the computational power of networks of evolutionary picture processors are extended over these simplified networks.
I will also attend four of these conferences: DLT 2009 in June, in Stuttgart, DCFS 2009 in July, in Magdeburg, FCT 2009 in September, in Wroclaw, and UC 2009 in September, in the Azores Islands.
Some Remarks on Superposition Based on Watson-Crick-like Complementarity, written together with Victor Mitrana and Jose Sempere. This paper was accepted at DLT 2009.
Abstract: In this note we solve a problem previously left open, namely we show that the iterated superposition of a regular language is regular. The proof of this result is based on two facts: (i) the iterated superposition of a language equals the restricted iterated superposition of the same language, (ii) the sequence of applying iteratively the restricted superposition can be precisely defined. We then define the restricted superposition distance between a word and a language and prove that this distance can be computed in time O(n^2 f(n)), where the language is accepted in time O(f(n)) on the unit cost RAM model. Finally, we briefly discuss the necessity of the n^2 factor for the classes of regular and context-free languages.
Small Universal Accepting Networks of Evolutionary Processors with Filtered Connections, written together with Remco Loos and Victor Mitrana. The paper was accepted at DCFS 2009.
Abstract: In this paper, we present some results regarding the size complexity of Accepting Networks of Evolutionary Processors with Filtered Connections (ANEPFCs). We show that there are universal ANEPFCs of size 10, by devising a method for simulating 2-Tag Systems. This result significantly improves the known upper bound for the size of universal ANEPFCs which is 18. We also propose a new, computationally and descriptionally efficient simulation of nondeterministic Turing machines by ANEPFCs. More precisely, due to space limitations we informally describe how ANEPFCs with 16 nodes can simulate in O(f(n)) time any nondeterministic Turing machine of time complexity f(n). Thus the known upper bound for the number of nodes in a network simulating an arbitrary Turing machine is decreased from 26 to 16.
Filter Position in Networks of Evolutionary Processors Does Not Matter, written together with Paolo Bottoni, Anna Labella, Victor Mitrana and Jose Sempere. This paper was accepted at DNA 2009.
Abstract: In this paper we give a direct proof of the fact that the computational power of networks of evolutionary processors and that of networks of evolutionary processors with filtered connections is the same. It was previously shown that both are equivalent to Turing machines, but here we propose here a direct simulation of one device by the other.
Combinatorial Queries and Updates on Partial Words, written together with Adrian Diaconu and Catalin Tiseanu (two of my students). The paper was accepted at FCT 2009. I am particularly proud of this work, since it is the first time I co-author a paper with some of my students. Also, I am happy that it was accepted at a conference with a good tradition, such as FCT.
Abstract: In this paper we define four combinatorial queries on partial words, asking if a factor of a partial word is a k-repetition, k-free, overlap-free, and primitive, respectively. We show how a given partial word can be preprocessed efficiently in order to answer each of these queries in constant time. Also, we define an update operation for partial words: add a new symbol at the rightmost end of a given partial word; further, we show that the data structures obtained during the preprocessing mentioned above can be updated efficiently in order to still be able to answer all the combinatorial queries, for the updated word, in constant time.
Networks of Evolutionary Picture Processors with Filtered Connections, written together with Paolo Bottoni, Anna Labella, Victor Mitrana and Jose Sempere. This paper was accepted at UC 2009.
Abstract: In this paper we simplify the model of computation of evolutionary picture processors, by moving the filters from the nodes to the edges. Each edge is now viewed as a two-way channel such that input and output filters, respectively, of the two nodes connected by the edge coincide. Thus, the possibility of controlling the computation in such networks seems to be diminished. In spite of this observation all the results concerning the computational power of networks of evolutionary picture processors are extended over these simplified networks.
I will also attend four of these conferences: DLT 2009 in June, in Stuttgart, DCFS 2009 in July, in Magdeburg, FCT 2009 in September, in Wroclaw, and UC 2009 in September, in the Azores Islands.
