×
Hromkovič, Juraj

On the power of alternation in automata theory. (English) Zbl 0582.68018

J. Comput. Syst. Sci. 31, 28-39 (1985).
An extended abstract of this paper appeared in Lect. Notes Comput. Sci. 176, 322-329 (1984; Zbl 0571.68035).

Cited in 16 Documents

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity

Keywords:

one-way multicounter machines; blind counters; P; Turing machines; polynomial time; multihead finite automata

Citations:

Zbl 0571.68035
PDFBibTeX XMLCite
\textit{J. Hromkovič}, J. Comput. Syst. Sci. 31, 28--39 (1985; Zbl 0582.68018)
Full Text: DOI

References:

[1] Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, J. Assoc. Comput. Mach., 28, 114-133 (1981) · Zbl 0473.68043
[2] Greibach, S. A., Remarks on blind and partially blind one-way multicounter machines, Theoret. Comput. Sci., 7, 311-324 (1978) · Zbl 0389.68030
[3] Hromkovič, J., One-way multihead deterministic finite automata, Acta Inform., 19, 377-384 (1983) · Zbl 0504.68049
[4] Hromkovič, J., On the power of alternation in finite automata, (Proc. 11th MFCS ’84. Proc. 11th MFCS ’84, Lecture Notes in Comput. Sci., Vol. 176 (1984), Springer-Verlag: Springer-Verlag Berlin/Heidelberg/New York/Tokyo), 312-321 · Zbl 0571.68035
[5] Lander, R. E.; Lipton, R. J.; Stockmeyer, L. J., Alternating pushdown and stack automata, SIAM J. Comput., 13, 135-155 (1984) · Zbl 0538.68039
[6] King, K. N., Alternating multihead finite automata, (Proc. 8th ICALP’81. Proc. 8th ICALP’81, Lecture Notes in Comput. Sci., Vol. 115 (1981), Springer-Verlag: Springer-Verlag Berlin/Heidelberg/New York) · Zbl 0665.68064
[7] K.N. King, “Alternating Finite Automata,” Doctoral dissertation, University of California, Berkeley.; K.N. King, “Alternating Finite Automata,” Doctoral dissertation, University of California, Berkeley.
[8] Yao, A. C.; Rivest, R. L., \(K+1\) heads are better than K, J. Assoc. Comput. Mach., 25, 337-340 (1978) · Zbl 0372.68017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.