Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Seventh Annual IEEE Symposium on

Logic in Computer Science (LICS 1992)

Paper: Strong sequentiality of left-linear overlapping term rewriting systems (at LICS 1992)

Authors: Yoshihito Toyama

Abstract

G. Huet and J.J. Levy (INRIA Rep. 359, 1979) showed that for every strongly sequential orthogonal (i.e., left-linear and non-overlapping) term rewriting system, index reduction strategy is normalizing. Their result is extended to overlapping term rewriting systems. It is shown that index reduction is normalizing for the class of strongly sequential left-linear term rewriting systems in which every critical pair can be joined with root balanced reductions. This class includes all weakly orthogonal left-normal systems, for which a leftmost-outermost reduction strategy is normalizing

BibTeX

  @InProceedings{Toyama-Strongsequentiality,
    author = 	 {Yoshihito Toyama},
    title = 	 {Strong sequentiality of left-linear overlapping term rewriting systems },
    booktitle =  {Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science (LICS 1992)},
    year =	 {1992},
    month =	 {June}, 
    pages =      {274--284},
    location =   {Santa Cruz, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2018-06-2121:59
Andrzej Murawski