Quasi-interpretations. A way to control resources

DOI10.1016/j.tcs.2011.02.007zbMath1230.68077OpenAlexW2025130727MaRDI QIDQ541228

Guillaume Bonfante, Jean-Yves Marion, Jean-Yves Moyen

Publication date: 6 June 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.02.007

zbMATH Keywords

implicit complexityquasi-interpretationtermination orderings

Mathematics Subject Classification ID

Abstract data types; algebraic specification (68Q65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items (21)

Higher-order interpretations and program complexity ⋮ A Short Introduction to Implicit Computational Complexity ⋮ On sharing, memoization, and polynomial time ⋮ On quasi-interpretations, blind abstractions and implicit complexity ⋮ Size-based termination of higher-order rewriting ⋮ A Characterization of NC k by First Order Functional Programs ⋮ Read/write factorizable programs ⋮ Complete and tractable machine-independent characterizations of second-order polytime ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Combining linear logic and size types for implicit complexity ⋮ Unnamed Item ⋮ Resource control for synchronous cooperative threads ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dependency Pairs and Polynomial Path Orders ⋮ Upper Bounds on Stream I/O Using Semantic Interpretations ⋮ Unnamed Item ⋮ On the expressivity of elementary linear logic: characterizing Ptime and an exponential time hierarchy ⋮ A new order-theoretic characterisation of the polytime computable functions ⋮ Characterizing polynomial time complexity of stream programs using interpretations

Cites Work

• Orderings for term-rewriting systems
• Some undecidable termination problems for semi-Thue systems
• Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths
• On recursive path ordering
• Termination proofs by multiset path orderings imply primitive recursive derivation lengths
• A new recursion-theoretic characterization of the polytime functions
• Results and trends in theoretical computer science, Colloquium in honor of Arto Salomaa, Graz, Austria, June 10-11, 1994. Proceedings
• Analysing the implicit complexity of programs.
• LOGSPACE and PTIME characterized by programming languages
• Relationships between nondeterministic and deterministic tape complexities
• Algorithms with polynomial interpretation termination proof
• Resource Analysis by Sup-interpretation
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Alternation
• On the combinatorial and algebraic complexity of quantifier elimination
• Computer Science Logic
• A Characterization of Alternating Log Time by First Order Functional Programs
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Quasi-interpretations. A way to control resources