Cover Image

Fixed Parameter Tractable Linearizability Monitoring

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Han, Lee Zheng, Mathur, Umang
Format:	Preprint
Published:	2025
Subjects:	Programming Languages Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Efficient Decrease-and-Conquer Linearizability Monitoring
by: Han, Lee Zheng, et al.
Published: (2024)

Counting and Sampling Traces in Regular Languages
by: de Colnet, Alexis, et al.
Published: (2025)

A faster FPRAS for #NFA
by: Meel, Kuldeep S., et al.
Published: (2023)

Parametrizing Reads-From Equivalence for Predictive Monitoring
by: Farzan, Azadeh, et al.
Published: (2026)

Predictive Monitoring with Strong Trace Prefixes
by: Ang, Zhendong, et al.
Published: (2024)

Predictive Monitoring against Pattern Regular Languages
by: Ang, Zhendong, et al.
Published: (2023)

$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
by: Yi, Yongming
Published: (2026)

Homogeneous Network Caching is Fixed-Parameter Tractable Parameterized by the Number of Caches
by: Pintér, József, et al.
Published: (2026)

Efficient Linearizability Monitoring
by: Abdulla, Parosh Aziz, et al.
Published: (2025)

Reversible Computation with Stacks and "Reversible Management of Failures"
by: Palazzo, Matteo, et al.
Published: (2025)

Reasonable Space for the $λ$-Calculus, Logarithmically
by: Accattoli, Beniamino, et al.
Published: (2022)

Runtime Repeated Recursion Unfolding in CHR: A Just-In-Time Online Program Optimization Strategy That Can Achieve Super-Linear Speedup
by: Fruehwirth, Thom
Published: (2023)

LFPL: Revisited and Mechanized
by: Glover, Nathaniel, et al.
Published: (2026)

Complete and tractable machine-independent characterizations of second-order polytime
by: Hainry, Emmanuel, et al.
Published: (2022)

Program Synthesis is $Σ_3^0$-Complete
by: Kim, Jinwoo
Published: (2024)

The Decision Problem for Regular First-Order Theories
by: Mathur, Umang, et al.
Published: (2024)

Kleene algebra with commutativity conditions is undecidable
by: de Amorim, Arthur Azevedo, et al.
Published: (2024)

The Power of Negation in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2025)

From Time to Space: The Impact of Linearity in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2026)

Enhanced Data Race Prediction Through Modular Reasoning
by: Ang, Zhendong, et al.
Published: (2025)

Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
by: Halftermeyer, Pierre
Published: (2026)

Flexible Type-Based Resource Estimation in Quantum Circuit Description Languages
by: Colledan, Andrea, et al.
Published: (2024)

Learning Randomized Reductions
by: Erata, Ferhat, et al.
Published: (2024)

Pathways to Tractability for Geometric Thickness
by: Depian, Thomas, et al.
Published: (2024)

SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism
by: Marzouk, Reda, et al.
Published: (2025)

Tractability results for integration in subspaces of the Wiener algebra
by: Dick, Josef, et al.
Published: (2024)

The Limits of Tractable Marginalization
by: Broadrick, Oliver, et al.
Published: (2025)

Towards a Characterization of Two-way Bijections in a Reversible Computational Model
by: Palazzo, Matteo, et al.
Published: (2025)

Gateways to Tractability for Satisfiability in Pearl's Causal Hierarchy
by: Ganian, Robert, et al.
Published: (2025)

Decentralized Projection-free Online Upper-Linearizable Optimization with Applications to DR-Submodular Optimization
by: Lu, Yiyang, et al.
Published: (2025)

On the Computational Tractability of the (Many) Shapley Values
by: Marzouk, Reda, et al.
Published: (2025)

Automatically Verifying Replication-aware Linearizability
by: Soundarapandian, Vimala, et al.
Published: (2025)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
by: Gaikwad, Ajinkya, et al.
Published: (2026)

Grid Programs: A Two-Dimensional, Variable-Free Model of Computation
by: López-Rubio, Ezequiel
Published: (2026)

Program Analysis via Multiple Context Free Language Reachability
by: Conrado, Giovanna Kobus, et al.
Published: (2024)

Complexity of Consistency Testing for the Release-Acquire Semantics
by: Govind, R., et al.
Published: (2026)

On the Complexity of Combinatorial Optimization on Fixed Structures
by: Megiddo, Nimrod
Published: (2024)

From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization
by: Pedramfar, Mohammad, et al.
Published: (2024)

A Tree Clock Data Structure for Causal Orderings in Concurrent Executions
by: Mathur, Umang, et al.
Published: (2022)

The Complexity of Testing Message-Passing Concurrency
by: Shi, Zheng, et al.
Published: (2025)