Properties that characterize LOGCFL

AbstractTwo properties, called semi-unboundedness and polynomial proof-size, are identified as key properties shared by the definitions of LOGCFL on several models of computations. The semi-unboundedness property leads to the definition of semi-unbounded fan-in circuit families. These are circuits obtained from unbounded fan-in circuits by restricting the fan-in of gates of one type. A new characterization of LOGCFL is obtained on such a model in which the fan-in of the AND gates are bounded by a constant. This property also suggests new characterizations of LOGCFL on the following models: alternating Turing machines, nondeterministic auxiliary pushdown automata, and bounded fan-in Boolean circuits