### Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairnessEffective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness

Access Restriction
Subscribed

 Author Harel, David Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1986 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $“\textit{P}-abiding”$ infinite paths of the former. Here $\textit{P}$ can be any member of a very wide class of properties of infinite paths. For many properties ??, 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 III11-complete, and (b) the existence of a general method for proving termination of nondeterministic or concurrent programs under any reasonable notion of fairness. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1986-01-02 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 33 Issue Number 1 Page Count 25 Starting Page 224 Ending Page 248

#### Open content in new tab

Source: ACM Digital Library