# zbMATH — the first resource for mathematics

Nondeterministic programs definable in typed $$\lambda$$-calculus. (English) Zbl 0579.68022
Summary: In this paper term grammars are introduced. The expressive power of these grammars with variables of natural number type is just that of nondeterministic programs built up without composition but with iteration of extended polynomials.

##### MSC:
 68Q65 Abstract data types; algebraic specification 03B40 Combinatory logic and lambda calculus 68N01 General topics in the theory of software 68Q45 Formal languages and automata 68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
##### Keywords:
dynamic algebras; lambda calculus; term grammars