Efficient recognition algorithms for boundary and linear eNCE graph languages |
| |
| Authors: | Changwook Kim |
| |
| Affiliation: | (1) School of Computer Science, University of Oklahoma, Norman, OK 73019, USA (e-mail: ckim@ou.edu) , US |
| |
| Abstract: | It is well known that every boundary (linear) eNCE graph language that is connected and degree-bounded by a constant is in
LOGCFL (NLOG). The present paper proves an upper bound of the complexity of boundary (linear) eNCE graph languages whose component
and degree bounds are functions in the size of the graph. As a corollary of this analysis, the known LOGCFL and NLOG results
stated above hold even if “connected” is replaced by “component-bounded by log n.”
Received: 15 January 1997 / 17 January 2001 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
