1983/01/01 by Neil Immerman · 1 citation
Computer Science · #semigroups and automata theory #Computability, Logic, AI Algorithms #Logic, programming, and type systems
paper · doi:10.1145/800061.808765
openalex publication_date 1983/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We present in this paper a series of languages adequate for expressing exactly those properties checkable in a series of computational complexity classes. For example, we show that a graph property is in polynomial time if and only if it is expressible in the language of first order graph theory together with a least fixed point operator. As another example, a group theoretic property is in the logspace hierarchy if and only if it is expressible in the language of first order group theory together with a transitive closure operator.