Simulation as a correct transformation of rewrite systems

Wan Fokkink, Jaco van de Pol

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Kamperman and Walters proposed the notion of a simulation of one rewrite system by another one, whereby each term of the simulating rewrite system is related to a term in the original rewrite system. In this paper it is shown that if such a simulation is sound and complete and preserves termination, then the transformation of the original into the simulating rewrite system constitutes a correct step in the compilation of the original rewrite system. That is, the normal forms of a term in the original rewrite system can then be obtained by computing the normal forms of a related term in the simulating rewrite system.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 1997 - 22nd International Symposium, MFCS 1997, Proceedings
EditorsIgor Privara, Peter Ruzicka
PublisherSpringer - Verlag
Pages249-258
Number of pages10
ISBN (Print)3540634371, 9783540634379
Publication statusPublished - 1 Jan 1997
Event22nd International Symposium on Mathematical Foundations of Computer Science, MFCS 1997 - Bratislava, Slovakia
Duration: 25 Aug 199729 Aug 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1295
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Symposium on Mathematical Foundations of Computer Science, MFCS 1997
CountrySlovakia
CityBratislava
Period25/08/9729/08/97

    Fingerprint

Cite this

Fokkink, W., & van de Pol, J. (1997). Simulation as a correct transformation of rewrite systems. In I. Privara, & P. Ruzicka (Eds.), Mathematical Foundations of Computer Science 1997 - 22nd International Symposium, MFCS 1997, Proceedings (pp. 249-258). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1295). Springer - Verlag.