In a couple recent questions (q1 q2), there has been discussion of "Theory A" vs "Theory B", seemingly to capture the divide between the study of logic and programming languages and the study of algorithms and complexity.

This terminology was new to me, and a quick web search didn't come up with any obvious references explaining it.

Does anyone know of a reference or references that explain the origin of this terminology, and what, if any, substantive benefit is intended to be derived from making this distinction?

  • Off-topic: I suggest editing the links to q1 & q2, and linking to their "permalink"s. This way, even if the questions' titles are edited, the links remain valid. – M.S. Dousti Sep 20 '10 at 21:37
  • 4
    The title is ignored; cstheory.stackexchange.com/questions/944/foobar works ok even though it doesn't match the title. – Jukka Suomela Sep 20 '10 at 21:46
  • 1
    Nice question, I've wondered this myself. "Theory B" always seemed a little derogatory! – Aaron Roth Sep 21 '10 at 2:11
  • 4
    @Aaron: I think it's better than calling PL "Eurotheory", as is sometimes done. This has always struck me as hard on PL researchers in the US or Japan, and dually complexity theorists in Europe. :) – Neel Krishnaswami Sep 21 '10 at 8:18
  • Moshe Vardi has a brief overview with some refs in this blog post Why Doesn’t ACM Have a SIG for Theoretical Computer Science? & attributes some of it to nationality; US (more theory A) vs European emphasis (mixed) – vzn Jun 10 '15 at 15:00
up vote 32 down vote accepted

It comes from the handbook on theoretical computer science, which had two volumes: A was for algorithms and complexity, and B was for logic and semantics.

Jukka, did ICALP predate this ? Or was it in response to this ?

As for benefits, I think there's always some utility in taxonomizing areas based on topics of interest, and forms of study. However, as with all taxonomizations, the problem comes when you forget to "go back up the tree and down the other side" :).

EDIT: as ICALP explicitly states, this division comes from the Elsevier journal Theoretical Computer Science, which itself predates the handbook, so I think that's a more accurate source.

EDIT ++: From the history of the EATCS comes this snippet about TCS, the journal:

Since that time M. Nivat, who is still Editor-in-Chief has reported regularly to council and general assembly and occasionally in the Bulletin - e.g. when the split into sections A (automata, algebra und algorithms) and B (logic, semantics and related topics) was decided upon (Bulletin no. 45, p.2,3, October 1991);

which yields 1991 as when this first started happening at the journal. However, the Handbook was first published in September 1990 !

  • 3
    It seems that ICALP took their tracks from the TCS journal in 1997. However, the oldest references to "track A" and "track B" that I could find on their web pages was from 1999. – Jukka Suomela Sep 20 '10 at 21:44
  • 1
    ICALP 1997 it was: "The silver jubilee is also an occasion to re-shape the general format of ICALP. The program committee represents the two tracks as known from the two subseries of the journal Theoretical Computer Science and covers algorithms' and formal methods' equally. " (from the ICALP 1997 page) – Suresh Venkat Sep 20 '10 at 21:51
  • But the 1997 page does not seem to use the labels "A" and "B" to refer to the two tracks. – Jukka Suomela Sep 20 '10 at 21:53
  • no but it's clear what the intent is. and TCS had the A/B distinction I think. – Suresh Venkat Sep 20 '10 at 22:08
  • 1
    Related historical point: TCS (C) was a "natural computing" journal, but the topic of ICALP's Track C has changed each year I think. – Aaron Sterling Sep 20 '10 at 22:24

ICALP track A vs. B.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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