I encountered a well-documented case last weekend at the third History of Programming Languages conference (HOPL III). David Harel discussed the difficulties he had encountered in trying to publish a paper on statecharts:
I still remember the talk on statecharts (and the digital watch) that David gave at DEC/SRC, circa 1984-5. And I remember the number of people I urged to have a look at the method, but did not have the eloquence to convince.
The process leading to the eventual publication of this paper is interesting in its own right. For almost two years, from early 1984 until late 1985, I repeatedly submitted it to what seemed to be the most appropriate widely read venues for such a topic. These were, in order, Communications of the ACM, IEEE Computer and IEEE Software. The paper was rejected from all three of these journals. In fact, from IEEE Computer it was rejected twice ― once when submitted to a special issue on visual languages and once when submitted as a regular paper. My files contain quite an interesting collection of referee reports and editors' rejection letters. Here are some of the comments therein:
"I find the concept of statecharts to be quite interesting, but unfortunately only to a small segment of our readership. I find the information presented to be somewhat innovative, but not wholly new. I feel that the use of the digital watch example to be useful, but somewhat simple in light of what our readership would be looking for."
"The basic problem […] is that […] the paper does not make a specific contribution in any area."
"A research contribution must contain 'new, novel, basic results'. A reviewer must certify its 'originality, significance, and accuracy'. It must contain 'all technical information required to convince other researchers in the area that the results are valid, verifiable and reproducible'. I believe that you have not satisfied these requirements."
"I think your contribution is similar to earlier contributions."
"The paper is excellent in technical content; however, it is too long and the topic is good only for a very narrow audience."
"I doubt if anyone is going to print something this long."
Indeed, the paper was quite long; it contained almost 50 figures. The main running example was my Citizen Quartz Multi-Alarm digital wristwatch, which was claimed in the rejection material by some to be too simple an example for illustrating the concepts and by others to be far too detailed for a scientific article… Some claimed that since the paper was about the much studied finite-state machine formalism it could not contain anything new or interesting…
One must understand that in the mid-1980s there was only scant support for visual languages. Visual programming in the classical sense had not really succeeded; it was very hard to find ways to visualize nontrivial algorithmic systems (as opposed to visualizing the dynamic running of certain algorithms on a particular data structure), and the only visual languages that seemed to be successful in system design were those intended to specify structure rather than behavior. Flowcharts, of course, were a failure in that most people used them to help explain the real thing, which was the computer program. There was precious little real use of flowcharts as a language that people programmed in and then actually executed. In terms of languages for structure, there were structure diagrams and structure charts, hierarchical tree-like diagrams, and so on. The issue of a visual language with precise semantics for specifying behavior was not adequately addressed at all. Petri nets were an exception, but except for some telecommunication applications they did not seem to have caught on widely in the real world. My feeling was that this had mainly to do with the lack of adequate support in Petri nets for hierarchical specification of behavior...
[T]he inability to get it published was extremely frustrating. Interestingly, during the two years of repeated rejections, new printings of the 1984 technical report had to be prepared, to address the multitude of requests for reprints. This was before the era of the internet and before papers were sent around electronically. So here was a paper that no one wanted to publish but that so many seemed to want to read... I revised the paper twice during that period, and the title changed again, to the final "Statecharts: A Visual Formalism for Complex Systems". Eventually, two and half years later, in July 1987, the paper was published in the theoretical journal Science of Computer Programming. That happened as a result of Amir Pnueli, who was one of its editors, seeing the difficulties I was having and soliciting the paper for the journal.* [pp. 9-10]* By the way, this story of the repeated rejections of the paper would not be as interesting were it not for the fact that in the 20 years or so since its publication it has become quite popular. According to Citeseer, it has been for several years among the top handful of most widely quoted papers in computer science, measured by accumulated citations since publication (in late 2002 it was in the second place on the list).