Intensional Kleene and Rice theorems for abstract program semantics

DOI10.1016/J.IC.2022.104953MaRDI QIDQ2105439zbMATH OpenOpenAlexWikidataFDO

Authors Paolo Baldan, Francesco Ranzato, 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 theoryRice's theoremprogram analysisrecursive functionaffine program invariantsKleene's second recursion theorem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• More intensional versions of Rice's theorem
• The intensional content of Rice's theorem
• Approximation of abstract semantics by formal models of programs
• Analogues of Rice's theorem for semantic classes of propositions
• Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory

Cites work

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

Cited in

(2)

• Case-free programs: An abstraction of definite horn programs
• Correctness kernels of abstract interpretations

This page was built for publication: Intensional Kleene and Rice theorems for abstract program semantics

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