ω-Computations on deterministic pushdown machines
作者：
Highlights：
•
摘要
Deterministic pushdown machines working on ω-tapes are studied; the ω-languages recognized by such machines are called ω-DCFL's. Various ω-recognition mechanisms in the machines are considered, yielding a hierarchy of “i-recognizable” classes of ω-DCFL's. Algebraic characterizations are obtained for each of these classes. Certain decision problems, generally undecidable, are shown to be decidable within some of the classes.
论文关键词：
论文评审过程：Received 12 October 1976, Revised 7 February 1977, Available online 2 December 2003.
论文官网地址：https://doi.org/10.1016/0022-0000(78)90019-3
