✦ LIBER ✦
A lexicographic path order with slow growing derivation bounds
✍ Scribed by Naohi Eguchi
- Publisher
- John Wiley and Sons
- Year
- 2009
- Tongue
- English
- Weight
- 172 KB
- Volume
- 55
- Category
- Article
- ISSN
- 0044-3050
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
This paper is concerned with implicit computational complexity of the exptime computable functions. Modifying the lexicographic path order, we introduce a path order EPO. It is shown that a termination proof for a term rewriting system via EPO implies an exponential bound on the lengths of derivations. The path order EPO is designed so that every exptime function is representable as a term rewrite system compatible with EPO (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)