RT Conference Proceedings
T1 Optimal context-sensitive dynamic partial order reduction with observers
A1 Albert Albiol, Elvira María
A1 García de la Banda, María
A1 Stuckey, Peter J.
A1 Gómez-Zamalloa Gil, Miguel
A1 Isabel Márquez, Miguel
AB Dynamic Partial Order Reduction (DPOR) algorithms are used in stateless model checking to avoid the exploration of equivalent execution sequences. DPOR relies on the notion of independence between execution steps to detect equivalence. Recent progress in the area has introduced more accurate ways to detect independence: Context-Sensitive DPOR considers two steps p and t independent in the current state if the states obtained by executing p ·t and t ·p are the same; Optimal DPOR with Observers makes their dependency conditional to the existence of future events that observe their operations. We introduce a new algorithm, Optimal Context-Sensitive DPOR with Observers, that combines these two notions of conditional independence, and goes beyond them by exploiting their synergies. Experimental evaluation shows that our gains increase exponentially with the size of the considered inputs.
SN 978-1-4503-6224-5
YR 2019
FD 2019
LK https://hdl.handle.net/20.500.14352/96664
UL https://hdl.handle.net/20.500.14352/96664
LA eng
NO Elvira Albert, Maria Garcia de la Banda, Miguel Gómez-Zamalloa, Miguel Isabel, and Peter J. Stuckey. 2019. Optimal context-sensitive dynamic partial order reduction with observers. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA 2019). Association for Computing Machinery, New York, NY, USA, 352–362. https://doi.org/10.1145/3293882.3330565
DS Docta Complutense
RD 21 abr 2025