Intensional Kleene and Rice theorems for abstract program semantics

DOI10.1016/J.IC.2022.104953OpenAlexW3199468696WikidataQ113872834 ScholiaQ113872834MaRDI QIDQ2105439FDOQ2105439

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

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

zbMATH Keywords

computability theoryRice's theoremprogram analysisrecursive functionaffine program invariantsKleene's second recursion theorem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)