Properties that Characterize LOGCFL

Two 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 new models of computation based on unbounded fan-in circuits. 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 [CKS81], nondeterministic auxiliary pushdown automata [Co71], and bounded fan-in Boolean circuits [Co85].

Authors

• H. Venkateswaran

Keywords

No keywords are indexed for this paper.