Cover Image

Deciding Termination of Simple Randomized Loops

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Meyer, Éléanore, Giesl, Jürgen
Format:	Preprint
Published:	2025
Subjects:	Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Deciding Constant Runtime of Linear Loops
by: Frohn, Florian, et al.
Published: (2026)

Control-Flow Refinement for Complexity Analysis of Probabilistic Programs in KoAT
by: Lommen, Nils, et al.
Published: (2024)

Targeting Completeness: Automated Complexity Analysis of Integer Programs
by: Lommen, Nils, et al.
Published: (2024)

Termination of Triangular Polynomial Loops
by: Hark, Marcel, et al.
Published: (2019)

Automatic Complexity Analysis of Integer Programs via Triangular Weakly Non-Linear Loops
by: Lommen, Nils, et al.
Published: (2022)

Accelerating Loops with Arrays
by: Frohn, Florian, et al.
Published: (2026)

Small Term Reachability and Related Problems for Terminating Term Rewriting Systems
by: Baader, Franz, et al.
Published: (2024)

Integrating Loop Acceleration into Bounded Model Checking
by: Frohn, Florian, et al.
Published: (2024)

Annotated Dependency Pairs for Full Almost-Sure Termination of Probabilistic Term Rewriting
by: Kassing, Jan-Christoph, et al.
Published: (2024)

The Annotated Dependency Pair Framework for Almost-Sure Termination of Probabilistic Term Rewriting
by: Kassing, Jan-Christoph, et al.
Published: (2024)

Disproving (Positive) Almost-Sure Termination of Probabilistic Term Rewriting via Random Walks
by: Kassing, Jan-Christoph, et al.
Published: (2026)

From Innermost to Full Probabilistic Term Rewriting: Almost-Sure Termination, Complexity, and Modularity
by: Kassing, Jan-Christoph, et al.
Published: (2024)

AProVE: Modular Termination Analysis of Memory-Manipulating C Programs
by: Emrich, Frank, et al.
Published: (2023)

A Dependency Pair Framework for Relative Termination of Term Rewriting
by: Kassing, Jan-Christoph, et al.
Published: (2024)

From Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting
by: Kassing, Jan-Christoph, et al.
Published: (2023)

A Complete Dependency Pair Framework for Almost-Sure Innermost Termination of Probabilistic Term Rewriting
by: Kassing, Jan-Christoph, et al.
Published: (2023)

Dependency Pairs for Expected Innermost Runtime Complexity and Strong Almost-Sure Termination of Probabilistic Term Rewriting
by: Kassing, Jan-Christoph, et al.
Published: (2025)

Modular Automatic Complexity Analysis of Recursive Integer Programs
by: Lommen, Nils, et al.
Published: (2025)

Infinite State Model Checking by Learning Transitive Relations
by: Frohn, Florian, et al.
Published: (2025)

Targeting Completeness: Using Closed Forms for Size Bounds of Integer Programs
by: Lommen, Nils, et al.
Published: (2023)

Satisfiability Modulo Exponential Integer Arithmetic
by: Frohn, Florian, et al.
Published: (2024)

The 2-Dimensional Constraint Loop Problem is Decidable
by: Guilmant, Quentin, et al.
Published: (2024)

Decidability of Quantum Modal Logic
by: Tokuo, Kenji
Published: (2026)

Decidability for Sturmian words
by: Hieronymi, Philipp, et al.
Published: (2021)

Termination of Real Linear Loops
by: Neumann, Eike, et al.
Published: (2026)

Generalized Decidability via Brouwer Trees
by: de Jong, Tom, et al.
Published: (2026)

Dynamic Probability Logic: Decidability & Computability
by: Chopoghloo, Somayeh, et al.
Published: (2024)

Decidability of Quasi-Dense Modal Logics
by: Ostropolski-Nalewaja, Piotr, et al.
Published: (2024)

Deciding Equations in the Time Warp Algebra
by: van Gool, Sam, et al.
Published: (2023)

Weighted Rewriting: Semiring Semantics for Abstract Reduction Systems
by: Ahrens, Emma, et al.
Published: (2025)

Decidability in First-Order Modal Logic with Non-Rigid Constants and Definite Descriptions
by: Artale, Alessandro, et al.
Published: (2025)

Positive Almost-Sure Termination of Polynomial Random Walks
by: Winkler, Lorenz, et al.
Published: (2025)

Loop Termination and Generalized Collatz Sequences
by: Carelli, Mishel
Published: (2026)

Measuring Decidability as Related to Busy Beaver Numbers
by: Tandi, Gurpreet, et al.
Published: (2026)

Terminating Hybrid Tableaus for Ordered Models
by: Nishimura, Yuki
Published: (2025)

On the Decidability of Monadic Theories of Arithmetic Predicates
by: Berthé, Valérie, et al.
Published: (2024)

On the Decidability of Presburger Arithmetic Expanded with Powers
by: Karimov, Toghrul, et al.
Published: (2024)

Complete and Terminating Tableau Calculus for Undirected Graph
by: Nishimura, Yuki, et al.
Published: (2024)

Decidability of MSO Reparameterization over Countable Chains
by: Rabinovich, Alexander
Published: (2026)

Craig Interpolation for Decidable First-Order Fragments
by: Cate, Balder ten, et al.
Published: (2023)