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.

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.