@article{LEWIS1980317,
    Abstract = {We analyze the computational complexity of determining whether F is satisfiable when F is a formula of the classical predicate calculus obeying certain syntactic restrictions. For example, for the monadic predicate calculus and the G{\"o}del or 3 {\ldots} ∃∀∀∃ {\ldots} 3 prefix class we obtain lower and upper nondeterministic time bounds of the form cn/log n. The lower bounds are established by using acceptance problems for time-bounded Turing machines and alternating pushdown and stack automata.},
    Author = {Lewis, Harry R.},
    File = {Complexity results for classes of quantificational formulas - 1-s2.0-0022000080900276-main - a - c.pdf},
    ISSN = {0022-0000},
    Journal = {Journal of Computer and System Sciences},
    Number = {3},
    Pages = {317 - 353},
    Title = {Complexity results for classes of quantificational formulas},
    URL = {http://www.sciencedirect.com/science/article/pii/0022000080900276},
    Volume = {21},
    Year = {1980},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/0022000080900276},
    bdsk-url-2 = {https://doi.org/10.1016/0022-0000(80)90027-6},
    date-added = {2020-05-25 09:41:31 +0200},
    date-modified = {2020-05-25 09:41:31 +0200},
    doi = {10.1016/0022-0000(80)90027-6}
}

@article{LEWIS1980317, Abstract = {We analyze the computational complexity of determining whether F is satisfiable when F is a formula of the classical predicate calculus obeying certain syntactic restrictions. For example, for the monadic predicate calculus and the G{\"o}del or 3 {\ldots} ∃∀∀∃ {\ldots} 3 prefix class we obtain lower and upper nondeterministic time bounds of the form cn/log n. The lower bounds are established by using acceptance problems for time-bounded Turing machines and alternating pushdown and stack automata.}, Author = {Lewis, Harry R.}, File = {Complexity results for classes of quantificational formulas - 1-s2.0-0022000080900276-main - a - c.pdf}, ISSN = {0022-0000}, Journal = {Journal of Computer and System Sciences}, Number = {3}, Pages = {317 - 353}, Title = {Complexity results for classes of quantificational formulas}, URL = {http://www.sciencedirect.com/science/article/pii/0022000080900276}, Volume = {21}, Year = {1980}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/0022000080900276}, bdsk-url-2 = {https://doi.org/10.1016/0022-0000(80)90027-6}, date-added = {2020-05-25 09:41:31 +0200}, date-modified = {2020-05-25 09:41:31 +0200}, doi = {10.1016/0022-0000(80)90027-6} }