A hierarchy of propositional Horn formulas

Bogdan S. Chlebus

doi:10.1016/0304-3975(89)90123-0

A hierarchy of propositional Horn formulas

Research output: Contribution to journal › Article › peer-review

Abstract

A hierarchy of propositional Horn formulas is introduced. The levels σ^H_k and ∏^H_k of the hierarchy are defined by way of the number of alternations between players in a certain game related to the satisfiability of Horn formulas. The satisfiability problems for formulas from a given level of the hierarchy are shown to be complete in NSPACE(log n). A certain relationship between the hierarchy and the bounded-depth circuits is exhibited. Using it we show that for some σ^H_k and ∏^H_k formulas the equivalent formulas in the lower levels of the hierarchy must be exponentially longer.

Original language	English (US)
Pages (from-to)	113-119
Number of pages	7
Journal	Theoretical Computer Science
Volume	68
Issue number	1
DOIs	https://doi.org/10.1016/0304-3975(89)90123-0
State	Published - Oct 16 1989
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/0304-3975(89)90123-0

Cite this

@article{fd5ef1f6fded4df89f279e0943a6062c,

title = "A hierarchy of propositional Horn formulas",

abstract = "A hierarchy of propositional Horn formulas is introduced. The levels σHk and ∏Hk of the hierarchy are defined by way of the number of alternations between players in a certain game related to the satisfiability of Horn formulas. The satisfiability problems for formulas from a given level of the hierarchy are shown to be complete in NSPACE(log n). A certain relationship between the hierarchy and the bounded-depth circuits is exhibited. Using it we show that for some σHk and ∏Hk formulas the equivalent formulas in the lower levels of the hierarchy must be exponentially longer.",

author = "Chlebus, {Bogdan S.}",

year = "1989",

month = oct,

day = "16",

doi = "10.1016/0304-3975(89)90123-0",

language = "English (US)",

volume = "68",

pages = "113--119",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - A hierarchy of propositional Horn formulas

AU - Chlebus, Bogdan S.

PY - 1989/10/16

Y1 - 1989/10/16

N2 - A hierarchy of propositional Horn formulas is introduced. The levels σHk and ∏Hk of the hierarchy are defined by way of the number of alternations between players in a certain game related to the satisfiability of Horn formulas. The satisfiability problems for formulas from a given level of the hierarchy are shown to be complete in NSPACE(log n). A certain relationship between the hierarchy and the bounded-depth circuits is exhibited. Using it we show that for some σHk and ∏Hk formulas the equivalent formulas in the lower levels of the hierarchy must be exponentially longer.

AB - A hierarchy of propositional Horn formulas is introduced. The levels σHk and ∏Hk of the hierarchy are defined by way of the number of alternations between players in a certain game related to the satisfiability of Horn formulas. The satisfiability problems for formulas from a given level of the hierarchy are shown to be complete in NSPACE(log n). A certain relationship between the hierarchy and the bounded-depth circuits is exhibited. Using it we show that for some σHk and ∏Hk formulas the equivalent formulas in the lower levels of the hierarchy must be exponentially longer.

UR - http://www.scopus.com/inward/record.url?scp=0024750658&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024750658&partnerID=8YFLogxK

U2 - 10.1016/0304-3975(89)90123-0

DO - 10.1016/0304-3975(89)90123-0

M3 - Article

AN - SCOPUS:0024750658

SN - 0304-3975

VL - 68

SP - 113

EP - 119

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1

ER -

A hierarchy of propositional Horn formulas

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this