Computational Complexity

Tuesday, March 11, 2003

 
Theory A and Theory B

Posted by Lance

Four speakers are chosen for the NVTI Theory Day along two axis: In and out of the Netherlands, and Theory A and Theory B. For example I was the non-Dutch Theory A speaker. But what is Theory A and B?

In 1994, the Handbook of Theoretical Computer Science was published as a two volume set each containing many survey articles that have for the most part stood the test of time. From the backcover: Volume A [Algorithms and Complexity] covers models of computation, complexity theory, data structure and efficient computation. Volume B [Formal Models and Semantics] presents material on automata and rewriting systems, foundations of programming languages, logics for program specification and verification and modeling of advanced information processing.

Over the years, Theory A and Theory B have come to represent the areas discussed in the corresponding volumes. In the US the term theoretical computer science covers areas mostly in Theory A. For example STOC and FOCS, the major US theory conferences, cover very little in Theory B. This is not to say Theory B is not done in this country; it is just labelled as logic or programming languages.

Outside the US there is a broader view of what is theory. The European ICALP conference covers both areas and has two submission tracks A and B that again correspond to Theory A and B.

Some countries, like Britain and France, focuses mostly on Theory B. Other countries, like the Netherlands and Germany have many groups in both areas.

Some Europeans are upset that their research is not considered theory by the Americans. Too bad.

12:47 PM # 0 comments

Comment Feeds: This Post All