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.
Facts
Comparison
Era of Emergence Formal Languages and Automata Theory
Filter Results21 entries
Sources
1. Wikipedia: Automata theory
Wikimedia FoundationAutomata theory, History section, structure-theory sentenceQuote, Automata theory, History section, structure-theory sentence
In the 1960s, a body of algebraic results known as "structure theory" or "algebraic decomposition theory" emerged, which dealt with the realization of sequential machines from smaller machines by interconnection.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.