Intensional Kleene and Rice theorems for abstract program semantics

DOI10.1016/j.ic.2022.104953OpenAlexW3199468696WikidataQ113872834 ScholiaQ113872834MaRDI QIDQ2105439

Francesco Ranzato, Paolo Baldan, Linpeng Zhang

Publication date: 8 December 2022

Published in: Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

computability theoryprogram analysisrecursive functionRice's theoremaffine program invariantsKleene's second recursion theorem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Indexings of subrecursive classes
• Classical recursion theory. The theory of functions and sets of natural numbers
• Affine relationships among variables of a program
• Monotone data flow analysis frameworks
• More intensional versions of Rice's theorem
• New results on the computability and complexity of points--to analysis
• The intensional content of Rice's theorem
• Gödel numberings of partial recursive functions
• Undecidability and recursive inseparability
• Precise interprocedural analysis through linear algebra
• Über die Erfüllung gewisser Erhaltungssätze durch Kompliziertheitsmasse
• Natürliche Kompliziertheitsmasze und Erhaltungssätze I
• Natürliche Kompliziertheitsmasze und Erhaltungssätze II
• The decidable properties of subrecursive functions
• Polynomial Invariants for Affine Programs
• Automata, Languages and Programming
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On Effective Procedures for Speeding Up Algorithms
• On notation for ordinal numbers
• Classes of Recursively Enumerable Sets and Their Decision Problems
• Program analysis is harder than verification: a computability perspective