scientific article; zbMATH DE number 4007730

From MaRDI portal
Publication:3758246





[For the entire collection see Zbl 0604.00016.] The paper consists of two independent parts. The first one involves a negative answer to the open question of \textit{R. Wagner} and \textit{G. Wechsung} [Computational complexity (1986; Zbl 0584.68062)] whether the family of languages recognized by one-way real-time nondeterministic multicounter machines with constant number of counter reversals is closed under complementation. This unclosure property is proved for other bounds on counter reversals and time complexity, too. The second part is devoted to the study of lower bound techniques for a general model of alternating computations. The best known lower bound \(\Omega (n^{1/3}/\log_ 2n)\) on the complexity measure REVERSALS\(\cdot SPACE\cdot PARALLELISM\) of multihead alternating machines is improved to \(\Omega (n^{1/2}/\log_ 2n)\). Several strongest lower bounds for different complexity measures are direct consequences of this result.











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 Q3758246)