Final Update: The workshop took place on September 15 and 16, and according to the feedback we received from the participants it was successful. Thanks to all who contributed to the success of DACS 2014, and I am looking forward to the next edition.
Update 2: The list of accepted papers is online.
Update 1: The submission deadline for the workshop was extended to July 14, 2014, 23:59 EET.
Theory Day in Computer Science 2014 (DACS-2014) is the first in a series of workshops that (hopefully) will take place yearly in Romania, focused on presenting to a mostly-Romanian audience new results on various topics related to Theoretical Computer Science. This year’s workshop takes place on the 16th of September at the Faculty of Mathematics and Computer Science, University of Bucharest, and it is affiliated to the 11th International Colloquium on Theoretical Aspects of Computing - ICTAC 2014.
The main goal of the workshop series is to build a solid and modern TCS community in Romania, closely connected to the current global research-trends. Ideally, our workshop will also attract, either as invited speakers or authors of contributed papers, participants from other European countries, helping to establish international collaborations on common topics. So far, this only reflects in the composition of the Program Committee, but the submission deadline for contributed papers is still one month away: 1st of July 2014.
This year we have two well-recognised Romanian researchers as invited speakers: Ion Petre - Åbo Akademi University, Turku, Finland, and Robert Mercas - Kiel University, Germany. Also, Gabriel Istrate from the West University of Timisoara has a tutorial in the first day of the workshop.
Coming back to contributed papers, we look for three types of submissions: original papers, surveys, and informal presentations. While the first two types are self-explanatory, informal presentations should address work-in-progress, review some recent results, as well as present open problems.
Last, but not least, we will try to keep the registration fee at a very low level, so that every interested person can come.
Please visit the webpage of our workshop for more details on when, where and how to submit and participate!
Showing posts with label Research: Various Comments. Show all posts
Showing posts with label Research: Various Comments. Show all posts
NCMA 2014
The deadline for this year's NCMA is just days away: May 4, 2014. Update: the deadline was extended to May 13, 2014.
NCMA is the acronym of the Workshop on Non-Classical Models of Automata and Applications, which reaches this year its sixth edition. The workshop will take place in Kassel, in the centre of Germany, at the end of July (28,29 July 2014).
As usual, we are mainly looking for works on different aspects of non-classical models of automata and grammars. Submissions on the following topics (but not limited to them) are welcome:
-- formal models inspired by Linguistics, Bio-Computing, Text Processing, Document Engineering, Self-Assembly, etc.,
-- bio-inspired models of automata and generative devices,
-- cellular automata,
-- forgetting automata and restarting automata,
-- automata with additional resources,
-- regulated rewriting/automata,
-- networks of automata or generative devices,
-- models of cooperation and communication,
-- quantum automata.
Note that this year the workshop also looks for short papers, on work in progress. The deadline for these papers is 8 june 2014.
So, please submit your latest paper on the above topics to NCMA 2014!
NCMA is the acronym of the Workshop on Non-Classical Models of Automata and Applications, which reaches this year its sixth edition. The workshop will take place in Kassel, in the centre of Germany, at the end of July (28,29 July 2014).
As usual, we are mainly looking for works on different aspects of non-classical models of automata and grammars. Submissions on the following topics (but not limited to them) are welcome:
-- formal models inspired by Linguistics, Bio-Computing, Text Processing, Document Engineering, Self-Assembly, etc.,
-- bio-inspired models of automata and generative devices,
-- cellular automata,
-- forgetting automata and restarting automata,
-- automata with additional resources,
-- regulated rewriting/automata,
-- networks of automata or generative devices,
-- models of cooperation and communication,
-- quantum automata.
Note that this year the workshop also looks for short papers, on work in progress. The deadline for these papers is 8 june 2014.
So, please submit your latest paper on the above topics to NCMA 2014!
Computability in Europe - Steering Committee
Computability in Europe is one of my favourite conferences: I attended the conference six times, each time having an accepted paper, and I enjoyed each of these participations a lot. Among the things I like, the mixture between theoretical computer science and mathematics comes first, but I also appreciated the very good selection of invited speakers, the special sessions, as well as the satellite workshops.
That's why I was very happy and honoured when, this summer, I was invited to be part of the Steering Committee of the Computability in Europe Conference Series. Of course, I accepted this invitation. I can only hope that, in this new position, I will be able to contribute to the development of this (still young) conference into a major theory conference.
That's why I was very happy and honoured when, this summer, I was invited to be part of the Steering Committee of the Computability in Europe Conference Series. Of course, I accepted this invitation. I can only hope that, in this new position, I will be able to contribute to the development of this (still young) conference into a major theory conference.
Faculty of Science @ Unibuc - 150 years
The year 2013 marks the celebration of the 150th anniversary of the birth of the Faculty of Sciences, one of the initial three faculties of the University of Bucharest. The faculty was founded in 1863, joined the University of Bucharest in 1864 (when the University was founded), and in 1866 it was split into the Department of Physical and Mathematical Sciences and the Department of Physical and Natural Sciences. To cut the history short, the faculty went through many further splits and changes, until it became in 2001 the Faculty of Mathematics and Computer Science (FMI).
With this occasion, my colleagues from FMI are organising, from August 29 to September 1, an anniversary conference, taking place between. The programme of the conference consists in talks given by researchers from all over the world, some of them with remarkable careers, that graduated from FMI (or its ancestor-faculties). I strongly recommend any of the readers of this post (that are in Bucharest in that period) to attend the conference.
I was much honoured to be also invited to give a talk at this conference, in the computer science track. In my talk, entitled Hidden structures in words, I will present parts of my current work on combinatorics and algorithmics on words, including the results of my recent papers from STACS 2013 and CiE 2013.
I am ending this post looking forward for the talks given by the others invited speakers, as well as hoping to meet some of the Romanian readers of this post at the conference.
Update: The official programme of the (entire) conference can be found at this link. The programme of the computer science track of the conference can be seen here. There is also a document containing all the abstracts of the talks.
With this occasion, my colleagues from FMI are organising, from August 29 to September 1, an anniversary conference, taking place between. The programme of the conference consists in talks given by researchers from all over the world, some of them with remarkable careers, that graduated from FMI (or its ancestor-faculties). I strongly recommend any of the readers of this post (that are in Bucharest in that period) to attend the conference.
I was much honoured to be also invited to give a talk at this conference, in the computer science track. In my talk, entitled Hidden structures in words, I will present parts of my current work on combinatorics and algorithmics on words, including the results of my recent papers from STACS 2013 and CiE 2013.
I am ending this post looking forward for the talks given by the others invited speakers, as well as hoping to meet some of the Romanian readers of this post at the conference.
Update: The official programme of the (entire) conference can be found at this link. The programme of the computer science track of the conference can be seen here. There is also a document containing all the abstracts of the talks.
NCMA 2013: Deadline Approaching
The submission deadline for NCMA 2013 is next week: 26 May 2013.
We are looking for papers on (but not limited to) the topics:
-- formal models inspired by Linguistics, Bio-Computing, Text Processing, Document Engineering, Self-Assembly, etc.,
-- bio-inspired models of automata and generative devices,
-- cellular automata,
-- forgetting automata and restarting automata,
-- automata with additional resources,
-- regulated rewriting/automata,
-- networks of automata or generative devices,
-- models of cooperation and communication,
-- quantum automata.
So, if you just finished writing a nice paper related to one of these topics, please submit it to NCMA 2013!
We are looking for papers on (but not limited to) the topics:
-- formal models inspired by Linguistics, Bio-Computing, Text Processing, Document Engineering, Self-Assembly, etc.,
-- bio-inspired models of automata and generative devices,
-- cellular automata,
-- forgetting automata and restarting automata,
-- automata with additional resources,
-- regulated rewriting/automata,
-- networks of automata or generative devices,
-- models of cooperation and communication,
-- quantum automata.
So, if you just finished writing a nice paper related to one of these topics, please submit it to NCMA 2013!
Plagiat in Romania
Dupa faimosul Danut Marcu, un nou scandal de plagiat are loc in Romania. Am scris ceva despre asta pe blogul infoarena.
NCMA 2012: Deadline
Just a quick reminder, for those interested. The submission deadline for NCMA 2012 is getting closer: 13 May 2012.
Update: The submission deadline was moved to 29 May 2012.
Update: The submission deadline was moved to 29 May 2012.
DCM: Deadline
Those of you interested in submitting papers to DCM 2012 should note that the submissions deadline is one week away: 15 April 2012.
NCMA 2012: Call for Papers
The second workshop announced in a previous post, namely the 4th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2012), has issued its Call for Papers; the topics of interest are available on the workshop's web-page. Here is a short preview:
Researchers are invited to submit papers concerning original contributions on non-classical models of automata and applications and related subjects for NCMA 2012. The aim of this workshop is to bring together researchers working on different aspects of different variants of non-classical automata models.Please feel encouraged to submit your paper to NCMA 2012! Note that the submissions deadline is 13 May 2012.
Topics of NCMA 2012 include, but are not limited to:
Bio-inspired Automata;
Cellular Automata;
Restart- ing/Forgetting Automata;
Automata with Additional Resources;
Automata Networks, Cooperation, and Communication;
Quantum Automata;
Other Formal Models (Inspired by: Linguistics; Bio-Computing; Text Processing; Document Engineering; Self-Assembling).
NCMA 2012 will take place after DLT 2012 and before MFCS 2012. It is held in Fribourg, Switzerland.
DCM 2012: Call for Papers
Following the announcements in the previous post, please note that the Call for Papers for the 8th International Workshop on Developments in Computational Models was published on the workshop's site. Here is a short preview:
Topics of interest include all abstract models of computation and their properties, and their applications to the development of programming languages and systems:Once more, I encourage any of you working on some of the topics in this call for papers to submit papers to DCM 2012.
- quantum computation, including implementations and formal methods in quantum protocols;
- probabilistic computation and verification in modeling situations;
- chemical, biological and bio-inspired computation, including spatial models, self-assembly, growth models;
- general concurrent models including the treatment of mobility, trust, and security;
- information-theoretic ideas in computing;
- infinitary models of computation;
- comparisons of different models of computations.
The proceedings will be published electronically in the series "Electronic Proceedings in Theoretical Computer Science" (EPTCS) as post-proceedings after the workshop.
All papers have to be prepared using the EPTCS macro package which can be downloaded here. Papers can have up to 12 pages in EPTCS style.
Papers have to be submitted via our easychair site in PDF format before the deadline of 15 April 2012.
DCM and NCMA
This year I was invited to be part of the Program Committee of two workshops. So, I think it is a good idea to advertise them here...
The first one is the 8th International Workshop on Developments in Computational Models, and will take place in June, in Cambridgde, as a satellite event of the Turing Centenary Conference CiE 2012. The call for papers is yet to be posted, and the important dates were not yet announced. However, a great list of invited keynote speakers was already posted. The aim of the workshop (that was six time a satellite event of ICALP, and in 2010 a satellite event of FLoC) remains, as stated on the DCM workshop series site:
... to bring together researchers who are currently developing new computational models or new features for traditional computational models, in order to foster their interaction, to provide a forum for presenting new ideas and work in progress, and to enable newcomers to learn about current activities in this area.I strongly encourage everybody working in the area of computability (either conventional or unconventional) to submit papers to DCM 2012, and everybody else to consider spending a day in Cambridge listening to the talks of this workshop. I also strongly encourage you all to consider participating at the host conference, CiE 2012, which promises to be a great event! The second one is the 4th International Workshop Non-Classical Models of Automata and Applications, and will take place in August, in Fribourg, Switzerland. As in the former case, the details were not yet posted. However, the idea behind the workshop is to atract...
... researchers working on different aspects of different variants of non-classical automata models in order to exchange and develop novel ideas. A deeper and interdisciplinary coverage of this particular area may gain new insights and substantial progress.Thus, if you are interested in new developments in the area of non-classical-automata theory please consider submitting a paper or only participating at NCMA 2012. Compared to the DCM workshop, it seems to me that this one is addressed more to researchers working closer to language-theory. The topics of the conference will surely include bio-inspired, cellular, or quantum automata, restarting automata, networks and cooperating automata, but also other any other relevant work on emerging language-theoretic models. I will conclude this post by telling you my personal experience with these two workshops, hoping that it will convince some of you to attend them. I had a paper at DCM 2005, but, unfortunately, I was not able to participate at the event; one of my co-authors gave the talk, and told the rest of us that he had a great experience. However, I have some nice scientific memories related to this workshop, as the results presented there and those contained in the follow-up paper, which was invited to a special issue of the Mathematical Structures in Computer Science, are among my favourites (although, they were greatly improved ever since). On the other hand, I participated myself at NCMA 2011, in Milano, a satellite event of DLT 2011. Taking place for two days, in a wonderful location, the workshop had some nice talks that gave birth to interesting discussions. The social event was also very pleasant. After the workshop, some authors (including my co-authors and me) were invited to submit follow-up papers to a special issue of the RAIRO journal. To conclude, I was happy that I participated at the workshop, both from the scientific and the personal points of view.
Kiel
After finishing my Humboldt Research Fellowship in Magdeburg, I have decided to continue my stay in Germany. Luckily, I was offered and I accepted a temporary position (starting 1st of November) in the Computer Science Department at the Christian-Albrechts-University in Kiel, in the group of Dirk Nowotka. The main focus of my research will be in the area of algorithmic combinatorics on words, which coincides with my latest research interests. News on what exactly I do will come as soon as I obtain some results!
Fun Stuff
I think that all of us heard about the dangers of plagiarism in the scientific world, but, on the other hand, none of us really met such a case. I came across a plagiarism discussion only once (paper 17 from this list), but I didn't really follow all the details.
However, I recently found out (credits: Dominik Freydenberger) about a famous case of plagiarism: Danut Marcu. This guy, who has a PhD from my Alma Mater, plagiarized hundreds of papers, becoming one of the most prolific authors in Graph Theory. Finally, he was caught and banned by many journals, but it is really funny to see how he tricked so many reviewers.
On a serious note, I would be curious to find out if his PhD supervisor knows about it. I am pretty sure that this way of publishing started during his doctorate years, and maybe his thesis is based on some stolen results. I would be also curios to hear the reaction of my faculty/ university about this guy (maybe cancel his PhD title?).
Later Edit: It seems that this is an old page of Danut Marcu. He states that
However, I recently found out (credits: Dominik Freydenberger) about a famous case of plagiarism: Danut Marcu. This guy, who has a PhD from my Alma Mater, plagiarized hundreds of papers, becoming one of the most prolific authors in Graph Theory. Finally, he was caught and banned by many journals, but it is really funny to see how he tricked so many reviewers.
On a serious note, I would be curious to find out if his PhD supervisor knows about it. I am pretty sure that this way of publishing started during his doctorate years, and maybe his thesis is based on some stolen results. I would be also curios to hear the reaction of my faculty/ university about this guy (maybe cancel his PhD title?).
Later Edit: It seems that this is an old page of Danut Marcu. He states that
Each mathematician, from every part of the world, any time, is a friend of mine, as well as, any kind person.This explains a lot :)
Doctorate
I was happy to see that two friends defended their PhDs this summer. In chronological order, Radu Atanasiu defended his PhD in Iasi, at the end of June, and Robert Mercas defended his PhD in Tarragona, in July. Both of them work in theoretical computer science (on the formal languages "side of the world"), they had quite nice results in their papers, and I am sure that the PhD is just the beginning of their research career. Good luck in the future!
However, these happy events made me think about a "fundamental" thing: what "being a PhD" really means, and what social impact should such a title have? In Germany there is quite an important thing, since everybody who has a doctorate proudly lists a "Dr." in front of his/her name on any occasion (including here all the official papers); however, there are people who really don't have a clue what this means: is he/she a medical doctor? or what this prefix means?, but, anyway, they show respect to a person owning this title. In last years, nobody cares about this thing in Romania: there were so many "overnight PhDs" so the title is not meaningful anymore.
I think that being a PhD means that you've reached a certain scientific maturity: you were able to produce a series of original research results, that were considered relevant by the community, an where published in respectable venues. Of course, every university (or every supervisor) has the right to define what makes a PhD, but, generally speaking, all these definitions should encode the same idea: a person becomes a PhD when it is capable to move on from being a junior researcher to being a senior researcher, when it is capable of identifying new research topics and of working on them independently. In Germany the requirements that one should meet before becoming a PhD are quite high; in Romania they are very low. And probably this reflects in the manner a doctor is seen in the society. But...
... Should this title really have a social impact? I think that it should, but not a very deep one. Of course, a person who is a PhD must receive some respect in the society: that person is a certified expert in a certain area (which, by the way, is not encoded in any way in the "Dr." prefix), has proved certain intellectual capacities, and is also capable of working on a long term, difficult, project. But this is all! It's important not to make a big fuss about a title that says much about your professional capabilities, but not so much about you as part of the society, and to concentrate more on the actions and deeds that actually define you as a person.
However, these happy events made me think about a "fundamental" thing: what "being a PhD" really means, and what social impact should such a title have? In Germany there is quite an important thing, since everybody who has a doctorate proudly lists a "Dr." in front of his/her name on any occasion (including here all the official papers); however, there are people who really don't have a clue what this means: is he/she a medical doctor? or what this prefix means?, but, anyway, they show respect to a person owning this title. In last years, nobody cares about this thing in Romania: there were so many "overnight PhDs" so the title is not meaningful anymore.
I think that being a PhD means that you've reached a certain scientific maturity: you were able to produce a series of original research results, that were considered relevant by the community, an where published in respectable venues. Of course, every university (or every supervisor) has the right to define what makes a PhD, but, generally speaking, all these definitions should encode the same idea: a person becomes a PhD when it is capable to move on from being a junior researcher to being a senior researcher, when it is capable of identifying new research topics and of working on them independently. In Germany the requirements that one should meet before becoming a PhD are quite high; in Romania they are very low. And probably this reflects in the manner a doctor is seen in the society. But...
... Should this title really have a social impact? I think that it should, but not a very deep one. Of course, a person who is a PhD must receive some respect in the society: that person is a certified expert in a certain area (which, by the way, is not encoded in any way in the "Dr." prefix), has proved certain intellectual capacities, and is also capable of working on a long term, difficult, project. But this is all! It's important not to make a big fuss about a title that says much about your professional capabilities, but not so much about you as part of the society, and to concentrate more on the actions and deeds that actually define you as a person.
Theoretical Computer Science at SYNASC 2010
Continuing the work he started last year, Gabriel Istrate organizes again, this fall, a special track of SYNASC 2010, on Theoretical Computer Science, and, this time, he invited me to be co-chair of the Program Committee. Advances in the Theory of Computing (AITC'10) will host papers in all areas of Theoretical Computer Science, broadly construed. Here you can have a look at the Program Committee, and here is the Call for Papers: differently from the conference organized last year, we added to the CFP topics like automata theory, formal languages, combinatorics on words, algorithmic learning theory (let's say with a more European flavor).
As I said last year, the idea behind this workshop is to create a serious Romanian theory-conference: it would be good to gather some good papers from abroad, in order to offer the Romanian community a view on some subjects of interest in TCS, but, also, it seems to me a good chance for some Romanian researchers (both beginners and experienced) to publish their work in a conference refereed at high-standards (and published in a decent venue). Moreover, the submission deadline (July.1) is in a period when there are not so many conference-deadlines in Europe.
So, when you look for a venue where to present your newly obtained results, have in mind also AITC 2010!
As I said last year, the idea behind this workshop is to create a serious Romanian theory-conference: it would be good to gather some good papers from abroad, in order to offer the Romanian community a view on some subjects of interest in TCS, but, also, it seems to me a good chance for some Romanian researchers (both beginners and experienced) to publish their work in a conference refereed at high-standards (and published in a decent venue). Moreover, the submission deadline (July.1) is in a period when there are not so many conference-deadlines in Europe.
So, when you look for a venue where to present your newly obtained results, have in mind also AITC 2010!
Romanian Academy Prize
I just found out that I received one of the prizes awarded yearly by the Romanian Academy, for the papers I wrote in 2007. The name of the prize is Tudor Tanasescu, and is awarded by the Section for Information Sciences and Technologies of the Academy.
Romjist Special Issue
I have edited, together with my colleague Professor Gheorghe Stefanescu, a special issue of the Romanian Journal of Information Science and Technology, dedicated to the 50th anniversary of Professor Victor Mitrana. This journal is published by the Publishing House of the Romanian Academy, edited by Section of Information Science and Technology from the Romanian Academy, and was recently included in the ISI Web of Science database (of course, how relevant is this last information is disputable). The contents of the special issue, which just became available online, can be found here.
Conferences 2009
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.
TCS Workshop at SYNASC2009
I received from Gabriel Istrate an e-mail announcing a special track of SYNASC 2009, on Theoretical Computer Science. More precisely, the workshop(?) is entitled Advances in the Theory of Computing (AITC'09), welcomes papers from various areas of Theoretical Computer Science, has a rather strong Program Committee, co-chaired by Gabriel Istrate and Mihai Patrascu.
I think that organizing such a conference in Romania is a great initiative (although it appears as a special track of a not so impressive conference), and I hope that it will grow to become a stand-alone conference. To conclude, I wish good luck to the organizers, and I hope they'll put up a really good conference (by the way, the submission details are here).
I think that organizing such a conference in Romania is a great initiative (although it appears as a special track of a not so impressive conference), and I hope that it will grow to become a stand-alone conference. To conclude, I wish good luck to the organizers, and I hope they'll put up a really good conference (by the way, the submission details are here).
Humboldt Research Fellowship
I am happy to announce that I have been awarded an Alexander von Humboldt Postdoctoral Research Fellowship (from the Humboldt Foundation). Therefore, I will spend the next two years, starting from this summer (probably June) in Germany, doing research. My choice was to be part of the Theoretical Computer Science group of the Otto-von-Guericke-University, in Magdeburg. My host for this period is Professor Jürgen Dassow.
Subscribe to:
Posts (Atom)