Some decision problems for bottom-up triangle acceptors |
| |
Authors: | Nakamura A |
| |
Affiliation: | Department of Applied Mathematics, Hiroshima University, Hiroshima, Japan; Computer Science Center, University of Maryland, College Park, MD 20742.; |
| |
Abstract: | It is proved that the emptiness problem for deterministic bottom-up triangle acceptors (BTA's) over a single input symbol is recursively unsolvable. From this result, it is also shown that certain decision problems involving BTA's and BPA's (deterministic bottom-up pyramid acceptors) are unsolvable. |
| |
Keywords: | |
本文献已被 PubMed 等数据库收录! |
|