Paper Info
Title
On the longest perpetual reductions in orthogonal expression reduction systems
Abstract
We study perpetual reductions in orthogonal (or conflict-free) fully extended expression reduction systems (OERS). ERS is a formalism for rewriting that subsumes term rewriting systems (TRSs) and the &lgr;-calculus. We design a strategy that, for any given term t in a fully extended OERS, constructs a longest reduction starting from t if t is strongly normalizing and otherwise constructs an infinite reduction. We call this strategy a limit strategy. For a large class of OERSs a limit strategy is computable. The Conservation Theorem for fully extended OERSs follows easily from the properties of the strategy. We develop a method for computing the lengths of longest developments in OERSs. Copyright 2001 Elsevier Science B.V.
Year
DOI
Venue
2001
10.1016/S0304-3975(00)00372-8
Theor. Comput. Sci.
Keywords
DocType
Volume
longest development,λ -calculus,subsumes term,Conservation Theorem,longest reduction,extended expression reduction system,Perpetual reductions,Elsevier Science B.V.,extended OERSs,perpetual reduction,longest perpetual reduction,limit strategy,orthogonal expression reduction system,Rewrite systems,infinite reduction,Strong normalization
Journal
266
Issue
ISSN
ISBN
1-2
Theoretical Computer Science
3-540-58140-5
Citations 
PageRank 
References 
16
1.05
31
Authors
1
Name
Order
Citations
PageRank
Zurab Khasidashvili130725.40