Two new papers that I have co-authored are available on Arxiv:
"Detecting Unary Patterns" (SPIRE 2017, new title: Detecting One-Variable Patterns), written together with Dmitry Kosolobov and Dirk Nowotka, proposes an efficient algorithm that locates in a text all the instances of a pattern that includes strings of letters and one-repeated variable (that can be replaced, uniformly, by any string of letters); the repeated variable can appear also reveresed.
This paper was started last year, when Dmitry visited us in Kiel, and put on Arxiv a while ago. However, since then it went through many changes and reached the current (nicer) form. It improves some of the algorithms presented in the papers from STACS 2014 (written together with Pawel Gawrychowski and Dirk Nowotka) and STACS 2015 (written together with Markus Schmid, Robert Mercas, and Henning Fernau).
"The Hardness of Solving Simple Word Equations" (MFCS 2017), written together with Joel Day and Dirk Nowotka, shows that the satisfiability of some very simple word equations is NP-complete. In word equations, we equate two strings (called sides) that contain variables and strings of letters. We want to check whether there is a way to assign (uniformly) strings of letters to the variables, such that the two sides become equal. In our simple case, each variable occurs at most once in each side and the order of the variables occurring in both sides is the preserved (the variables can be, however, separated by potentially distinct constant factors). Surprisingly, solving such simple equations, even when the sides contain exactly the same variables, is NP-hard. By considerations regarding the combinatorial structure of the shortest solutions of the more general quadratic equations we obtain that the satisfiability problem for regular-ordered equations is in NP. Finally, we also show that a related class of simple word equations, that generalises one-variable equations, is in P.
This paper was the result of the work Joel and I started recently on word equations and closes some of the open problems left in the paper from DLT 2016, written together with Markus Schmid and Dirk Nowotka. The paper published on Arxiv is a "cleaner" version of the paper we submitted, with some type-o-s and imprecisions fixed.
Both these papers are part of my current DFG-research project, on algorithms and combinatorics of words.
Showing posts with label Research: Resources. Show all posts
Showing posts with label Research: Resources. Show all posts
WORDS 2015 in Kiel - Call for Participation
10th International Conference on WORDS 2015 (the main conference dedicated to the study of combinatorics on words) takes place in Kiel from September 14 to September 17, 2015. We invite everyone who is interested in the topics and program of WORDS 2015 to register for the conference. More details are given below.
IMPORTANT DATES:
Starting Date of the Conference: September 14, 2pm.
Ending Date of the Conference: September 17, 5pm
IMPORTANT INFORMATION is to be found at the following links:
Registration Web-site, Information for Participants, Local Info.
SCHEDULE:
Invited Speakers:
Jörg Endrullis (Amsterdam), Markus Lohrey (Siegen), Jean Néraud (Rouen), Dominique Perrin (Paris), Michaël Rao (Lyon), Thomas Stoll (Nancy).
See also the list of contributed talks as well as the tentative schedule (a more detailed schedule will be published soon).
In the first day of the conference, an Open Problems (in Combinatorics on Words and Stringology) session will also be organized.
SOCIAL PROGRAM:
The social program of the conference includes an excursion and the conference dinner (supported by the organizers), as well as a couple of informal dinners.
About WORDS:
WORDS is a biannual international conference covering the mathematical theory of words (sequences of symbols) from all points of view: combinatorial, algebraic, algorithmic, as well as its applications to biology, linguistics, physics, and others. The previous WORDS conferences have taken place in Rouen (1997, 1999), Palermo (2001), Turku (2003, 2013), Montreal (2005), Marseille (2007), Salerno (2009), Prague (2011). This year we celebrate the 10th edition of WORDS.
A refereed proceedings volume, including extended abstracts of the invited talks as well as original contributions, that fulfil the high quality standards required by a formal publication in computer science, will be published in Springer's Lecture Notes in Computer Science series. In addition, a local proceedings volume will be published, including, in the spirit of mathematics conferences, a series of less formal contributions informing on current research and work in progress.
The PROGRAM COMMITTEE, that selected the talks to be presented at the conference, consists of: Maxime Crochemore (London), Juhani Karhumäki (Turku), Dirk Nowotka (Kiel - chair), Stepan Holub (Prague), Antonio Restivo (Palermo), Manfred Kufleitner (Stuttgart), Gad Landau (Haifa), Michel Rigo (Liege), James Currie (Winnipeg), Mikhail V. Volkov (Ekaterinburg), Wojciech Plandowski (Warsaw), Luca Zamboni (Lyon).
QUESTIONS regarding the conference can be addressed to the organizers (Dirk Nowotka, Florin Manea) via E-mail:
info[at]words2015[dot]uni-kiel[dot]de
IMPORTANT DATES:
Ending Date of the Conference: September 17, 5pm
IMPORTANT INFORMATION is to be found at the following links:
Registration Web-site, Information for Participants, Local Info.
SCHEDULE:
Invited Speakers:
Jörg Endrullis (Amsterdam), Markus Lohrey (Siegen), Jean Néraud (Rouen), Dominique Perrin (Paris), Michaël Rao (Lyon), Thomas Stoll (Nancy).
See also the list of contributed talks as well as the tentative schedule (a more detailed schedule will be published soon).
In the first day of the conference, an Open Problems (in Combinatorics on Words and Stringology) session will also be organized.
SOCIAL PROGRAM:
The social program of the conference includes an excursion and the conference dinner (supported by the organizers), as well as a couple of informal dinners.
About WORDS:
WORDS is a biannual international conference covering the mathematical theory of words (sequences of symbols) from all points of view: combinatorial, algebraic, algorithmic, as well as its applications to biology, linguistics, physics, and others. The previous WORDS conferences have taken place in Rouen (1997, 1999), Palermo (2001), Turku (2003, 2013), Montreal (2005), Marseille (2007), Salerno (2009), Prague (2011). This year we celebrate the 10th edition of WORDS.
A refereed proceedings volume, including extended abstracts of the invited talks as well as original contributions, that fulfil the high quality standards required by a formal publication in computer science, will be published in Springer's Lecture Notes in Computer Science series. In addition, a local proceedings volume will be published, including, in the spirit of mathematics conferences, a series of less formal contributions informing on current research and work in progress.
The PROGRAM COMMITTEE, that selected the talks to be presented at the conference, consists of: Maxime Crochemore (London), Juhani Karhumäki (Turku), Dirk Nowotka (Kiel - chair), Stepan Holub (Prague), Antonio Restivo (Palermo), Manfred Kufleitner (Stuttgart), Gad Landau (Haifa), Michel Rigo (Liege), James Currie (Winnipeg), Mikhail V. Volkov (Ekaterinburg), Wojciech Plandowski (Warsaw), Luca Zamboni (Lyon).
QUESTIONS regarding the conference can be addressed to the organizers (Dirk Nowotka, Florin Manea) via E-mail:
info[at]words2015[dot]uni-kiel[dot]de
Theory Day @ Bucharest: DACS 2015
Later update: The submission deadline was extended to March 31.
The second edition of our workshop Days of Computer Science takes place as a satellite event of CiE 2015, at the Faculty of Mathematics and Computer Science, University of Bucharest, on June 26 and 27, 2015. Days of Computer Science (DACS 2015) is the second edition of a workshop-series interested in building a solid and modern CS-research community in Romania, closely connected to the current global research-trends. Here is a link to DACS 2014, last year's event, and here is a link to its description on this blog. Generally, our workshop aims to attract participants from Romania and other European countries, helping to establish international collaborations between researchers working on common topics. This year the program consists mainly in a series of very interesting invited presentations of the work of remarkable researchers (selected by the Program Committee) relevant to the topics of the workshop. Besides these, we also invite submissions, especially by researchers at early stages of their career (e.g., doctoral students, postdocs), offering them the possibility to disseminate their work in a workshop with high-quality standards.
As highlight in our program, we host a special session dedicated to the memory of Mihai Patrascu, that will include an one hour scientific lecture given by Mikkel Thorup (Copenhagen).
Coming back to the main program, this year's list of invited speakers consists of:
Alexandru Baltag (Amsterdam)
Ștefan Ciobâcă (Iași)
Radu Curticapean (Saarbrücken)
Cătălin Dima (Paris)
Cezara Drăgoi (Paris) - tutorial
Radu Ionescu (Bucharest)
Marius Minea (Timișoara)
Daniela Petrișan (Nijmegen)
Alexandru Tomescu (Helsinki)
I am very happy to have such amazing speakers, and I thank all of them for accepting to come and give talks at our workshop!.
As said, for DACS 2015 we welcome submissions presenting original research results on the topics of the workshop. The accepted papers, as well as extended abstracts of the invited talks, will be published in the proceedings volume that will appear as an issue of the Annals of the University of Bucharest.
The topics of interest for DACS 2015 include, but are not restricted to: Algorithms and data structures, Computability and computational complexity, Knowledge representation, reasoning and logic, Formal verification, Data and text mining, Reasoning under uncertainty, Algebraic specification, Formal languages and automata theory, Machine learning, Cryptography, Combinatorics and algorithmics on words, Non-classical and graded logics, Natural language and speech automatic processing, Computational biology, bioinformatics and bio-inspired computing. Submissions on any other related topics are welcome.
We invite full research papers of up to 12 pages (Annals of the University of Bucharest style). Proof omitted due to space constraints may be put into an appendix, to be read by the reviewers at their discretion. Submit here.
As our higher goal is to allow the Romanian community easy access to quality research, this year the participation to the workshop is free of any charge. However, for logistic purposes, we ask the persons that wish to participate to the workshop to register prior to the event by sending an e-mail to theory-day@fmi.unibuc.ro with the name and affiliation.
Note the important dates:
Submission deadline: 23rd of March 2015, 23:59 EET
Notification: 17th of April 2015
Camera-ready version: 24th of April 2015
Deadline for Registration: 12th of June 2015
Organising this workshop would not have been possible without the help of my colleagues from the Program Committee:Denisa Diaconescu (Bern) – chair
Radu Gramatovici (Bucharest)
Georgiana Ifrim (Dublin)
Gabriel Istrate (Timișoara)
Ioana Leuștean (Bucharest)
Robert Mercas (London)
Marius Popescu (Bucharest)
... as well as the local Organising Committee:
Adela Georgescu (Bucharest)
Marius Popescu (Bucharest) – chair
Andrei Sipoș (Bucharest)
For questions about the workshop details please write e-mail to: theory-day[at]fmi.unibuc.ro
The second edition of our workshop Days of Computer Science takes place as a satellite event of CiE 2015, at the Faculty of Mathematics and Computer Science, University of Bucharest, on June 26 and 27, 2015. Days of Computer Science (DACS 2015) is the second edition of a workshop-series interested in building a solid and modern CS-research community in Romania, closely connected to the current global research-trends. Here is a link to DACS 2014, last year's event, and here is a link to its description on this blog. Generally, our workshop aims to attract participants from Romania and other European countries, helping to establish international collaborations between researchers working on common topics. This year the program consists mainly in a series of very interesting invited presentations of the work of remarkable researchers (selected by the Program Committee) relevant to the topics of the workshop. Besides these, we also invite submissions, especially by researchers at early stages of their career (e.g., doctoral students, postdocs), offering them the possibility to disseminate their work in a workshop with high-quality standards.
Notification: 17th of April 2015
Camera-ready version: 24th of April 2015
Deadline for Registration: 12th of June 2015
Organising this workshop would not have been possible without the help of my colleagues from the Program Committee:
CiE 2015 in Bucharest - Call for Papers
COMPUTABILITY IN EUROPE 2015: Evolving Computability, Bucharest, Romania,
June 29 - July 3
Web-site: http://fmi.unibuc.ro/CiE2015/
IMPORTANT DATES:
Extended Submission Deadline: 21 January 2015
Notification of authors: 9 March 2015
Deadline for final revisions: 6 April 2015
CiE 2015 is the 11-th conference organized by CiE (Computability in Europe), a European
association of mathematicians, logicians, computer scientists, philosophers, physicists
and others interested in new developments in computability and their underlying significance
for the real world. Previous meetings in the CiE conference series have taken place in Amsterdam (2005), Swansea (2006),
Siena (2007), Athens (2008), Heidelberg (2009), Ponta Delgada (2010), Sofia (2011),
Cambridge (2012), Milan (2013) and Budapest (2014).
For CiE 2015, we are looking for fundamental and theoretical submissions. In line with other
conferences in this series, CiE 2015 has a broad scope and provides a forum for the discussion
of theoretical and practical issues in Computability with an emphasis on new paradigms of
computation and the development of their mathematical theory.
We particularly invite papers that build bridges between
different parts of the research community.
For topics covered by the conference, please visit
http://fmi.unibuc.ro/CiE2015/topics.html
FUNDING OPPORTUNITIES:
CiE 2015 has received funding from ASL (Association for Symbolic Logic) and EATCS (European Association for Theoretical Computer Science) that allows students who are members of ASL or EATCS and want to attend CiE 2015 to apply for travel funds or a reduction of the early registration fee. Preference will be given to presenters of accepted papers. Applications for ASL travel grants have to be addressed directly to ASL, with a strict deadline of March 28, 2015.
Applications for EATCS travel grants have to be sent to cie2015[at]fmi[dot]unibuc[dot]ro prior to the early registration deadline.
CiE 2015 will host invited talks from the following:
TUTORIAL SPEAKERS:
John Reif (Duke Unversity),
Steve Simpson (Pennsylvania State University).
PLENARY SPEAKERS:
Ann Copestake (University of Cambridge),
Mircea Dumitru (University of Bucharest, Public Lecture),
Pawel Gawrychowski (Warsaw University),
Julia Knight (University of Notre Dame),
Anca Muscholl (Universite Bordeaux),
Gheorghe Paun (Romanian Academy),
Alexander Razborov (University of Chicago and Steklov Mathematical Institute), Vlatko Vedral (University of Oxford).
CiE 2015 will also host SPECIAL SESSIONS on Representing streams, Automata, logic and infinite games, Reverse mathematics, Classical computability theory, Bio-inspired computation, History and philosophy of computing.
The speakers of the special sessions are listed at http://fmi.unibuc.ro/CiE2015/sessions.html
The PROGRAMME COMMITTEE cordially invites all researchers (European and non-European) in computability related areas to submit their papers (in PDF format, max 10 pages using
the LNCS style) for presentation at CiE 2015.
The submission site
https://www.easychair.org/conferences/?conf=cie2015
is open. For more submission instructions consult
http://fmi.unibuc.ro/CiE2015/submission.html
The conference proceedings will be published by LNCS, Springer Verlag.
WORDS 2015 in Kiel - Preliminary Announcement
10th International Conference on WORDS 2015, Kiel, Germany, September 14-18, 2015
Web-site: http://words2015.uni-kiel.de/
IMPORTANT DATES:
Submission deadline: April 17, 2015
Notification of authors: May 27, 2015
Deadline for final versions: June 10, 2015
WORDS is a biannual international conference covering the mathematical theory of words (sequences of symbols) from all points of view: combinatorial, algebraic, algorithmic, as well as its applications to biology, linguistics, physics, and others.
The previous WORDS conferences have taken place in Rouen (1997, 1999), Palermo (2001), Turku (2003, 2013), Montreal (2005), Marseille (2007), Salerno (2009), Prague (2011). This year we celebrate the 10th edition of WORDS.
Please mark the conference dates in your agendas for 2015.
CONFIRMED INVITED SPEAKERS:
Jörg Endrullis (Amsterdam), Jean Néraud (Rouen), Michaël Rao (Lyon), Thomas Stoll (Nancy). Another two invited speakers are still to be announced.
For WORDS 2015, we are looking for original contributions on combinatorics on words, in the form of extended abstracts, for publication in a refereed proceedings volume.
In the tradition of the previous WORDS conferences, authors are also invited to submit high level contributions, which might not meet the requirements of the proceedings volume, for publication in a local abstract-booklet.
The PROGRAMME COMMITTEE, that will select the papers to be presented at the conference, consists of:
Maxime Crochemore (London), Juhani Karhumäki (Turku), Dirk Nowotka (Kiel - chair), Stepan Holub (Prague), Antonio Restivo (Palermo), Manfred Kufleitner (Stuttgart), Gad Landau (Haifa), Michel Rigo (Liege), James Currie (Winnipeg), Mikhail V. Volkov (Ekaterinburg), Wojciech Plandowski (Warsaw), Luca Zamboni (Lyon).
Questions regarding the conference can be addressed to the organisers (Dirk Nowotka, Florin Manea) via E-mail:
info[at]words2015[dot]uni-kiel[dot]de
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.
ICAART 2009: Special Session on NEPs
ICAART (International Conference on Agents and Artificial Intelligence) is a new AI conference (its first edition takes place in January 2009, in Porto), organized by INSTICC, together with AAAI, APPIA and ACM SIGART. The conference seems to be of a decent quality, if we consider the program comitee and the list of keynote speakers; also, the proceedings are indexed by INSPEC and DBLP, and a book containing the best papers will be published by Springer.
Usually, I am not very interested in AI conferences, so it would have been very improbable for me to take part at such a conference. However, I am interested in this conference because one of its special sessions is dedicated to Networks of Evolutionary Processors (NEPs, the topic of my PhD thesis). I was invited to contribute to this session, so I wrote a survey paper, together with Victor Mitrana, covering the most significant results obtained so far for NEPs, and other closely related models, in the computational and descriptional complexity area. Here is a short description of the talk I will give in Porto:
Accepting Networks of Evolutionary Processors: Complexity Aspects. Recent Results and New Challenges
Abstract: In this paper we survey some results reported so far, for the new computational model of Accepting Networks of Evolutionary Processors (ANEPs), in the area of computational and descriptional complexity. First we give the definitions of the computational model, and its variants, then we define several ANEP complexity classes, and, further, we show how some classical complexity classes, defined for Turing Machines, can be characterized in this framework. After this, we briefly show how ANEPs can be used to solve efficiently NP-complete problems. Finally, we discuss a list of open problems and further directions of research which appear interesting to us.
Usually, I am not very interested in AI conferences, so it would have been very improbable for me to take part at such a conference. However, I am interested in this conference because one of its special sessions is dedicated to Networks of Evolutionary Processors (NEPs, the topic of my PhD thesis). I was invited to contribute to this session, so I wrote a survey paper, together with Victor Mitrana, covering the most significant results obtained so far for NEPs, and other closely related models, in the computational and descriptional complexity area. Here is a short description of the talk I will give in Porto:
Accepting Networks of Evolutionary Processors: Complexity Aspects. Recent Results and New Challenges
Abstract: In this paper we survey some results reported so far, for the new computational model of Accepting Networks of Evolutionary Processors (ANEPs), in the area of computational and descriptional complexity. First we give the definitions of the computational model, and its variants, then we define several ANEP complexity classes, and, further, we show how some classical complexity classes, defined for Turing Machines, can be characterized in this framework. After this, we briefly show how ANEPs can be used to solve efficiently NP-complete problems. Finally, we discuss a list of open problems and further directions of research which appear interesting to us.
Language Theory in Biocomputing
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.
Natural Computing in CACM
I was very glad to see that the cover story of the Communications of ACM, October 2008 issue, is an article closely related to my main research interests, namely bio-inspired computing: The Many Facets of Natural Computing, written by Lila Kari and Grzegorz Rozenberg. The original article can be found here, and another version with extended References list but with no picture can be found here. The paper offers a broad perspective on how biology and computer science are related, on how nature may be used as inspiration for computation, or on how nature itself computes; the authors mention the main trends and theories that appeared so far, some of results that were obtained, the perspectives, and some of the most important journals and book series aimed at the general natural computing community.
AFL 2008: Final Remarks
AFL 2008 ended almost a week ago, and I think it is the time to complete my so-called report on this conference. So, I'll start by describing the talks of the last two days.
The third day of the conference started with the invited talk of Viliam Geffert, which turned out to be one of the most interesting (in my opinion) talks presented at AFL. Basically, the author proposed a polynomial algorithm that reduces a given deterministic finite automaton (DFA for short) to a hyper-minimized DFA, which may have fewer states than the minimized DFA; however this newly obtained automaton accepts a language which differs from the one accepted by the input DFA by a finite number of words. Moreover any other DFA, with fewer states, accepts a language which differs from the one accepted by the input DFA by an infinite number of words; of course, a hyper-minimized DFA is not unique for a given language (as it is the case of minimized DFAs), but there are some structural similarities between hyper-minimized DFAs for languages differing only by a finite number of words. The talk left a series of open problems, some dealing with language theoretic properties and some dealing with algorithmic properties of hyper-minimized DFAs.
From the rest of the contributed talks presented in that day I recall as interesting the talk of Jurgen Dassow and Bianca Truthe on Subregularly Tree Controlled Grammars and Languages, a subject that seems interesting to me: context-free grammars whose derivation is restricted by some conditions on the structure of the derivation trees. The two authors approached the problem only from a language theoretic point of view, but it seems appealing to me to see if these languages still have the good computational properties of context-free languages; more precisely, it would be interesting to see how complex should be the conditions that we put on the derivation trees such that the classes of languages we obtain are still contained in the class of languages accepted in deterministic polynomial time.
In the fourth, and last, day of the conference I attended only the invited talk of Ion Petre, who approached the same topic as in the presentation he gave in April at FMI. Since I wasn't able to attend the conference in FMI, and I work also in a field were computing meets biology, I was quite curious to see what was the talk about. I will not go into details, but I will just say that the speaker showed how formal languages tools and algorithmic tools can model the study of the biological properties of the ciliates; there were shown several important ideas in this direction, as well as the most important results obtained so far. Finally, some ideas on how ciliates can be used in computing (as part of some bio-inspired computing models) were given. Concluding, it was an interesting talk.
The social part of the conference had its most important parts in the third day of the conference: the visit to the Tihany Abbey, a Benedictine abbey built in the 18th century, on the place of a 11th century monastery which hosted the crypt of King Andrew I. During the visit to the Abbey we were also offered an organ concert, of about half an hour. The evening ended with the conference dinner, at the oldest traditional Hungarian restaurant in Tihany.
In conclusion, my final remarks on AFL 2008 are: there were some excellent invited talks, the level of the papers presented at the conference was rather high, the organization was also excellent. I know already that AFL 2011 is one of the conferences that I will try to attend, and I recommend this to anyone interested in formal languages and automata theory.
Latest news (Jun. 20, 2008): We were invited to submit a follow-up of our paper for a special issue of IJFCS dedicated to AFL 2008. Of course, we will submit such a paper.
The third day of the conference started with the invited talk of Viliam Geffert, which turned out to be one of the most interesting (in my opinion) talks presented at AFL. Basically, the author proposed a polynomial algorithm that reduces a given deterministic finite automaton (DFA for short) to a hyper-minimized DFA, which may have fewer states than the minimized DFA; however this newly obtained automaton accepts a language which differs from the one accepted by the input DFA by a finite number of words. Moreover any other DFA, with fewer states, accepts a language which differs from the one accepted by the input DFA by an infinite number of words; of course, a hyper-minimized DFA is not unique for a given language (as it is the case of minimized DFAs), but there are some structural similarities between hyper-minimized DFAs for languages differing only by a finite number of words. The talk left a series of open problems, some dealing with language theoretic properties and some dealing with algorithmic properties of hyper-minimized DFAs.
From the rest of the contributed talks presented in that day I recall as interesting the talk of Jurgen Dassow and Bianca Truthe on Subregularly Tree Controlled Grammars and Languages, a subject that seems interesting to me: context-free grammars whose derivation is restricted by some conditions on the structure of the derivation trees. The two authors approached the problem only from a language theoretic point of view, but it seems appealing to me to see if these languages still have the good computational properties of context-free languages; more precisely, it would be interesting to see how complex should be the conditions that we put on the derivation trees such that the classes of languages we obtain are still contained in the class of languages accepted in deterministic polynomial time.
In the fourth, and last, day of the conference I attended only the invited talk of Ion Petre, who approached the same topic as in the presentation he gave in April at FMI. Since I wasn't able to attend the conference in FMI, and I work also in a field were computing meets biology, I was quite curious to see what was the talk about. I will not go into details, but I will just say that the speaker showed how formal languages tools and algorithmic tools can model the study of the biological properties of the ciliates; there were shown several important ideas in this direction, as well as the most important results obtained so far. Finally, some ideas on how ciliates can be used in computing (as part of some bio-inspired computing models) were given. Concluding, it was an interesting talk.
The social part of the conference had its most important parts in the third day of the conference: the visit to the Tihany Abbey, a Benedictine abbey built in the 18th century, on the place of a 11th century monastery which hosted the crypt of King Andrew I. During the visit to the Abbey we were also offered an organ concert, of about half an hour. The evening ended with the conference dinner, at the oldest traditional Hungarian restaurant in Tihany.
In conclusion, my final remarks on AFL 2008 are: there were some excellent invited talks, the level of the papers presented at the conference was rather high, the organization was also excellent. I know already that AFL 2011 is one of the conferences that I will try to attend, and I recommend this to anyone interested in formal languages and automata theory.
Latest news (Jun. 20, 2008): We were invited to submit a follow-up of our paper for a special issue of IJFCS dedicated to AFL 2008. Of course, we will submit such a paper.
AFL 2008: Impressions
There are already two days since the beginning of the Automata and Formal Languages 2008 Conference, and I am glad to say that the conference fully met my expectation, so far. Here are a few impressions on this conference (I will mention only the talks that impressed me, and give some brief information about them):
The first day of the conference began with the Satellite Event "Challenges in Computing and Complexity", which consisted in three invited talks, given by Gheorghe Paun, Tamas Roska and Eors Szathmary. The first talk, of Paun, was, as the speaker himself announced, a propaganda for membrane computing; basically, we were offered an overview on the area: the results obtained so far, the perspectives, open problems, and, nevertheless, a short list of research groups working in P-systems. Tamas Roska proposed an approach to distributed computing: how to use cellular neural network universal machine and supercomputer (a construction by which one can obtain million processors chips, based on some deep mathematical ideas). Finally, Eors Szathmary gave a talk on Evolutionary Developmental Neurobiology.
The afternoon of the first day marked the official opening of the conference. From the presentations of that day I especially enjoyed the invited talk of Jacques Sakarovitch on "The Sequentialisation of Automata and Transducers", although it does not fit exactly my research interests: algebraic theory of automata (in Schutzenberger-Nivat style). The rest of the day was dedicated to papers in the same line of research.
The second day was more important for me, since my talk took place then. The first invited talk of the day was that of Markus Lohrey, dealing with algorithms on compressed strings - basically membership problems in the context of compressed strings in regular languages. The framework was a language theoretic one (strings were given by straight-line programs, basically context-free grammars which generate only one string, and regular languages were defined by means of automata or regular expressions). Several upper and lower bounds were proposed for such problems, and also an answer to an open problem of Rytter and Plandowsky was given: the compressed membership problem for regular expressions with intersection is PSPACE-complete. I consider this as the most interesting talk so far. The day continued with two (good) talks on combinatorial properties of partial words -a domain in which I am interested, in which I published and I will probably work in the future-, both coming from the group of Francine Blanchet-Sadri (one of them was a joint work with my co-author Robert Mercas). Our presentation went all right, as far as I could figure (while giving the talk).
In the afternoon of the second day there were also some good talks, most of them in the area of automata theory. I only mention that Markus Lohrey gave another talk (contributed, this time) on automatic and recursive graphs, Fred Otto presented some results on stateless Two-PDA and Restarting Automata, and Peter Leupold brought to discussion the recently introduced Deep Push-Down Automata (PDAs whose stack may contain both terminal and non-terminal symbols, and in which only the non-terminals found in the stack up to a given depth can be rewritten); Peter's paper was interesting to me since I worked sometime ago on some other, somehow similar, generalization of PDAs, the go-through automata. Finally, the last paper gave some interesting complexity results concerning reset words for some particular type of finite automata (related somehow to Cerny conjecture).
The last two days of the conference will be covered in another post.
I cannot end this brief report on AFL 2008 without mentioning the excellent organization: the location of the conference was very good chosen (a hotel on the shores of lake Balaton, in a nice touristic area), the fact that the hosts are always ready to meet all the requests and needs of the participants, the conference welcome dinner with its most friendly atmosphere, and so on. And the best is yet to come: the excursion to Tihany Benedictine Abbey and the conference dinner at some traditional Hungarian "csarda".
Concluding, what I like most about AFL is probably the fact that it is a conference that brings together people working in the same area (and, usually, some of the important names in this area), people who know each other (and, often, worked together, and are even friends) and creates the perfect framework for sharing your ideas, for presenting your work, and learning what others are doing.
The first day of the conference began with the Satellite Event "Challenges in Computing and Complexity", which consisted in three invited talks, given by Gheorghe Paun, Tamas Roska and Eors Szathmary. The first talk, of Paun, was, as the speaker himself announced, a propaganda for membrane computing; basically, we were offered an overview on the area: the results obtained so far, the perspectives, open problems, and, nevertheless, a short list of research groups working in P-systems. Tamas Roska proposed an approach to distributed computing: how to use cellular neural network universal machine and supercomputer (a construction by which one can obtain million processors chips, based on some deep mathematical ideas). Finally, Eors Szathmary gave a talk on Evolutionary Developmental Neurobiology.
The afternoon of the first day marked the official opening of the conference. From the presentations of that day I especially enjoyed the invited talk of Jacques Sakarovitch on "The Sequentialisation of Automata and Transducers", although it does not fit exactly my research interests: algebraic theory of automata (in Schutzenberger-Nivat style). The rest of the day was dedicated to papers in the same line of research.
The second day was more important for me, since my talk took place then. The first invited talk of the day was that of Markus Lohrey, dealing with algorithms on compressed strings - basically membership problems in the context of compressed strings in regular languages. The framework was a language theoretic one (strings were given by straight-line programs, basically context-free grammars which generate only one string, and regular languages were defined by means of automata or regular expressions). Several upper and lower bounds were proposed for such problems, and also an answer to an open problem of Rytter and Plandowsky was given: the compressed membership problem for regular expressions with intersection is PSPACE-complete. I consider this as the most interesting talk so far. The day continued with two (good) talks on combinatorial properties of partial words -a domain in which I am interested, in which I published and I will probably work in the future-, both coming from the group of Francine Blanchet-Sadri (one of them was a joint work with my co-author Robert Mercas). Our presentation went all right, as far as I could figure (while giving the talk).
In the afternoon of the second day there were also some good talks, most of them in the area of automata theory. I only mention that Markus Lohrey gave another talk (contributed, this time) on automatic and recursive graphs, Fred Otto presented some results on stateless Two-PDA and Restarting Automata, and Peter Leupold brought to discussion the recently introduced Deep Push-Down Automata (PDAs whose stack may contain both terminal and non-terminal symbols, and in which only the non-terminals found in the stack up to a given depth can be rewritten); Peter's paper was interesting to me since I worked sometime ago on some other, somehow similar, generalization of PDAs, the go-through automata. Finally, the last paper gave some interesting complexity results concerning reset words for some particular type of finite automata (related somehow to Cerny conjecture).
The last two days of the conference will be covered in another post.
I cannot end this brief report on AFL 2008 without mentioning the excellent organization: the location of the conference was very good chosen (a hotel on the shores of lake Balaton, in a nice touristic area), the fact that the hosts are always ready to meet all the requests and needs of the participants, the conference welcome dinner with its most friendly atmosphere, and so on. And the best is yet to come: the excursion to Tihany Benedictine Abbey and the conference dinner at some traditional Hungarian "csarda".
Concluding, what I like most about AFL is probably the fact that it is a conference that brings together people working in the same area (and, usually, some of the important names in this area), people who know each other (and, often, worked together, and are even friends) and creates the perfect framework for sharing your ideas, for presenting your work, and learning what others are doing.
AFL 2008: Some Remarks on the Hairpin Completion
As I have already announced in previous post, the 12th International Conference on Automata and Formal Languages (AFL) will take place at the end of May 2008 in Balatonfured, Hungary. I was glad to see that the paper I wrote for this conference, with Victor Mitrana and Takashi Yokomori, was accepted. If everything works as planned I will attend the conference, and present the paper; of course I will write some blog posts about the conference and the work presented there. The complete list of accepted papers can be found here (and I must say that the names on that list, as well as the names of the invited speakers, make me belive that AFL 2008 is going to be a good conference, similar to its past editions).
The title of our paper is Some Remarks on the Hairpin Completion, and below you can find its abstract. The complete version of the paper is available upon request.
Abstract: We consider some problems regarding the iterated or non-iterated hairpin completion of some subclasses of regular languages. Thus we obtain a characterization of the class of regular languages as the weak-code images of the k-hairpin completion of center-disjoint k-locally testable languages in the strict sense. This result completes two results from D. Cheptea, C. Martin-Vide, V. Mitrana, A new operation on words suggested by DNA biochemistry: hairpin completion, in Proc. Transgressive Computing, 216-228, 2006, and F. Manea, V. Mitrana, T. Yokomori, Two complementary operations inspired by the DNA hairpin formation: completion and reduction, to appear in Theoretical Computer Science. Then we investigate some decision problems and closure properties of the family of the iterated hairpin completion of singleton languages. Finally, we discuss some algorithms regarding the possibility of computing the values of k such that the non-iterated or iterated k-hairpin completion of a given regular language does not produce new words.
CIE 2007 Post-conference Publications
After the Computability in Europe 2007 Conference, several authors were invited to submit papers that continue their work presented at the conference for special issues of some journals. You can find below brief presentations of the two such papers I co-authored, and that were acceped to appear in Theoretical Computer Science - Track C.
Two Complementary Operations Inspired by the DNA Hairpin Formation: Completion and Reduction, written together with Victor Mitrana and Takashi Yokomori.
Abstract: We consider two complementary operations: hairpin completion introduced in [D. Cheptea, C. Martin-Vide, V. Mitrana, A new operation on words suggested by DNA biochemistry: hairpin completion, in Proc. Transgressive Computing, 216--228, 2006] with motivations coming from DNA biochemistry and hairpin reduction as the inverse operation of the hairpin completion. Both operations are viewed here as formal operations on words and languages. We settle the closure properties of the classes of regular and linear context-free languages under hairpin completion in comparison with hairpin reduction. While the class of linear context-free languages is exactly the weak-code image of the class of the hairpin completion of regular languages, rather surprisingly, the weak-code image of the class of the hairpin completion of linear context-free languages is a class of mildly context-sensitive languages. The closure properties with respect to the hairpin reduction of some time and space complexity classes are also studied. We show that the factors found in the general cases are not necessary for regular and context-free languages. This part of the paper completes the results in the previously cited paper, where a similar investigation was made for hairpin completion. Finally, we briefly discuss the iterated variants of these operations.
On Small, Reduced, and Fast Universal Accepting Networks of Splicing Processors, written together with Remco Loos and Victor Mitrana.
Abstract: In this paper, we show that accepting networks of splicing processors (ANSPs) of size 2 are computationally complete. Since, by definition, an ANSP needs at least two nodes to perform non-trivial computations, this completely settles the question of designing complete ANSPs of minimal size. Also, we derive from this result the fact that all the languages in PSPACE can be accepted by ANSPs of size 2, having polynomial length complexity (the ANSP complexity measure for the space used in a computation). However, the construction that we propose, although efficient from the descriptional complexity and space complexity points of view, does not seem to have good properties from the time complexity point of view. In this respect, we prove that ANSPs of size 3 can decide all languages in NP in polynomial time. The previous lower bound on size for both completeness and efficient acceptance of NP-languages was 7. We also consider ANSPs with restricted features, proving the following normal forms: for any ANSP there exists an equivalent ANSP without input filters, and one without output filters. Finally, we show how to construct a small universal ANSP and make several considerations on the computational efficiency of universal ANSPs.
Complete versions of these papers are available upon request.
Two Complementary Operations Inspired by the DNA Hairpin Formation: Completion and Reduction, written together with Victor Mitrana and Takashi Yokomori.
Abstract: We consider two complementary operations: hairpin completion introduced in [D. Cheptea, C. Martin-Vide, V. Mitrana, A new operation on words suggested by DNA biochemistry: hairpin completion, in Proc. Transgressive Computing, 216--228, 2006] with motivations coming from DNA biochemistry and hairpin reduction as the inverse operation of the hairpin completion. Both operations are viewed here as formal operations on words and languages. We settle the closure properties of the classes of regular and linear context-free languages under hairpin completion in comparison with hairpin reduction. While the class of linear context-free languages is exactly the weak-code image of the class of the hairpin completion of regular languages, rather surprisingly, the weak-code image of the class of the hairpin completion of linear context-free languages is a class of mildly context-sensitive languages. The closure properties with respect to the hairpin reduction of some time and space complexity classes are also studied. We show that the factors found in the general cases are not necessary for regular and context-free languages. This part of the paper completes the results in the previously cited paper, where a similar investigation was made for hairpin completion. Finally, we briefly discuss the iterated variants of these operations.
On Small, Reduced, and Fast Universal Accepting Networks of Splicing Processors, written together with Remco Loos and Victor Mitrana.
Abstract: In this paper, we show that accepting networks of splicing processors (ANSPs) of size 2 are computationally complete. Since, by definition, an ANSP needs at least two nodes to perform non-trivial computations, this completely settles the question of designing complete ANSPs of minimal size. Also, we derive from this result the fact that all the languages in PSPACE can be accepted by ANSPs of size 2, having polynomial length complexity (the ANSP complexity measure for the space used in a computation). However, the construction that we propose, although efficient from the descriptional complexity and space complexity points of view, does not seem to have good properties from the time complexity point of view. In this respect, we prove that ANSPs of size 3 can decide all languages in NP in polynomial time. The previous lower bound on size for both completeness and efficient acceptance of NP-languages was 7. We also consider ANSPs with restricted features, proving the following normal forms: for any ANSP there exists an equivalent ANSP without input filters, and one without output filters. Finally, we show how to construct a small universal ANSP and make several considerations on the computational efficiency of universal ANSPs.
Complete versions of these papers are available upon request.
Influential Computer Science Books
It was an old wish of mine to write down a list of the computer science books that influenced (positively) my career. In the following you can find a preliminary version of this list. The books, briefly described below, are not necessary "advanced", or the most comprehensive references in their domain, but they offered me an interesting, rewarding, and fruitful lecture.
1. Introduction to Algorithms, by Cormen, Leisserson, Rivest and Stein. It's the book that made me choose a research career in CS rather than a research career in math.
2. Introduction to Automata Theory, Languages, and Computation, by Hopcroft, Motwani and Ullman. One of the best bibliographical references in formal languages, at undergraduate level. Offers also a glimpse towards computability and complexity.
3. Handbook of Formal Languages, eds. Rozenberg and Salomaa. Written in 1997, it contains a collection of papers presenting the hot subjects (at that moment) in formal languages. Some of them are still of great interest, at least for me.
4. Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson. A nice presentation of the complexity theory, focused on NP-Completeness (the central topic in TCS, in my oppinion).
5. DNA Computing - New Computing Paradigms, by Paun, Rozenberg and Salomaa. Interesting for those of use working with bio-inspired computational models.
6. Introduction to the Theory of Computation, by Sipser. A good book from which you can learn the basics of computability and complexity.
7. Jewels of Stringology, by Crochemore and Rytter. Great book on string algorithms.
8. Randomized Algorithms, by Motwani and Raghavan. Published in 1995, it is a very well written survey on how probability theory can be applied in the development efficient (yet not deterministic) algorithms.
9. Data Structures and Algorithms, by Mehlhorn. A good reference on classical algorithms and data structures.
10. Network Flows, by Ahuja, Magnati and Orlin. Written in 1995, it is a good introduction to the network flows (algorithmic) theory.
...Please feel encouraged to recommend any other book, as a comment on this post.
An interesting discussion on a similar topic can be found on the Computational Complexity blog.
1. Introduction to Algorithms, by Cormen, Leisserson, Rivest and Stein. It's the book that made me choose a research career in CS rather than a research career in math.
2. Introduction to Automata Theory, Languages, and Computation, by Hopcroft, Motwani and Ullman. One of the best bibliographical references in formal languages, at undergraduate level. Offers also a glimpse towards computability and complexity.
3. Handbook of Formal Languages, eds. Rozenberg and Salomaa. Written in 1997, it contains a collection of papers presenting the hot subjects (at that moment) in formal languages. Some of them are still of great interest, at least for me.
4. Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson. A nice presentation of the complexity theory, focused on NP-Completeness (the central topic in TCS, in my oppinion).
5. DNA Computing - New Computing Paradigms, by Paun, Rozenberg and Salomaa. Interesting for those of use working with bio-inspired computational models.
6. Introduction to the Theory of Computation, by Sipser. A good book from which you can learn the basics of computability and complexity.
7. Jewels of Stringology, by Crochemore and Rytter. Great book on string algorithms.
8. Randomized Algorithms, by Motwani and Raghavan. Published in 1995, it is a very well written survey on how probability theory can be applied in the development efficient (yet not deterministic) algorithms.
9. Data Structures and Algorithms, by Mehlhorn. A good reference on classical algorithms and data structures.
10. Network Flows, by Ahuja, Magnati and Orlin. Written in 1995, it is a good introduction to the network flows (algorithmic) theory.
...Please feel encouraged to recommend any other book, as a comment on this post.
An interesting discussion on a similar topic can be found on the Computational Complexity blog.
New Book on Computational Paradigms
I have just received an e-mail from Barry Cooper (one of the coordinators of the Computability in Europe Network) announcing this new book:
NEW COMPUTATIONAL PARADIGMS - CHANGING CONCEPTIONS OF WHAT IS COMPUTABLE
Cooper, S. Barry; Loewe, Benedikt; Sorbi, Andrea (Eds.)
2008, Springer Mathematics of Computing series XIII,
560 pp. 19 illus., Hardcover, ISBN: 978-0-387-36033-1
As written in the description of the book on the Springer site:
[It] examines new developments in the theory and practice of computation from a mathematical perspective, with topics ranging from classical computability to complexity, from biocomputing to quantum computing. The book opens with an introduction by Andrew Hodges, the Turing biographer, who analyzes the pioneering work that anticipated recent developments concerning computation’s allegedly new paradigms. The remaining material covers traditional topics in computability theory such as relative computability, theory of numberings, and domain theory, in addition to topics on the relationships between proof theory, computability, and complexity theory. New paradigms of computation arising from biology and quantum physics are also discussed, as well as the computability of the real numbers and its related issues.
The researchers that contributed to this book are: Serikzhan Badaev, Johan van Benthem, Olivier Bournez, Vasco Brattka, Samuel R. Buss, Manuel L. Campagnolo, Abbas Edalat, Sergey Goncharov, Joel David Hamkins, Peter Hertling, Andrew Hodges, Ulrich Kohlenbach, Yuri Matiyasevich, Elvira Mayordomo, Russell Miller, Yiannis N. Moschovakis, Dag Normann, Dana Pardubska, Vasilis Paschalis, Gheorghe Paun, Michael Rathjen, Grzegorz Rozenberg, Helmut Schwichtenberg, Daniel Seabold, Wilfried Sieg, Viggo Stoltenberg-Hansen, John V. Tucker, Steve Warner, Klaus Wehirauch, Jiri Wiedermann.
You can find more about the book here (the announcement sent by Barry Cooper).
Research Papers for High-School/Undergraduate Students
Infoarena tries to build up a page containing links to some algorithms-related research papers, presenting results that may be understood (and even used in programming contests) by high-school and undergraduate students. There are already several nice papers listed there (selected by Mihai Patrascu, Cosmin Negruseri and others). I intend to add to that list some of the papers that influenced me in the past (as far as they are available online); moreover I will add any paper I read and consider as being suitable for this page.
Various Sites on TCS Conferences
I recently read on the Computational Complexity Blog about a site containing the list of invited talks given at some of the most important theoretical computer science conferences. The author of this site also proposes a site with the list of papers accepted in theoretical computer science conferences and a site with information on the upcoming theoretical computer science conferences.
The site contains interesting resources, although several important theory conferences are not listed. I mention here only the Computability in Europe Conference Series and the Developments in Language Theory Conference Series, and the list may continue.
The site contains interesting resources, although several important theory conferences are not listed. I mention here only the Computability in Europe Conference Series and the Developments in Language Theory Conference Series, and the list may continue.
Theory of Computing Archive
I've read on the WebDiarios de Motocicleta blog about the Theory of Computing Blog Aggregator: a site that collects posts from several research blogs written by computer science theorists, as well as some articles from arXiv on topics linked to the theory of computing. Yesterday I read part of the posts archived on this site, and I found them really interesting. Thus, I added the link to this site in my blogroll.
Subscribe to:
Posts (Atom)