Verifying Multithreaded Recursive Programs with Integer Variables

We consider the verification problem of programs containing the following complex features: (1) dynamic creation of parallel threads, (2) synchronisation between parallel threads via global variables, (3) (possibly recursive) procedure calls, and (4) integer variables. The configurations of such programs are represented by terms, and their transitions by term rewriting systems. The novelty of our modeling w.r.t. other existing works consists in explicitely modeling integer variables in the terms. We propose a semi-decision procedure that, in case of termination, checks whether an infinite set of configurations, represented by a regular tree language, is reachable from an infinite set of initial configurations of the program (usually represented by a set of non ground terms). As fas as we know, this is the first time that reachability between non-ground terms and regular tree languages is considered. We implemented our techniques in a tool, and tested it successfully on several examples.