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?
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.)