Origines et applications de la théorie A contre la théorie B?

30

Dans quelques questions récentes ( q1 q2 ), il y a eu une discussion entre "Théorie A" et "Théorie B", apparemment pour capturer le fossé entre l'étude de la logique et des langages de programmation et l'étude des algorithmes et de la complexité.

Cette terminologie était nouvelle pour moi, et une recherche rapide sur le Web n'a trouvé aucune référence évidente l'expliquant.

Quelqu'un connaît-il une référence ou des références qui expliquent l'origine de cette terminologie et, le cas échéant, quel avantage substantiel devrait être tiré de cette distinction?

Marc Hamann
la source
Hors sujet: je suggère de modifier les liens vers q1 et q2, et de les relier à leurs "permaliens". De cette façon, même si les titres des questions sont modifiés, les liens restent valides.
MS Dousti
5
Le titre est ignoré; cstheory.stackexchange.com/questions/944/foobar fonctionne bien même s'il ne correspond pas au titre.
Jukka Suomela
1
Belle question, je me suis posé cette question moi-même. La "théorie B" a toujours semblé un peu péjorative!
Aaron Roth
5
@Aaron: Je pense que c'est mieux que d'appeler PL "Eurotheory", comme cela se fait parfois. Cela m'a toujours frappé aussi durement pour les chercheurs en PL aux États-Unis ou au Japon que pour les théoriciens de la complexité en Europe. :)
Neel Krishnaswami
Moshe Vardi a un bref aperçu avec quelques références dans ce billet de blog Pourquoi ACM n'a-t-il pas un SIG pour l'informatique théorique? & en attribue une partie à la nationalité; États-Unis (plus de théorie A) vs accent européen (mixte)
vzn

Réponses:

33

Il provient du manuel sur l'informatique théorique , qui avait deux volumes: A était pour les algorithmes et la complexité, et B était pour la logique et la sémantique.

Jukka, l'ICALP est-il antérieur à cela? Ou était-ce en réponse à cela?

En ce qui concerne les avantages, je pense qu'il est toujours utile de taxonomiser des domaines basés sur des sujets d'intérêt et des formes d'étude. Cependant, comme pour toutes les taxonomisations, le problème survient lorsque vous oubliez de "remonter l'arbre et descendre de l'autre côté" :).

EDIT : comme ICALP l'indique explicitement, cette division provient de la revue Elsevier Theoretical Computer Science , qui elle-même est antérieure au manuel, donc je pense que c'est une source plus précise.

EDIT ++ : De l' histoire de l'EATCS vient cet extrait sur TCS, le journal:

Depuis lors, M. Nivat, qui est toujours rédacteur en chef, fait régulièrement rapport au conseil et à l'assemblée générale et occasionnellement dans le Bulletin - par exemple lorsque la division en sections A (automates, algèbre et algorithmes) et B (logique, sémantique et sujets connexes) a été décidé (Bulletin n ° 45, p. 2,3, octobre 1991);

qui donne 1991 comme lorsque cela a commencé à se produire au journal. Cependant, le manuel a été publié pour la première fois en septembre 1990!

Suresh Venkat
la source
3
Il semble que l'ICALP ait pris leurs traces dans le journal TCS en 1997 . Cependant, les références les plus anciennes à la "piste A" et à la "piste B" que j'ai pu trouver sur leurs pages Web remontaient à 1999 .
Jukka Suomela
1
ICALP 1997, c'était: "Le jubilé d'argent est aussi l'occasion de remodeler le format général de l'ICALP. Le comité de programme représente les deux pistes telles qu'elles sont connues des deux sous-séries de la revue Theoretical Computer Science et couvre également algorithms' and les méthodes formelles." (à partir de la page ICALP 1997)
Suresh Venkat
Mais la page de 1997 ne semble pas utiliser les étiquettes "A" et "B" pour faire référence aux deux pistes.
Jukka Suomela
non, mais il est clair quelle est l'intention. et TCS avait la distinction A / B je pense.
Suresh Venkat
2
Point historique connexe: TCS (C) était une revue «informatique naturelle», mais le sujet de la piste C d'ICALP a changé chaque année, je pense.
Aaron Sterling
3

ICALP piste A contre B.

Jukka Suomela
la source