Function-algebraic characterizations of log and polylog parallel time
Could computational complexity classes be described without reference to Turing machines or other specific computation models? In 1965, Cobham gave a ``Yes'' answer for the class of polynomial-time computable functions. He showed that this class is the algebra generated from a few base functions by closure under composition and a form of recursion. In this paper, the author presents similar results for two parallel complexity classes.
scientific article; zbMATH DE number 627640