37
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Sadeq Dousti
    Sep 20, 2010 at 21:37
  • 5
    $\begingroup$ The title is ignored; cstheory.stackexchange.com/questions/944/foobar works ok even though it doesn't match the title. $\endgroup$
    – Jukka Suomela
    Sep 20, 2010 at 21:46
  • 1
    $\begingroup$ Nice question, I've wondered this myself. "Theory B" always seemed a little derogatory! $\endgroup$
    – Aaron Roth
    Sep 21, 2010 at 2:11
  • 5
    $\begingroup$ @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. :) $\endgroup$
    – Neel Krishnaswami
    Sep 21, 2010 at 8:18
  • 1
    $\begingroup$ 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) $\endgroup$
    – vzn
    Jun 10, 2015 at 15:00

2 Answers 2

Reset to default
39
$\begingroup$

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 !

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ 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. $\endgroup$
    – Jukka Suomela
    Sep 20, 2010 at 21:44
  • 1
    $\begingroup$ 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) $\endgroup$
    – Suresh Venkat
    Sep 20, 2010 at 21:51
  • $\begingroup$ But the 1997 page does not seem to use the labels "A" and "B" to refer to the two tracks. $\endgroup$
    – Jukka Suomela
    Sep 20, 2010 at 21:53
  • $\begingroup$ no but it's clear what the intent is. and TCS had the A/B distinction I think. $\endgroup$
    – Suresh Venkat
    Sep 20, 2010 at 22:08
  • 2
    $\begingroup$ Related historical point: TCS (C) was a "natural computing" journal, but the topic of ICALP's Track C has changed each year I think. $\endgroup$
    – Aaron Sterling
    Sep 20, 2010 at 22:24
3
$\begingroup$

ICALP track A vs. B.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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