Geneza i zastosowania teorii A vs. teorii B?

30

W kilku ostatnich pytaniach ( q1 q2 ) omawiano „Teorię A” vs. „Teorię B”, najwyraźniej w celu uchwycenia podziału między nauką logiki i języków programowania a badaniem algorytmów i złożoności.

Ta terminologia była dla mnie nowa, a szybkie wyszukiwanie w Internecie nie przyniosło żadnych oczywistych referencji.

Czy ktoś wie o referencji lub referencjach, które wyjaśniają pochodzenie tej terminologii i jakie ewentualne korzyści materialne można uzyskać z takiego rozróżnienia?

Marc Hamann
źródło
Poza tematem: Sugeruję edycję linków do q1 i q2 oraz linkowanie do ich „linków bezpośrednich”. W ten sposób, nawet jeśli tytuły pytań są edytowane, linki pozostają ważne.
MS Dousti,
5
Tytuł jest ignorowany; cstheory.stackexchange.com/questions/944/foobar działa dobrze, nawet jeśli nie pasuje do tytułu.
Jukka Suomela,
1
Ładne pytanie, zastanawiałem się nad tym sam. „Teoria B” zawsze wydawała się trochę uwłaczająca!
Aaron Roth,
5
@Aaron: Myślę, że to lepsze niż nazywanie PL „Eurotheory”, jak to się czasem robi. Zawsze uderzyło mnie to tak mocno w badaczy PL w Stanach Zjednoczonych i Japonii, jak i podwójnie teoretyków złożoności w Europie. :)
Neel Krishnaswami,
Moshe Vardi ma krótki przegląd z kilkoma referencjami w tym poście na blogu Dlaczego ACM nie ma SIG dla teoretycznej informatyki? i przypisuje część tego narodowości; USA (więcej teorii A) a nacisk europejski (mieszany)
od

Odpowiedzi:

33

Pochodzi z podręcznika z informatyki teoretycznej , który miał dwa tomy: A dotyczył algorytmów i złożoności, a B - logiki i semantyki.

Jukka, czy ICALP było wcześniej? A może było to odpowiedzią?

Jeśli chodzi o korzyści, myślę, że zawsze istnieje pewna użyteczność w obszarach taksonomizacji na podstawie interesujących tematów i form studiów. Jednak, podobnie jak w przypadku wszystkich taksonomizacji, problem pojawia się wtedy, gdy zapomnisz „wrócić do drzewa i z drugiej strony” :).

EDYCJA : jak wyraźnie stwierdza ICALP, ten podział pochodzi z czasopisma Elsevier Theoretical Computer Science , który sam poprzedza podręcznik, więc uważam, że jest to dokładniejsze źródło.

EDIT ++ : Z historii EATCS pochodzi ten fragment o TCS, czasopiśmie:

Od tego czasu M. Nivat, który nadal jest redaktorem naczelnym, regularnie składa sprawozdania radzie i walnemu zgromadzeniu, a czasami w Biuletynie - np. Kiedy dzieli się na sekcje A (automaty, algebra i algorytmy) i B (logika, semantyka i tematy pokrewne) podjęto decyzję (Biuletyn nr 45, s. 2,3, październik 1991 r.);

co daje 1991 rok, kiedy to zaczęło się po raz pierwszy w czasopiśmie. Podręcznik został jednak opublikowany po raz pierwszy we wrześniu 1990 roku!

Suresh Venkat
źródło
3
Wygląda na to, że ICALP wziął swoje ślady z czasopisma TCS w 1997 roku . Jednak najstarsze odniesienia do „ścieżki A” i „ścieżki B”, które mogłem znaleźć na ich stronach internetowych, pochodziły z 1999 roku .
Jukka Suomela,
1
ICALP 1997 brzmiał: „Srebrny jubileusz to także okazja do zmiany kształtu ogólnego formatu ICALP. Komitet programowy reprezentuje dwie ścieżki znane z dwóch podstron czasopisma Theoretical Computer Science i obejmuje algorithms' and „ metody równorzędne ”z metodami formalnymi.” (ze strony ICALP 1997)
Suresh Venkat
Ale strona z 1997 roku nie wydaje się używać etykiet „A” i „B” w odniesieniu do dwóch ścieżek.
Jukka Suomela,
nie, ale jasne jest, co to za intencja. a TCS miał chyba rozróżnienie A / B.
Suresh Venkat,
2
Powiązany punkt historyczny: TCS (C) był czasopismem z zakresu „naturalnego przetwarzania danych”, ale myślę, że temat ścieżki C ICALP zmieniał się każdego roku.
Aaron Sterling