Complexity, Graphs, and the Dependency Pair Method

DOI10.1007/978-3-540-89439-1_45MaRDI QIDQ5505587zbMATH OpenOpenAlexFDO

Authors Nao Hirokawa, Georg Moser

Publication date 27 January 2009

Published in Logic for Programming, Artificial Intelligence, and Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-89439-1_45

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Automated Complexity Analysis Based on the Dependency Pair Method
• A dependency pair framework for innermost complexity analysis of term rewrite systems
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• Dependency Pairs and Polynomial Path Orders
• Rewriting Techniques and Applications

Cited in

(16)

• A combination framework for complexity
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• A dependency pair framework for innermost complexity analysis of term rewrite systems
• scientific article; zbMATH DE number 910356 (Why is no real title available?)
• Estimation of expressions' complexities for two-terminal directed acyclic graphs
• The derivational complexity induced by the dependency pair method
• An assessment of assignment schemes for dependency graphs
• An algorithm for reading dependencies from the minimal undirected independence map of a graphoid that satisfies weak transitivity
• Dependency Pairs and Polynomial Path Orders
• scientific article; zbMATH DE number 33703 (Why is no real title available?)
• The Derivational Complexity Induced by the Dependency Pair Method
• Solving a special case of the P conjecture using dependency graphs with dissolution
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• From Jinja bytecode to term rewriting: a complexity reflecting transformation
• Data complexity measured by principal graphs
• Automated Complexity Analysis Based on the Dependency Pair Method

This page was built for publication: Complexity, Graphs, and the Dependency Pair Method

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