Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: reduction graph

Sortuj według:

Ogranicz wyniki do:

Diamond Subgraphs in the Reduction Graph of a One-Rule String Rewriting System

Adinayev Arthur, Stein Itamar

Fundamenta Informaticae

2021

Vol. 178, nr 3

173--185

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.

Two problems on reduction graphs in lambda calculus

Intrigila B., Laurenzi A.R.

Fundamenta Informaticae

2000

Vol. 44, Nr 1,2

133-144

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.