Strategy independent reduction lengths in rewriting and binary arithmetic

H. Zantema

Strategy independent reduction lengths in rewriting and binary arithmetic

H. Zantema

Formal System Analysis

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

107 Downloads (Pure)

Abstract

In this paper we give a criterion by which one can conclude that every reduction of a basic term to normal form has the same length. As a consequence, the number of steps to reach the normal form is independent of the chosen strategy. In particular this holds for TRSs computing addition and multiplication of natural numbers, both in unary and binary notation.

Original language	English
Title of host publication	Reduction Strategies in Rewriting and Programming (10th International Workshop, WRS 2011, Novi Sad, Serbia, May 29, 2011. Informal proceedings)
Editors	S. Escobar
Place of Publication	Valencia
Publisher	Universidad Politecnica de Valencia
Pages	41-45
Publication status	Published - 2011

Access to Document

Metis254728Final published version, 75.4 KB

Cite this

@inproceedings{ab1bae7d55794074944988d55d9f8683,

title = "Strategy independent reduction lengths in rewriting and binary arithmetic",

abstract = "In this paper we give a criterion by which one can conclude that every reduction of a basic term to normal form has the same length. As a consequence, the number of steps to reach the normal form is independent of the chosen strategy. In particular this holds for TRSs computing addition and multiplication of natural numbers, both in unary and binary notation.",

author = "H. Zantema",

year = "2011",

language = "English",

pages = "41--45",

editor = "S. Escobar",

booktitle = "Reduction Strategies in Rewriting and Programming (10th International Workshop, WRS 2011, Novi Sad, Serbia, May 29, 2011. Informal proceedings)",

publisher = "Universidad Politecnica de Valencia",

address = "Spain",

}

Strategy independent reduction lengths in rewriting and binary arithmetic. / Zantema, H.
Reduction Strategies in Rewriting and Programming (10th International Workshop, WRS 2011, Novi Sad, Serbia, May 29, 2011. Informal proceedings). ed. / S. Escobar. Valencia: Universidad Politecnica de Valencia, 2011. p. 41-45.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Strategy independent reduction lengths in rewriting and binary arithmetic

AU - Zantema, H.

PY - 2011

Y1 - 2011

N2 - In this paper we give a criterion by which one can conclude that every reduction of a basic term to normal form has the same length. As a consequence, the number of steps to reach the normal form is independent of the chosen strategy. In particular this holds for TRSs computing addition and multiplication of natural numbers, both in unary and binary notation.

AB - In this paper we give a criterion by which one can conclude that every reduction of a basic term to normal form has the same length. As a consequence, the number of steps to reach the normal form is independent of the chosen strategy. In particular this holds for TRSs computing addition and multiplication of natural numbers, both in unary and binary notation.

M3 - Conference contribution

SP - 41

EP - 45

BT - Reduction Strategies in Rewriting and Programming (10th International Workshop, WRS 2011, Novi Sad, Serbia, May 29, 2011. Informal proceedings)

A2 - Escobar, S.

PB - Universidad Politecnica de Valencia

CY - Valencia

ER -

Strategy independent reduction lengths in rewriting and binary arithmetic

Abstract

Access to Document

Fingerprint

Cite this