From Implicit Complexity to Quantitative Resource Analysis Overview

(1)

From Implicit Complexity to Quantitative Resource Analysis

Overview

Ugo Dal Lago

PhD Open, University of Warsaw, June 25-27, 2015

(2)

About This Course

I Introduction to Implicit Computational Complexity.

I Approximately 5 hours.

I This slideset.

I Exercise sessions along the way.

I Complexity Analysis by Program Transformation.

I Approximately 1 hour.

I Bounded Linear Logic.

I Website: http://www.cs.unibo.it/~dallago/FICQRA/

I Email: [email protected]

I Please contact me whenever you want!

I Exam: there will be one one week after the end of the Tutorial

(3)

About This Course

I This slideset.

(4)

About This Course

I This slideset.

(5)

About This Course

I This slideset.

(6)

Implicit Computational Complexity

I Goal

I Machine-free characterizations of complexity classes.

I No explicit reference to resource bounds.

I P, PSPACE, L, NC,. . .

I Why?

I Simple and elegant presentations of complexity classes.

I Formal methods for complexity analysis of programs.

I How?

I First-order functional programs [BC92], [Leivant94], . . .

I Model theory [Fagin73], . . . ,

I Type Systems and λ-calculi [Hofmann97], [Girard97], . . .

I . . .

(7)

Implicit Computational Complexity

I Goal

I Why?

I How?

I . . .

(8)

Implicit Computational Complexity

I Goal

I Why?

I How?

I . . .

(9)

Part I

Implicit Complexity at a Glance

(10)

Characterizing Complexity Classes

L C

Programs Functions

(11)

Characterizing Complexity Classes

L C

J·K

Programs Functions

(12)

Characterizing Complexity Classes

L C

P

Programs Functions

(13)

Characterizing Complexity Classes

L C

S P

Programs Functions

(14)

Proving JSK = P

I P ⊆ JSK

I For every function f which can be computed within the bounds prescribed byP, there is P ∈ S such that JP K = f.

I JSK ⊆ P

I Semantically

I For every P ∈ S,JP K ∈ P is proved by showing that some algorithms computingJP K exists which works within the prescribed resource bounds.

I P ∈ L does not necessarily exhibit a nice computational behavior.

I Example: soundness by realizability [DLHofmann05].

I Operationally

I Sometimes, L can be endowed with an effective operational semantics.

I Let LP⊆ L be the set of those programs which work within the bounds prescribed by C.

I JS K ⊆ P can be shown by proving S ⊆ L^P.

(15)

Proving JSK = P

I P ⊆ JSK

I For every function f which can be computed within the bounds prescribed byP, there is P ∈ S such that JP K = f.

I JSK ⊆ P

I Semantically

I For every P ∈ S,JP K ∈ P is proved by showing that some algorithms computingJP K exists which works within the prescribed resource bounds.

I P ∈ L does not necessarily exhibit a nice computational behavior.

I Example: soundness by realizability [DLHofmann05].

I Operationally

I Sometimes, L can be endowed with an effective operational semantics.

I Let LP⊆ L be the set of those programs which work within the bounds prescribed by C.

I JS K ⊆ P can be shown by proving S ⊆ L^P.

(16)

If Soundness is Proved Operationally...

L L P

S

(17)

If Soundness is Proved Operationally...

L L P

S

(18)

ICC Systems as Static Analyzers

P ∈ L S

Don’t know

Yes, P ∈ LP

(19)

ICC Systems as Static Analyzers

P ∈ L S

Don’t know Yes, P ∈ LP

+ bounds

(20)

ICC: Intensional Expressive Power

L L P

S

(21)

ICC: Intensional Expressive Power

L L P

S

(22)

ICC: Intensional Expressive Power

L L P

S

(23)

ICC: Intensional Expressive Power

L L P

S

(24)

ICC: Intensional Expressive Power

L L P

S

(25)

ICC: Intensional Expressive Power

L L P

S

Safe Recursion [BC92]

Light Linear Logic [Girard97]

...

(26)

ICC: Intensional Expressive Power

L L P

S

Bounded Recursion on Notation [Cobham63]

Bounded Arithmetic [Buss80]

...

(27)

Program Logics

Degree of Completeness

Prop ert y Co mplexit y

(28)

ICC Systems

Degree of Completeness

Prop ert y Co mplexit y

(29)

ICC Systems

Degree of Completeness

Prop ert y Co mplexit y

(30)

ICC Systems

Degree of Completeness

