×

Constructions for alternating finite automata. (English) Zbl 0699.68081

Summary: Alternation is a natural generalization of nondeterminism. The model of alternating finite automata was first introduced and studied by A. K. Chandra, D. C. Kozen and L.J. Stockmeyer [J. Assoc. Comput. Mach. 28, 114-133 (1981; Zbl 0473.68043)]. Although alternating finite automata are no more powerful than deterministic finite automata with respect to language recognition, special features of alternating finite automata may provide new approaches and techniques for solving theoretical and practical problems concerning regular languages. We present direct constructions for the usual language theoretic operations in terms of alternating finite automata. Moreover, we discuss minimization and direct transformations between alternating, non- deterministic, and deterministic finite automata.

MSC:

68Q45 Formal languages and automata

Citations:

Zbl 0473.68043
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chandra A. K. Kozen D. C. Stockmeyer L. J. IBM T. J. Watson Research Center Yorktown Heights, NY 1978 Alternation. Res. Rept. R7489
[2] DOI: 10.1145/322234.322243 · Zbl 0473.68043 · doi:10.1145/322234.322243
[3] DOI: 10.1016/0020-0190(87)90085-8 · Zbl 0635.68040 · doi:10.1016/0020-0190(87)90085-8
[4] Hopcroft J.E., Introduction to Automata Theory, Languages, and Computation (1979) · Zbl 0426.68001
[5] DOI: 10.1016/0020-0190(85)90100-0 · Zbl 0579.68033 · doi:10.1016/0020-0190(85)90100-0
[6] DOI: 10.1016/0022-0000(85)90063-7 · Zbl 0582.68018 · doi:10.1016/0022-0000(85)90063-7
[7] Inoue, K., Takanami, I. and Tanaguchi, H. Two-dimensional alternating turing machines. Proc. 14th Ann. ACM Symp. pp.37–46. New York: ACM. On Theory of Computing
[8] DOI: 10.1016/0020-0190(82)90098-9 · Zbl 0532.68054 · doi:10.1016/0020-0190(82)90098-9
[9] King K.N., Restricted Forms of Alternation (1980)
[10] DOI: 10.1016/0304-3975(86)90170-2 · Zbl 0612.68074 · doi:10.1016/0304-3975(86)90170-2
[11] Ladner, R.E., Lipton, R.J and Stockmeyer, L.J. 1978. Alternating pushdown automata. Proc. 19th IEEE Symp. 1978. pp.92–106. on Foundations of Computer Science, IEEE · Zbl 0538.68039
[12] DOI: 10.1007/BF00264255 · Zbl 0437.68025 · doi:10.1007/BF00264255
[13] DOI: 10.1016/0022-0000(80)90036-7 · Zbl 0445.68034 · doi:10.1016/0022-0000(80)90036-7
[14] Sudborough, I.H. 1980. Efficient algorithms for path system problems and applications to alternating and time-space complexity classes. Proc 21st IEEE Ann. Symp. 1980. pp.62–72. On Foundations of Computer Science, IEEE
[15] Wagner K., Computational Complexity (1986) · Zbl 0584.68061
[16] Wood D., Theory of Computation (1987) · Zbl 0734.68001
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.