¿Orígenes y aplicaciones de la teoría A contra la teoría B?

30

En un par de preguntas recientes ( q1 q2 ), se ha debatido sobre "Teoría A" versus "Teoría B", aparentemente para capturar la división entre el estudio de los lenguajes de lógica y programación y el estudio de algoritmos y complejidad.

Esta terminología era nueva para mí, y una búsqueda rápida en la web no arrojó referencias obvias que lo explicaran.

¿Alguien sabe de una referencia o referencias que expliquen el origen de esta terminología, y qué beneficio sustancial, si lo hay, se deriva de hacer esta distinción?

Marc Hamann
fuente
Fuera de tema: sugiero editar los enlaces a q1 y q2, y vincularlos a sus "enlaces permanentes". De esta manera, incluso si se editan los títulos de las preguntas, los enlaces siguen siendo válidos.
MS Dousti
55
El título se ignora; cstheory.stackexchange.com/questions/944/foobar funciona bien aunque no coincida con el título.
Jukka Suomela
1
Buena pregunta, me lo he preguntado yo mismo. ¡La "Teoría B" siempre parecía un poco despectiva!
Aaron Roth
55
@ Aaron: Creo que es mejor que llamar a PL "Eurotheory", como a veces se hace. Esto siempre me ha parecido muy duro para los investigadores de PL en los EE. UU. O Japón, y para los teóricos de la doble complejidad en Europa. :)
Neel Krishnaswami
Moshe Vardi tiene una breve descripción general con algunas referencias en esta publicación de blog ¿Por qué ACM no tiene un SIG para la informática teórica? y atribuye parte de ello a la nacionalidad; EE. UU. (Más teoría A) vs énfasis europeo (mixto)
vzn

Respuestas:

33

Proviene del manual sobre informática teórica , que tenía dos volúmenes: A era para algoritmos y complejidad, y B era para lógica y semántica.

Jukka, ¿ICALP fue anterior a esto? ¿O fue en respuesta a esto?

En cuanto a los beneficios, creo que siempre hay alguna utilidad en taxonomizar áreas basadas en temas de interés y formas de estudio. Sin embargo, como con todas las taxonomizaciones, el problema surge cuando olvida "volver al árbol y bajar al otro lado" :).

EDITAR : como indica explícitamente ICALP, esta división proviene de la revista Elsevier Theoretical Computer Science , que es anterior al manual, por lo que creo que es una fuente más precisa.

EDIT ++ : De la historia de EATCS viene este fragmento sobre TCS, la revista:

Desde ese momento, M. Nivat, que todavía es editor en jefe, ha informado regularmente al consejo y a la asamblea general y ocasionalmente en el Boletín, por ejemplo, cuando se divide en las secciones A (autómatas, álgebra y algoritmos) y B (lógica, semántica y temas relacionados) se decidió (Boletín no. 45, p.2,3, octubre de 1991);

que produce 1991 como cuando esto comenzó a suceder en la revista. ¡Sin embargo, el Manual se publicó por primera vez en septiembre de 1990!

Suresh Venkat
fuente
3
Parece que ICALP tomó sus huellas de la revista TCS en 1997 . Sin embargo, las referencias más antiguas a "pista A" y "pista B" que pude encontrar en sus páginas web fueron de 1999 .
Jukka Suomela
1
ICALP 1997 fue: "El aniversario de plata también es una ocasión para remodelar el formato general de ICALP. El comité del programa representa las dos pistas conocidas de las dos subseries de la revista Theoretical Computer Science y cubre algorithms' and los métodos formales" por igual ". (de la página de ICALP 1997)
Suresh Venkat
Pero la página de 1997 no parece usar las etiquetas "A" y "B" para referirse a las dos pistas.
Jukka Suomela
no, pero está claro cuál es la intención. y TCS tenía la distinción A / B, creo.
Suresh Venkat
2
Punto histórico relacionado: TCS (C) era una revista de "computación natural", pero creo que el tema de la Pista C de ICALP ha cambiado cada año.
Aaron Sterling