Complexity of conditional term rewriting

DOI10.23638/LMCS-13(1:6)2017MaRDI QIDQ2980968zbMATH OpenFDO

Authors Cynthia Kop, Aart Middeldorp, Thomas Sternagel

Publication date 8 May 2017

Full work available at URL https://arxiv.org/abs/1510.07276

zbMATH Keywords

complexityconditional term rewriting

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Conditional complexity
• Reachability in conditional term rewriting systems
• Recent Trends in Algebraic Development Techniques
• Computationally Equivalent Elimination of Conditions
• scientific article; zbMATH DE number 4074465

Cites work

• scientific article; zbMATH DE number 1729952 (Why is no real title available?)
• scientific article; zbMATH DE number 1332639 (Why is no real title available?)
• scientific article; zbMATH DE number 1380895 (Why is no real title available?)
• scientific article; zbMATH DE number 1405447 (Why is no real title available?)
• 2D dependency pairs for proving operational termination of CTRSs
• A rationale for conditional equational programming
• Algorithms with polynomial interpretation termination proof
• All about Maude -- a high-performance logical framework. How to specify, program and verify systems in rewriting logic. With CD-ROM.
• Analyzing innermost runtime complexity of term rewriting by dependency pairs
• Automated Complexity Analysis Based on Context-Sensitive Rewriting
• Automated Complexity Analysis Based on the Dependency Pair Method
• Characterizing and proving operational termination of deterministic conditional term rewriting systems
• Complexity Analysis by Rewriting
• Complexity analysis of term rewriting based on matrix and context dependent interpretations
• Computationally Equivalent Elimination of Conditions
• Conditional complexity
• Conditional confluence (system description)
• Context-sensitive rewriting strategies
• Elimination of conditions
• Joint spectral radius theory for automated complexity analysis of rewrite systems
• Max/Plus tree automata for termination of term rewriting
• Modular complexity analysis for term rewriting
• On tree automata that certify termination of left-linear term rewriting systems
• Operational termination of conditional term rewriting systems
• Polynomial path orders
• Polynomially bounded matrix interpretations
• Proving termination of programs automatically with AProVE
• Soundness of unravelings for conditional term rewriting systems via ultra-properties related to linearity
• Term Rewriting and All That
• The derivational complexity induced by the dependency pair method
• Tyrolean Complexity Tool: Features and Usage.
• Unravelings and ultra-properties

Cited in

(11)

• Operational termination of conditional rewriting with built-in numbers and semantic data structures
• Determinization of conditional term rewriting systems
• Simplifying conditional term rewriting systems: Unification, termination and confluence
• The 2D dependency pair framework for conditional rewrite systems. I: Definition and basic processors
• Complexity analysis of term-rewriting systems
• Conditional term rewriting and first-order theorem proving
• scientific article; zbMATH DE number 4092746 (Why is no real title available?)
• Conditional complexity
• Applications and extensions of context-sensitive rewriting
• Constant runtime complexity of term rewriting is semi-decidable
• scientific article; zbMATH DE number 4074465 (Why is no real title available?)

Describes a project that uses

Uses Software

• Conditional Confluence
• VMTL
• AProVE
• Maude

This page was built for publication: Complexity of conditional term rewriting

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