Alternating automata, the weak monadic theory of trees and its complexity. (English) Zbl 0776.03017

Full version of the authors’ paper in Lect. Notes Comput. Sci. 226, 275- 283 (1986; Zbl 0617.03020).


03D05 Automata and formal grammars in connection with logical questions
03B25 Decidability of theories and sets of sentences
03D15 Complexity of computation (including implicit computational complexity)
68Q45 Formal languages and automata


Zbl 0617.03020
Full Text: DOI


[1] Büchi, J. R., On a decision method in restricted second-order arithmetic, (Proc. 1960 Internat. Congr. on Logic, Methodology and Philosophy of Science (1960), Stanford University Press: Stanford University Press Stanford, CA), 1-11 · Zbl 0147.25103
[2] Chandra, A.; Kozen, D.; Stockmeyer, L., Alternation, J. ACM, 28, 114-133 (1981) · Zbl 0473.68043
[3] Gurevitch, Y.; Harrington, L., Trees, automata and games, Proc. ACM Symp. on the Theory of Computing, 60-65 (1982), San Francisco
[4] Lindsay, P., On alternating ω-automata, Theoret. Comput. Sci., 43, 107-116 (1986)
[5] Lindsay, P., Alternation and ω-type Turing acceptors, J. Comput System Sci., 36, 16-24 (1988)
[6] McNaughton, R., Testing and generating infinite sequences by a finite automaton, Inform. and Control, 9, 521-530 (1966) · Zbl 0212.33902
[7] Muller, D. E., Infinite sequences and finite machines, Proc. 4th Ann. IEEE Symp. on Switching Circuit Theory and Logical Design, 3-16 (1963)
[8] Muller, D. E.; Schupp, P. E., The theory of ends, pushdown automata and second-order logic, Theoret. Comput. Sci., 37, 51-75 (1985) · Zbl 0605.03005
[9] Muller, D. E.; Schupp, P., Alternating automata on infinite trees, Theoret. Comput. Sci., 54, 267-276 (1987) · Zbl 0636.68108
[10] Muller, D. E.; Saoudi, A.; Schupp, P. E., Alternating automata, the weak monadic theory of the tree and its complexity, (Proc. ICALP’86, Vol. 226 (1986), Springer: Springer Berlin), 275-283, Lecture Notes in Computer Science
[11] Muller, D. E.; Saoudi, A.; Schupp, P. E., Weak alternating automata give a simple uniform explanation of why most temporal and dynamic logics are decidable in exponential time, Proc. 3rd IEEE Ann. Symp. on Logic in Computer Science, 422-427 (1988)
[12] Rabin, M. O., Decidability of second-order theories and automata on infinite trees, Trans. Amer. Math. Soc., 141, 1-35 (1969) · Zbl 0221.02031
[13] Rabin, M. O., Weakly definable relations and special automata, (Bar-Hillel, Mathematical Logic and Foundations of Set Theory (1970), North-Holland: North-Holland Amsterdam), 1-23 · Zbl 0214.02208
[14] Robertson, E. L., Structure of complexity in the weak monadic second-order theory of the natural numbers, Proc. 6th ACM STOC Conference, 161-171 (1974)
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.