3 papers
cs.PL2025
Efficient Linearizability Monitoring
Parosh Aziz Abdulla, Samuel Grahn, Bengt Jonsson +2
This paper revisits the fundamental problem of monitoring the linearizability of concurrent stacks, queues, sets, and multisets. Given a history of a library implementing one of th…
cs.DB2024
Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions
Diego Figueira, S. Krishna, Om Swostik Mishra +1
The problem of checking whether a recursive query can be rewritten as query without recursion is a fundamental reasoning task, known as the boundedness problem. Here we study the b…
cs.LO2024
An efficient quantifier elimination procedure for Presburger arithmetic
Christoph Haase, Shankara Narayanan Krishna, Khushraj Madnani +2
All known quantifier elimination procedures for Presburger arithmetic require doubly exponential time for eliminating a single block of existentially quantified variables. It has e…