Ursprünge und Anwendungen von Theorie A vs Theorie B?

30

In einigen kürzlich gestellten Fragen ( q1 q2 ) wurde "Theorie A" gegen "Theorie B" diskutiert, um die Kluft zwischen dem Studium von Logik und Programmiersprachen und dem Studium von Algorithmen und Komplexität zu erfassen.

Diese Terminologie war für mich neu, und bei einer schnellen Websuche wurden keine offensichtlichen Verweise gefunden, die dies erläuterten.

Kennt jemand eine Referenz oder Referenzen, die den Ursprung dieser Terminologie erklären, und welchen, wenn überhaupt, materiellen Nutzen soll diese Unterscheidung haben?

ho.history-overview terminology Marc Hamann
quelle
Off-Topic: Ich schlage vor, die Links zu q1 & q2 zu bearbeiten und auf deren "Permalink" zu verlinken. Auf diese Weise bleiben die Links auch dann gültig, wenn die Titel der Fragen bearbeitet werden.
MS Dousti
5
Der Titel wird ignoriert. cstheory.stackexchange.com/questions/944/foobar funktioniert einwandfrei , obwohl es nicht mit dem Titel übereinstimmt.
Jukka Suomela
1
Gute Frage, das habe ich mich selbst gefragt. "Theorie B" schien immer etwas abfällig!
Aaron Roth
5
@ Aaron: Ich denke, es ist besser, als PL "Eurotheory" zu nennen, wie es manchmal gemacht wird. Das hat mich bei PL-Forschern in den USA oder in Japan und bei zweifachen Komplexitätstheoretikern in Europa immer sehr beeindruckt. :)
Neel Krishnaswami
Moshe Vardi hat einen kurzen Überblick mit einigen Referenzen in diesem Blogbeitrag. Warum hat ACM kein SIG für Theoretische Informatik? & schreibt einen Teil davon der Nationalität zu; US (mehr Theorie A) vs europäische Betonung (gemischt)
vzn

Antworten:

33

Es stammt aus dem Handbuch zur theoretischen Informatik , das zwei Bände umfasste: A war für Algorithmen und Komplexität, und B war für Logik und Semantik.

Jukka, hat ICALP das früher gemacht? Oder war es eine Reaktion darauf?

Was die Vorteile angeht, so gibt es meiner Meinung nach immer einen Nutzen bei der Taxonomisierung von Bereichen, die auf interessanten Themen und Studienformen basieren. Wie bei allen Taxonomisierungen tritt das Problem jedoch auf, wenn Sie vergessen, "den Baum wieder hoch und die andere Seite runter zu gehen" :).

EDIT : Wie ICALP ausdrücklich feststellt, stammt diese Unterteilung aus der Zeitschrift Theoretical Computer Science von Elsevier , die bereits vor dem Handbuch veröffentlicht wurde. Ich denke, das ist eine genauere Quelle.

EDIT ++ : Aus der Geschichte des EATCS stammt dieser Ausschnitt über TCS, die Zeitschrift:

Seitdem berichtet M. Nivat, der immer noch Chefredakteur ist, regelmäßig an den Rat und die Generalversammlung sowie gelegentlich im Bulletin - zB wenn die Aufteilung in die Abschnitte A (Automaten, Algebra und Algorithmen) und B (Logik, Semantik und verwandte Themen) beschlossen (Bulletin Nr. 45, S. 2,3, Oktober 1991);

Das ergibt 1991, als dies zum ersten Mal in der Zeitschrift passierte. Das Handbuch wurde jedoch erstmals im September 1990 veröffentlicht!

Suresh Venkat
quelle
3
Es scheint, dass ICALP ihre Spuren 1997 aus dem TCS-Journal übernommen hat . Die ältesten Verweise auf "Spur A" und "Spur B", die ich auf ihren Webseiten finden konnte, stammten jedoch aus dem Jahr 1999 .
Jukka Suomela
1
ICALP 1997 hieß es: "Das Silberjubiläum ist auch eine Gelegenheit, das allgemeine Format von ICALP neu zu gestalten. Das Programmkomitee vertritt die beiden Titel, wie sie aus den beiden Unterreihen der Zeitschrift Theoretical Computer Science bekannt sind, und deckt algorithms' and formale Methoden gleichermaßen ab." (von der ICALP 1997 Seite)
Suresh Venkat
Die 1997er Seite scheint jedoch nicht die Bezeichnungen "A" und "B" zu verwenden, um auf die beiden Spuren zu verweisen.
Jukka Suomela
nein, aber es ist klar, was die Absicht ist. und TCS hatte die A / B-Unterscheidung, denke ich.
Suresh Venkat
2
Verwandter historischer Punkt: TCS (C) war eine Zeitschrift für "Natural Computing", aber das Thema von ICALPs Track C hat sich meines Erachtens jedes Jahr geändert.
Aaron Sterling
3

ICALP Strecke A vs. B.

Jukka Suomela
quelle