| ||||
| ||||
![]() Title:Term rewriting characterisation of LOGSPACE for finite and infinite data Authors:Łukasz Czajka Conference:FSCD 2018 Tags:coinduction, implicit complexity, infinitary rewriting, LOGSPACE and term rewriting Abstract: We show that LOGSPACE is characterised by finite orthogonal tail-recursive cons-free constructor term rewriting systems, contributing to a line of research initiated by Neil Jones. We describe a LOGSPACE algorithm which computes constructor normal forms. This algorithm is used in the proof of our main result: that simple stream term rewriting systems characterise LOGSPACE-computable stream functions as defined by Ramyaa and Leivant. This result concerns characterising logarithmic-space computation on infinite streams by means of infinitary rewriting. Term rewriting characterisation of LOGSPACE for finite and infinite data ![]() Term rewriting characterisation of LOGSPACE for finite and infinite data | ||||
Copyright © 2002 – 2025 EasyChair |