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.
