cl-banner

Automated Complexity Analysis Based on Context-Sensitive Rewriting

Nao Hirokawa and Georg Moser

Proceedings of the Joint 25th International Conference on Rewriting Techniques and Applications and 12th International Conference on Typed Lambda Calculi and Applications (RTA-TLCA 2014), Lecture Notes in Computer Science 8560, pp. 257 – 271, 2014.

Abstract

In this paper we present a simple technique for analysing the runtime complexity of rewrite systems. In complexity analysis many techniques are based on reduction orders. We show how the monotonicity condition for orders can be weakened by using the notion of context-sensitive rewriting. The presented technique is very easy to implement, even in a modular setting, and has been integrated in the Tyrolean Complexity Tool. We provide ample experimental data for assessing the viability of our method.

 

  PDF |    doi:10.1007/978-3-319-08918-8_18  |  © Springer International Publishing Switzerland

BibTeX 

@inproceedings{NHGM-RTATLCA14,
author = "Nao Hirokawa and Georg Moser",
title = "Automated Complexity Analysis Based on Context-Sensitive Rewriting",
booktitle = "Proceedings of the Joint 25th International Conference on
Rewriting Techniques and Applications and 12th
International Conference on Typed Lambda Calculi and Applications",
editor = "Gilles Dowek",
series = "Lecture Notes in Computer Science (Advanced Research in
Computing and Software Science)",
volume = 8560,
pages = "257--271",
year = 2014,
doi = "10.1007/978-3-319-08918-8_18"
}
Nach oben scrollen