Prop ert y Co mplexit y

(31)

Part II

Playing with Computational Models

as Languages

(32)

Preliminaries

I Alphabet: a finite nonempty set, denoted with meta-variables likeΣ, Υ, Φ.

I String over an alphabet Σ: a finite, ordered, possibly empty sequence of symbols fromΣ. The Kleene’s closure Σ^∗ ofΣ is the set of all words over Σ, including the empty word ε.

I Language over the alphabetΣ: a subset of Σ^∗.

(33)

Preliminaries

I One way of defining a language L is by saying that L is the smallest set satisfying some closure conditions, formulated as a set of productions.

I Example: the language P of palindrome words over the alphabet {a, b} can be defined as follows

W ::= ε| a | b | aW a | bW b.

I Example: the language N of all sequences in {0, . . . , 9}^∗ denoting natural numbers. It will be ranged over by meta-variables like N, M . Given N , JNK ∈ N is the natural number denoted by N .

I Example: the language B of all binary strings, namely {0, 1}^∗.

(34)

Preliminaries

I One way of defining a language L is by saying that L is the smallest set satisfying some closure conditions, formulated as a set of productions.

I Example: the language P of palindrome words over the alphabet {a, b} can be defined as follows

W ::= ε| a | b | aW a | bW b.

I Example: the language N of all sequences in {0, . . . , 9}^∗ denoting natural numbers. It will be ranged over by meta-variables like N, M . Given N , JNK ∈ N is the natural number denoted by N .

I Example: the language B of all binary strings, namely {0, 1}^∗.

(35)

Counter Machines

I Counter Programs:

P ::= I| I,P

I ::= inc(N )| jmpz(N,N)

where N ranges over N and thus stands for any natural number in decimal notation, e.g. 12, 0, 67123.

I Example:

jmpz(0,4),inc(1),jmpz(2,1)

(36)

Counter Machines

I Counter Programs:

P ::= I| I,P

I ::= inc(N )| jmpz(N,N)

where N ranges over N and thus stands for any natural number in decimal notation, e.g. 12, 0, 67123.

I Example:

jmpz(0,4),inc(1),jmpz(2,1)

(37)

Counter Programs

I Instructions modify the content of some registers R₀, R₁, . . ., each containing a natural number.

I Formally:

I The instruction inc(N ) increments by one the content of R_n (where n=JNK is the natural number denoted by N).

The next instruction to be executed is the following one in the program.

I The instruction jmpz(N ,M ) determines the content n of RJN K and

I If n is positive, decrements R_{JN K}by one; the next instruction is the following one in the program.

I If it is zero, the next instruction to be executed is the JM K-th in the program.

I Whenever the next instruction to be executed cannot be determined following the two rules above, the execution of the program terminates.

(38)

Counter Programs

I Instructions modify the content of some registers R₀, R₁, . . ., each containing a natural number.

I Formally:

I The instruction inc(N ) increments by one the content of R_n (where n=JNK is the natural number denoted by N).

The next instruction to be executed is the following one in the program.

I The instruction jmpz(N ,M ) determines the content n of RJN K and

I If n is positive, decrements R_{JN K}by one; the next instruction is the following one in the program.

I If it is zero, the next instruction to be executed is the JM K-th in the program.

I Whenever the next instruction to be executed cannot be determined following the two rules above, the execution of the program terminates.

(39)

Counter Programs — Example

jmpz(0,4), inc(1), jmpz(2,1)

Current Instruction R₀ R₁ R₂

jmpz(0,4) 4 0 0

inc(1) 3 0 0

jmpz(2,1) 3 1 0

jmpz(0,4) 3 1 0

inc(1) 2 1 0

jmpz(2,1) 2 2 0

jmpz(0,4) 2 2 0

inc(1) 1 2 0

jmpz(2,1) 1 3 0

jmpz(0,4) 1 3 0

inc(1) 0 3 0

jmpz(2,1) 0 4 0

jmpz(0,4) 0 4 0

(40)

Turing Programs

I Turing Programs:

P ::= I| I,P

I ::= (N ,c) > (N ,a)| (N,c) > stop

where c ranges over the input alphabet Σ which includes a special symbol (called the blank symbol), and a ranges over the alphabet alphabet Σ∪ {<, >}.

(41)

Turing Programs

I Intuitively, an instruction (N ,c) > (M ,a) tells the machine to move to state M when the symbol under the head is c and the current state is N :

I If a is inΣ, than the symbol under the head is changed to a;

