In this paper we describe a new method for proving lower bounds on the complexity of VLSI - computations and more generally distributed computations. Lipton and Sedgewick observed that the crossing sequence arguments used to prove lower bounds in VLSI (or TM or distributed computing) apply to (accepting) nondeterministic computations as well as to deterministic computations. Hence whenever a boolean function f is such that f and -&-fmarc; (the complement of f, -&-fmarc; -&-equil; 1 -&-minus; f) have efficient nondeterministic chips then the known techniques are of no help for proving lower bounds on the complexity of deterministic chips. In this paper we describe a lower bound technique (Thm 1) which only applies to deterministic computations

AnSTV.ACT.A new class of generalized one-way stack automata, called s-pd machines, is mvestlgated The machines are obtained by augmenting a stack automaton with a pushdown store, whose bottom is attached to the top of the stack and whose top follows the movements of the stack-pointer into the stack.Motivations for the modal include a possible protocol for macro expansion with intermittent parameter evaluatton.The languages recogmzed by these machmes are characterized by a natural class of grammars, vlz, the 91ass of OI macro grammars with set-parameters and nonnested function calls (the "extended basic" or EB macro grammars) If the stack is required to be nonerasing or checking, then a useful machine characterizatton for the ETOL languages is obtained, together with the known characterization of this family by means of extended "linear" basic or [~LB macro grammars.It follows that the nonerasmg one-way stack languages are (strictly) included m ETOL.It is proved that the family of unrestricted one-way stack languages and ETOL are incomparable, as are the general OI macro languages and the yields of ranges of topdown tree transducers.It follows that ETOL is strictly included m the family of EB macro languages (which, m turn, is strxctly included in the famdy of indexed languages) Certain determuustic restrictions of s-pd machines lead to machine models for famlhes of nonextended macro languages, vlz, for Ftscher's original linear basic macro (i e, EDTOL) and basle macro languages.

There is no recursive function bounding the succinctness gained using ambiguous grammars rather than unambiguous ones in the description of unambiguous context-free languages.