Asal dan aplikasi Teori A vs Teori B?

30

Dalam beberapa pertanyaan terakhir ( q1 q2 ), telah ada diskusi tentang "Teori A" vs "Teori B", yang tampaknya menangkap kesenjangan antara studi logika dan bahasa pemrograman dan studi tentang algoritma dan kompleksitas.

Terminologi ini baru bagi saya, dan pencarian web cepat tidak menghasilkan referensi yang jelas untuk menjelaskannya.

Adakah yang tahu tentang referensi atau referensi yang menjelaskan asal usul terminologi ini, dan apa, jika ada, manfaat substantif yang dimaksudkan berasal dari membuat perbedaan ini?

ho.history-overview terminology Marc Hamann
sumber
Di luar topik: Saya sarankan untuk mengedit tautan ke q1 & q2, dan menautkan ke "permalink" mereka. Dengan cara ini, bahkan jika judul pertanyaan diedit, tautan tetap valid.
MS Dousti
5
Judul diabaikan; cstheory.stackexchange.com/questions/944/foobar berfungsi dengan baik meskipun tidak sesuai dengan judul.
Jukka Suomela
1
Pertanyaan yang bagus, saya sendiri sudah bertanya-tanya. "Teori B" selalu tampak sedikit merendahkan!
Aaron Roth
5
@ Harun: Saya pikir itu lebih baik daripada memanggil PL "Eurotheory", seperti yang kadang-kadang dilakukan. Ini selalu mengejutkan saya sebagai hal yang sulit bagi para peneliti PL di AS atau Jepang, dan para ahli teori kompleksitas di Eropa. :)
Neel Krishnaswami
Moshe Vardi memiliki tinjauan singkat dengan beberapa referensi di posting blog ini. Mengapa ACM Tidak Memiliki SIG untuk Ilmu Komputer Teoritis? & mengaitkannya dengan kebangsaan; AS (lebih banyak teori A) vs penekanan Eropa (campuran)
vzn

Jawaban:

33

Itu berasal dari buku pegangan tentang ilmu komputer teoretis , yang memiliki dua volume: A adalah untuk algoritma dan kompleksitas, dan B adalah untuk logika dan semantik.

Jukka, apakah ICALP mendahului ini? Atau apakah itu menanggapi hal ini?

Adapun manfaat, saya pikir selalu ada beberapa utilitas dalam bidang taksonomi berdasarkan topik yang menarik, dan bentuk studi. Namun, seperti halnya semua taksonomi, masalah muncul ketika Anda lupa untuk "naik ke atas pohon dan turun ke sisi lain" :).

EDIT : seperti yang dinyatakan ICALP secara eksplisit, divisi ini berasal dari jurnal Elsevier Theoretical Computer Science , yang dengan sendirinya mendahului buku pegangan, jadi saya pikir itu sumber yang lebih akurat.

EDIT ++ : Dari sejarah EATCS, muncul cuplikan tentang TCS ini, jurnal:

Sejak saat itu M. Nivat, yang masih menjabat sebagai Pemimpin Redaksi telah melaporkan secara teratur kepada dewan dan majelis umum dan kadang-kadang dalam Buletin - misalnya ketika dipecah menjadi bagian A (automata, aljabar und algoritma) dan B (logika, semantik, dan topik terkait) diputuskan (Bulletin no. 45, hal.2,3, Oktober 1991);

yang menghasilkan 1991 seperti ketika ini pertama kali mulai terjadi di jurnal. Namun, Buku Pegangan ini pertama kali diterbitkan pada bulan September 1990!

Suresh Venkat
sumber
3
Tampaknya ICALP mengambil jejak mereka dari jurnal TCS pada tahun 1997 . Namun, referensi tertua untuk "track A" dan "track B" yang bisa saya temukan di halaman web mereka adalah dari tahun 1999 .
Jukka Suomela
1
ICALP 1997 adalah: "Yobel perak juga merupakan kesempatan untuk membentuk kembali format umum ICALP. Komite program mewakili dua lagu yang diketahui dari dua subseries jurnal Theoretical Computer Science dan mencakup algorithms' and metode formal yang setara." (dari halaman ICALP 1997)
Suresh Venkat
Tetapi halaman 1997 tampaknya tidak menggunakan label "A" dan "B" untuk merujuk ke dua lagu.
Jukka Suomela
tidak, tapi jelas apa tujuannya. dan TCS memiliki perbedaan A / B saya pikir.
Suresh Venkat
2
Poin historis terkait: TCS (C) adalah jurnal "komputasi alami", tetapi topik Track C ICALP telah berubah setiap tahun saya pikir.
Aaron Sterling
3

ICALP track A vs B.

Jukka Suomela
sumber