Complexity Analysis for Term Rewriting by Integer Transition Systems
| Autor: | Juergen Giesl, Marc Brockschmidt, Florian Frohn, Carsten Fuhs, Matthias Naaf |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Theoretical computer science
Recursion business.industry Computer science 020207 software engineering 0102 computer and information sciences 02 engineering and technology Modular design 01 natural sciences Automatic summarization Term (time) Transformation (function) 010201 computation theory & mathematics Computer Science::Logic in Computer Science Transition system 0202 electrical engineering electronic engineering information engineering Computer Science::Programming Languages Rewriting business Algorithm Integer (computer science) |
| Zdroj: | Frontiers of Combining Systems ISBN: 9783319661667 FroCoS |
| DOI: | 10.1007/978-3-319-66167-4_8 |
| Popis: | We present a new method to infer upper bounds on the innermost runtime complexity of term rewrite systems (TRSs), which benefits from recent advances on complexity analysis of integer transition systems (ITSs). To this end, we develop a transformation from TRSs to a generalized notion of ITSs with (possibly non-tail) recursion. To analyze their complexity, we introduce a modular technique which allows us to use existing tools for standard ITSs in order to infer complexity bounds for our generalized ITSs. The key idea of our technique is a summarization method that allows us to analyze components of the transition system independently. We implemented our contributions in the tool AProVE, and our experiments show that one can now infer bounds for significantly more TRSs than with previous state-of-the-art tools for term rewriting. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|