Summary
A special case of the satisfiability problem, in which the clauses have a hierarchical structure, is shown to be solvable in linear time, assuming that the clauses have been represented in a convenient way.
Similar content being viewed by others
References
Lichtenstein, D.: Planar formulæ and their uses. SIAM J. Comput.11, 329–343 (1982).
Author information
Authors and Affiliations
Additional information
Research supported in part by National Science Foundation grant CCR-8610181.
Rights and permissions
About this article
Cite this article
Knuth, D.E. Nested satisfiability. Acta Informatica 28, 1–6 (1990). https://doi.org/10.1007/BF02983372
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02983372