text: We investigate the power of non-determinism in purely functional programming languages with higher-order types. Specifically, we consider cons-free programs of varying data orders, equipped with explicit non-deterministic choice. Cons-freeness roughly means that data constructors cannot occur in function bodies and all manipulation of storage space thus has to happen indirectly using the call stack. While cons-free programs have previously been used by several au thors to characterise complexity classes, the work on non-deterministic programs has almost exclusively considered programs of data order 0. Previous work has shown that adding explicit non-determinism to cons-free programs taking data of order 0 does not increase expressivity; we prove that this - dramatically - is not the case for higher data orders: adding non-determinism to programs with data order at least 1 allows for a characterisation of the entire class of elementary-time decidable sets.
  @cite_7: 
  @cite_1: We propose two characterizations of complexity classes by means of programming languages. The first concerns Logspace while the second leads to Ptime. This latter characterization shows that adding a choice command to a Ptime language (the language WHILE of Jones [1]) may not necessarily provide NPtime computations. The result is close to Cook in [2] who used “auxiliary push-down automata”. Logspace is obtained through a decidable mechanism of tiering. It is based on an analysis of deforestation due to Wadler in [3]. We get also a characterization of NLogspace.
  @cite_6: Two restricted imperative programming languages are considered: One is a slight modification of a loop language studied intensively in the literature, the other is a stack programming language over an arbitrary but fixed alphabet, supporting a suitable loop concept over stacks. The paper presents a purely syntactical method for analysing the impact of nesting loops on the running time. This gives rise to a uniform measure µ on both loop and stack programs, that is, a function that assigns to each such program P a natural number µ(P) computable from the syntax of P.It is shown that stack programs of µ-measure n compute exactly those functions computed by a Turing machine whose running time lies in Grzegorczyk class en-2. In particular, stack programs of µ-measure 0 compute precisely the polynomial-time computable functions.Furthermore, it is shown that loop programs of µ-measure n compute exactly the functions in en-2. In particular, loop programs of µ-measure 0 compute precisely the linear-space computable functions.
  @cite_0: We investigate an imperative and a functional programming language. The computational power of fragments of these languages induce two hierarchies of complexity classes. Our first main theorem says that these hierarchies match, level by level, a complexity-theoretic alternating space-time hierarchy known from the literature. Our second main theorems says that a slightly different complexity-theoretic hierarchy (the Goerdt-Seidl hierarchy) also can be captured by hierarchies induced by fragments of the programming languages. Well known complexity classes like LOGSPACE, LINSPACE, P, PSPACE, etc., occur in the hierarchies.
  @cite_5: 
  @cite_10: 1 I n t r o d u c t i o n 1.1 B a c k g r o u n d Programming paradigms and related features of programming languages are subjects of continuing interest within the computer science community. While all general purpose programming languages provide Turing completeness, there are obvious differences with respect to ease of use and efficiency. One of the few results establishing such discrepancies in a precise sense is the recent separation of pure and impure (destructive) LISP programs by Pippenger [7], where the two language variants are separated with respect to efficiency. In the present work we consider a more restrictive setting of sub-recursive languages. Their study is mainly motivated by the observation that for such restricted languages, it is meaningful to compare language variants with respect to express ive power, regardless of efficiency. This kind of study has led in the past to fundamental results that characterize the expressive power of various types of automata, and show that important complexity classes can be captured by restricted languages.
  @cite_17: Compare first-order functional programs with higher-order programs allowing functions as function parameters. Can the the first program class solve fewer problems than the second? The answer is no: both classes are Turing complete, meaning that they can compute all partial recursive functions. In particular, higher-order values may be first-order simulated by use of the list constructor ‘cons’ to build function closures. This paper uses complexity theory to prove some expressivity results about small programming languages that are less than Turing complete. Complexity classes of decision problems are used to characterize the expressive power of functional programming language features. An example: second-order programs are more powerful than first-order, since a function f of type lBoolr-〉Bool is computable by a cons-free first-order functional program if and only if f is in PTIME, whereas f is computable by a cons-free second-order program if and only if f is in EXPTIME. Exact characterizations are given for those problems of type lBoolr-〉Bool solvable by programs with several combinations of operations on data: presence or absence of constructors; the order of data values: 0, 1, or higher; and program control structures: general recursion, tail recursion, primitive recursion.
summary: Cons-free programs, combined with various limitations on recursion, were introduced by Jones @cite_17 , building on ground-breaking work by Goerdt @cite_7 @cite_5 , and have been studied by a number of authors (see, e.g., @cite_10 @cite_1 @cite_0 @cite_6 ). The main difference with our work is that we consider full recursion with full non-determinism, but impose constraints not present in the previous literature.