Properties that characterize LOGCFL Export

@inproceedings{citeulike:4013891, abstract = {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].}, address = {New York, NY, USA}, author = {Venkateswaran, H.}, booktitle = {STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing}, citeulike-article-id = {4013891}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=28395.28411}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/28395.28411}, doi = {10.1145/28395.28411}, isbn = {0-89791-221-7}, keywords = {atm}, location = {New York, New York, United States}, pages = {141--150}, posted-at = {2009-02-05 20:11:55}, priority = {2}, publisher = {ACM}, title = {Properties that characterize LOGCFL}, url = {http://dx.doi.org/10.1145/28395.28411}, year = {1987} }

TY - CONF ID - citeulike:4013891 L3 - citeulike-article-id:4013891 N2 - 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]. CY - New York, New York, United States SN - 0-89791-221-7 AD - New York, NY, USA EP - 150 TI - Properties that characterize LOGCFL PB - ACM T2 - STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing SP - 141 KW - atm AU - Venkateswaran, H PY - 1987/// UR - http://dx.doi.org/10.1145/28395.28411 ER -