Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies
We study normalising reduction strategies for infinitary Combinatory Reduction Systems (iCRSs). We prove that all fair, outermost-fair, and needed-fair strategies are normalising for orthogonal, fully-extended iCRSs. These facts properly generalise a number of results on normalising strategies in fi...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2010-02-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/841/pdf |
| _version_ | 1797268783001239552 |
|---|---|
| author | Jeroen Ketema Jakob Grue Simonsen |
| author_facet | Jeroen Ketema Jakob Grue Simonsen |
| author_sort | Jeroen Ketema |
| collection | DOAJ |
| description | We study normalising reduction strategies for infinitary Combinatory
Reduction Systems (iCRSs). We prove that all fair, outermost-fair, and
needed-fair strategies are normalising for orthogonal, fully-extended iCRSs.
These facts properly generalise a number of results on normalising strategies
in first-order infinitary rewriting and provide the first examples of
normalising strategies for infinitary lambda calculus. |
| first_indexed | 2024-04-25T01:37:58Z |
| format | Article |
| id | doaj.art-a9da3cda982a4ad18204762ddca38577 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:37:58Z |
| publishDate | 2010-02-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-a9da3cda982a4ad18204762ddca385772024-03-08T09:10:33ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742010-02-01Volume 6, Issue 110.2168/LMCS-6(1:7)2010841Infinitary Combinatory Reduction Systems: Normalising Reduction StrategiesJeroen KetemaJakob Grue SimonsenWe study normalising reduction strategies for infinitary Combinatory Reduction Systems (iCRSs). We prove that all fair, outermost-fair, and needed-fair strategies are normalising for orthogonal, fully-extended iCRSs. These facts properly generalise a number of results on normalising strategies in first-order infinitary rewriting and provide the first examples of normalising strategies for infinitary lambda calculus.https://lmcs.episciences.org/841/pdfcomputer science - logic in computer scienced.3.1f.3.2f.4.1f.4.2 |
| spellingShingle | Jeroen Ketema Jakob Grue Simonsen Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies Logical Methods in Computer Science computer science - logic in computer science d.3.1 f.3.2 f.4.1 f.4.2 |
| title | Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies |
| title_full | Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies |
| title_fullStr | Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies |
| title_full_unstemmed | Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies |
| title_short | Infinitary Combinatory Reduction Systems: Normalising Reduction Strategies |
| title_sort | infinitary combinatory reduction systems normalising reduction strategies |
| topic | computer science - logic in computer science d.3.1 f.3.2 f.4.1 f.4.2 |
| url | https://lmcs.episciences.org/841/pdf |
| work_keys_str_mv | AT jeroenketema infinitarycombinatoryreductionsystemsnormalisingreductionstrategies AT jakobgruesimonsen infinitarycombinatoryreductionsystemsnormalisingreductionstrategies |