Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert Endre A linear-time algorithm for testing the truth of certain quantified Boolean formulas. (English) Zbl 0398.68042 Inf. Process. Lett. 8, 121-123 (1979). Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 4 ReviewsCited in 292 Documents MSC: 68T15 Theorem proving (deduction, resolution, etc.) (MSC2010) 03G05 Logical aspects of Boolean algebras Keywords:Linear-Time Algorithm; Testing the Truth of Quantified Boolean Formulas; Finding Strongly Connected; Components of a Directed Graph PDFBibTeX XMLCite \textit{B. Aspvall} et al., Inf. Process. Lett. 8, 121--123 (1979; Zbl 0398.68042) Full Text: DOI References: [1] Aho, A. V.; Hopcroft, I. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0326.68005 [2] Cook, S. A., The complexity of theorem proving procedures, Proc. 3rd Ann. ACM Symp. Theory Comput., 151-158 (1971) [3] Even, S.; Itai, A.; Shamir, A., On the complexity of timetable and multi-commodity flow problems, SIAM J. Comput., 5, 4, 691-703 (1976) · Zbl 0358.90021 [4] Reingold, E. M.; Nievergelt, J.; Deo, N., Combinatorial Algorithms: Theory and Practice (1977), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0367.68032 [5] Schaefer, T. J., The complexity of satisfiability problems, Proc. 10th Ann. ACM Symp. Theory Comput., 216-226 (1978) · Zbl 1282.68143 [6] Stockmeyer, L. J.; Meyer, A. R., Word problems requiring exponential time, Proc. 5th Ann. ACM Symp. Theory Comput., 1-9 (1973) · Zbl 0359.68050 [7] Tarjan, R. E., Depth first search and linear graph algorithms, SIAM J. Comput., 1, 2, 146-160 (1972) · Zbl 0251.05107 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.