Cover Image

Supermartingales for Unique Fixed Points: A Unified Approach to Lower Bound Verification

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kura, Satoshi, Unno, Hiroshi, Tsukada, Takeshi
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

A Hierarchy of Supermartingales for $ω$-Regular Verification
by: Kura, Satoshi, et al.
Published: (2025)

Automated Verification of Higher-Order Probabilistic Programs via a Dependent Refinement Type System
by: Kura, Satoshi, et al.
Published: (2024)

A Denotational Product Construction for Temporal Verification of Effectful Higher-Order Programs
by: Watanabe, Kazuki, et al.
Published: (2025)

A Primal-Dual Perspective on Program Verification Algorithms (Extended Version)
by: Tsukada, Takeshi, et al.
Published: (2025)

A Category-Theoretic Framework for Dependent Effect Systems
by: Kura, Satoshi, et al.
Published: (2026)

Formal Verification of Probing Security via Conditional Independence
by: Kura, Satoshi, et al.
Published: (2026)

On Complete Categorical Semantics for Effect Handlers
by: Kura, Satoshi
Published: (2026)

Higher-Order Weakest Precondition Transformers via a CPS Transformation
by: Kura, Satoshi
Published: (2023)

Stochastic Omega-Regular Verification and Control with Supermartingales
by: Abate, Alessandro, et al.
Published: (2024)

Supermartingale Certificates for Quantitative Omega-regular Verification and Control
by: Henzinger, Thomas A., et al.
Published: (2025)

Complete $ω$-Regular Supermartingale Certificates
by: Abate, Alessandro, et al.
Published: (2026)

Inapproximability of Unique Games in Fixed-Point Logic with Counting
by: Tucker-Foltz, Jamie
Published: (2021)

Quantitative Supermartingale Certificates
by: Abate, Alessandro, et al.
Published: (2025)

Value Functions as Supermartingale Certificates
by: Abate, Alessandro, et al.
Published: (2026)

Full Definability in a Profunctorial Model
by: Tsukada, Takeshi, et al.
Published: (2026)

Fixed Point Theorems in Computability Theory
by: Terwijn, Sebastiaan A.
Published: (2024)

Logical relations for call-by-push-value models, via internal fibrations in a 2-category
by: de Amorim, Pedro H. Azevedo, et al.
Published: (2025)

On Explicit Solutions to Fixed-Point Equations in Propositional Dynamic Logic
by: Lyon, Tim S.
Published: (2024)

Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting
by: Lichter, Moritz
Published: (2022)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
by: Nechesov, Andrey
Published: (2024)

Diagonalizing Through the $ω$-Chain: Iterated Self-Certification on Bounded Turing Machines and its Least Fixed Point
by: Sung, Miara
Published: (2026)

On Lower Bounding Minimal Model Count
by: Kabir, Mohimenul, et al.
Published: (2024)

Constructing Witnesses for Lower Bounds on Behavioural Distances
by: Turkenburg, Ruben, et al.
Published: (2025)

Strong Nominal Semantics for Fixed-Point Constraints
by: Caires-Santos, Ali K., et al.
Published: (2024)

SuperDP: Differential Privacy Refutation via Supermartingales
by: Chatterjee, Krishnendu, et al.
Published: (2026)

Optimal Lower Bounds for Symmetric Modular Circuits
by: Pago, Benedikt
Published: (2026)

Scalable Counting of Minimal Trap Spaces and Fixed Points in Boolean Networks
by: Kabir, Mohimenul, et al.
Published: (2025)

Unifying Model Execution and Deductive Verification with Interaction Trees in Isabelle/HOL
by: Foster, Simon, et al.
Published: (2024)

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
by: Li, Jiawei, et al.
Published: (2024)

Lower Bounds on Inverse Cellular Automata via Proof Complexity
by: Kapytka, Maryia
Published: (2026)

A Unifying Approach to Probabilistic Testing Equivalences
by: Chen, Weijun, et al.
Published: (2025)

Fuzzy Implicative Rules: A Unified Approach
by: Fernandez-Peralta, Raquel
Published: (2025)

Branch and Bound for Piecewise Linear Neural Network Verification
by: Bunel, Rudy, et al.
Published: (2019)

Automatic Verification of Floating-Point Accumulation Networks
by: Zhang, David K., et al.
Published: (2025)

Proceedings Twelfth Workshop on Fixed Points in Computer Science
by: Saurin, Alexis
Published: (2025)

A Unifying Approach to Product Constructions for Quantitative Temporal Inference
by: Watanabe, Kazuki, et al.
Published: (2024)

On proving consistency of equational theories in Bounded Arithmetic
by: Beckmann, Arnold, et al.
Published: (2022)

Verification of Nonblockingness in Bounded Petri Nets With Minimax Basis Reachability Graphs
by: Gu, Chao, et al.
Published: (2020)

A Unified Automata-Theoretic Approach to LTLf Modulo Theories (Extended Version)
by: Faella, Marco, et al.
Published: (2024)

A Fixed-Parameter Study on Propositional Dynamic Logic
by: Hosseinpour, Mohammad Javad, et al.
Published: (2024)