Proving positive almost-sure termination

DOI10.1007/978-3-540-32033-3_24MaRDI QIDQ5703859zbMATH OpenOpenAlexFDO

Authors Florent Garnier, Olivier Bournez

Publication date 11 November 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b135673

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• Proving Positive Almost Sure Termination Under Strategies
• Proving Termination with (Boolean) Satisfaction
• Termination conditions for positivity proving procedures
• On the hardness of almost-sure termination
• Proving Termination by Invariance Relations
• On proving termination by innermost termination
• Proof-theoretic analysis of termination proofs
• Proving termination through conditional termination
• scientific article; zbMATH DE number 408817
• Learning probabilistic termination proofs

Cited in

(36)

• On probabilistic term rewriting
• Confluence and convergence in probabilistically terminating reduction systems
• Confluence and convergence modulo equivalence in probabilistically terminating reduction systems
• On the hardness of analyzing probabilistic programs
• On randomised strategies in the -calculus
• Inferring expected runtimes of probabilistic integer programs using expected sizes
• Time-bounded termination analysis for probabilistic programs with delays
• Correctness of sequential Monte Carlo inference for probabilistic programming languages
• Automated termination analysis of polynomial probabilistic programs
• Computing expected runtimes for constant probability programs
• Confluence in probabilistic rewriting
• On higher-order probabilistic subrecursion
• Probabilistic termination by monadic affine sized typing
• Proving Positive Almost Sure Termination Under Strategies
• A generalization of equational proof theory?
• On higher-order probabilistic subrecursion
• Probabilistic rewriting: normalization, termination, and unique normal forms
• Probabilistic rewriting and asymptotic behaviour: on termination and unique normal forms
• On the termination problem for probabilistic higher-order recursive programs
• The probabilistic termination tool amber
• Automated Expected Amortised Cost Analysis of Probabilistic Data Structures
• On Lexicographic Proof Rules for Probabilistic Termination
• Proving Almost-Sure Innermost Termination of Probabilistic Term Rewriting Using Dependency Pairs
• Generative Datalog with continuous distributions
• On lexicographic proof rules for probabilistic termination
• From innermost to full almost-sure termination of probabilistic term rewriting
• Probabilistic unifying relations for modelling epistemic and aleatoric uncertainty: semantics and automated reasoning with theorem proving
• Quantum expectation transformers for cost analysis
• A note on confluence in typed probabilistic lambda calculi
• Weighted rewriting
• From innermost to full probabilistic term rewriting: almost-sure termination, complexity, and modularity
• A distribution semantics for probabilistic term rewriting
• Weighted rewriting: semiring semantics for abstract reduction systems
• Deciding termination of simple randomized loops
• Disproving (positive) almost-sure termination of probabilistic term rewriting via random walks
• Learning probabilistic termination proofs

This page was built for publication: Proving positive almost-sure termination

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