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.
