×
Matsuno, Hiroshi; Inoue, Katsushi; Taniguchi, Hiroshi; Takanami, Itsuo

Alternating simple multihead finite automata. (English) Zbl 0565.68055

Theor. Comput. Sci. 36, 291-308 (1985).
This paper introduces the alternating simple multihead finite automaton (ASPMHFA), which can be considered as an alternating version of a simple multihead finite automaton (SPMHFA). We first show that ASPMHFA’s are equivalent to ordinary alternating multihead finite automata. We investigate a relationship among the accepting powers of SPMHFA’s, ASPMHFA’s, and ASPMHFA’s with only universal states. We next introduce a simple, natural complexity measure for ASPMHFA’s, called ’leaf-size’, and provide a spectrum of complexity classes of ASPMHFA’s, based on simultaneously leaf-size, the number of heads, and the move directions of heads. We finally investigate closure properties (under Boolean operations) of ASPMHFA’s.

Cited in 5 Documents

MSC:

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

Keywords:

accepting powers; complexity measure; complexity classes; closure properties
PDFBibTeX XMLCite
\textit{H. Matsuno} et al., Theor. Comput. Sci. 36, 291--308 (1985; Zbl 0565.68055)
Full Text: DOI

References:

[1] Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, J. ACM, 28, 114-133 (1981) · Zbl 0473.68043
[2] Ďuriš, P.; Hromkovič, J., One-way simple multihead finite automata are not closed under concatenation, Theoret. Comput. Sci., 27, 121-125 (1983) · Zbl 0523.68070
[3] Gurari, E. M.; Ibarra, O. H., (Semi) Alternating stack automata, Math. Systems Theory, 15, 211-224 (1982) · Zbl 0495.68075
[4] Harrison, M. A.; Ibarra, O. H., Multi-tape and multi-head pushdown automata, Information and Control, 13, 433-470 (1968) · Zbl 0174.02701
[5] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[6] Ibarra, O. H., On two-way multihead automata, J. Comput. System Sci., 7, 28-36 (1973) · Zbl 0256.68028
[7] Ibarra, O. H.; Kim, C. E., A useful device for showing the solvability of some decision problems, J. Comput. System Sci., 13, 153-160 (1976) · Zbl 0338.68046
[8] Ibarra, O. H.; Sahni, S. K.; Kim, C. E., Finite automata with multiplication, Theoret. Comput. Sci., 2, 271-294 (1976) · Zbl 0345.68029
[9] Inoue, K.; Takanami, I.; Nakamura, A.; Ae, T., One-way simple multihead finite automata, Theoret. Comput. Sci., 9, 311-328 (1979) · Zbl 0408.68050
[10] Inoue, K.; Takanami, I.; Taniguchi, H., Two-dimensional alternating Turing machines, Theoret. Comput. Sci., 27, 61-83 (1983) · Zbl 0539.68039
[11] Inoue, K.; Taniguchi, H.; Takanami, I., Semi-one-way simple multihead finite automata, Trans. IECE of Japan, J63-D, 25-32 (1980)
[12] King, K. N., Measures of parallelism in alternating computation trees, (Proc. 13th Ann. ACM Symp. on Theory of Computing (1981)), 189-201
[13] King, K. N., Alternating multihead finite automata, (Automata, Languages and Programming, 8th Colloquium. Automata, Languages and Programming, 8th Colloquium, 1981. Automata, Languages and Programming, 8th Colloquium. Automata, Languages and Programming, 8th Colloquium, 1981, Lecture Notes in Computer Science, 115 (1981), Springer: Springer Berlin), 506-520 · Zbl 0665.68064
[14] Ladner, R. E.; Lipton, R. J.; Stockmeyer, L. J., Alternating pushdown automata, (Conf. Rec. IEEE 19th Ann. Symp. on Foundations of Computer Science. Conf. Rec. IEEE 19th Ann. Symp. on Foundations of Computer Science, Ann Arbor, MI (1978)), 92-106
[15] Matsuno, H.; Inoue, K.; Taniguchi, H.; Takanami, I., One-dimensional alternating simple multihead finite automata, (Tech. Rept. No. AL82-17. Tech. Rept. No. AL82-17, IECE of Japan (1982)) · Zbl 0565.68055
[16] Paul, W. J.; Prauss, E. J.; Reischuk, R., On alternation, Acta Informatica, 14, 243-255 (1980) · Zbl 0437.68025
[17] Ruzzo, W. L., Tree-size bounded alternation, J. Comput. System Sci., 21, 218-235 (1980) · Zbl 0445.68034
[18] Sudborough, I. H., On tape-bounded complexity classes and multihead finite automata, J. Comput. System Sci., 10, 62-76 (1975) · Zbl 0299.68031
[19] Sudborough, I. H., One-way multihead writing finite automata, Information and Control, 30, 1-20 (1976) · Zbl 0337.02023
[20] Sudborough, I. H., Efficient algorithms for path system problems and applications to alternating time-space complexity classes, (Conf. Rec. IEEE 21st Ann. Symp. on Foundations of Computer Science (1980)), 62-73 · Zbl 0299.68031
[21] Taniguchi, H.; Inoue, K.; Takanami, I., Some classes of simple multihead finite automata, (Tech. Rept. No. AL78-64. Tech. Rept. No. AL78-64, IECE of Japan (1978))
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.