×

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)
PDF BibTeX XML Cite