Constant runtime complexity of term rewriting is semi-decidable

DOI10.1016/J.IPL.2018.06.012MaRDI QIDQ1799562zbMATH OpenOpenAlexWikidataFDO

Authors Florian Frohn, Jürgen Giesl

Publication date 19 October 2018

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2018.06.012

zbMATH Keywords

computational complexitydecidabilityformal methodsterm rewritingprogram correctness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Grammars and rewriting systems (68Q42)

Recommendations

• The exact hardness of deciding derivational and runtime complexity
• Lower bounds for runtime complexity of term rewriting
• Analyzing runtime complexity via innermost runtime complexity
• Complexity analysis by graph rewriting
• Complexity of conditional term rewriting

Cites work

• scientific article; zbMATH DE number 3688776 (Why is no real title available?)
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• Analyzing program termination and complexity automatically with \textsf{AProVE}
• Automated Complexity Analysis Based on the Dependency Pair Method
• Complexity analysis for \textbf{Java} with \textsf{AProVE}
• From Jinja bytecode to term rewriting: a complexity reflecting transformation
• Lower bounds for runtime complexity of term rewriting
• Modular complexity analysis for term rewriting
• On Forward Closure and the Finite Variant Property
• Term Rewriting and All That
• Termination Competition (termCOMP 2015)
• Termination of narrowing revisited
• Termination proofs and the length of derivations
• The finite power property for context-free languages

Cited in

(1)

• The exact hardness of deciding derivational and runtime complexity

Describes a project that uses

Uses Software

• TcT
• AProVE

This page was built for publication: Constant runtime complexity of term rewriting is semi-decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1799562)