scientific article; zbMATH DE number 18628
[For the entire collection see Zbl 0731.00026.] This paper is a short version of a detailed forthcoming article of the same authors. A language \(L\) belongs to NSPACE-AMBIGUITY\([s(n),a(n)]\) if \(L\) is acceptable by a nondeterministic \(s(n)\) space-bounded Turing machine the computation trees of which have \(\leq a(n)\) computation paths leading from the start configuration to any configuration that appears in the trees. The constructability of a function will be understood as in \textit{J. Balcázar}, \textit{J. Díaz}, and \textit{J. Gabarró} [Structural complexity, I. Springer-Verlag (1988; Zbl 0638.68040)]. The authors describe, in short, a new technique based on \textit{N. Immerman} [SIAM Comput. 17(5), 935-938 (1988; Zbl 0668.68056)] and \textit{R. Szelepcsényi} [Acta Inf. 26(3), 279-284 (1988; Zbl 0649.68055)]. The authors show that for all functions \(s(n)\) and \(a(n)\) if \(a(n)\) is constructible so that \(a(n)=O(2^{s(n)})\) and \(s(n)\geq\log(n)\), then NSPACE-AMBIGUITY\([s(n),a(n)]\) is contained in the class of languages accepted by \(s(n)\) a space bounded unique Turing machine.
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976031)