I If a is <, then the symbol c is left unchanged but the head moves one position leftward.

I Similarly when a is >.

I The instruction (N ,c) > stop tells the machine to simply stop whenever in state N and faced with the symbol c.

I The state of the program is composed of a state and of the state of the tape.

(42)

Turing Programs — Example

I A (deterministic) Turing program on {0, 1}, called R:

(0,) > (1,>), (1,0) > (2,1), (1,1) > (2,0), (2,0) > (1,>), (2,1) > (1,>), (1,) > stop

I Execution:

(ε, , 010, 0)−→ (, 0, 10, 1)^R −→ (, 1, 10, 2)^R

−→ (1, 1, 0, 1)R −→ (1, 0, 0, 2)^R

−→ (10, 0, ε, 1)R −→ (10, 1, ε, 2)^R

−→ (101, , ε, 1).R

(43)

Turing Programs — Example

I A (deterministic) Turing program on {0, 1}, called R:

(0,) > (1,>), (1,0) > (2,1), (1,1) > (2,0), (2,0) > (1,>), (2,1) > (1,>), (1,) > stop

I Execution:

(ε, , 010, 0)−→ (, 0, 10, 1)^R −→ (, 1, 10, 2)^R

−→ (1, 1, 0, 1)R −→ (1, 0, 0, 2)^R

−→ (10, 0, ε, 1)R −→ (10, 1, ε, 2)^R

−→ (101, , ε, 1).R

(44)

Function Algebras

I Another, different, way to capture computation is as follows:

I Start from a set of basic functions. . .

I . . . and close it under some operators.

I The set of recursive functions is the smallest set of functions which contains the basic functions and which is closed with respect to the operators.

I Where are the programs?

I They are proofs of recursivity, which are finitary.

I They support an induction principle.

(45)

Function Algebras

(46)

Function Algebras

(47)

Function Algebras — Basic Functions

I Zero. The function z: N→ N defined as follows: z(n) = 0 for every n∈ N.

I Successor. The function s: N→ N defined as follows:

s(n) = n + 1 for every n∈ N.

I Projections. For every positive n∈ N and for whenever 1≤ m ≤ n, the function Πⁿm : Nⁿ→ N is defined as follows:

Πⁿ_m(k₁, . . . , k_n) = k_m.

(48)

Function Algebras — Operations (I)

I Composition. Suppose that n∈ N is positive, that f : Nⁿ→ N and that gm : N^k→ N for every 1 ≤ m ≤ n.

Then the composition of f and g₁, . . . , gn is the function h: N^k→ N defined as h(~i) = f(g1(~i), . . . , g_n(~i)).

I Primitive Recursion. Suppose that n∈ N is positive, that f : Nⁿ→ N and that g : Nⁿ⁺²→ N. Then the function h: Nⁿ⁺¹→ N defined as follows

h(0, ~m) = f ( ~m);

h(k + 1, ~m) = g(k, ~m, h(k, ~m));

is said to be defined by primitive recursion form f and g.

(49)

Function Algebras — Operations (II)

I Minimization. Suppose that n∈ N is positive and that f : Nⁿ⁺¹ * N. Then the function g : Nⁿ* N defined as follows:

g(m,~i) =







k if f(0,~i), . . . , f (k,~i) are all defined

and f(k,~i) is the only one in the list being 0.

↑ otherwise

is said to be defined by minimization from f .

(50)

Functional Programs — Preliminaries

I Signature. It is a pairS = (Σ, α) where:

I Σ is an alphabet;

I α: Σ→ N assigns to any symbol c in Σ a natural number α(c), called its arity.

I Examples.

I The signatureSNdefined as({0, s}, αN) where α_N(0) = 0 and α_N(s) = 1.

I The signatureSBdefined as({0, 1, e}, αB) where α_B(0) = α_B(1) = 1 and α_B(e) = 0.

I Given two signatures S and T such that the underlying set of symbols are disjoint, one can naturally form the sum S + T .

(51)

Functional Programs

I Closed Terms. Given a signatureS = (Σ, α), they are the smallest set of expressions C(S) satisfying the following closure property: if f∈ Σ and t1, . . . , t_α(f)∈ C(S), then f(t₁, . . . , t_α(f))∈ C(S).

I Examples.

C(SN) ={0, s(0), s(s(0)), . . .};

C(SB) ={e, 0(e), 1(e), 0(0(e)), . . .}.

I Open Terms. Given a set of variables L distinct from Σ, the set of open termsO(S, L) is defined as the smallest set of words including L and satisfying the closure condition above.

