/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCInline.xml --traceabstraction.trace.refinement.strategy FIXED_PREFERENCES --cacsl2boogietranslator.allow.undefined.functions true --traceabstraction.smt.solver External_ModelsAndUnsatCoreMode --traceabstraction.command.for.external.solver 'cvc4 --incremental --print-success --lang smt' -s ../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Bitvector.epf -i ../../../trunk/examples/svcomp/aws-c-common/aws_linked_list_prev_harness.i -------------------------------------------------------------------------------- This is Ultimate 0.2.5-dev-b75d321-m [2024-11-04 20:48:03,523 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-04 20:48:03,591 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/automizer/svcomp-Reach-64bit-Automizer_Bitvector.epf [2024-11-04 20:48:03,598 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-04 20:48:03,599 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-04 20:48:03,628 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-04 20:48:03,628 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-04 20:48:03,629 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-04 20:48:03,629 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-04 20:48:03,630 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-04 20:48:03,631 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-04 20:48:03,631 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-04 20:48:03,632 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-04 20:48:03,632 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-04 20:48:03,632 INFO L153 SettingsManager]: * Use SBE=true [2024-11-04 20:48:03,632 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-04 20:48:03,633 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-04 20:48:03,633 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-04 20:48:03,633 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-04 20:48:03,634 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-04 20:48:03,634 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-04 20:48:03,638 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-04 20:48:03,638 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-04 20:48:03,638 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-04 20:48:03,638 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-04 20:48:03,639 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-04 20:48:03,639 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-04 20:48:03,639 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-04 20:48:03,640 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-04 20:48:03,640 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-04 20:48:03,640 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-04 20:48:03,640 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 20:48:03,641 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-04 20:48:03,641 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-04 20:48:03,641 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-04 20:48:03,642 INFO L153 SettingsManager]: * Trace refinement strategy=WOLF [2024-11-04 20:48:03,642 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:03,642 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-04 20:48:03,642 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-04 20:48:03,643 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-04 20:48:03,643 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-04 20:48:03,643 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Trace refinement strategy -> FIXED_PREFERENCES Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Allow undefined functions -> true Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: SMT solver -> External_ModelsAndUnsatCoreMode Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: Command for external solver -> cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:03,879 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-04 20:48:03,902 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-04 20:48:03,906 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-04 20:48:03,907 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-04 20:48:03,908 INFO L274 PluginConnector]: CDTParser initialized [2024-11-04 20:48:03,909 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/aws-c-common/aws_linked_list_prev_harness.i [2024-11-04 20:48:05,290 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-04 20:48:05,678 INFO L384 CDTParser]: Found 1 translation units. [2024-11-04 20:48:05,679 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_prev_harness.i [2024-11-04 20:48:05,714 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a7f7845ee/1c11400f463c482ba3f8baef665392dd/FLAG77241baf8 [2024-11-04 20:48:05,863 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a7f7845ee/1c11400f463c482ba3f8baef665392dd [2024-11-04 20:48:05,865 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-04 20:48:05,866 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-11-04 20:48:05,867 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-04 20:48:05,867 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-04 20:48:05,872 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-04 20:48:05,873 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 08:48:05" (1/1) ... [2024-11-04 20:48:05,873 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@dd5d6c7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:05, skipping insertion in model container [2024-11-04 20:48:05,874 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 08:48:05" (1/1) ... [2024-11-04 20:48:05,957 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 20:48:06,253 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_prev_harness.i[4494,4507] [2024-11-04 20:48:06,261 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_prev_harness.i[4554,4567] [2024-11-04 20:48:06,818 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,908 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,909 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,909 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,917 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,920 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:06,920 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:06,921 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:06,921 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,921 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:06,922 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:06,929 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,929 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,935 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,935 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,943 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:06,943 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,944 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:06,944 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,945 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:06,946 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,946 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:06,947 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,949 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:06,950 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,950 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:06,950 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:06,951 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:06,951 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,197 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,198 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,199 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,199 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,304 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,318 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 20:48:07,344 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-04 20:48:07,402 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 20:48:07,409 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_prev_harness.i[4494,4507] [2024-11-04 20:48:07,410 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_prev_harness.i[4554,4567] [2024-11-04 20:48:07,443 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,462 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,463 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,463 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,467 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,468 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,469 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,469 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,469 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,470 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,470 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,472 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,472 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,473 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,473 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,477 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,477 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,478 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,478 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,479 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,479 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,481 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,482 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,483 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,483 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,483 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,484 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,484 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,484 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,541 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,541 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,542 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,542 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,573 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:07,580 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 20:48:07,586 INFO L200 MainTranslator]: Completed pre-run [2024-11-04 20:48:07,598 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_prev_harness.i[4494,4507] [2024-11-04 20:48:07,599 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_prev_harness.i[4554,4567] [2024-11-04 20:48:07,631 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,631 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,632 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,634 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,635 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,644 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,644 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,645 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,645 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,648 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,649 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,649 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,650 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:07,728 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 20:48:07,910 WARN L710 CHandler]: The following functions are not defined or handled internally: aws_array_list_ensure_capacity [2024-11-04 20:48:07,918 INFO L204 MainTranslator]: Completed translation [2024-11-04 20:48:07,919 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07 WrapperNode [2024-11-04 20:48:07,919 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-04 20:48:07,920 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-04 20:48:07,922 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-04 20:48:07,922 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-04 20:48:07,928 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (1/1) ... [2024-11-04 20:48:07,998 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (1/1) ... [2024-11-04 20:48:08,029 INFO L138 Inliner]: procedures = 687, calls = 1039, calls flagged for inlining = 50, calls inlined = 4, statements flattened = 57 [2024-11-04 20:48:08,030 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-04 20:48:08,030 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-04 20:48:08,030 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-04 20:48:08,031 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-04 20:48:08,041 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (1/1) ... [2024-11-04 20:48:08,041 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (1/1) ... [2024-11-04 20:48:08,045 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (1/1) ... [2024-11-04 20:48:08,076 INFO L175 MemorySlicer]: Split 17 memory accesses to 4 slices as follows [2, 5, 6, 4]. 35 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [2, 5, 0, 0]. The 2 writes are split as follows [0, 0, 1, 1]. [2024-11-04 20:48:08,076 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (1/1) ... [2024-11-04 20:48:08,076 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (1/1) ... [2024-11-04 20:48:08,094 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (1/1) ... [2024-11-04 20:48:08,095 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (1/1) ... [2024-11-04 20:48:08,104 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (1/1) ... [2024-11-04 20:48:08,112 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (1/1) ... [2024-11-04 20:48:08,123 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-04 20:48:08,124 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-04 20:48:08,124 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-04 20:48:08,124 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-04 20:48:08,125 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (1/1) ... [2024-11-04 20:48:08,132 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 20:48:08,143 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 20:48:08,158 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-04 20:48:08,161 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-04 20:48:08,185 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-04 20:48:08,185 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-04 20:48:08,185 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-04 20:48:08,186 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2024-11-04 20:48:08,186 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#3 [2024-11-04 20:48:08,187 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-04 20:48:08,187 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-04 20:48:08,187 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2024-11-04 20:48:08,187 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2024-11-04 20:48:08,187 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-04 20:48:08,187 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-04 20:48:08,187 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-04 20:48:08,187 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2024-11-04 20:48:08,187 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#3 [2024-11-04 20:48:08,187 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-04 20:48:08,188 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-04 20:48:08,188 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-04 20:48:08,188 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-04 20:48:08,188 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-04 20:48:08,188 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-04 20:48:08,188 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-04 20:48:08,188 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2024-11-04 20:48:08,188 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#3 [2024-11-04 20:48:08,188 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2024-11-04 20:48:08,188 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2024-11-04 20:48:08,188 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2024-11-04 20:48:08,188 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#3 [2024-11-04 20:48:08,189 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_prev_is_valid [2024-11-04 20:48:08,189 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_prev_is_valid [2024-11-04 20:48:08,503 INFO L238 CfgBuilder]: Building ICFG [2024-11-04 20:48:08,505 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-04 20:48:08,735 INFO L? ?]: Removed 31 outVars from TransFormulas that were not future-live. [2024-11-04 20:48:08,735 INFO L287 CfgBuilder]: Performing block encoding [2024-11-04 20:48:08,746 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-04 20:48:08,746 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-04 20:48:08,747 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 08:48:08 BoogieIcfgContainer [2024-11-04 20:48:08,747 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-04 20:48:08,749 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-04 20:48:08,749 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-04 20:48:08,752 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-04 20:48:08,752 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 04.11 08:48:05" (1/3) ... [2024-11-04 20:48:08,753 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4298bae7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 08:48:08, skipping insertion in model container [2024-11-04 20:48:08,753 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:07" (2/3) ... [2024-11-04 20:48:08,754 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@4298bae7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 08:48:08, skipping insertion in model container [2024-11-04 20:48:08,754 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 08:48:08" (3/3) ... [2024-11-04 20:48:08,755 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_prev_harness.i [2024-11-04 20:48:08,767 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-04 20:48:08,767 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-04 20:48:08,822 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-04 20:48:08,830 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@528f7e9c, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-04 20:48:08,831 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-04 20:48:08,834 INFO L276 IsEmpty]: Start isEmpty. Operand has 50 states, 32 states have (on average 1.21875) internal successors, (39), 33 states have internal predecessors, (39), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-04 20:48:08,840 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-04 20:48:08,841 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:08,841 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:08,841 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:08,845 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:08,845 INFO L85 PathProgramCache]: Analyzing trace with hash 690008246, now seen corresponding path program 1 times [2024-11-04 20:48:08,852 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:08,852 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1766875303] [2024-11-04 20:48:08,852 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:08,854 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:08,855 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:08,858 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:08,861 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (2)] Waiting until timeout for monitored process [2024-11-04 20:48:09,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:09,092 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-04 20:48:09,097 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:09,124 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-04 20:48:09,124 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:09,149 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-11-04 20:48:09,150 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:09,151 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1766875303] [2024-11-04 20:48:09,153 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1766875303] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:48:09,153 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:48:09,153 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 2 [2024-11-04 20:48:09,155 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1102323992] [2024-11-04 20:48:09,155 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:09,160 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-04 20:48:09,160 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:09,183 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-04 20:48:09,183 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 20:48:09,185 INFO L87 Difference]: Start difference. First operand has 50 states, 32 states have (on average 1.21875) internal successors, (39), 33 states have internal predecessors, (39), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) Second operand has 2 states, 2 states have (on average 10.5) internal successors, (21), 2 states have internal predecessors, (21), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-04 20:48:09,202 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:09,202 INFO L93 Difference]: Finished difference Result 94 states and 124 transitions. [2024-11-04 20:48:09,203 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-04 20:48:09,204 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 10.5) internal successors, (21), 2 states have internal predecessors, (21), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 28 [2024-11-04 20:48:09,204 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:09,209 INFO L225 Difference]: With dead ends: 94 [2024-11-04 20:48:09,209 INFO L226 Difference]: Without dead ends: 45 [2024-11-04 20:48:09,212 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 20:48:09,215 INFO L432 NwaCegarLoop]: 61 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 61 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:09,215 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 61 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:48:09,231 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2024-11-04 20:48:09,246 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2024-11-04 20:48:09,247 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 28 states have (on average 1.1785714285714286) internal successors, (33), 29 states have internal predecessors, (33), 12 states have call successors, (12), 4 states have call predecessors, (12), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-04 20:48:09,249 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 56 transitions. [2024-11-04 20:48:09,250 INFO L78 Accepts]: Start accepts. Automaton has 45 states and 56 transitions. Word has length 28 [2024-11-04 20:48:09,251 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:09,252 INFO L471 AbstractCegarLoop]: Abstraction has 45 states and 56 transitions. [2024-11-04 20:48:09,252 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 10.5) internal successors, (21), 2 states have internal predecessors, (21), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-04 20:48:09,252 INFO L276 IsEmpty]: Start isEmpty. Operand 45 states and 56 transitions. [2024-11-04 20:48:09,253 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-04 20:48:09,253 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:09,253 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:09,257 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (2)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:09,454 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:09,455 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:09,455 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:09,455 INFO L85 PathProgramCache]: Analyzing trace with hash -331060108, now seen corresponding path program 1 times [2024-11-04 20:48:09,455 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:09,456 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [247230497] [2024-11-04 20:48:09,456 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:09,456 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:09,456 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:09,458 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:09,460 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (3)] Waiting until timeout for monitored process [2024-11-04 20:48:09,764 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:09,767 INFO L255 TraceCheckSpWp]: Trace formula consists of 121 conjuncts, 41 conjuncts are in the unsatisfiable core [2024-11-04 20:48:09,778 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:09,872 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-04 20:48:09,876 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-04 20:48:09,888 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-04 20:48:09,903 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-04 20:48:11,126 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-04 20:48:11,127 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:12,057 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-04 20:48:12,057 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:12,058 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [247230497] [2024-11-04 20:48:12,058 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [247230497] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:48:12,058 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:48:12,058 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10, 9] imperfect sequences [] total 17 [2024-11-04 20:48:12,058 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1650520634] [2024-11-04 20:48:12,058 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:12,059 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2024-11-04 20:48:12,060 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:12,061 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2024-11-04 20:48:12,061 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=230, Unknown=0, NotChecked=0, Total=272 [2024-11-04 20:48:12,061 INFO L87 Difference]: Start difference. First operand 45 states and 56 transitions. Second operand has 17 states, 15 states have (on average 2.4) internal successors, (36), 13 states have internal predecessors, (36), 4 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 4 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-04 20:48:13,404 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:13,405 INFO L93 Difference]: Finished difference Result 56 states and 69 transitions. [2024-11-04 20:48:13,405 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-04 20:48:13,406 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 2.4) internal successors, (36), 13 states have internal predecessors, (36), 4 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 4 states have call predecessors, (6), 2 states have call successors, (6) Word has length 28 [2024-11-04 20:48:13,406 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:13,408 INFO L225 Difference]: With dead ends: 56 [2024-11-04 20:48:13,408 INFO L226 Difference]: Without dead ends: 54 [2024-11-04 20:48:13,408 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 35 SyntacticMatches, 4 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 71 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=62, Invalid=318, Unknown=0, NotChecked=0, Total=380 [2024-11-04 20:48:13,410 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 48 mSDsluCounter, 340 mSDsCounter, 0 mSdLazyCounter, 366 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 382 SdHoareTripleChecker+Invalid, 375 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 366 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:13,410 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 382 Invalid, 375 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 366 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2024-11-04 20:48:13,410 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 54 states. [2024-11-04 20:48:13,423 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 54 to 53. [2024-11-04 20:48:13,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 33 states have (on average 1.1515151515151516) internal successors, (38), 35 states have internal predecessors, (38), 13 states have call successors, (13), 5 states have call predecessors, (13), 6 states have return successors, (15), 12 states have call predecessors, (15), 12 states have call successors, (15) [2024-11-04 20:48:13,426 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 66 transitions. [2024-11-04 20:48:13,427 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 66 transitions. Word has length 28 [2024-11-04 20:48:13,427 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:13,427 INFO L471 AbstractCegarLoop]: Abstraction has 53 states and 66 transitions. [2024-11-04 20:48:13,427 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 2.4) internal successors, (36), 13 states have internal predecessors, (36), 4 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (6), 4 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-04 20:48:13,428 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 66 transitions. [2024-11-04 20:48:13,428 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-04 20:48:13,428 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:13,429 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:13,434 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (3)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:13,629 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:13,629 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:13,630 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:13,630 INFO L85 PathProgramCache]: Analyzing trace with hash -1140406734, now seen corresponding path program 1 times [2024-11-04 20:48:13,630 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:13,630 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1640269318] [2024-11-04 20:48:13,631 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:13,631 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:13,631 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:13,633 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:13,634 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (4)] Waiting until timeout for monitored process [2024-11-04 20:48:13,844 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:13,847 INFO L255 TraceCheckSpWp]: Trace formula consists of 116 conjuncts, 22 conjuncts are in the unsatisfiable core [2024-11-04 20:48:13,850 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:13,864 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-04 20:48:14,209 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-04 20:48:14,210 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:14,502 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-04 20:48:14,502 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:14,502 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1640269318] [2024-11-04 20:48:14,502 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1640269318] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:48:14,502 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:48:14,503 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8, 7] imperfect sequences [] total 13 [2024-11-04 20:48:14,503 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1399530841] [2024-11-04 20:48:14,503 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:14,503 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-04 20:48:14,503 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:14,504 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-04 20:48:14,504 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=41, Invalid=115, Unknown=0, NotChecked=0, Total=156 [2024-11-04 20:48:14,504 INFO L87 Difference]: Start difference. First operand 53 states and 66 transitions. Second operand has 13 states, 13 states have (on average 2.8461538461538463) internal successors, (37), 13 states have internal predecessors, (37), 3 states have call successors, (7), 3 states have call predecessors, (7), 4 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-04 20:48:15,420 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:15,420 INFO L93 Difference]: Finished difference Result 108 states and 135 transitions. [2024-11-04 20:48:15,421 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-04 20:48:15,421 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 2.8461538461538463) internal successors, (37), 13 states have internal predecessors, (37), 3 states have call successors, (7), 3 states have call predecessors, (7), 4 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 28 [2024-11-04 20:48:15,421 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:15,422 INFO L225 Difference]: With dead ends: 108 [2024-11-04 20:48:15,423 INFO L226 Difference]: Without dead ends: 58 [2024-11-04 20:48:15,423 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 58 GetRequests, 40 SyntacticMatches, 4 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 44 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=68, Invalid=172, Unknown=0, NotChecked=0, Total=240 [2024-11-04 20:48:15,424 INFO L432 NwaCegarLoop]: 45 mSDtfsCounter, 40 mSDsluCounter, 169 mSDsCounter, 0 mSdLazyCounter, 240 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 44 SdHoareTripleChecker+Valid, 214 SdHoareTripleChecker+Invalid, 244 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 240 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:15,424 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [44 Valid, 214 Invalid, 244 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 240 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-04 20:48:15,425 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2024-11-04 20:48:15,435 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 58. [2024-11-04 20:48:15,436 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 58 states, 37 states have (on average 1.162162162162162) internal successors, (43), 40 states have internal predecessors, (43), 13 states have call successors, (13), 5 states have call predecessors, (13), 7 states have return successors, (16), 12 states have call predecessors, (16), 12 states have call successors, (16) [2024-11-04 20:48:15,438 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 58 states to 58 states and 72 transitions. [2024-11-04 20:48:15,439 INFO L78 Accepts]: Start accepts. Automaton has 58 states and 72 transitions. Word has length 28 [2024-11-04 20:48:15,439 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:15,439 INFO L471 AbstractCegarLoop]: Abstraction has 58 states and 72 transitions. [2024-11-04 20:48:15,439 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 2.8461538461538463) internal successors, (37), 13 states have internal predecessors, (37), 3 states have call successors, (7), 3 states have call predecessors, (7), 4 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-04 20:48:15,440 INFO L276 IsEmpty]: Start isEmpty. Operand 58 states and 72 transitions. [2024-11-04 20:48:15,440 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2024-11-04 20:48:15,440 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:15,441 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:15,449 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (4)] Ended with exit code 0 [2024-11-04 20:48:15,641 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:15,642 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:15,642 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:15,642 INFO L85 PathProgramCache]: Analyzing trace with hash -1533433744, now seen corresponding path program 1 times [2024-11-04 20:48:15,642 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:15,643 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [2087286704] [2024-11-04 20:48:15,643 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:15,643 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:15,643 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:15,645 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:15,652 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (5)] Waiting until timeout for monitored process [2024-11-04 20:48:15,810 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:15,814 INFO L255 TraceCheckSpWp]: Trace formula consists of 113 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-04 20:48:15,816 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:15,884 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-04 20:48:15,884 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:15,950 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-04 20:48:15,950 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:15,950 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [2087286704] [2024-11-04 20:48:15,951 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [2087286704] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:48:15,951 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:48:15,951 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5, 5] imperfect sequences [] total 5 [2024-11-04 20:48:15,951 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1211652332] [2024-11-04 20:48:15,951 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:15,952 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-04 20:48:15,952 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:15,952 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-04 20:48:15,952 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-04 20:48:15,953 INFO L87 Difference]: Start difference. First operand 58 states and 72 transitions. Second operand has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-04 20:48:16,021 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:16,022 INFO L93 Difference]: Finished difference Result 115 states and 142 transitions. [2024-11-04 20:48:16,024 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-04 20:48:16,024 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 28 [2024-11-04 20:48:16,024 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:16,027 INFO L225 Difference]: With dead ends: 115 [2024-11-04 20:48:16,027 INFO L226 Difference]: Without dead ends: 60 [2024-11-04 20:48:16,027 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 51 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-04 20:48:16,030 INFO L432 NwaCegarLoop]: 57 mSDtfsCounter, 2 mSDsluCounter, 142 mSDsCounter, 0 mSdLazyCounter, 27 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 199 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 27 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:16,031 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 199 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 27 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:48:16,032 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2024-11-04 20:48:16,051 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 54. [2024-11-04 20:48:16,052 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 35 states have (on average 1.1714285714285715) internal successors, (41), 37 states have internal predecessors, (41), 12 states have call successors, (12), 5 states have call predecessors, (12), 6 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2024-11-04 20:48:16,052 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 65 transitions. [2024-11-04 20:48:16,053 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 65 transitions. Word has length 28 [2024-11-04 20:48:16,054 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:16,054 INFO L471 AbstractCegarLoop]: Abstraction has 54 states and 65 transitions. [2024-11-04 20:48:16,054 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.2) internal successors, (21), 5 states have internal predecessors, (21), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-04 20:48:16,054 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 65 transitions. [2024-11-04 20:48:16,055 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-11-04 20:48:16,055 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:16,055 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:16,060 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (5)] Ended with exit code 0 [2024-11-04 20:48:16,256 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:16,256 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:16,257 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:16,257 INFO L85 PathProgramCache]: Analyzing trace with hash -398531466, now seen corresponding path program 1 times [2024-11-04 20:48:16,257 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:16,257 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1935903765] [2024-11-04 20:48:16,257 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:16,257 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:16,257 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:16,258 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:16,259 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (6)] Waiting until timeout for monitored process [2024-11-04 20:48:16,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:16,588 INFO L255 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 43 conjuncts are in the unsatisfiable core [2024-11-04 20:48:16,595 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:16,613 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-04 20:48:16,619 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-04 20:48:16,625 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-04 20:48:16,630 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-04 20:48:17,815 INFO L349 Elim1Store]: treesize reduction 13, result has 48.0 percent of original size [2024-11-04 20:48:17,815 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 125 treesize of output 87 [2024-11-04 20:48:17,908 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-04 20:48:17,908 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:22,836 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-11-04 20:48:22,836 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:22,836 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1935903765] [2024-11-04 20:48:22,836 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1935903765] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:22,836 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:22,836 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [13] total 21 [2024-11-04 20:48:22,836 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1644137159] [2024-11-04 20:48:22,836 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:22,837 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-04 20:48:22,837 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:22,837 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-04 20:48:22,838 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=366, Unknown=0, NotChecked=0, Total=420 [2024-11-04 20:48:22,838 INFO L87 Difference]: Start difference. First operand 54 states and 65 transitions. Second operand has 10 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-04 20:48:23,499 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:23,499 INFO L93 Difference]: Finished difference Result 65 states and 77 transitions. [2024-11-04 20:48:23,499 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-04 20:48:23,499 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) Word has length 42 [2024-11-04 20:48:23,500 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:23,500 INFO L225 Difference]: With dead ends: 65 [2024-11-04 20:48:23,500 INFO L226 Difference]: Without dead ends: 63 [2024-11-04 20:48:23,501 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 55 SyntacticMatches, 8 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 145 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=68, Invalid=484, Unknown=0, NotChecked=0, Total=552 [2024-11-04 20:48:23,502 INFO L432 NwaCegarLoop]: 50 mSDtfsCounter, 11 mSDsluCounter, 293 mSDsCounter, 0 mSdLazyCounter, 190 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 343 SdHoareTripleChecker+Invalid, 201 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 190 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:23,502 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 343 Invalid, 201 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 190 Invalid, 0 Unknown, 0 Unchecked, 0.5s Time] [2024-11-04 20:48:23,502 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-11-04 20:48:23,515 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 62. [2024-11-04 20:48:23,515 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 62 states, 40 states have (on average 1.15) internal successors, (46), 43 states have internal predecessors, (46), 13 states have call successors, (13), 6 states have call predecessors, (13), 8 states have return successors, (15), 12 states have call predecessors, (15), 12 states have call successors, (15) [2024-11-04 20:48:23,516 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 62 states to 62 states and 74 transitions. [2024-11-04 20:48:23,516 INFO L78 Accepts]: Start accepts. Automaton has 62 states and 74 transitions. Word has length 42 [2024-11-04 20:48:23,516 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:23,516 INFO L471 AbstractCegarLoop]: Abstraction has 62 states and 74 transitions. [2024-11-04 20:48:23,517 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-04 20:48:23,517 INFO L276 IsEmpty]: Start isEmpty. Operand 62 states and 74 transitions. [2024-11-04 20:48:23,521 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-11-04 20:48:23,521 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:23,521 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:23,526 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (6)] Ended with exit code 0 [2024-11-04 20:48:23,721 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:23,722 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:23,722 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:23,722 INFO L85 PathProgramCache]: Analyzing trace with hash -1207878092, now seen corresponding path program 1 times [2024-11-04 20:48:23,722 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:23,723 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [223344874] [2024-11-04 20:48:23,723 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:23,723 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:23,723 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:23,724 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:23,725 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (7)] Waiting until timeout for monitored process [2024-11-04 20:48:23,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:23,951 INFO L255 TraceCheckSpWp]: Trace formula consists of 145 conjuncts, 27 conjuncts are in the unsatisfiable core [2024-11-04 20:48:23,954 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:23,964 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-04 20:48:23,968 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-04 20:48:23,975 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-04 20:48:24,167 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-11-04 20:48:24,170 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-04 20:48:24,511 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-04 20:48:24,511 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:24,826 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-11-04 20:48:24,826 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:24,826 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [223344874] [2024-11-04 20:48:24,826 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [223344874] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:24,827 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:24,827 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [11] total 17 [2024-11-04 20:48:24,827 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [403343493] [2024-11-04 20:48:24,827 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:24,827 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 20:48:24,827 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:24,828 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 20:48:24,828 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=216, Unknown=0, NotChecked=0, Total=272 [2024-11-04 20:48:24,828 INFO L87 Difference]: Start difference. First operand 62 states and 74 transitions. Second operand has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-04 20:48:25,135 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:25,136 INFO L93 Difference]: Finished difference Result 107 states and 129 transitions. [2024-11-04 20:48:25,136 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-04 20:48:25,136 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) Word has length 42 [2024-11-04 20:48:25,136 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:25,137 INFO L225 Difference]: With dead ends: 107 [2024-11-04 20:48:25,137 INFO L226 Difference]: Without dead ends: 67 [2024-11-04 20:48:25,138 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 85 GetRequests, 62 SyntacticMatches, 5 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 97 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=72, Invalid=308, Unknown=0, NotChecked=0, Total=380 [2024-11-04 20:48:25,139 INFO L432 NwaCegarLoop]: 51 mSDtfsCounter, 10 mSDsluCounter, 157 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 132 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:25,139 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [11 Valid, 208 Invalid, 132 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-04 20:48:25,139 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-04 20:48:25,151 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2024-11-04 20:48:25,151 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 44 states have (on average 1.1590909090909092) internal successors, (51), 48 states have internal predecessors, (51), 13 states have call successors, (13), 6 states have call predecessors, (13), 9 states have return successors, (16), 12 states have call predecessors, (16), 12 states have call successors, (16) [2024-11-04 20:48:25,152 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 80 transitions. [2024-11-04 20:48:25,152 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 80 transitions. Word has length 42 [2024-11-04 20:48:25,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:25,153 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 80 transitions. [2024-11-04 20:48:25,153 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.125) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-04 20:48:25,153 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 80 transitions. [2024-11-04 20:48:25,154 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 43 [2024-11-04 20:48:25,154 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:25,154 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:25,159 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (7)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:25,354 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:25,355 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:25,355 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:25,355 INFO L85 PathProgramCache]: Analyzing trace with hash -1600905102, now seen corresponding path program 1 times [2024-11-04 20:48:25,355 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:25,355 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [970458080] [2024-11-04 20:48:25,355 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:25,356 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:25,356 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:25,358 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:25,359 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (8)] Waiting until timeout for monitored process [2024-11-04 20:48:25,554 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:25,556 INFO L255 TraceCheckSpWp]: Trace formula consists of 142 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-04 20:48:25,558 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:25,569 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-04 20:48:25,653 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 8 [2024-11-04 20:48:25,697 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-04 20:48:25,697 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:25,767 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2024-11-04 20:48:25,767 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:25,767 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [970458080] [2024-11-04 20:48:25,767 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [970458080] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:25,767 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:25,767 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 8 [2024-11-04 20:48:25,767 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1261383210] [2024-11-04 20:48:25,767 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:25,768 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 20:48:25,768 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:25,768 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 20:48:25,768 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:48:25,769 INFO L87 Difference]: Start difference. First operand 67 states and 80 transitions. Second operand has 6 states, 6 states have (on average 4.166666666666667) internal successors, (25), 6 states have internal predecessors, (25), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-04 20:48:25,860 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:25,860 INFO L93 Difference]: Finished difference Result 119 states and 141 transitions. [2024-11-04 20:48:25,861 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 20:48:25,861 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.166666666666667) internal successors, (25), 6 states have internal predecessors, (25), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) Word has length 42 [2024-11-04 20:48:25,861 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:25,862 INFO L225 Difference]: With dead ends: 119 [2024-11-04 20:48:25,862 INFO L226 Difference]: Without dead ends: 69 [2024-11-04 20:48:25,863 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 73 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2024-11-04 20:48:25,863 INFO L432 NwaCegarLoop]: 56 mSDtfsCounter, 5 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 187 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:25,863 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 187 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 20:48:25,864 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 69 states. [2024-11-04 20:48:25,874 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 69 to 63. [2024-11-04 20:48:25,875 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 42 states have (on average 1.1666666666666667) internal successors, (49), 45 states have internal predecessors, (49), 12 states have call successors, (12), 6 states have call predecessors, (12), 8 states have return successors, (13), 11 states have call predecessors, (13), 11 states have call successors, (13) [2024-11-04 20:48:25,875 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 74 transitions. [2024-11-04 20:48:25,875 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 74 transitions. Word has length 42 [2024-11-04 20:48:25,876 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:25,876 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 74 transitions. [2024-11-04 20:48:25,876 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.166666666666667) internal successors, (25), 6 states have internal predecessors, (25), 3 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-04 20:48:25,876 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 74 transitions. [2024-11-04 20:48:25,877 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2024-11-04 20:48:25,877 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:25,877 INFO L215 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:25,882 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (8)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:26,077 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:26,078 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:26,078 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:26,078 INFO L85 PathProgramCache]: Analyzing trace with hash -181120997, now seen corresponding path program 1 times [2024-11-04 20:48:26,078 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:26,079 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [806257005] [2024-11-04 20:48:26,079 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:26,079 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:26,079 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:26,080 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:26,081 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (9)] Waiting until timeout for monitored process [2024-11-04 20:48:26,320 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:26,324 INFO L255 TraceCheckSpWp]: Trace formula consists of 159 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-04 20:48:26,326 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:26,398 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 7 [2024-11-04 20:48:26,401 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 7 [2024-11-04 20:48:26,438 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-04 20:48:26,439 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:26,548 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 11 trivial. 0 not checked. [2024-11-04 20:48:26,548 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:26,548 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [806257005] [2024-11-04 20:48:26,548 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [806257005] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:48:26,548 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:48:26,549 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6, 6] imperfect sequences [] total 8 [2024-11-04 20:48:26,549 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [831911433] [2024-11-04 20:48:26,549 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:26,549 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 20:48:26,549 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:26,550 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 20:48:26,550 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:48:26,550 INFO L87 Difference]: Start difference. First operand 63 states and 74 transitions. Second operand has 8 states, 7 states have (on average 4.0) internal successors, (28), 6 states have internal predecessors, (28), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-04 20:48:26,682 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:26,683 INFO L93 Difference]: Finished difference Result 69 states and 79 transitions. [2024-11-04 20:48:26,683 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 20:48:26,683 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 4.0) internal successors, (28), 6 states have internal predecessors, (28), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 48 [2024-11-04 20:48:26,684 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:26,685 INFO L225 Difference]: With dead ends: 69 [2024-11-04 20:48:26,685 INFO L226 Difference]: Without dead ends: 67 [2024-11-04 20:48:26,685 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 88 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2024-11-04 20:48:26,685 INFO L432 NwaCegarLoop]: 54 mSDtfsCounter, 6 mSDsluCounter, 183 mSDsCounter, 0 mSdLazyCounter, 45 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 237 SdHoareTripleChecker+Invalid, 45 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 45 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:26,686 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 237 Invalid, 45 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 45 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 20:48:26,686 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2024-11-04 20:48:26,703 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 67. [2024-11-04 20:48:26,704 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 67 states, 45 states have (on average 1.1555555555555554) internal successors, (52), 48 states have internal predecessors, (52), 12 states have call successors, (12), 7 states have call predecessors, (12), 9 states have return successors, (13), 11 states have call predecessors, (13), 11 states have call successors, (13) [2024-11-04 20:48:26,704 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 67 states to 67 states and 77 transitions. [2024-11-04 20:48:26,705 INFO L78 Accepts]: Start accepts. Automaton has 67 states and 77 transitions. Word has length 48 [2024-11-04 20:48:26,705 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:26,705 INFO L471 AbstractCegarLoop]: Abstraction has 67 states and 77 transitions. [2024-11-04 20:48:26,705 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 4.0) internal successors, (28), 6 states have internal predecessors, (28), 3 states have call successors, (8), 3 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2024-11-04 20:48:26,705 INFO L276 IsEmpty]: Start isEmpty. Operand 67 states and 77 transitions. [2024-11-04 20:48:26,706 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-11-04 20:48:26,706 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:26,706 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:26,714 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (9)] Ended with exit code 0 [2024-11-04 20:48:26,906 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:26,907 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:26,907 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:26,907 INFO L85 PathProgramCache]: Analyzing trace with hash 1509321987, now seen corresponding path program 1 times [2024-11-04 20:48:26,907 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:26,907 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [628760650] [2024-11-04 20:48:26,908 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:26,908 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:26,908 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:26,909 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:26,910 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (10)] Waiting until timeout for monitored process [2024-11-04 20:48:27,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:27,179 INFO L255 TraceCheckSpWp]: Trace formula consists of 191 conjuncts, 42 conjuncts are in the unsatisfiable core [2024-11-04 20:48:27,183 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:27,193 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-04 20:48:27,201 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-04 20:48:27,209 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-04 20:48:27,219 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-04 20:48:28,910 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 18 proven. 6 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-04 20:48:28,910 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:34,002 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 23 proven. 1 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2024-11-04 20:48:34,002 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:34,002 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [628760650] [2024-11-04 20:48:34,002 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [628760650] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 20:48:34,002 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 20:48:34,002 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 26 [2024-11-04 20:48:34,002 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [186333802] [2024-11-04 20:48:34,002 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 20:48:34,003 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-11-04 20:48:34,003 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:34,004 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-11-04 20:48:34,004 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=91, Invalid=558, Unknown=1, NotChecked=0, Total=650 [2024-11-04 20:48:34,004 INFO L87 Difference]: Start difference. First operand 67 states and 77 transitions. Second operand has 26 states, 22 states have (on average 3.272727272727273) internal successors, (72), 22 states have internal predecessors, (72), 9 states have call successors, (18), 4 states have call predecessors, (18), 6 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2024-11-04 20:48:35,823 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:35,823 INFO L93 Difference]: Finished difference Result 78 states and 88 transitions. [2024-11-04 20:48:35,823 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2024-11-04 20:48:35,824 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 22 states have (on average 3.272727272727273) internal successors, (72), 22 states have internal predecessors, (72), 9 states have call successors, (18), 4 states have call predecessors, (18), 6 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) Word has length 63 [2024-11-04 20:48:35,824 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:35,825 INFO L225 Difference]: With dead ends: 78 [2024-11-04 20:48:35,825 INFO L226 Difference]: Without dead ends: 76 [2024-11-04 20:48:35,825 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 129 GetRequests, 88 SyntacticMatches, 13 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 241 ImplicationChecksByTransitivity, 5.6s TimeCoverageRelationStatistics Valid=129, Invalid=740, Unknown=1, NotChecked=0, Total=870 [2024-11-04 20:48:35,826 INFO L432 NwaCegarLoop]: 38 mSDtfsCounter, 27 mSDsluCounter, 339 mSDsCounter, 0 mSdLazyCounter, 482 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 377 SdHoareTripleChecker+Invalid, 511 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 482 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.5s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:35,826 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 377 Invalid, 511 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 482 Invalid, 0 Unknown, 0 Unchecked, 1.5s Time] [2024-11-04 20:48:35,827 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 76 states. [2024-11-04 20:48:35,847 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 76 to 75. [2024-11-04 20:48:35,848 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 50 states have (on average 1.14) internal successors, (57), 54 states have internal predecessors, (57), 13 states have call successors, (13), 8 states have call predecessors, (13), 11 states have return successors, (15), 12 states have call predecessors, (15), 12 states have call successors, (15) [2024-11-04 20:48:35,849 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 85 transitions. [2024-11-04 20:48:35,849 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 85 transitions. Word has length 63 [2024-11-04 20:48:35,849 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:35,849 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 85 transitions. [2024-11-04 20:48:35,849 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 22 states have (on average 3.272727272727273) internal successors, (72), 22 states have internal predecessors, (72), 9 states have call successors, (18), 4 states have call predecessors, (18), 6 states have return successors, (16), 7 states have call predecessors, (16), 7 states have call successors, (16) [2024-11-04 20:48:35,849 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 85 transitions. [2024-11-04 20:48:35,854 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-11-04 20:48:35,854 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:35,854 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:35,861 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (10)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:36,055 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:36,056 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:36,056 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:36,056 INFO L85 PathProgramCache]: Analyzing trace with hash 699975361, now seen corresponding path program 1 times [2024-11-04 20:48:36,056 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:36,056 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [376624309] [2024-11-04 20:48:36,056 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:36,056 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:36,057 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:36,058 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:36,059 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (11)] Waiting until timeout for monitored process [2024-11-04 20:48:36,297 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:36,299 INFO L255 TraceCheckSpWp]: Trace formula consists of 186 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-04 20:48:36,302 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:36,317 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-04 20:48:36,877 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 18 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2024-11-04 20:48:36,877 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:37,149 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 18 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2024-11-04 20:48:37,150 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:37,150 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [376624309] [2024-11-04 20:48:37,150 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [376624309] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:48:37,150 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:48:37,150 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11, 7] imperfect sequences [] total 16 [2024-11-04 20:48:37,150 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [728050288] [2024-11-04 20:48:37,150 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:37,150 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2024-11-04 20:48:37,150 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:37,151 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2024-11-04 20:48:37,151 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=58, Invalid=182, Unknown=0, NotChecked=0, Total=240 [2024-11-04 20:48:37,151 INFO L87 Difference]: Start difference. First operand 75 states and 85 transitions. Second operand has 16 states, 15 states have (on average 4.333333333333333) internal successors, (65), 16 states have internal predecessors, (65), 6 states have call successors, (17), 3 states have call predecessors, (17), 4 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-04 20:48:38,236 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:38,237 INFO L93 Difference]: Finished difference Result 102 states and 116 transitions. [2024-11-04 20:48:38,237 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-04 20:48:38,237 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 15 states have (on average 4.333333333333333) internal successors, (65), 16 states have internal predecessors, (65), 6 states have call successors, (17), 3 states have call predecessors, (17), 4 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) Word has length 63 [2024-11-04 20:48:38,238 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:38,239 INFO L225 Difference]: With dead ends: 102 [2024-11-04 20:48:38,239 INFO L226 Difference]: Without dead ends: 75 [2024-11-04 20:48:38,239 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 128 GetRequests, 102 SyntacticMatches, 9 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 110 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=85, Invalid=257, Unknown=0, NotChecked=0, Total=342 [2024-11-04 20:48:38,240 INFO L432 NwaCegarLoop]: 39 mSDtfsCounter, 21 mSDsluCounter, 166 mSDsCounter, 0 mSdLazyCounter, 259 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 30 SdHoareTripleChecker+Valid, 205 SdHoareTripleChecker+Invalid, 271 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 259 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:38,240 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [30 Valid, 205 Invalid, 271 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 259 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2024-11-04 20:48:38,240 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2024-11-04 20:48:38,258 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 75. [2024-11-04 20:48:38,258 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 75 states, 50 states have (on average 1.12) internal successors, (56), 54 states have internal predecessors, (56), 13 states have call successors, (13), 8 states have call predecessors, (13), 11 states have return successors, (15), 12 states have call predecessors, (15), 12 states have call successors, (15) [2024-11-04 20:48:38,259 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 75 states to 75 states and 84 transitions. [2024-11-04 20:48:38,259 INFO L78 Accepts]: Start accepts. Automaton has 75 states and 84 transitions. Word has length 63 [2024-11-04 20:48:38,259 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:38,259 INFO L471 AbstractCegarLoop]: Abstraction has 75 states and 84 transitions. [2024-11-04 20:48:38,260 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 15 states have (on average 4.333333333333333) internal successors, (65), 16 states have internal predecessors, (65), 6 states have call successors, (17), 3 states have call predecessors, (17), 4 states have return successors, (16), 5 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-04 20:48:38,260 INFO L276 IsEmpty]: Start isEmpty. Operand 75 states and 84 transitions. [2024-11-04 20:48:38,260 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2024-11-04 20:48:38,260 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:38,261 INFO L215 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:38,271 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (11)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:38,461 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:38,461 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:38,462 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:38,462 INFO L85 PathProgramCache]: Analyzing trace with hash 306948351, now seen corresponding path program 1 times [2024-11-04 20:48:38,462 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:38,462 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [2133568073] [2024-11-04 20:48:38,462 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:38,462 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:38,462 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:38,463 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:38,464 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (12)] Waiting until timeout for monitored process [2024-11-04 20:48:38,621 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:38,623 INFO L255 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 20:48:38,625 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:38,699 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 18 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2024-11-04 20:48:38,699 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:38,793 INFO L134 CoverageAnalysis]: Checked inductivity of 39 backedges. 18 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2024-11-04 20:48:38,793 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:38,793 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [2133568073] [2024-11-04 20:48:38,793 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [2133568073] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:48:38,793 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:48:38,794 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5, 5] imperfect sequences [] total 5 [2024-11-04 20:48:38,794 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1225943896] [2024-11-04 20:48:38,794 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:38,794 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-04 20:48:38,794 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:38,795 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-04 20:48:38,795 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-04 20:48:38,795 INFO L87 Difference]: Start difference. First operand 75 states and 84 transitions. Second operand has 5 states, 5 states have (on average 6.8) internal successors, (34), 5 states have internal predecessors, (34), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 1 states have call successors, (8) [2024-11-04 20:48:38,830 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:38,830 INFO L93 Difference]: Finished difference Result 103 states and 115 transitions. [2024-11-04 20:48:38,830 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-04 20:48:38,831 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 6.8) internal successors, (34), 5 states have internal predecessors, (34), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 1 states have call successors, (8) Word has length 63 [2024-11-04 20:48:38,831 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:38,832 INFO L225 Difference]: With dead ends: 103 [2024-11-04 20:48:38,832 INFO L226 Difference]: Without dead ends: 66 [2024-11-04 20:48:38,832 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 124 GetRequests, 121 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2024-11-04 20:48:38,832 INFO L432 NwaCegarLoop]: 58 mSDtfsCounter, 3 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 193 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:38,833 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [7 Valid, 193 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:48:38,833 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2024-11-04 20:48:38,845 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 66. [2024-11-04 20:48:38,845 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 66 states, 44 states have (on average 1.0909090909090908) internal successors, (48), 46 states have internal predecessors, (48), 12 states have call successors, (12), 8 states have call predecessors, (12), 9 states have return successors, (12), 11 states have call predecessors, (12), 11 states have call successors, (12) [2024-11-04 20:48:38,845 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 66 states to 66 states and 72 transitions. [2024-11-04 20:48:38,846 INFO L78 Accepts]: Start accepts. Automaton has 66 states and 72 transitions. Word has length 63 [2024-11-04 20:48:38,846 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:38,846 INFO L471 AbstractCegarLoop]: Abstraction has 66 states and 72 transitions. [2024-11-04 20:48:38,846 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 6.8) internal successors, (34), 5 states have internal predecessors, (34), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 2 states have call predecessors, (8), 1 states have call successors, (8) [2024-11-04 20:48:38,846 INFO L276 IsEmpty]: Start isEmpty. Operand 66 states and 72 transitions. [2024-11-04 20:48:38,847 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2024-11-04 20:48:38,847 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:38,847 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:38,850 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (12)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:39,047 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:39,048 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:39,048 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:39,048 INFO L85 PathProgramCache]: Analyzing trace with hash 424365179, now seen corresponding path program 1 times [2024-11-04 20:48:39,048 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:39,048 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [274130721] [2024-11-04 20:48:39,048 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:39,049 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:39,049 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:39,050 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:39,051 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (13)] Waiting until timeout for monitored process [2024-11-04 20:48:39,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:39,374 INFO L255 TraceCheckSpWp]: Trace formula consists of 220 conjuncts, 48 conjuncts are in the unsatisfiable core [2024-11-04 20:48:39,378 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:39,386 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-04 20:48:39,392 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-04 20:48:39,397 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-04 20:48:39,407 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-04 20:48:41,577 INFO L349 Elim1Store]: treesize reduction 13, result has 48.0 percent of original size [2024-11-04 20:48:41,578 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 125 treesize of output 87 [2024-11-04 20:48:41,661 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 9 proven. 11 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-04 20:48:41,661 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:51,442 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 19 proven. 4 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2024-11-04 20:48:51,442 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:51,442 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [274130721] [2024-11-04 20:48:51,442 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [274130721] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 20:48:51,442 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 20:48:51,443 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 16] total 31 [2024-11-04 20:48:51,443 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1957711115] [2024-11-04 20:48:51,443 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 20:48:51,443 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2024-11-04 20:48:51,443 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:51,444 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2024-11-04 20:48:51,444 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=823, Unknown=2, NotChecked=0, Total=930 [2024-11-04 20:48:51,445 INFO L87 Difference]: Start difference. First operand 66 states and 72 transitions. Second operand has 31 states, 27 states have (on average 2.6296296296296298) internal successors, (71), 25 states have internal predecessors, (71), 10 states have call successors, (22), 4 states have call predecessors, (22), 6 states have return successors, (20), 10 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-04 20:48:53,531 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:53,532 INFO L93 Difference]: Finished difference Result 77 states and 83 transitions. [2024-11-04 20:48:53,532 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-04 20:48:53,532 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 27 states have (on average 2.6296296296296298) internal successors, (71), 25 states have internal predecessors, (71), 10 states have call successors, (22), 4 states have call predecessors, (22), 6 states have return successors, (20), 10 states have call predecessors, (20), 8 states have call successors, (20) Word has length 77 [2024-11-04 20:48:53,532 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:53,533 INFO L225 Difference]: With dead ends: 77 [2024-11-04 20:48:53,533 INFO L226 Difference]: Without dead ends: 75 [2024-11-04 20:48:53,534 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 157 GetRequests, 109 SyntacticMatches, 15 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 364 ImplicationChecksByTransitivity, 10.6s TimeCoverageRelationStatistics Valid=139, Invalid=1049, Unknown=2, NotChecked=0, Total=1190 [2024-11-04 20:48:53,534 INFO L432 NwaCegarLoop]: 35 mSDtfsCounter, 15 mSDsluCounter, 285 mSDsCounter, 0 mSdLazyCounter, 492 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 320 SdHoareTripleChecker+Invalid, 506 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 492 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:53,534 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [19 Valid, 320 Invalid, 506 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 492 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2024-11-04 20:48:53,535 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 75 states. [2024-11-04 20:48:53,552 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 75 to 74. [2024-11-04 20:48:53,552 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 49 states have (on average 1.0816326530612246) internal successors, (53), 52 states have internal predecessors, (53), 13 states have call successors, (13), 9 states have call predecessors, (13), 11 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) [2024-11-04 20:48:53,553 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 80 transitions. [2024-11-04 20:48:53,553 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 80 transitions. Word has length 77 [2024-11-04 20:48:53,553 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:53,553 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 80 transitions. [2024-11-04 20:48:53,554 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 27 states have (on average 2.6296296296296298) internal successors, (71), 25 states have internal predecessors, (71), 10 states have call successors, (22), 4 states have call predecessors, (22), 6 states have return successors, (20), 10 states have call predecessors, (20), 8 states have call successors, (20) [2024-11-04 20:48:53,554 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 80 transitions. [2024-11-04 20:48:53,554 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2024-11-04 20:48:53,554 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:53,554 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:53,562 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (13)] Ended with exit code 0 [2024-11-04 20:48:53,755 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:53,755 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:53,756 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:53,756 INFO L85 PathProgramCache]: Analyzing trace with hash -384981447, now seen corresponding path program 1 times [2024-11-04 20:48:53,756 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:53,756 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [48558245] [2024-11-04 20:48:53,756 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:53,756 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:53,756 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:53,757 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:53,758 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (14)] Waiting until timeout for monitored process [2024-11-04 20:48:54,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:54,022 INFO L255 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-04 20:48:54,025 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:54,032 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-04 20:48:54,040 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-04 20:48:54,050 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-04 20:48:54,267 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-11-04 20:48:54,271 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-04 20:48:55,076 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 14 proven. 14 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2024-11-04 20:48:55,076 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:55,503 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2024-11-04 20:48:55,503 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:55,503 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [48558245] [2024-11-04 20:48:55,503 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [48558245] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:55,503 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:55,503 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [13] total 21 [2024-11-04 20:48:55,503 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2068888298] [2024-11-04 20:48:55,504 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:55,504 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-04 20:48:55,504 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:55,505 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-04 20:48:55,505 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=352, Unknown=0, NotChecked=0, Total=420 [2024-11-04 20:48:55,505 INFO L87 Difference]: Start difference. First operand 74 states and 80 transitions. Second operand has 10 states, 10 states have (on average 3.5) internal successors, (35), 10 states have internal predecessors, (35), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-04 20:48:55,974 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:55,975 INFO L93 Difference]: Finished difference Result 86 states and 92 transitions. [2024-11-04 20:48:55,975 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2024-11-04 20:48:55,975 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.5) internal successors, (35), 10 states have internal predecessors, (35), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 3 states have call successors, (10) Word has length 77 [2024-11-04 20:48:55,976 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:55,976 INFO L225 Difference]: With dead ends: 86 [2024-11-04 20:48:55,976 INFO L226 Difference]: Without dead ends: 74 [2024-11-04 20:48:55,977 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 118 SyntacticMatches, 15 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 173 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=84, Invalid=468, Unknown=0, NotChecked=0, Total=552 [2024-11-04 20:48:55,977 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 10 mSDsluCounter, 150 mSDsCounter, 0 mSdLazyCounter, 231 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 198 SdHoareTripleChecker+Invalid, 235 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 231 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:55,977 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 198 Invalid, 235 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 231 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-04 20:48:55,978 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 74 states. [2024-11-04 20:48:55,995 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 74 to 74. [2024-11-04 20:48:55,996 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 49 states have (on average 1.0612244897959184) internal successors, (52), 52 states have internal predecessors, (52), 13 states have call successors, (13), 9 states have call predecessors, (13), 11 states have return successors, (14), 12 states have call predecessors, (14), 12 states have call successors, (14) [2024-11-04 20:48:55,996 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 79 transitions. [2024-11-04 20:48:55,996 INFO L78 Accepts]: Start accepts. Automaton has 74 states and 79 transitions. Word has length 77 [2024-11-04 20:48:55,997 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:55,997 INFO L471 AbstractCegarLoop]: Abstraction has 74 states and 79 transitions. [2024-11-04 20:48:55,997 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.5) internal successors, (35), 10 states have internal predecessors, (35), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-04 20:48:55,997 INFO L276 IsEmpty]: Start isEmpty. Operand 74 states and 79 transitions. [2024-11-04 20:48:55,997 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2024-11-04 20:48:55,997 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:55,998 INFO L215 NwaCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:56,004 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (14)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:56,198 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:56,198 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:56,199 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:56,199 INFO L85 PathProgramCache]: Analyzing trace with hash -778008457, now seen corresponding path program 1 times [2024-11-04 20:48:56,199 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:56,199 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [768630340] [2024-11-04 20:48:56,199 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:56,199 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:56,199 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:56,200 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:56,202 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (15)] Waiting until timeout for monitored process [2024-11-04 20:48:56,508 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:56,511 INFO L255 TraceCheckSpWp]: Trace formula consists of 212 conjuncts, 16 conjuncts are in the unsatisfiable core [2024-11-04 20:48:56,513 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:56,522 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-04 20:48:56,620 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 8 [2024-11-04 20:48:56,749 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 14 proven. 14 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2024-11-04 20:48:56,749 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:56,883 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2024-11-04 20:48:56,884 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:56,884 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [768630340] [2024-11-04 20:48:56,884 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [768630340] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:56,884 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:56,884 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 10 [2024-11-04 20:48:56,884 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [831223101] [2024-11-04 20:48:56,884 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:56,884 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 20:48:56,885 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:56,885 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 20:48:56,885 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2024-11-04 20:48:56,885 INFO L87 Difference]: Start difference. First operand 74 states and 79 transitions. Second operand has 8 states, 8 states have (on average 4.375) internal successors, (35), 8 states have internal predecessors, (35), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-04 20:48:57,057 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:57,058 INFO L93 Difference]: Finished difference Result 87 states and 91 transitions. [2024-11-04 20:48:57,058 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-04 20:48:57,058 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 4.375) internal successors, (35), 8 states have internal predecessors, (35), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 3 states have call successors, (10) Word has length 77 [2024-11-04 20:48:57,058 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:57,059 INFO L225 Difference]: With dead ends: 87 [2024-11-04 20:48:57,059 INFO L226 Difference]: Without dead ends: 63 [2024-11-04 20:48:57,059 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 153 GetRequests, 141 SyntacticMatches, 3 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2024-11-04 20:48:57,060 INFO L432 NwaCegarLoop]: 52 mSDtfsCounter, 4 mSDsluCounter, 261 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 313 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:57,060 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 313 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 20:48:57,061 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-11-04 20:48:57,073 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2024-11-04 20:48:57,074 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 42 states have (on average 1.0) internal successors, (42), 42 states have internal predecessors, (42), 12 states have call successors, (12), 9 states have call predecessors, (12), 8 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-04 20:48:57,074 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 65 transitions. [2024-11-04 20:48:57,074 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 65 transitions. Word has length 77 [2024-11-04 20:48:57,075 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:57,075 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 65 transitions. [2024-11-04 20:48:57,075 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 4.375) internal successors, (35), 8 states have internal predecessors, (35), 4 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (10), 4 states have call predecessors, (10), 3 states have call successors, (10) [2024-11-04 20:48:57,075 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 65 transitions. [2024-11-04 20:48:57,075 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2024-11-04 20:48:57,075 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:57,075 INFO L215 NwaCegarLoop]: trace histogram [6, 5, 5, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:57,081 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (15)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:57,276 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:57,276 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:57,276 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:57,276 INFO L85 PathProgramCache]: Analyzing trace with hash -814494378, now seen corresponding path program 1 times [2024-11-04 20:48:57,277 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:57,277 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [956081198] [2024-11-04 20:48:57,277 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:57,277 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:57,277 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:57,278 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:57,279 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (16)] Waiting until timeout for monitored process [2024-11-04 20:48:57,580 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:57,605 INFO L255 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-04 20:48:57,607 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:57,614 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-04 20:48:57,624 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-04 20:48:57,739 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-11-04 20:48:57,946 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 10 proven. 14 refuted. 0 times theorem prover too weak. 54 trivial. 0 not checked. [2024-11-04 20:48:57,946 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:58,270 INFO L134 CoverageAnalysis]: Checked inductivity of 78 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 68 trivial. 0 not checked. [2024-11-04 20:48:58,270 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:58,271 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [956081198] [2024-11-04 20:48:58,271 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [956081198] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:58,271 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:58,271 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 15 [2024-11-04 20:48:58,271 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1459156429] [2024-11-04 20:48:58,271 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:58,271 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 20:48:58,271 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:58,272 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 20:48:58,272 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2024-11-04 20:48:58,272 INFO L87 Difference]: Start difference. First operand 63 states and 65 transitions. Second operand has 8 states, 8 states have (on average 3.75) internal successors, (30), 7 states have internal predecessors, (30), 3 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-04 20:48:58,608 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:58,608 INFO L93 Difference]: Finished difference Result 63 states and 65 transitions. [2024-11-04 20:48:58,608 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-04 20:48:58,608 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 3.75) internal successors, (30), 7 states have internal predecessors, (30), 3 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 83 [2024-11-04 20:48:58,609 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:58,609 INFO L225 Difference]: With dead ends: 63 [2024-11-04 20:48:58,609 INFO L226 Difference]: Without dead ends: 0 [2024-11-04 20:48:58,609 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 166 GetRequests, 148 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=42, Invalid=230, Unknown=0, NotChecked=0, Total=272 [2024-11-04 20:48:58,610 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 3 mSDsluCounter, 206 mSDsCounter, 0 mSdLazyCounter, 77 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 3 SdHoareTripleChecker+Valid, 252 SdHoareTripleChecker+Invalid, 81 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 77 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:58,610 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [3 Valid, 252 Invalid, 81 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 77 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-04 20:48:58,610 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2024-11-04 20:48:58,610 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2024-11-04 20:48:58,611 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-04 20:48:58,611 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2024-11-04 20:48:58,611 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 83 [2024-11-04 20:48:58,611 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:58,611 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-04 20:48:58,611 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 3.75) internal successors, (30), 7 states have internal predecessors, (30), 3 states have call successors, (12), 2 states have call predecessors, (12), 1 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-04 20:48:58,611 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2024-11-04 20:48:58,611 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2024-11-04 20:48:58,614 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2024-11-04 20:48:58,620 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (16)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:58,814 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:58,817 INFO L407 BasicCegarLoop]: Path program histogram: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:58,819 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions.