2
$\begingroup$

At some point in history, theoretical computer science emerged as a sub-discipline of computer science. Later, apparently it segregated into "volume A" work and "volume B" work. This can be seen for example at the Handbook of Theoretical Computer Science (1990), which is divided into Volume A: Algorithms and Complexity, and Volume B: Formal Models and Sematics. Other witnesses of the divide are the journal Theoretical Computer Science and the International Colloquium on Automata, Languages, and Programming, which also use Track A and B (with another Track C later). What were the reasons (in the sense of developments) that led to the divide, what were the cultural consequences (e.g. in the US, theory A is predominant), and when did it take place? Can we observe some point in time when the terms "A" and "B" (or similar) were used for the first time to denote this divide?

$\endgroup$
  • 1
    $\begingroup$ Well,they are non-intersecting topics of great interest, so there's that. $\endgroup$ – Carl Witthoft May 15 at 10:57
  • 2
    $\begingroup$ It seems a quite natural alternative to Volume 1, Volume 2, and so on... $\endgroup$ – Mauro ALLEGRANZA May 15 at 18:16
  • $\begingroup$ @Carl Witthoft you are certainly right, this is the reason why we have the divide. Let me explain a bit more: Both algorithms and formal models were studied from the very beginning. And there were textbooks that treated both. The beginning of the study of semantics is often attributed to a paper of Floyd (1967), and Cobham's paper (1965) defining the complexity class P is a landmark in computational complexity. I agree that the topics are interesting and non-intersecting today. But I suspect that these topics weren't considered to be non-intersecting in (say) 1970. When did it fall apart? $\endgroup$ – Hermann Gruber May 15 at 22:22
0
$\begingroup$

I later realized that I posed several questions. I try to give a partial answer the simplest of those questions (when). An article by Ute and Wilfried Brauer for the silver jubilee of the European Association for Theoretical Computer Science mentions that Maurice Nivat (then editor-in-chief) communicated the decision of dividing the journal Theoretical Computer Science into Track A and B in Bulletin of the EATCS no. 45, p.2,3, October 1991. (I could not access that article yet).

Maurice Nivat wrote an Editorial to Theoretical Computer Science 78(1) as well – he mentions "the huge increase of the number of subject areas in computer science that are open to formal, mathematical or logic methods and the huge increase of the number of researchers at work". Consequently, it was decided that the number of volumes per year would be increased by fifty percent, and that they would split the editorial board into Part A and Part B.

The conference ICALP started to have plenary sessions, and also two parallel sessions (with Track A and Track B papers) only in 1997. In the foreword, Pierpaolo Degano, Roberto Gorrieri and Alberto Marchetti-Spaccamela write:

ICALP '97 was organised differently than before and accommodated further events, to react positively to the new challenges that the theoretical science community faces in the information technology society. Indeed, our community has developed and now utilizes several approaches and different methodologies that require increased specialization. As a consequence, there is a growing number of specialized conferences and workshops, and it is difficult for researchers to follow the recent developments on specialized research topics. ICALP '97 was a first step towards having a conference offering a single unifying environment while leaving room for specialization. In such an event, the computer science community interested in the development of formal methods and methodologies can stress the relationships that exist among different branches.

I suspect that the A/B divide was caused by the growth of the field of theoretical computer science, and the development of specialized methods used in its subfields, and that it gradually took place before the "formal" split we can observe in the handbook of TCS, the journal TCS and ICALP. (This summary sounds much like a platitude to me, and there's certainly more to say about it.)

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.