(52)

Functional Programs

I Functional Programs on S = (Σ, α) and T = (Υ, β):

P ::= R| R,P R::= l -> t

l::= f₁(p¹₁, . . . ,p^α(f₁ ¹⁾)| . . . | fn(p¹_n, . . . ,p^α(f_n ⁿ⁾) where:

I Σ ={f¹. . . , f_n} and that Υ is disjoint from Σ.

I the metavariables p^k_mrange overO(T , L),

I t ranges overO(S + T , L).

(53)

Functional Programs

I Example:

add(0, x) -> x

add(s(x), y) -> s(add(x, y)).

I The evaluation of add(s(s(0)), s(s(s(0)))) goes as follows:

add(s(s(0)), s(s(s(0))))→ s(add(s(0), s(s(s(0)))))

→ s(s(add(0, s(s(s(0))))))

→ s(s(s(s(s(0))))).

(54)

λ-Calculus

I Terms:

M ::= x| λx.M | MM,

I The term obtained by substituting a term M for a variable x into another term N is denoted as N{M/x}.

I Values:

V ::= x| λx.M.

I Reduction:

(λx.M )V →^v M{V/x}

M →v N M L→^v N L

M →v N LM →^v LN Here M ranges over terms, while V ranges over values.

I Normal Forms. Any term M such that there is not any N with M →^v N . A term M has a normal form iff M →^∗v N . Otherwise, we write M ↑.

(55)

λ-Calculus — Computing on N

I Scott’s Numerals.

p0q = λx.λy.x;

pn + 1q = λx.λy.ypnq.

I Representing Functions. A λ-term M represents a function f : N * N iff for every n, if f(n) is defined and equals m, then Mpnq→^∗v pmq and otherwise M pnq↑

(56)

Computability

I For the five introduced computational models, one can define the class of functions from N to N they compute.

I Unsurprisingly, they are all the same: the five models are all Turing-powerful.

I This means, in particular, that programs in the five formalisms can be, in general, very inefficient.

I They can compute whatever (computable) function one can imagine, after all!

(57)

Efficiency

I Programs consume resources (time, space, communication, energy).

I How could one formalize the concept of being efficient with respect to a given resource?

I A Measure

I One can assign to any program P a un upper bound on the amount of resources (of a certain kind) P needs when executed.

I Can be either precise or asymptotic.

I The more precise, the more architecture-dependent.

I A Predicate

I The amount of resources P needs when executed is bounded by a function in a “robust” class. Examples:

I Polynomial Functions.

I Logarithmic Functions.

I Elementary Functions.

I We are mimicking complexity classes!

I If the predicate holds, extracting concrete asymptotic bounds is within reach.

(58)

Cost Models

I Let us focus our attention to time complexity.

I How do we measure the amount of time a computation takes in the five models we described?

I Counter Programs: number of steps.

I Turing Programs: number of steps.

I Functional Programs: number of reduction steps?

I λ-Calculus: number of reduction steps?

I Function Algebra: ?

I Invariance Thesis [SvEB1980]: a cost model is reasonable iff the class of polytime computable functions is the same as the one defined with Turing programs.

I The most interesting cost models are, clearly, the unitary ones. They are not always invariant by definition, however.

(59)

Cost Models

(60)

Cost Models

(61)

Cost Models

(62)

Cost Models

(63)

Cost Models

(64)

Cost Models

(65)

Complexity Classes

(66)

Complexity Classes

(67)

The Complexity’s Complexity

I Checking the resource consumption of a program P to be bounded by a function in a robust class is hard.

I The set of all polytime programs is invariably Σ₂-complete!

I This does not mean that there cannot be any decidable set of programsS such that JSK coincides with the class of polytime functions.

(68)

The Complexity’s Complexity

I Checking the resource consumption of a program P to be bounded by a function in a robust class is hard.

I The set of all polytime programs is invariably Σ₂-complete!

I This does not mean that there cannot be any decidable set of programsS such that JSK coincides with the class of polytime functions.

(69)

Exercises

I Prove that the class of functional programs over SN is Turing powerful.

I Prove that the set of functions which can be respresented in the λ-calculus is Turing powerful.

I Prove that the class of polytime Turing programs is Σ2-complete.

I Is the unitary cost model invariant in functional programs?

I Is it possible to define a functional program that produces an exponentially long output?

I Is the unitary cost model invariant in the λ-calculus?

I Try to play the same game as before.

(70)

Exercises

(71)

Exercises

(72)

Exercises

(73)

Part III

Implicit Complexity in Function

Algebras

(74)

Complexity Classes as Function Algebras?

I Recursion on Notation: since computation in unary notation is inefficient, we need to switch to binary notation.

I What Should we Keep in the Algebra?

I Basic functions are innoquous.

I Polytime functions are closed by composition.

I Minimization introduces partiality, and is not needed.

I Primitive Recursion?

I Certain uses of primitive recursion are dangerous, but if we do not have any form of recursion, we capture much less than polytime functions.

(75)

Complexity Classes as Function Algebras?

(76)

Complexity Classes as Function Algebras?

(77)

Safe Functions

I Safe Functions: pairs in the form (f, n), where f :B^m→ B and 0 ≤ n ≤ m.

I The number n identifies the number of normal arguments between those of f : they are the first n, while the other m− n are the safe arguments.

I Following [BellantoniCook93], we use semicolons to separate normal and safe arguments: if (f, n) is a safe function, we write f( ~W; ~V) to emphasize that the n words in ~W are the normal arguments, while the ones in ~V are the safe arguments.

(78)

Basic Safe Functions

I The safe function (e, 0) where e :B → B always returns the empty string ε.

I The safe function (a0,0) where a0:B → B is defined as follows: a₀(W ) = 0· W .

I The safe function (a1,0) where a1:B → B is defined as follows: a₁(W ) = 1· W .

I The safe function (t, 0) where t :B → B is defined as follows: t(ε) = ε, t(0W ) = W and t(1W ) = W .

I The safe function (c, 0) where c :B⁴ → B is defined as follows: c(ε, W, V, Y ) = W , c(0X, W, V, Y ) = V and c(1X, W, V, Y ) = Y .

I For every positive n∈ N and for whenever 1 ≤ m, k ≤ n, the safe function(Πⁿ_m, k), where Πⁿ_m is defined in a natural way.

(79)

Safe Composition

(f : B

ⁿ

→ B, m)

(g

j

: B

^k

→ B, k) for every 1 ≤ j ≤ m (h

j

: B

^k+i

→ B, k) for every m + 1 ≤ j ≤ n

⇓

(p : B

^k+i

→ B, k) defined as follows:

p( ~W; ~V) = f (g1( ~W; ), . . . , gm( ~W; ); hm+1( ~W; ~V), . . . , hn( ~W; ~V)).

(80)

Safe Composition

(f : B

ⁿ

→ B, m)

(g

j

: B

^k

→ B, k) for every 1 ≤ j ≤ m (h

j

: B

^k+i

→ B, k) for every m + 1 ≤ j ≤ n

⇓

(p : B

^k+i

→ B, k) defined as follows:

(81)

Safe Composition

(f : B

ⁿ

→ B, m)

(g

j

: B

^k

→ B, k) for every 1 ≤ j ≤ m (h

j

: B

^k+i

→ B, k) for every m + 1 ≤ j ≤ n

⇓

(p : B

^k+i

→ B, k) defined as follows:

(82)

Safe Composition

(f : B

ⁿ

→ B, m)

(g

j

: B

^k

→ B, k) for every 1 ≤ j ≤ m (h

j

: B

^k+i

→ B, k) for every m + 1 ≤ j ≤ n

⇓

(p : B

^k+i

→ B, k) defined as follows:

(83)

Safe Composition

(f : B

ⁿ

→ B, m)

(g

j

: B

^k

→ B, k) for every 1 ≤ j ≤ m (h

j

: B

^k+i

→ B, k) for every m + 1 ≤ j ≤ n

⇓

(p : B

^k+i

→ B, k) defined as follows:

(84)

(Simultaneous) Safe Recursion

(fⁱ :Bⁿ→ B, m) for every 1 ≤ i ≤ j

(gⁱ_k:B^n+j+2→ B, m + 1) for every 1 ≤ i ≤ j, k ∈ {0, 1}

⇓

(hⁱ :Bⁿ⁺¹→ B, m + 1) defined as follows:

hⁱ(0, ~W; ~V) = f ( ~W; ~V);

hⁱ(0X, ~W; ~V) = g₀ⁱ(X, ~W; ~V , h¹(X, ~W; ~V), . . . , h^j(X, ~W; ~V));

hⁱ(1X, ~W; ~V) = g₁ⁱ(X, ~W; ~V , h¹(X, ~W; ~V), . . . , h^j(X, ~W; ~V));

(85)

(Simultaneous) Safe Recursion

⇓

hⁱ(0, ~W; ~V) = f ( ~W; ~V);

(86)

(Simultaneous) Safe Recursion

⇓

hⁱ(0, ~W; ~V) = f ( ~W; ~V);

(87)

Classes of Functions

I BCS is the smallest class of safe functions which includes the basic safe functions above and which is closed by safe composition and safe recursion.

I BC is the set of those functions f :B → B such that (f, n)∈ BCS for some n ∈ {0, 1}.

(88)

Lemma (Max-Poly Lemma)

For every (f :Bⁿ→ B, m) in BCS, there is a monotonically increasing polynomial p_f : N→ N such that:

|f(V1, . . . , Vn)| ≤ pf



 X

1≤k≤m

|Vk|



+ max

m+1≤k≤n|Vk|.

Proof.

I An induction on the structure of the proof a function being in BCS.

I The restrictions safe recursion must satisfy are essential.

(89)

Lemma (Max-Poly Lemma)

For every (f :Bⁿ→ B, m) in BCS, there is a monotonically increasing polynomial p_f : N→ N such that:

|f(V1, . . . , Vn)| ≤ pf



 X

1≤k≤m

|Vk|



+ max

m+1≤k≤n|Vk|.

Proof.

I An induction on the structure of the proof a function being in BCS.

I The restrictions safe recursion must satisfy are essential.

(90)

Theorem (Polytime Soundness) BC⊆ FP{0,1}.

Proof.

I This is an induction on the structure of the proof of a function being in BCS.

I The proof becomes much easier if we first prove that simultaneous primitive recursion can be encoded into ordinary primitive recursion.

I We make essential use of the Max-Poly Lemma.

(91)

Theorem (Polytime Soundness) BC⊆ FP{0,1}.

Proof.

I This is an induction on the structure of the proof of a function being in BCS.

I The proof becomes much easier if we first prove that simultaneous primitive recursion can be encoded into ordinary primitive recursion.

I We make essential use of the Max-Poly Lemma.

(92)

Lemma (Polynomials)

For every polynomial p: N→ N with natural coefficients there is a safe function (f, 1) where f :B → B such that

|f(W )| = p(|W |) for every W ∈ B.

Theorem (Polytime Completeness) FP_{0,1} ⊆ BC.

Theorem (BellantoniCook1992) FP_{0,1} = BC.

(93)

Lemma (Polynomials)

(94)

Lemma (Polynomials)

(95)

Complexity Classes

(96)

Part IV

Implicit Complexity in Functional

Programs

(97)

Which Cost Model?

I Is it sensible to take the number of reduction steps as a measure of the execution time of a functional program P ?

I Apparently, the answer is negative.

I Consider

f(0) -> nil

f(s(x)) -> bin(f(x), f(x)).

I We need to exploit sharing!

I Can we perform rewriting on shared representations of terms?

I Does all this introduce an unacceptable overhead?

Theorem (DLMartini2009)

The unitary cost model is invariant.

(98)

Which Cost Model?

I Consider

f(0) -> nil

f(s(x)) -> bin(f(x), f(x)).

(99)

Which Cost Model?

I Consider

f(0) -> nil

f(s(x)) -> bin(f(x), f(x)).

(100)

Which Cost Model?

I Consider

f(0) -> nil

f(s(x)) -> bin(f(x), f(x)).

(101)

The Interpretation Method

I Domain: a well-founded partial order(D, ≤).

I Assignment A for a signature S = (Σ, α): to every symbol f inΣ, one puts in correspondence a function

[f]A :D^α(f)→ D

which is strictly increasing in any of its argument w.r.t. ≤.

I Given an assignment A, one can generalize it to a map on closed and open terms.

I Interpretation for a functional program P : an assignment such that for every rule l -> t, it holds that

[l]A >[t]A

Theorem (Lankford1979)

A functional program P is terminating iff there is one interpretation for it.

(102)

Polynomial Interpretations

I What if we choose N as the underlying domain, and polynomials on the natural numbers as the functions intepreting them?

I Do we get a characterization of polynomial time computable functions?

I Not really!

I Suppose that f is a unary function symbol, and that t is a closed term in, say,C(SB).

I If f(t)→ⁿ s, then n≤ [f(t)]A= [f]_A([t]_A)

I But[t]_A can be much bigger than|t|.

I Everything depends on the way you interpret data!

I You need to restrict to polynomial interpretations in which data are interpreted additively, e.g.