Constant runtime complexity of term rewriting is semi-decidable
| Autor: | Florian Frohn, Jürgen Giesl |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Theoretical computer science
Computer science 020207 software engineering 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science Applications Theoretical Computer Science Term (time) Decidability 010201 computation theory & mathematics Signal Processing 0202 electrical engineering electronic engineering information engineering Rewriting Analysis tools Constant (mathematics) Information Systems |
| Zdroj: | Information Processing Letters. 139:18-23 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/j.ipl.2018.06.012 |
| Popis: | We prove that it is semi-decidable whether the runtime complexity of a term rewrite system is constant. Our semi-decision procedure exploits that constant runtime complexity is equivalent to termination of a restricted form of narrowing, which can be examined by considering finitely many start terms. We implemented our semi-decision procedure in the tool AProVE to show its efficiency and its success for systems where state-of-the-art complexity analysis tools fail. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect