International Journal of Foundations of Computer Science and Formal Languages Conferences

I noticed that several important conferences having topics related to the theory of Formal Languages and Automata, such as DLT, AFL and CIAA, whose selected papers were usually published (besides the regular proceedings) in special issues of the Theoretical Computer Science journal, will have instead, in this year, dedicated special issues of the International Journal of Foundations of Computer Science for this purpose. Even if this decision of the conferences comitees applies only for this year, I think that it is a sign of the growing importance of this journal; it should be interesting to see how this will reflect in the journal's impact factor (which was, as far as I know, 0.5 in 2006).


g, said...

Dear Florin

(in the interest of readability I'll write in English - we could both, of course, use Romanian).

The conference list (and the lack of CIE and AFL on it) only reflects the relative order of importance of these conferences in the overall TCS conference landscape. That's it (and I'm saying as someone who submitted a paper to CiE and might submit - of all things - a formal language paper, albeit a rather nonstandard one, motivated by Symbolic Dynamics, to AFL).

I think that people doing TCS in Romania have to face the following reality: formal language theory is by and large passe. We (well I'm not really part of the FL direction anymore) would probably be better off spending our time *learning* and doing other things. There are so many directions that hardly anyone *inside* Romania is working on: approximation algorithms, computational biology, randomized algorithms, rapidly mixing Markov chains, online algorithms, data structures, theory of cryptography, game-theoretic methods in CS, algorithmic issues in networking, average case analysis of algorithms, random graphs and structures, discrete models from Physics, computational complexity of various flavors (circuit, interactive proofs, communication, holographic algorithms, derandomization, even quantum) !

I don't mean that you can't do good work in FL. You can, ocasionally (but it's harder than in other areas). I want even less to bad name the Romanian researchers working in the field (quite the opposite; my mentors - probably same as yours - come from this area, and I owe them so much). But I think Theoretical Computer Science in this country should move towards the more central problems in the field.

Yes, publishing in CiE,AFL,DLT is perfectly reasonable but one should try to publish -at least now and then- in conferences on that list. My own record at that is not great (especially since the list starts in 2002; after 2000 my interests expanded outside Theoretical Computer Science), but those are the venues that deal with problems of
(statistical) interest in our field.

Gabi Istrate

Florin Manea said...

Hello, Gabi! I am glad that you found the time to post a comment on my blog.

About the conferences: you can't say that CiE is a formal languages conference... its scope is rather large, and the papers presented at this conference, as well as the invited speakers, who are definitely important figures, and the topics they presented were very variated. I regard CiE as one of the most important European conferences, and I think that it may be included on a list containing important conferences world wide. DLT and AFL are basically formal languages conferences, so here your arguments may apply. However DLT still remains an important conference (and I also think it should be mentioned on that list). Another argument that such conferences should be present on a list of major theory conferences is that they determinate major interest among (not only) European researchers, each publishes about 40 papers and has an acceptance rate of approximatively 25%.

On the other hand can you give further arguments for your statement: "the following reality: formal language theory is by and large passe".

Best regards,

g, said...

CIE: a nice conference, in that brings together more mathematically oriented people and theoretical computer scientists.

My statement had to do with the dual status of conferences in our area: unlike pure mathematics or physics (where you go to conferences to meet people, and hear new resuts), our area, for good or worse, gives conference publications a status role that in other fields is reserved to journals such as Annals of Mathematics or Nature. The list you are referring to chooses these conferences from a "status" perspective. Yes, you might complain that it is a bit too U.S. centric (by the way MFCS and FCT are not on that list either), but I think that it pretty accurately reflects the prevailing views on what's most important in Theoretical Computer Science.

In other words: CiE is more of a nice workshop-like meeting, but publishing in it does not count as much (in my opinion) on the "status" side. And, as much as I don't agree with the exagerations in this direction in some venues, I think that this (publishing in more competitive, "status" conferences, ICALP, SODA, STOC, FOCS) is a game we (romanians *in Romania* working more or less in TCS) should be getting better at.

As to FLT: it's, of course, a matter of opinion. Or I could say that, if we take the really top venues for TCS, Journal of the ACM, STOC, FOCS, very few "formal language" papers get published. This is, of course, counting beans and I don't think is the best argument. So let me make a different, more precise, claim:

"Except for a few happy cases, FLT is not suited for its original mission. Its
the modeling power is not that great and the mathematics it uses is rather inelegant. The real practical applications don't benefit from the development of the theory, and the lack of real practical application is not compensated by increased understanding."

This is quite a statement, so let me give details:

1. Purpose of FLT/increased understanding.

What is the purpose of FLT ? I would say classification (which has modeling as a prerequisite).
In this case FLT has lost the battle to Computational Complexity, which provides a much more fine-grained picture. Computational Complexity also has areas which are kind of "passe" (some aspects of Structural Complexity), but (with the exception of regular/context-free portion of the Chomsky hierarchy)
it does the classification job much better.

2. Lack of modeling power.

If you look at some of its best success stories (the use of L-systems in plant drawing, or grammatical picture generation) you'll see that the actually relevant mechanisms are considerably more complicated than the "classical" L-systems, and the results proved by theoretical computer scientists don't really have any impact on the practical applications, similar to the one results about regular/context-free languages had on compiling. I would require a similar degree of success from any class of formal languages worth studying.

Ironically, L-systems are really useful in Physics (see for example the following book, written by a physicist

But it's a direction mainly for physicists',
not computer scientists'.

3. Inelegant mathematics.

A "most typical" formal language paper:

- defines a generative mechanism.
- compares the class of languages with that of other classes.
- investigates closure properties of the class of languages.

Arguments are usually combinatorial tricks, with hardly any mathematical depth. Contrast that with the use, say, of algebraic topology in Herlihy's work on wait-free computation, Fourier analysis on finite groups in the work on
threshold properties of monotone decision problems and that on quantum computing, game theory in a host of results, linear programming for approximation algorithms and more, semidefinite programming (in the same area), differential equations(probabilistic analysis of algorithms), stochastic processes, concentration inequalities etc (randomized algorithms and probabilistic combinatorics in general).

What are the comparably elegant recent results in FLT ?

4. Practical applications

I consider a theory useful when someone *outside Theoretical Computer Science* starts to speak that language and learn the concepts of the theory. For instance,
physicists teach about computational complexity in their books

and some of them were interested enough to become "experts" (from Physics) in this area. See one keynote presentation at

This is what I would call a successful research direction. Am I asking too much ?


Florin Manea said...

I'll try to give some answers to the four points supporting Gabi's statement, from the point of view of someone close to the FLT.

First, there is no battle between FLT and Complexity Theory. Actually, Complexity Theory would not have existed in its current form without the FL foundations: I think that one cannot talk about Complexity theory without mentioning Automata theory (after all, Turing machines are automata as well). However, it seems to me that Gabi tends to separate Automata Theory from FLT, which is not correct. Moreover, before one tries to apply the tools of Complexity theory to clasify a problem in some complexity class, usually one checks whether that problem is decidable or not; this brings us, again, closer to the framework of FLT.

As far as I know FLT finds direct applications in linguistics, biology, neurology, etc. There are many new operations on words strongly related to these domains, The results obtained in these cases are considered valuable and used by the scientists working in those domains (for example, parsing algorithms for formal languages are used in linguistics); note that linguists, biologists, etc., do not simply use some tools created by theorists, but they "borrow" the formalism, as well. And the classes of languages that find such applications are not only the classical ones, from the Chomsky hierarchy, but classes of contextual languages as well, or classes of multi-dimensional languages, tree languages, graph languages, accompanied by their corresponding accepting devices. Finally, there are trends in FLT dealing with new computational paradigms, inspired from various domains: biology, physics, etc. Considering all the above, I think that it should be clear by now that, nowadays, there is no typical formal languages paper, or at least it does not resemble to what Gabi calls typical FL paper. Indeed, the times when the papers published in FLT looked like your definition of typical paper are past.

The math involved in FLT is, in my oppinion, not that un-ellegant as you say. Take a look, for example, at the papers of Juhani Karhumaki, Jean Eric Pin or Maurice Margenstern. While the first two work mainly in Combinatorics on words (but their results and proofs are far from what you may call combinatorial trick), the third uses advanced geometry to prove some properties of cellular automata. This short list of researchers can be easily enriched: there are plenty of good examples of elegant mathematics in nowadays FLT papers. Also, I doubt that using advanced math is absolutely needed in all the cases; there are results that may have been obtained more easily by using a better, and simpler, definition (modelling more precisely the concepts) instead of using general definitions, accompanied by complicated (though ellegant) proofs, that have no other implications that the particular case already mentioned.

A general look on the status of FLT would reveal, in my oppinion, the following: it is a domain that reached its maturity, thus it is harder to obtain spectacular results, or to publish in the most important journals/conferences. However the domain still has impact: in every ICALP you find several FL papers, Information and Computation (a good journal) decided to publish follow-up papers from LATA (basically a conference on FL), almost every number of Theoretical Computer Science (again an important journal) or Information Processing Letters contains a paper on FL. Another indicator of the impact that FL has is that you can still find many open problems in the domain, that still induce great interest among theoreticians. Nevertheless, I would call an European trend the interest in Formal languages, not necessary a Romanian trend.

Last, I'll make a few considerations regarding the important conferences/journals in TCS. I agree that JACM (as a journal), ICALP, FOCS, SODA, STOC (as conferences) should be considered among the most important journals/conferences in TCS; however, it is clear, as Gabi said, that the list is US centric. And, I think we may add to the list of important, at least for the European TCS community, journals and conferences Theoretical Computer Science, Mathematical Structures in Computer Science (as journals), DLT, MFCS, FCT, CiE, ETAPS (as conferences), and the list may be continued. Btw, Gabi, your opinion on CiE is based on a personal experience? I ask you this because I have participated at two editions of CiE and I have a totally different opinion.


Anonymous said...

I am agree with Florin. I feel that FLT has become so mature that it is assumed and given for "standard" in may other fields. In other words, there is no need for learning it because it is already "part" of many fields, even when used "implicitely". In (theoretical) phisics, biology, linguistics, they use the concept of rewriting all the time, maybe only in a non-explicit manner like in TCS.

Florin Manea said...

As another argument that FL theory is still of interest, note that the Best Paper Award at ICALP 2008, track B, was won by the paper: Mai Gehrke, Serge Grigorieff and Jean-Eric Pin: "Duality and equational theory of regular languages".