학술논문
Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness.
Document Type
Article
Author
Source
Journal of the Association for Computing Machinery. Jan1986, Vol. 33 Issue 1, p224-248. 25p.
Subject
Language
Abstract
Elementary translations between various kinds of recursive trees are presented. It is shown that trees of either finite or countably infinite branching can be effectively put into one-one correspondence with infinitely branching trees in such a way that the infinite paths of the latter correspond to the ' phi -abiding' infinite paths of the former. Here phi can be any member of a very wide class of properties of infinite paths. For many properties phi , the converse holds too. Two of the applications involve (a) the formulation of large classes of highly undecidable variants of classical computational problems, and in particular, easily describable domino problems that are II sup 1 sub 1 -complete, and (b) the existence of a general method for proving termination of nondeterministic or concurrent programs under any reasonable notion of fairness. [ABSTRACT FROM AUTHOR]