Computing with Infinite Terms and Infinite Reductions

Jeroen Ketema; Jakob Grue Simonsen

doi:10.3233/FI-2019-1866

Computing with Infinite Terms and Infinite Reductions

Jeroen Ketema, Jakob Grue Simonsen^*

^*Corresponding author af dette arbejde

Programming Languages and Theory of Computing

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

Abstract

We define computable infinitary rewriting by introducing computability to the study of strongly convergent infinite reductions over infinite first-order terms. Given computable infinitary reductions, we show that descendants and origins - essential to proving fundamental properties such as compression and confluence - are computable across such reductions.

Originalsprog	Engelsk
Tidsskrift	Fundamenta Informaticae
Vol/bind	170
Udgave nummer	4
Sider (fra-til)	339-365
Antal sider	27
ISSN	0169-2968
DOI	https://doi.org/10.3233/FI-2019-1866
Status	Udgivet - 2019

Adgang til dokumentet

10.3233/FI-2019-1866

Andre filer og links

Link to publication in Scopus

Citationsformater

@article{bd8b034998f84942a7ffb1b6b6a02d1d,

title = "Computing with Infinite Terms and Infinite Reductions",

abstract = "We define computable infinitary rewriting by introducing computability to the study of strongly convergent infinite reductions over infinite first-order terms. Given computable infinitary reductions, we show that descendants and origins - essential to proving fundamental properties such as compression and confluence - are computable across such reductions.",

keywords = "computability, descendants, Infinitary term rewriting, needed reductions, origins",

author = "Jeroen Ketema and Simonsen, {Jakob Grue}",

year = "2019",

doi = "10.3233/FI-2019-1866",

language = "English",

volume = "170",

pages = "339--365",

journal = "Fundamenta Informaticae",

issn = "0169-2968",

publisher = "I O S Press",

number = "4",

}

TY - JOUR

T1 - Computing with Infinite Terms and Infinite Reductions

AU - Ketema, Jeroen

AU - Simonsen, Jakob Grue

PY - 2019

Y1 - 2019

N2 - We define computable infinitary rewriting by introducing computability to the study of strongly convergent infinite reductions over infinite first-order terms. Given computable infinitary reductions, we show that descendants and origins - essential to proving fundamental properties such as compression and confluence - are computable across such reductions.

AB - We define computable infinitary rewriting by introducing computability to the study of strongly convergent infinite reductions over infinite first-order terms. Given computable infinitary reductions, we show that descendants and origins - essential to proving fundamental properties such as compression and confluence - are computable across such reductions.

KW - computability

KW - descendants

KW - Infinitary term rewriting

KW - needed reductions

KW - origins

UR - http://www.scopus.com/inward/record.url?scp=85074375630&partnerID=8YFLogxK

U2 - 10.3233/FI-2019-1866

DO - 10.3233/FI-2019-1866

M3 - Journal article

AN - SCOPUS:85074375630

SN - 0169-2968

VL - 170

SP - 339

EP - 365

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

IS - 4

ER -