Content area
We discuss a nondeterministic variant of the recently introduced machine model of deterministic auxiliary depth-\(k\) storage automata (or aux-\(k\)-sda's) by Yamakami. It was proven that all languages recognized by polynomial-time logarithmic-space aux-\(k\)-sda's are located between \(\mathrm{LOGDCFL}\) and \(\mathrm{SC}^k\) (the \(k\)th level of Steve's class SC). We further propose a new and simple computational model of semi-unbounded fan-in Boolean circuits composed partly of cascading blocks, in which the first few AND gates of unbounded fan-out (called AND\(_{(\omega)}\) gates) at each layer from the left (where all gates at each layer are indexed from left to right) are linked in a "cascading" manner to their right neighbors though specific AND and OR gates. We use this new circuit model to characterize a nondeterministic variant of the aux-\(2k\)-sda's (called aux-\(2k\)-sna's) that run in polynomial time using logarithmic work space. By relaxing the requirement for cascading circuits, we also demonstrate how such cascading circuit families characterize the complexity class \(\mathrm{P}\). This yields an upper bound on the computational complexity of \(\mathrm{LOG}k\mathrm{SNA}\) by \(\mathrm{P}\).