• DocumentCode
    1956063
  • Title

    A stability theorem in rewriting theory

  • Author

    Mellies, Paul-Andre

  • Author_Institution
    Dept. of Comput. Sci., Edinburgh Univ., UK
  • fYear
    1998
  • fDate
    21-24 Jun 1998
  • Firstpage
    287
  • Lastpage
    298
  • Abstract
    One key property of the λ-calculus is that there exists a minimal computation (the head-reduction) M→eV from a λ-term M to the set of its head-normal forms. Minimality here means categorical “reflectivity” i.e. that every reduction path M→fW to a head-normal form W factors (up to redex permutation) to a path M→eV→hW. This paper establishes a stability a la Berry or poly-reflectivity theorem [D, La, T] which extends the minimality property to rewriting systems with critical pairs. The theorem is proved in the setting of axiomatic rewriting systems where sets of head-normal forms are characterised by their frontier property in the spirit of J. Glauert and Z. Khasidashvili (1996)
  • Keywords
    lambda calculus; rewriting systems; stability; axiomatic rewriting systems; head-normal forms; minimal computation; minimality; poly-reflectivity theorem; reduction path; rewriting theory; stability theorem; Calculus; Carbon capture and storage; Computational modeling; Computer science; Concrete; Petri nets; Stability; Turing machines;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Logic in Computer Science, 1998. Proceedings. Thirteenth Annual IEEE Symposium on
  • Conference_Location
    Indianapolis, IN
  • ISSN
    1043-6871
  • Print_ISBN
    0-8186-8506-9
  • Type

    conf

  • DOI
    10.1109/LICS.1998.705665
  • Filename
    705665