Combinatorial devices

Lifting a definition from Ward and Halstead's Computation Structures (ISBN 0-262-23139-5), pp4--5:

A combinatorial device is a circuit element have the following properties:

• One or more discrete-valued input terminals;
• One or more discrete-valued output terminals;
• A functional specification, detailing the value of each output for each of the possible combinations of input values; and
• A timing specification, consisting (at minimum) of an upper bound t_pd on the time required for the device to compute the specified output values from an arbitrary set of input values.

t_pd is known as the propagation delay of a device, and interpreted as a maximum time before outputs reflect the provided inputs (a minimum delay, if specified, is known as contamination delay). Thus, inputs provided and maintained for t seconds can be read for at least t - t_pd seconds. Combinatorial devices are closed under combinatorial composition:

A circuit is a combinatorial device if it consists of interconnected circuit elements such that:

• Each circuit element is itself combinatorial,
• Every node of the circuit is either designated as an input to the circuit or connects to exactly one output terminal of the circuit element, and
• The circuit contains no directed cycles.

Each output of a composed combinatorial device has its own t_pd, equal to the maxmium cumulative propagation delays encountered on any path from an input to that output.