Formal Languages and Automata Theory

This group gathers pioneers of theory of computation whose primary contribution was formal languages and automata theory, including finite automata, context-free grammars and parsing, Turing machines and computability, the Church-Turing thesis, recursive function theory, decidability and the halting problem, and the closely related theory of concurrent computation such as Petri nets, trace theory and process calculi that describe the non-sequential behavior of communicating systems. It follows the Formal languages and automata theory second-level heading of the ACM Computing Classification System under Theory of Computation. Their shared work is defining what a machine or grammar can express or decide at all, as distinct from how efficiently a solvable problem can be computed, which belongs to Algorithm Design and Analysis.