scientific article; zbMATH DE number 4007730
[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.
- Alternating multicounter machines with constant number of reversals
- Reversal-bounded nondeterministic multicounter machines and complementation
- Lower bounds for language recognition on two-dimensional alternating multihead machines
- Nondeterministic multicounter machines and complementation
- Reverse complexity
- GENERALIZED COUNTERS AND REVERSAL COMPLEXITY
- scientific article; zbMATH DE number 4005620 (Why is no real title available?)
- Reversal Complexity
- scientific article; zbMATH DE number 79114 (Why is no real title available?)
- scientific article; zbMATH DE number 512847 (Why is no real title available?)
- A note on real-time one-way alternating multicounter machines
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)