Albert Albiol, Elvira MaríaGarcía de la Banda, MaríaStuckey, Peter J.Gómez-Zamalloa Gil, MiguelIsabel Márquez, Miguel2024-01-302024-01-302019Elvira 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.3330565978-1-4503-6224-510.1145/3293882.3330565https://hdl.handle.net/20.500.14352/96664Dynamic 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.engconference paperhttps://doi.org/10.1145/3293882.3330565restricted accessInformática (Informática)1203.23 Lenguajes de Programación