scientific article; zbMATH DE number 3851045
[For the entire collection see Zbl 0516.00024.] If T is a \(\lambda\)-term, G(T) the reduction graph of T has as nodes the terms T reduces to and as arcs the individual reductions. A plane is a maximal subgraph such that all nodes in it can be reduced to each other. A plane is terminal if no node in it reduces to one outside of it. A reduction sequence \({\mathcal D}\) from a term T is cofinal in G(T) iff every term of G(T) reduces to a term in \({\mathcal D}\). A reduction sequence \({\mathcal D}\) is eventually flat in a plane \({\mathcal A}\) iff \({\mathcal D}\) from a certain point on all terms of \({\mathcal D}\) are in \({\mathcal A}\). \({\mathcal D}\) is exit secured if for every term in \({\mathcal D}\) there is a later term which has no residual of the redexes of the former term. The author proves that if G(T) has a terminal plane \({\mathcal A}\), then \({\mathcal D}\) is cofinal in G(T) iff \({\mathcal D}\) is eventually flat in \({\mathcal A}\). She also extends a result of \textit{J. W. Klop} [Combinatory reduction systems (1980; Zbl 0466.03006)] in showing that if \({\mathcal D}\) is exit secured then \({\mathcal D}\) is cofinal in G(T). She conjectures that the converse also holds.
- Cofinite graphs and their profinite completions
- Some coinductive graphs
- An algebraic theory of graph reduction
- An algebraic theory of graph reduction
- Reducibility in finite posets
- Reductions to graph isomorphism
- Reductions to Graph Isomorphism
- Reduction graph and its application on algebraic graphs
- Reducible properties of graphs
- Reducibility of Eulerian graphs and digraphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3320341)