Last week, I saw a post on embedding automata in a surface to measure its complexity. When discussing with tcs friends, we both believe formal languages may belong to the other side. Then, more interesting questions arose: what belongs to the theory of computer science, and, am I doing theory?

I know theoretical computer science(TCS) is occupied by some scientists. They study algorithms, computational complexity, coding theory, and cryptography, etc. Sometimes, I have to say I am doing theoretical topics when chatting with system guys.

I found these classifications for computer sciences.

1. Computer Science Subject Areas and Moderators at arXiv.org Computing Research Repository (CoRR)
2. ACM Computing Classification System ToC and the latest 2012 system. (the plain HTML version)
3. Computing Curricula by ACM and IEEE, and the latest 2013 version for Computer Science.

So, what do they say?

λ. 1. arXiv classification

The arXiv classification is based on the 1998 ACM classification with moderations. For example,

PL - Programming Languages - Gopalan Nadathur

Covers programming language semantics, language features, programming approaches (such as object-oriented programming, functional programming, logic programming). Also includes material on compilers oriented towards programming languages; other material on compilers may be more appropriate in Architecture (AR). Roughly includes material in ACM Subject Classes D.1 and D.3.

FL - Formal Languages and Automata Theory - Michael Domaratzki

Covers automata theory, formal language theory, grammars, and combinatorics on words. This roughly corresponds to ACM Subject Classes F.1.1, and F.4.3. Papers dealing with computational complexity should go to cs.CC; papers dealing with logic should go to cs.LO. Papers that simply make use of automata, transducers, grammars, and so on, are not appropriate unless the automata, transducers, or grammars are the main subjects of study.

LO - Logic in Computer Science - Gopalan Nadathur

Covers all aspects of logic in computer science, including finite model theory, logics of programs, modal logic, and program verification. Programming language semantics should have Programming Languages as the primary subject area. Roughly includes material in ACM Subject Classes D.2.4, F.3.1, F.4.0, F.4.1, and F.4.2; some material in F.4.3 (formal languages) may also be appropriate here, although Computational Complexity is typically the more appropriate subject area.

CC - Computational Complexity - Christopher Umans

Covers models of computation, complexity classes, structural complexity, complexity tradeoffs, upper and lower bounds. Roughly includes material in ACM Subject Classes F.1 (computation by abstract devices), F.2.3 (tradeoffs among complexity measures), and F.4.3 (formal languages), although some material in formal languages may be more appropriate for Logic in Computer Science. Some material in F.2.1 and F.2.2, may also be appropriate here, but is more likely to have Data Structures and Algorithms as the primary subject area.

Formal languages are in their own right. They don’t belong to Programming Languages. Both FL and PL intersect with Logic. Some F.4.3 (formal languages) are in CC, i.e, they are TCS.

λ. 2. The 2012 ACM Computing Classification System

The 2012 ACM Computing Classification System has been developed as a poly-hierarchical ontology that can be utilized in semantic web applications. It replaces the traditional 1998 version of the ACM Computing Classification System (CCS), which has served as the de facto standard classification system for the computing field. It is being integrated into the search capabilities and visual topic displays of the ACM Digital Library.

Under CCS/Theory of computation, it has:

Formal languages and automata theory

• Formalisms
• – Algebraic language theory
• – Rewrite systems
• Automata over infinite objects
• Grammars and context-free languages
• Tree languages
• Automata extensions
• – Transducers
• – Quantitative automata
• Regular languages

Logic

• Logic and verification
• Proof theory
• Modal and temporal logics
• Automated reasoning
• Constraint and logic programming
• Constructive mathematics
• Description logics
• Equational logic and rewriting
• Finite Model Theory
• Higher order logic
• Linear logic
• Programming logic
• Abstraction
• Verification by model checking
• Type theory
• Hoare logic
• Separation logic

As for programming languages, under CCS/Software and its engineering, General programming languages contains language types and Language features. Under CCS/Theory of computation, Semantics and reasoning has Program constructs, Program semantics, Program reasoning.

Program semantics

• Algebraic semantics
• Denotational semantics
• Operational semantics
• Axiomatic semantics
• Action semantics
• Categorical semantics

Program reasoning

• Invariants
• Program specifications
• Pre- and post-conditions
• Program verification
• Program analysis
• Assertions
• Parsing
• Abstraction

λ. 3. Computer Science Curricula 2013

Curricula sometimes work as a conceptual impression to understand an area. The 2013 report has a Knowledge Areas section which lists 18 topics of study in computing:

• AL - Algorithms and Complexity
• AR - Architecture and Organization
• CN - Computational Science
• DS - Discrete Structures
• GV - Graphics and Visualization
• HCI - Human-Computer Interaction
• IAS - Information Assurance and Security
• IM - Information Management
• IS - Intelligent Systems
• NC - Networking and Communications
• OS - Operating Systems
• PBD - Platform-based Development
• PD - Parallel and Distributed Computing
• PL - Programming Languages
• SDF - Software Development Fundamentals
• SE - Software Engineering
• SF - Systems Fundamentals
• SP - Social Issues and Professional Practice

Programming Languages here also contain general programming languages and the theoretical content in it. Formal languages can be in AL or DS. Logic is in DS while Logic Programming is in PL.

λ. Conclusion

Am I doing theory? Yes.

Do Formal Languages belong to Programming Languages or Theoretical Computer Science? Probably not. They belong to themselves.