2023/02/04 by Abdulla, Parosh Aziz, Atig, Mohamed Faouzi, Furbach, Florian +4
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Programming Languages (cs.PL)
paper · doi:10.48550/arxiv.2302.02163
We consider parameterized verification of systems executing according to the total store ordering (TSO) semantics. The processes manipulate abstract data types over potentially infinite domains. We present a framework that translates the reachability problem for such systems to the reachability problem for register machines enriched with the given abstract data type. We use the translation to obtain tight complexity bounds for TSO-based parameterized verification over several abstract data types, such as push-down automata, ordered multi push-down automata, one-counter nets, one-counter automata, and Petri nets. We apply the framework to get complexity bounds for higher order stack and counter variants as well.