Some Decision Problems for Bottom-Up Triangle Acceptors
Akira Nakamura · IEEE Transactions on Pattern Analysis and Machine Intelligence · 1979
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.