In this paper, we study a certain case of a subgraph isomorphism problem. We consider the Hasse diagram of the lattice Mk (the unique lattice with k + 2 elements and one anti-chain of length k ) and find the maximal k for which it is isomorphic to a subgraph of the reduction graph of a given one-rule string rewriting system. We obtain a complete characterization for this problem and show that there is a dichotomy. There are one-rule string rewriting systems for which the maximal such k is 2 and there are cases where there is no maximum. No other intermediate option is possible.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
In this paper we solve two open problems in the theory of reduction graphs in lambda calculus. The first question is whether the condensed reduction graph of a lambda term is always locally finite (conjecture of M.Venturini Zilli 1984). We give a negative answer to the conjecture by providing a counterexample. The second problem is whether there is a term such that its reduction graph is composed of two reduction cycles (not loops) intersecting in just one point (problem of J.W.Klop 1980). We show that such a term cannot exist.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.