/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_swap_contents_harness.i -------------------------------------------------------------------------------- This is Ultimate 0.2.5-dev-b75d321-m [2024-11-04 20:48:59,833 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-04 20:48:59,911 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:59,915 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-04 20:48:59,915 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-04 20:48:59,938 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-04 20:48:59,938 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-04 20:48:59,939 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-04 20:48:59,939 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-04 20:48:59,940 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-04 20:48:59,940 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-04 20:48:59,940 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-04 20:48:59,941 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-04 20:48:59,941 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-04 20:48:59,941 INFO L153 SettingsManager]: * Use SBE=true [2024-11-04 20:48:59,942 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-04 20:48:59,942 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-04 20:48:59,942 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-04 20:48:59,942 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-04 20:48:59,943 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-04 20:48:59,943 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-04 20:48:59,943 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-04 20:48:59,944 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-04 20:48:59,944 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-04 20:48:59,944 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-04 20:48:59,945 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-04 20:48:59,945 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-04 20:48:59,945 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-04 20:48:59,945 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-04 20:48:59,946 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-04 20:48:59,946 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-04 20:48:59,946 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 20:48:59,947 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-04 20:48:59,947 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-04 20:48:59,947 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-04 20:48:59,947 INFO L153 SettingsManager]: * Trace refinement strategy=WOLF [2024-11-04 20:48:59,947 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:59,948 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-04 20:48:59,948 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-04 20:48:59,948 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-04 20:48:59,948 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-04 20:48:59,949 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:49:00,172 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-04 20:49:00,200 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-04 20:49:00,205 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-04 20:49:00,207 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-04 20:49:00,208 INFO L274 PluginConnector]: CDTParser initialized [2024-11-04 20:49:00,209 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_swap_contents_harness.i [2024-11-04 20:49:01,680 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-04 20:49:02,066 INFO L384 CDTParser]: Found 1 translation units. [2024-11-04 20:49:02,067 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_swap_contents_harness.i [2024-11-04 20:49:02,093 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a48659f8a/8719aabbb52044ceac0e0cd0bc3fd449/FLAGaf994792d [2024-11-04 20:49:02,109 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/a48659f8a/8719aabbb52044ceac0e0cd0bc3fd449 [2024-11-04 20:49:02,111 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-04 20:49:02,112 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-11-04 20:49:02,113 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-04 20:49:02,113 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-04 20:49:02,121 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-04 20:49:02,121 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 08:49:02" (1/1) ... [2024-11-04 20:49:02,122 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@48a3914e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:02, skipping insertion in model container [2024-11-04 20:49:02,122 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 08:49:02" (1/1) ... [2024-11-04 20:49:02,213 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 20:49:02,493 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_swap_contents_harness.i[4503,4516] [2024-11-04 20:49:02,504 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_swap_contents_harness.i[4563,4576] [2024-11-04 20:49:03,396 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:49:03,513 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:49:03,513 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:49:03,514 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:49:03,523 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:49:03,525 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,526 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,526 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,527 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:49:03,527 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,528 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,531 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:49:03,531 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:49:03,533 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:49:03,534 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:49:03,546 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,547 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:49:03,547 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,548 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:49:03,549 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,550 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:49:03,550 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,550 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:49:03,552 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,553 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:49:03,554 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,554 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:49:03,555 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,555 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:03,811 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:49:03,811 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:49:03,812 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:49:03,812 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:49:03,916 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:49:03,941 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 20:49:03,971 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-04 20:49:04,010 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 20:49:04,016 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_swap_contents_harness.i[4503,4516] [2024-11-04 20:49:04,017 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_swap_contents_harness.i[4563,4576] [2024-11-04 20:49:04,052 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:49:04,073 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:49:04,073 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:49:04,074 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:49:04,088 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:49:04,093 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,094 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,094 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,094 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:49:04,095 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,095 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,099 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:49:04,100 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:49:04,101 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:49:04,102 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:49:04,117 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,117 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:49:04,118 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,118 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:49:04,119 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,123 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:49:04,123 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,123 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:49:04,125 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,125 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:49:04,125 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,126 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:49:04,126 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,128 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,190 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:49:04,191 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:49:04,192 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:49:04,192 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:49:04,231 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:49:04,242 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 20:49:04,253 INFO L200 MainTranslator]: Completed pre-run [2024-11-04 20:49:04,267 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_swap_contents_harness.i[4503,4516] [2024-11-04 20:49:04,267 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_swap_contents_harness.i[4563,4576] [2024-11-04 20:49:04,313 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,313 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,313 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,314 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,314 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,321 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,322 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,324 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,324 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,325 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,326 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,326 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,327 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:49:04,433 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 20:49:04,643 WARN L710 CHandler]: The following functions are not defined or handled internally: aws_array_list_ensure_capacity [2024-11-04 20:49:04,654 INFO L204 MainTranslator]: Completed translation [2024-11-04 20:49:04,654 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:04 WrapperNode [2024-11-04 20:49:04,654 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-04 20:49:04,657 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-04 20:49:04,657 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-04 20:49:04,657 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-04 20:49:04,665 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:49:04" (1/1) ... [2024-11-04 20:49:04,738 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:49:04" (1/1) ... [2024-11-04 20:49:04,793 INFO L138 Inliner]: procedures = 687, calls = 1078, calls flagged for inlining = 51, calls inlined = 5, statements flattened = 214 [2024-11-04 20:49:04,793 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-04 20:49:04,794 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-04 20:49:04,794 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-04 20:49:04,794 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-04 20:49:04,809 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:04" (1/1) ... [2024-11-04 20:49:04,809 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:04" (1/1) ... [2024-11-04 20:49:04,821 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:04" (1/1) ... [2024-11-04 20:49:04,849 INFO L175 MemorySlicer]: Split 68 memory accesses to 5 slices as follows [2, 5, 7, 7, 47]. 69 percent of accesses are in the largest equivalence class. The 15 initializations are split as follows [2, 5, 4, 4, 0]. The 18 writes are split as follows [0, 0, 0, 0, 18]. [2024-11-04 20:49:04,849 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:04" (1/1) ... [2024-11-04 20:49:04,850 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:04" (1/1) ... [2024-11-04 20:49:04,868 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:04" (1/1) ... [2024-11-04 20:49:04,871 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:04" (1/1) ... [2024-11-04 20:49:04,885 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:04" (1/1) ... [2024-11-04 20:49:04,892 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:04" (1/1) ... [2024-11-04 20:49:04,905 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-04 20:49:04,906 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-04 20:49:04,907 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-04 20:49:04,907 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-04 20:49:04,907 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:04" (1/1) ... [2024-11-04 20:49:04,912 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 20:49:04,925 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 20:49:04,941 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:49:04,947 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:49:04,970 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_init [2024-11-04 20:49:04,970 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_init [2024-11-04 20:49:04,970 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-04 20:49:04,970 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-04 20:49:04,971 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-04 20:49:04,971 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2024-11-04 20:49:04,971 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#3 [2024-11-04 20:49:04,971 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#4 [2024-11-04 20:49:04,971 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-04 20:49:04,971 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-04 20:49:04,971 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2024-11-04 20:49:04,971 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2024-11-04 20:49:04,972 INFO L130 BoogieDeclarations]: Found specification of procedure ensure_linked_list_is_allocated [2024-11-04 20:49:04,972 INFO L138 BoogieDeclarations]: Found implementation of procedure ensure_linked_list_is_allocated [2024-11-04 20:49:04,972 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-04 20:49:04,972 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2024-11-04 20:49:04,972 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2024-11-04 20:49:04,972 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-04 20:49:04,972 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-04 20:49:04,972 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-04 20:49:04,972 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2024-11-04 20:49:04,973 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#3 [2024-11-04 20:49:04,973 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#4 [2024-11-04 20:49:04,973 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-04 20:49:04,973 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-04 20:49:04,973 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_empty [2024-11-04 20:49:04,973 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_empty [2024-11-04 20:49:04,973 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-04 20:49:04,973 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-04 20:49:04,974 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-04 20:49:04,974 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-04 20:49:04,974 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-04 20:49:04,974 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2024-11-04 20:49:04,974 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#3 [2024-11-04 20:49:04,974 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#4 [2024-11-04 20:49:04,974 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2024-11-04 20:49:04,974 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2024-11-04 20:49:04,974 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2024-11-04 20:49:04,974 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#3 [2024-11-04 20:49:04,975 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#4 [2024-11-04 20:49:04,975 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2024-11-04 20:49:04,975 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2024-11-04 20:49:05,233 INFO L238 CfgBuilder]: Building ICFG [2024-11-04 20:49:05,234 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-04 20:49:06,475 INFO L? ?]: Removed 63 outVars from TransFormulas that were not future-live. [2024-11-04 20:49:06,475 INFO L287 CfgBuilder]: Performing block encoding [2024-11-04 20:49:06,494 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-04 20:49:06,495 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-04 20:49:06,496 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 08:49:06 BoogieIcfgContainer [2024-11-04 20:49:06,497 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-04 20:49:06,499 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-04 20:49:06,499 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-04 20:49:06,502 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-04 20:49:06,502 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 04.11 08:49:02" (1/3) ... [2024-11-04 20:49:06,503 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5dc74c59 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 08:49:06, skipping insertion in model container [2024-11-04 20:49:06,503 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:49:04" (2/3) ... [2024-11-04 20:49:06,503 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5dc74c59 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 08:49:06, skipping insertion in model container [2024-11-04 20:49:06,503 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 08:49:06" (3/3) ... [2024-11-04 20:49:06,505 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_swap_contents_harness.i [2024-11-04 20:49:06,521 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-04 20:49:06,521 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-04 20:49:06,610 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-04 20:49:06,617 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;@37f86c45, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-04 20:49:06,617 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-04 20:49:06,621 INFO L276 IsEmpty]: Start isEmpty. Operand has 114 states, 70 states have (on average 1.3) internal successors, (91), 73 states have internal predecessors, (91), 34 states have call successors, (34), 8 states have call predecessors, (34), 8 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) [2024-11-04 20:49:06,632 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 20:49:06,633 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:06,633 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 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, 1, 1, 1] [2024-11-04 20:49:06,634 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:06,639 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:06,640 INFO L85 PathProgramCache]: Analyzing trace with hash 408503669, now seen corresponding path program 1 times [2024-11-04 20:49:06,648 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:06,649 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [8122845] [2024-11-04 20:49:06,649 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:06,652 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:06,652 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:06,655 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:49:06,657 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:49:07,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:07,135 INFO L255 TraceCheckSpWp]: Trace formula consists of 404 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-04 20:49:07,145 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:07,186 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2024-11-04 20:49:07,186 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:07,295 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2024-11-04 20:49:07,296 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:07,296 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [8122845] [2024-11-04 20:49:07,296 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [8122845] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:49:07,297 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:49:07,297 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 2 [2024-11-04 20:49:07,298 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [697002524] [2024-11-04 20:49:07,299 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:07,302 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-04 20:49:07,302 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:07,317 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-04 20:49:07,318 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 20:49:07,319 INFO L87 Difference]: Start difference. First operand has 114 states, 70 states have (on average 1.3) internal successors, (91), 73 states have internal predecessors, (91), 34 states have call successors, (34), 8 states have call predecessors, (34), 8 states have return successors, (34), 34 states have call predecessors, (34), 34 states have call successors, (34) Second operand has 2 states, 2 states have (on average 23.0) internal successors, (46), 2 states have internal predecessors, (46), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-04 20:49:07,359 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:07,359 INFO L93 Difference]: Finished difference Result 225 states and 346 transitions. [2024-11-04 20:49:07,362 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-04 20:49:07,363 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 23.0) internal successors, (46), 2 states have internal predecessors, (46), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 101 [2024-11-04 20:49:07,364 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:07,373 INFO L225 Difference]: With dead ends: 225 [2024-11-04 20:49:07,373 INFO L226 Difference]: Without dead ends: 107 [2024-11-04 20:49:07,378 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 200 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:49:07,383 INFO L432 NwaCegarLoop]: 155 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, 155 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:49:07,384 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 155 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:49:07,401 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2024-11-04 20:49:07,421 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 107. [2024-11-04 20:49:07,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 107 states, 64 states have (on average 1.265625) internal successors, (81), 68 states have internal predecessors, (81), 34 states have call successors, (34), 8 states have call predecessors, (34), 8 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-04 20:49:07,424 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 107 states to 107 states and 147 transitions. [2024-11-04 20:49:07,426 INFO L78 Accepts]: Start accepts. Automaton has 107 states and 147 transitions. Word has length 101 [2024-11-04 20:49:07,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:07,428 INFO L471 AbstractCegarLoop]: Abstraction has 107 states and 147 transitions. [2024-11-04 20:49:07,429 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 23.0) internal successors, (46), 2 states have internal predecessors, (46), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-04 20:49:07,429 INFO L276 IsEmpty]: Start isEmpty. Operand 107 states and 147 transitions. [2024-11-04 20:49:07,433 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 20:49:07,433 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:07,433 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 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, 1, 1, 1] [2024-11-04 20:49:07,441 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:49:07,634 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:49:07,634 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:07,635 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:07,635 INFO L85 PathProgramCache]: Analyzing trace with hash 34190191, now seen corresponding path program 1 times [2024-11-04 20:49:07,635 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:07,635 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [919378537] [2024-11-04 20:49:07,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:07,636 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:07,636 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:07,637 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:49:07,638 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:49:08,003 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:08,010 INFO L255 TraceCheckSpWp]: Trace formula consists of 404 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 20:49:08,021 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:08,081 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 32 proven. 0 refuted. 0 times theorem prover too weak. 53 trivial. 0 not checked. [2024-11-04 20:49:08,082 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:08,213 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2024-11-04 20:49:08,214 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:08,214 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [919378537] [2024-11-04 20:49:08,214 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [919378537] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:08,214 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:08,214 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 20:49:08,214 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [47705166] [2024-11-04 20:49:08,215 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:08,216 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 20:49:08,216 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:08,218 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 20:49:08,219 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 20:49:08,219 INFO L87 Difference]: Start difference. First operand 107 states and 147 transitions. Second operand has 4 states, 4 states have (on average 10.25) internal successors, (41), 4 states have internal predecessors, (41), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 20:49:08,290 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:08,290 INFO L93 Difference]: Finished difference Result 198 states and 284 transitions. [2024-11-04 20:49:08,297 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 20:49:08,298 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 10.25) internal successors, (41), 4 states have internal predecessors, (41), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) Word has length 101 [2024-11-04 20:49:08,298 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:08,300 INFO L225 Difference]: With dead ends: 198 [2024-11-04 20:49:08,302 INFO L226 Difference]: Without dead ends: 110 [2024-11-04 20:49:08,303 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 198 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 20:49:08,304 INFO L432 NwaCegarLoop]: 144 mSDtfsCounter, 1 mSDsluCounter, 280 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 424 SdHoareTripleChecker+Invalid, 16 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:08,304 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 424 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:49:08,305 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states. [2024-11-04 20:49:08,319 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 109. [2024-11-04 20:49:08,320 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 109 states, 66 states have (on average 1.2575757575757576) internal successors, (83), 70 states have internal predecessors, (83), 34 states have call successors, (34), 8 states have call predecessors, (34), 8 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-04 20:49:08,322 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 109 states to 109 states and 149 transitions. [2024-11-04 20:49:08,322 INFO L78 Accepts]: Start accepts. Automaton has 109 states and 149 transitions. Word has length 101 [2024-11-04 20:49:08,324 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:08,324 INFO L471 AbstractCegarLoop]: Abstraction has 109 states and 149 transitions. [2024-11-04 20:49:08,324 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 10.25) internal successors, (41), 4 states have internal predecessors, (41), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 20:49:08,324 INFO L276 IsEmpty]: Start isEmpty. Operand 109 states and 149 transitions. [2024-11-04 20:49:08,326 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 20:49:08,326 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:08,326 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 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, 1, 1, 1] [2024-11-04 20:49:08,331 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:49:08,527 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:49:08,527 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:08,528 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:08,528 INFO L85 PathProgramCache]: Analyzing trace with hash 742326057, now seen corresponding path program 1 times [2024-11-04 20:49:08,528 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:08,528 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1077364743] [2024-11-04 20:49:08,528 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:08,529 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:08,529 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:08,532 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:49:08,533 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:49:08,891 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:08,898 INFO L255 TraceCheckSpWp]: Trace formula consists of 395 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-04 20:49:08,901 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:08,934 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 36 proven. 0 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2024-11-04 20:49:08,935 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:09,044 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2024-11-04 20:49:09,044 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:09,044 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1077364743] [2024-11-04 20:49:09,044 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1077364743] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:09,044 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:09,044 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 5 [2024-11-04 20:49:09,045 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [97432276] [2024-11-04 20:49:09,045 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:09,045 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-04 20:49:09,045 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:09,046 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-04 20:49:09,049 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-04 20:49:09,049 INFO L87 Difference]: Start difference. First operand 109 states and 149 transitions. Second operand has 5 states, 5 states have (on average 8.6) internal successors, (43), 5 states have internal predecessors, (43), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 20:49:09,111 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:09,112 INFO L93 Difference]: Finished difference Result 202 states and 288 transitions. [2024-11-04 20:49:09,112 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-04 20:49:09,112 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 8.6) internal successors, (43), 5 states have internal predecessors, (43), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) Word has length 101 [2024-11-04 20:49:09,113 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:09,114 INFO L225 Difference]: With dead ends: 202 [2024-11-04 20:49:09,114 INFO L226 Difference]: Without dead ends: 112 [2024-11-04 20:49:09,115 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 197 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-04 20:49:09,116 INFO L432 NwaCegarLoop]: 142 mSDtfsCounter, 1 mSDsluCounter, 415 mSDsCounter, 0 mSdLazyCounter, 28 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 557 SdHoareTripleChecker+Invalid, 30 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 28 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:09,116 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 557 Invalid, 30 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 28 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:49:09,117 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 112 states. [2024-11-04 20:49:09,132 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 112 to 111. [2024-11-04 20:49:09,133 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 111 states, 68 states have (on average 1.25) internal successors, (85), 72 states have internal predecessors, (85), 34 states have call successors, (34), 8 states have call predecessors, (34), 8 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-04 20:49:09,134 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 111 states to 111 states and 151 transitions. [2024-11-04 20:49:09,135 INFO L78 Accepts]: Start accepts. Automaton has 111 states and 151 transitions. Word has length 101 [2024-11-04 20:49:09,135 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:09,137 INFO L471 AbstractCegarLoop]: Abstraction has 111 states and 151 transitions. [2024-11-04 20:49:09,138 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 8.6) internal successors, (43), 5 states have internal predecessors, (43), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 20:49:09,138 INFO L276 IsEmpty]: Start isEmpty. Operand 111 states and 151 transitions. [2024-11-04 20:49:09,140 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 20:49:09,140 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:09,140 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 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, 1, 1, 1] [2024-11-04 20:49:09,148 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:49:09,340 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:49:09,341 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:09,341 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:09,341 INFO L85 PathProgramCache]: Analyzing trace with hash -588779165, now seen corresponding path program 1 times [2024-11-04 20:49:09,342 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:09,342 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1990705492] [2024-11-04 20:49:09,342 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:09,342 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:09,342 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:09,344 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:49:09,346 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:49:09,688 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:09,694 INFO L255 TraceCheckSpWp]: Trace formula consists of 386 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 20:49:09,698 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:09,750 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 40 proven. 0 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2024-11-04 20:49:09,751 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:09,855 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2024-11-04 20:49:09,855 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:09,855 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1990705492] [2024-11-04 20:49:09,855 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1990705492] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:09,855 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:09,855 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2024-11-04 20:49:09,856 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1696115481] [2024-11-04 20:49:09,856 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:09,856 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 20:49:09,856 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:09,857 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 20:49:09,857 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-04 20:49:09,858 INFO L87 Difference]: Start difference. First operand 111 states and 151 transitions. Second operand has 6 states, 6 states have (on average 7.5) internal successors, (45), 6 states have internal predecessors, (45), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 20:49:09,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:09,925 INFO L93 Difference]: Finished difference Result 206 states and 293 transitions. [2024-11-04 20:49:09,926 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 20:49:09,927 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 7.5) internal successors, (45), 6 states have internal predecessors, (45), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) Word has length 101 [2024-11-04 20:49:09,927 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:09,929 INFO L225 Difference]: With dead ends: 206 [2024-11-04 20:49:09,929 INFO L226 Difference]: Without dead ends: 114 [2024-11-04 20:49:09,930 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 196 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2024-11-04 20:49:09,930 INFO L432 NwaCegarLoop]: 140 mSDtfsCounter, 1 mSDsluCounter, 550 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 690 SdHoareTripleChecker+Invalid, 45 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:09,931 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 690 Invalid, 45 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:49:09,931 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2024-11-04 20:49:09,940 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 114. [2024-11-04 20:49:09,941 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 114 states, 71 states have (on average 1.2394366197183098) internal successors, (88), 75 states have internal predecessors, (88), 34 states have call successors, (34), 8 states have call predecessors, (34), 8 states have return successors, (32), 32 states have call predecessors, (32), 32 states have call successors, (32) [2024-11-04 20:49:09,944 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 114 states to 114 states and 154 transitions. [2024-11-04 20:49:09,944 INFO L78 Accepts]: Start accepts. Automaton has 114 states and 154 transitions. Word has length 101 [2024-11-04 20:49:09,945 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:09,945 INFO L471 AbstractCegarLoop]: Abstraction has 114 states and 154 transitions. [2024-11-04 20:49:09,945 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 7.5) internal successors, (45), 6 states have internal predecessors, (45), 2 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 2 states have call predecessors, (11), 2 states have call successors, (11) [2024-11-04 20:49:09,945 INFO L276 IsEmpty]: Start isEmpty. Operand 114 states and 154 transitions. [2024-11-04 20:49:09,946 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 20:49:09,947 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:09,947 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 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, 1, 1, 1] [2024-11-04 20:49:09,952 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:49:10,147 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:49:10,148 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:10,148 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:10,148 INFO L85 PathProgramCache]: Analyzing trace with hash 1908156957, now seen corresponding path program 1 times [2024-11-04 20:49:10,148 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:10,148 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1750570543] [2024-11-04 20:49:10,149 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:10,149 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:10,149 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:10,150 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:49:10,151 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:49:10,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:10,502 INFO L255 TraceCheckSpWp]: Trace formula consists of 377 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-04 20:49:10,505 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:10,584 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-04 20:49:10,585 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:10,756 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 20:49:10,757 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:10,757 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1750570543] [2024-11-04 20:49:10,757 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1750570543] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:10,757 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:10,757 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2024-11-04 20:49:10,757 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1369594469] [2024-11-04 20:49:10,757 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:10,758 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 20:49:10,758 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:10,758 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 20:49:10,758 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-04 20:49:10,759 INFO L87 Difference]: Start difference. First operand 114 states and 154 transitions. Second operand has 6 states, 5 states have (on average 9.4) internal successors, (47), 6 states have internal predecessors, (47), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 20:49:12,696 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:12,696 INFO L93 Difference]: Finished difference Result 216 states and 298 transitions. [2024-11-04 20:49:12,697 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 20:49:12,697 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 9.4) internal successors, (47), 6 states have internal predecessors, (47), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 101 [2024-11-04 20:49:12,698 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:12,701 INFO L225 Difference]: With dead ends: 216 [2024-11-04 20:49:12,701 INFO L226 Difference]: Without dead ends: 121 [2024-11-04 20:49:12,702 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 196 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2024-11-04 20:49:12,702 INFO L432 NwaCegarLoop]: 134 mSDtfsCounter, 28 mSDsluCounter, 469 mSDsCounter, 0 mSdLazyCounter, 65 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 39 SdHoareTripleChecker+Valid, 603 SdHoareTripleChecker+Invalid, 93 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 65 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.9s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:12,703 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [39 Valid, 603 Invalid, 93 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 65 Invalid, 0 Unknown, 0 Unchecked, 1.9s Time] [2024-11-04 20:49:12,703 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2024-11-04 20:49:12,720 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 121. [2024-11-04 20:49:12,721 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 77 states have (on average 1.2207792207792207) internal successors, (94), 82 states have internal predecessors, (94), 34 states have call successors, (34), 8 states have call predecessors, (34), 9 states have return successors, (36), 32 states have call predecessors, (36), 32 states have call successors, (36) [2024-11-04 20:49:12,722 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 164 transitions. [2024-11-04 20:49:12,723 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 164 transitions. Word has length 101 [2024-11-04 20:49:12,725 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:12,726 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 164 transitions. [2024-11-04 20:49:12,726 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 9.4) internal successors, (47), 6 states have internal predecessors, (47), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 20:49:12,726 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 164 transitions. [2024-11-04 20:49:12,727 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 20:49:12,727 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:12,728 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:49:12,734 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (6)] Forceful destruction successful, exit code 0 [2024-11-04 20:49:12,928 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:49:12,929 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:12,929 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:12,929 INFO L85 PathProgramCache]: Analyzing trace with hash -1786984915, now seen corresponding path program 1 times [2024-11-04 20:49:12,929 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:12,929 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [487414254] [2024-11-04 20:49:12,929 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:12,930 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:12,930 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:12,931 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:49:12,932 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:49:13,241 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:13,247 INFO L255 TraceCheckSpWp]: Trace formula consists of 401 conjuncts, 7 conjuncts are in the unsatisfiable core [2024-11-04 20:49:13,250 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:13,349 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 56 proven. 0 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2024-11-04 20:49:13,350 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:13,518 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 10 proven. 10 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 20:49:13,519 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:13,519 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [487414254] [2024-11-04 20:49:13,519 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [487414254] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:13,519 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:13,519 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 6 [2024-11-04 20:49:13,519 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [198017236] [2024-11-04 20:49:13,520 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:13,520 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 20:49:13,520 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:13,521 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 20:49:13,521 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2024-11-04 20:49:13,521 INFO L87 Difference]: Start difference. First operand 121 states and 164 transitions. Second operand has 6 states, 6 states have (on average 9.5) internal successors, (57), 6 states have internal predecessors, (57), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 20:49:15,302 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:15,303 INFO L93 Difference]: Finished difference Result 220 states and 299 transitions. [2024-11-04 20:49:15,304 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 20:49:15,304 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 9.5) internal successors, (57), 6 states have internal predecessors, (57), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) Word has length 101 [2024-11-04 20:49:15,304 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:15,306 INFO L225 Difference]: With dead ends: 220 [2024-11-04 20:49:15,306 INFO L226 Difference]: Without dead ends: 121 [2024-11-04 20:49:15,306 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 201 GetRequests, 196 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2024-11-04 20:49:15,307 INFO L432 NwaCegarLoop]: 139 mSDtfsCounter, 27 mSDsluCounter, 349 mSDsCounter, 0 mSdLazyCounter, 35 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 488 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 35 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.7s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:15,307 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 488 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 35 Invalid, 0 Unknown, 0 Unchecked, 1.7s Time] [2024-11-04 20:49:15,308 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2024-11-04 20:49:15,317 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 121. [2024-11-04 20:49:15,317 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 121 states, 77 states have (on average 1.2207792207792207) internal successors, (94), 82 states have internal predecessors, (94), 34 states have call successors, (34), 8 states have call predecessors, (34), 9 states have return successors, (33), 32 states have call predecessors, (33), 32 states have call successors, (33) [2024-11-04 20:49:15,318 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 121 states to 121 states and 161 transitions. [2024-11-04 20:49:15,319 INFO L78 Accepts]: Start accepts. Automaton has 121 states and 161 transitions. Word has length 101 [2024-11-04 20:49:15,319 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:15,319 INFO L471 AbstractCegarLoop]: Abstraction has 121 states and 161 transitions. [2024-11-04 20:49:15,319 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 9.5) internal successors, (57), 6 states have internal predecessors, (57), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 4 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 20:49:15,320 INFO L276 IsEmpty]: Start isEmpty. Operand 121 states and 161 transitions. [2024-11-04 20:49:15,320 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 102 [2024-11-04 20:49:15,320 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:15,321 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 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, 1, 1, 1] [2024-11-04 20:49:15,327 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (7)] Ended with exit code 0 [2024-11-04 20:49:15,521 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:49:15,521 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:15,522 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:15,522 INFO L85 PathProgramCache]: Analyzing trace with hash -1879544267, now seen corresponding path program 1 times [2024-11-04 20:49:15,522 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:15,522 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1478241247] [2024-11-04 20:49:15,522 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:15,522 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:15,522 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:15,525 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:49:15,526 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:49:16,036 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:16,059 INFO L255 TraceCheckSpWp]: Trace formula consists of 413 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 20:49:16,062 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:16,090 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 52 proven. 0 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2024-11-04 20:49:16,091 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:16,211 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-11-04 20:49:16,212 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:16,212 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1478241247] [2024-11-04 20:49:16,212 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1478241247] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:16,212 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:16,212 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2024-11-04 20:49:16,212 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [323717463] [2024-11-04 20:49:16,212 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:16,213 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 20:49:16,213 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:16,213 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 20:49:16,214 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 20:49:16,214 INFO L87 Difference]: Start difference. First operand 121 states and 161 transitions. Second operand has 6 states, 5 states have (on average 10.0) internal successors, (50), 5 states have internal predecessors, (50), 3 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-04 20:49:16,298 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:16,298 INFO L93 Difference]: Finished difference Result 225 states and 307 transitions. [2024-11-04 20:49:16,298 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 20:49:16,299 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 10.0) internal successors, (50), 5 states have internal predecessors, (50), 3 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) Word has length 101 [2024-11-04 20:49:16,299 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:16,300 INFO L225 Difference]: With dead ends: 225 [2024-11-04 20:49:16,301 INFO L226 Difference]: Without dead ends: 123 [2024-11-04 20:49:16,301 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 200 GetRequests, 195 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 20:49:16,302 INFO L432 NwaCegarLoop]: 141 mSDtfsCounter, 0 mSDsluCounter, 546 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 687 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:16,302 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 687 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 20:49:16,303 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 123 states. [2024-11-04 20:49:16,319 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 123 to 123. [2024-11-04 20:49:16,319 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 123 states, 78 states have (on average 1.2179487179487178) internal successors, (95), 84 states have internal predecessors, (95), 34 states have call successors, (34), 8 states have call predecessors, (34), 10 states have return successors, (39), 32 states have call predecessors, (39), 32 states have call successors, (39) [2024-11-04 20:49:16,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 123 states to 123 states and 168 transitions. [2024-11-04 20:49:16,321 INFO L78 Accepts]: Start accepts. Automaton has 123 states and 168 transitions. Word has length 101 [2024-11-04 20:49:16,325 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:16,325 INFO L471 AbstractCegarLoop]: Abstraction has 123 states and 168 transitions. [2024-11-04 20:49:16,325 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 10.0) internal successors, (50), 5 states have internal predecessors, (50), 3 states have call successors, (12), 2 states have call predecessors, (12), 4 states have return successors, (11), 3 states have call predecessors, (11), 3 states have call successors, (11) [2024-11-04 20:49:16,325 INFO L276 IsEmpty]: Start isEmpty. Operand 123 states and 168 transitions. [2024-11-04 20:49:16,326 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 104 [2024-11-04 20:49:16,326 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:16,326 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1] [2024-11-04 20:49:16,337 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:49:16,527 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:49:16,527 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:16,528 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:16,528 INFO L85 PathProgramCache]: Analyzing trace with hash 574804529, now seen corresponding path program 1 times [2024-11-04 20:49:16,528 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:16,528 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1245036789] [2024-11-04 20:49:16,528 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:16,528 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:16,529 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:16,531 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:49:16,532 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:49:16,863 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:16,868 INFO L255 TraceCheckSpWp]: Trace formula consists of 420 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-04 20:49:16,870 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:16,954 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-04 20:49:16,955 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:17,157 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 20:49:17,159 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:17,160 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1245036789] [2024-11-04 20:49:17,160 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1245036789] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:17,160 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:17,160 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2024-11-04 20:49:17,160 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1993534469] [2024-11-04 20:49:17,160 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:17,161 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 20:49:17,161 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:17,161 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 20:49:17,161 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-04 20:49:17,161 INFO L87 Difference]: Start difference. First operand 123 states and 168 transitions. Second operand has 7 states, 6 states have (on average 8.166666666666666) internal successors, (49), 7 states have internal predecessors, (49), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 20:49:20,661 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:20,661 INFO L93 Difference]: Finished difference Result 232 states and 324 transitions. [2024-11-04 20:49:20,662 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 20:49:20,663 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 8.166666666666666) internal successors, (49), 7 states have internal predecessors, (49), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 103 [2024-11-04 20:49:20,663 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:20,664 INFO L225 Difference]: With dead ends: 232 [2024-11-04 20:49:20,664 INFO L226 Difference]: Without dead ends: 128 [2024-11-04 20:49:20,665 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 205 GetRequests, 197 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-11-04 20:49:20,666 INFO L432 NwaCegarLoop]: 127 mSDtfsCounter, 41 mSDsluCounter, 546 mSDsCounter, 0 mSdLazyCounter, 151 mSolverCounterSat, 34 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 673 SdHoareTripleChecker+Invalid, 185 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 34 IncrementalHoareTripleChecker+Valid, 151 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.5s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:20,666 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 673 Invalid, 185 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [34 Valid, 151 Invalid, 0 Unknown, 0 Unchecked, 3.5s Time] [2024-11-04 20:49:20,668 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states. [2024-11-04 20:49:20,682 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 126. [2024-11-04 20:49:20,682 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 80 states have (on average 1.2125) internal successors, (97), 87 states have internal predecessors, (97), 34 states have call successors, (34), 8 states have call predecessors, (34), 11 states have return successors, (43), 32 states have call predecessors, (43), 32 states have call successors, (43) [2024-11-04 20:49:20,685 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 174 transitions. [2024-11-04 20:49:20,686 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 174 transitions. Word has length 103 [2024-11-04 20:49:20,686 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:20,686 INFO L471 AbstractCegarLoop]: Abstraction has 126 states and 174 transitions. [2024-11-04 20:49:20,686 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 8.166666666666666) internal successors, (49), 7 states have internal predecessors, (49), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 20:49:20,686 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 174 transitions. [2024-11-04 20:49:20,687 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 106 [2024-11-04 20:49:20,687 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:20,687 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:49:20,694 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:49:20,888 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:49:20,888 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:20,888 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:20,889 INFO L85 PathProgramCache]: Analyzing trace with hash 1835480350, now seen corresponding path program 1 times [2024-11-04 20:49:20,889 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:20,889 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1747996797] [2024-11-04 20:49:20,889 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:20,889 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:20,889 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:20,890 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:49:20,892 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:49:21,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:21,211 INFO L255 TraceCheckSpWp]: Trace formula consists of 424 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-04 20:49:21,214 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:21,316 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-04 20:49:21,316 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:21,535 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 20:49:21,535 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:21,535 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1747996797] [2024-11-04 20:49:21,535 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1747996797] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:21,535 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:21,536 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 11 [2024-11-04 20:49:21,536 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2058865712] [2024-11-04 20:49:21,536 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:21,536 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 20:49:21,536 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:21,537 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 20:49:21,537 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-11-04 20:49:21,537 INFO L87 Difference]: Start difference. First operand 126 states and 174 transitions. Second operand has 8 states, 7 states have (on average 7.285714285714286) internal successors, (51), 8 states have internal predecessors, (51), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 20:49:25,244 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:25,244 INFO L93 Difference]: Finished difference Result 244 states and 346 transitions. [2024-11-04 20:49:25,245 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-04 20:49:25,245 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 7.285714285714286) internal successors, (51), 8 states have internal predecessors, (51), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 105 [2024-11-04 20:49:25,245 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:25,247 INFO L225 Difference]: With dead ends: 244 [2024-11-04 20:49:25,247 INFO L226 Difference]: Without dead ends: 137 [2024-11-04 20:49:25,248 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 199 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2024-11-04 20:49:25,248 INFO L432 NwaCegarLoop]: 125 mSDtfsCounter, 50 mSDsluCounter, 653 mSDsCounter, 0 mSdLazyCounter, 206 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 778 SdHoareTripleChecker+Invalid, 243 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 206 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.7s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:25,249 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 778 Invalid, 243 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 206 Invalid, 0 Unknown, 0 Unchecked, 3.7s Time] [2024-11-04 20:49:25,249 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2024-11-04 20:49:25,260 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 128. [2024-11-04 20:49:25,261 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 128 states, 82 states have (on average 1.2195121951219512) internal successors, (100), 89 states have internal predecessors, (100), 34 states have call successors, (34), 8 states have call predecessors, (34), 11 states have return successors, (43), 32 states have call predecessors, (43), 32 states have call successors, (43) [2024-11-04 20:49:25,262 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 128 states to 128 states and 177 transitions. [2024-11-04 20:49:25,262 INFO L78 Accepts]: Start accepts. Automaton has 128 states and 177 transitions. Word has length 105 [2024-11-04 20:49:25,263 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:25,263 INFO L471 AbstractCegarLoop]: Abstraction has 128 states and 177 transitions. [2024-11-04 20:49:25,263 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 7.285714285714286) internal successors, (51), 8 states have internal predecessors, (51), 4 states have call successors, (12), 2 states have call predecessors, (12), 3 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 20:49:25,263 INFO L276 IsEmpty]: Start isEmpty. Operand 128 states and 177 transitions. [2024-11-04 20:49:25,265 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 107 [2024-11-04 20:49:25,265 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:25,265 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:49:25,272 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (10)] Ended with exit code 0 [2024-11-04 20:49:25,465 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:49:25,466 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:25,466 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:25,466 INFO L85 PathProgramCache]: Analyzing trace with hash 2014676356, now seen corresponding path program 1 times [2024-11-04 20:49:25,466 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:25,466 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [980140957] [2024-11-04 20:49:25,466 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:25,467 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:25,467 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:25,468 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:49:25,469 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:49:25,809 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:25,820 INFO L255 TraceCheckSpWp]: Trace formula consists of 426 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-04 20:49:25,824 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:25,920 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2024-11-04 20:49:25,920 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:26,028 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2024-11-04 20:49:26,029 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:26,029 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [980140957] [2024-11-04 20:49:26,029 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [980140957] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:26,029 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:26,029 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [3] total 8 [2024-11-04 20:49:26,029 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [625291447] [2024-11-04 20:49:26,030 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:26,030 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 20:49:26,030 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:26,031 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 20:49:26,031 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:49:26,031 INFO L87 Difference]: Start difference. First operand 128 states and 177 transitions. Second operand has 7 states, 6 states have (on average 8.5) internal successors, (51), 7 states have internal predecessors, (51), 4 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 20:49:26,907 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:26,907 INFO L93 Difference]: Finished difference Result 250 states and 359 transitions. [2024-11-04 20:49:26,908 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 20:49:26,908 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 8.5) internal successors, (51), 7 states have internal predecessors, (51), 4 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) Word has length 106 [2024-11-04 20:49:26,908 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:26,910 INFO L225 Difference]: With dead ends: 250 [2024-11-04 20:49:26,910 INFO L226 Difference]: Without dead ends: 141 [2024-11-04 20:49:26,912 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 211 GetRequests, 204 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-04 20:49:26,912 INFO L432 NwaCegarLoop]: 124 mSDtfsCounter, 42 mSDsluCounter, 540 mSDsCounter, 0 mSdLazyCounter, 152 mSolverCounterSat, 28 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 55 SdHoareTripleChecker+Valid, 664 SdHoareTripleChecker+Invalid, 180 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 28 IncrementalHoareTripleChecker+Valid, 152 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.8s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:26,913 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [55 Valid, 664 Invalid, 180 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [28 Valid, 152 Invalid, 0 Unknown, 0 Unchecked, 0.8s Time] [2024-11-04 20:49:26,914 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 141 states. [2024-11-04 20:49:26,930 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 141 to 129. [2024-11-04 20:49:26,931 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 129 states, 83 states have (on average 1.216867469879518) internal successors, (101), 90 states have internal predecessors, (101), 34 states have call successors, (34), 8 states have call predecessors, (34), 11 states have return successors, (43), 32 states have call predecessors, (43), 32 states have call successors, (43) [2024-11-04 20:49:26,932 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 178 transitions. [2024-11-04 20:49:26,933 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 178 transitions. Word has length 106 [2024-11-04 20:49:26,933 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:26,933 INFO L471 AbstractCegarLoop]: Abstraction has 129 states and 178 transitions. [2024-11-04 20:49:26,933 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 8.5) internal successors, (51), 7 states have internal predecessors, (51), 4 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (11), 3 states have call predecessors, (11), 4 states have call successors, (11) [2024-11-04 20:49:26,933 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 178 transitions. [2024-11-04 20:49:26,934 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2024-11-04 20:49:26,934 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:26,935 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:49:26,943 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (11)] Ended with exit code 0 [2024-11-04 20:49:27,135 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:49:27,135 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:27,136 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:27,136 INFO L85 PathProgramCache]: Analyzing trace with hash -1966687324, now seen corresponding path program 1 times [2024-11-04 20:49:27,136 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:27,136 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1961297363] [2024-11-04 20:49:27,136 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:27,137 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:27,137 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:27,138 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:49:27,139 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:49:27,567 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:27,576 INFO L255 TraceCheckSpWp]: Trace formula consists of 443 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 20:49:27,579 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:27,612 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2024-11-04 20:49:27,612 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:27,722 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 81 trivial. 0 not checked. [2024-11-04 20:49:27,722 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:27,722 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1961297363] [2024-11-04 20:49:27,722 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1961297363] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:27,722 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:27,723 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 20:49:27,723 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2081826361] [2024-11-04 20:49:27,723 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:27,723 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 20:49:27,723 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:27,724 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 20:49:27,724 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 20:49:27,724 INFO L87 Difference]: Start difference. First operand 129 states and 178 transitions. Second operand has 4 states, 4 states have (on average 14.25) internal successors, (57), 4 states have internal predecessors, (57), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-04 20:49:27,757 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:27,757 INFO L93 Difference]: Finished difference Result 242 states and 347 transitions. [2024-11-04 20:49:27,758 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 20:49:27,758 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 14.25) internal successors, (57), 4 states have internal predecessors, (57), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) Word has length 114 [2024-11-04 20:49:27,758 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:27,761 INFO L225 Difference]: With dead ends: 242 [2024-11-04 20:49:27,761 INFO L226 Difference]: Without dead ends: 132 [2024-11-04 20:49:27,762 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 226 GetRequests, 224 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 20:49:27,763 INFO L432 NwaCegarLoop]: 144 mSDtfsCounter, 1 mSDsluCounter, 284 mSDsCounter, 0 mSdLazyCounter, 11 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 428 SdHoareTripleChecker+Invalid, 12 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 11 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:27,763 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 428 Invalid, 12 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 11 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:49:27,764 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2024-11-04 20:49:27,775 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 131. [2024-11-04 20:49:27,775 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 131 states, 85 states have (on average 1.2117647058823529) internal successors, (103), 92 states have internal predecessors, (103), 34 states have call successors, (34), 8 states have call predecessors, (34), 11 states have return successors, (43), 32 states have call predecessors, (43), 32 states have call successors, (43) [2024-11-04 20:49:27,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 131 states to 131 states and 180 transitions. [2024-11-04 20:49:27,777 INFO L78 Accepts]: Start accepts. Automaton has 131 states and 180 transitions. Word has length 114 [2024-11-04 20:49:27,777 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:27,777 INFO L471 AbstractCegarLoop]: Abstraction has 131 states and 180 transitions. [2024-11-04 20:49:27,777 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 14.25) internal successors, (57), 4 states have internal predecessors, (57), 2 states have call successors, (13), 2 states have call predecessors, (13), 2 states have return successors, (12), 2 states have call predecessors, (12), 2 states have call successors, (12) [2024-11-04 20:49:27,777 INFO L276 IsEmpty]: Start isEmpty. Operand 131 states and 180 transitions. [2024-11-04 20:49:27,779 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2024-11-04 20:49:27,779 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:27,779 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:49:27,784 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:49:27,983 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:49:27,983 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:27,984 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:27,984 INFO L85 PathProgramCache]: Analyzing trace with hash -1764863390, now seen corresponding path program 1 times [2024-11-04 20:49:27,984 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:27,984 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1182091103] [2024-11-04 20:49:27,984 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:27,984 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:27,984 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:27,986 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:49:27,987 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:49:28,322 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:28,327 INFO L255 TraceCheckSpWp]: Trace formula consists of 438 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-04 20:49:28,331 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:28,479 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2024-11-04 20:49:28,480 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:28,783 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2024-11-04 20:49:28,784 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:28,784 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1182091103] [2024-11-04 20:49:28,784 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1182091103] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:28,784 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:28,784 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [10] total 13 [2024-11-04 20:49:28,784 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [324325592] [2024-11-04 20:49:28,784 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:28,785 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-04 20:49:28,785 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:28,785 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-04 20:49:28,785 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2024-11-04 20:49:28,786 INFO L87 Difference]: Start difference. First operand 131 states and 180 transitions. Second operand has 10 states, 9 states have (on average 6.444444444444445) internal successors, (58), 10 states have internal predecessors, (58), 5 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-04 20:49:32,888 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:32,889 INFO L93 Difference]: Finished difference Result 264 states and 373 transitions. [2024-11-04 20:49:32,889 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-04 20:49:32,890 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 9 states have (on average 6.444444444444445) internal successors, (58), 10 states have internal predecessors, (58), 5 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) Word has length 114 [2024-11-04 20:49:32,890 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:32,892 INFO L225 Difference]: With dead ends: 264 [2024-11-04 20:49:32,892 INFO L226 Difference]: Without dead ends: 152 [2024-11-04 20:49:32,893 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 230 GetRequests, 215 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=57, Invalid=215, Unknown=0, NotChecked=0, Total=272 [2024-11-04 20:49:32,893 INFO L432 NwaCegarLoop]: 125 mSDtfsCounter, 62 mSDsluCounter, 770 mSDsCounter, 0 mSdLazyCounter, 272 mSolverCounterSat, 45 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 77 SdHoareTripleChecker+Valid, 895 SdHoareTripleChecker+Invalid, 317 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 45 IncrementalHoareTripleChecker+Valid, 272 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:32,893 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [77 Valid, 895 Invalid, 317 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [45 Valid, 272 Invalid, 0 Unknown, 0 Unchecked, 4.0s Time] [2024-11-04 20:49:32,894 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 152 states. [2024-11-04 20:49:32,902 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 152 to 139. [2024-11-04 20:49:32,903 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 90 states have (on average 1.2333333333333334) internal successors, (111), 99 states have internal predecessors, (111), 36 states have call successors, (36), 8 states have call predecessors, (36), 12 states have return successors, (48), 33 states have call predecessors, (48), 34 states have call successors, (48) [2024-11-04 20:49:32,904 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 195 transitions. [2024-11-04 20:49:32,904 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 195 transitions. Word has length 114 [2024-11-04 20:49:32,905 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:32,905 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 195 transitions. [2024-11-04 20:49:32,905 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 9 states have (on average 6.444444444444445) internal successors, (58), 10 states have internal predecessors, (58), 5 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 4 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-04 20:49:32,905 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 195 transitions. [2024-11-04 20:49:32,906 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 115 [2024-11-04 20:49:32,906 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:32,906 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:49:32,912 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:49:33,107 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:49:33,108 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:33,108 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:33,108 INFO L85 PathProgramCache]: Analyzing trace with hash 1649007718, now seen corresponding path program 1 times [2024-11-04 20:49:33,108 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:33,109 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [580117686] [2024-11-04 20:49:33,109 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:33,109 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:33,109 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:33,111 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:49:33,113 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:49:33,801 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:33,807 INFO L255 TraceCheckSpWp]: Trace formula consists of 446 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 20:49:33,809 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:33,847 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 52 proven. 0 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2024-11-04 20:49:33,847 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:33,997 INFO L134 CoverageAnalysis]: Checked inductivity of 85 backedges. 6 proven. 10 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2024-11-04 20:49:33,997 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:33,997 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [580117686] [2024-11-04 20:49:33,998 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [580117686] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:33,998 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:33,998 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 8 [2024-11-04 20:49:33,998 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [936195965] [2024-11-04 20:49:33,998 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:33,998 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 20:49:33,999 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:33,999 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 20:49:33,999 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:49:33,999 INFO L87 Difference]: Start difference. First operand 139 states and 195 transitions. Second operand has 7 states, 6 states have (on average 10.166666666666666) internal successors, (61), 6 states have internal predecessors, (61), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-04 20:49:34,133 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:34,133 INFO L93 Difference]: Finished difference Result 265 states and 382 transitions. [2024-11-04 20:49:34,133 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 20:49:34,134 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 10.166666666666666) internal successors, (61), 6 states have internal predecessors, (61), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 114 [2024-11-04 20:49:34,134 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:34,135 INFO L225 Difference]: With dead ends: 265 [2024-11-04 20:49:34,135 INFO L226 Difference]: Without dead ends: 145 [2024-11-04 20:49:34,136 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 226 GetRequests, 220 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:49:34,137 INFO L432 NwaCegarLoop]: 140 mSDtfsCounter, 0 mSDsluCounter, 679 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 819 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:34,137 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 819 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 20:49:34,137 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 145 states. [2024-11-04 20:49:34,145 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 145 to 140. [2024-11-04 20:49:34,146 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 91 states have (on average 1.2307692307692308) internal successors, (112), 100 states have internal predecessors, (112), 36 states have call successors, (36), 8 states have call predecessors, (36), 12 states have return successors, (48), 33 states have call predecessors, (48), 34 states have call successors, (48) [2024-11-04 20:49:34,147 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 196 transitions. [2024-11-04 20:49:34,147 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 196 transitions. Word has length 114 [2024-11-04 20:49:34,148 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:34,148 INFO L471 AbstractCegarLoop]: Abstraction has 140 states and 196 transitions. [2024-11-04 20:49:34,148 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 10.166666666666666) internal successors, (61), 6 states have internal predecessors, (61), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-04 20:49:34,148 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 196 transitions. [2024-11-04 20:49:34,149 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-11-04 20:49:34,149 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:34,149 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:49:34,162 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (14)] Ended with exit code 0 [2024-11-04 20:49:34,349 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:49:34,350 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:34,350 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:34,350 INFO L85 PathProgramCache]: Analyzing trace with hash -942373357, now seen corresponding path program 1 times [2024-11-04 20:49:34,350 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:34,350 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1542245657] [2024-11-04 20:49:34,350 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:34,350 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:34,351 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:34,352 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:49:34,353 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:49:34,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:34,980 INFO L255 TraceCheckSpWp]: Trace formula consists of 450 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 20:49:34,982 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:35,014 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 49 proven. 0 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2024-11-04 20:49:35,014 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:35,128 INFO L134 CoverageAnalysis]: Checked inductivity of 86 backedges. 11 proven. 5 refuted. 0 times theorem prover too weak. 70 trivial. 0 not checked. [2024-11-04 20:49:35,129 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:35,129 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1542245657] [2024-11-04 20:49:35,129 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1542245657] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:35,129 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:35,129 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2024-11-04 20:49:35,129 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [533240471] [2024-11-04 20:49:35,129 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:35,130 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 20:49:35,130 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:35,130 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 20:49:35,130 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 20:49:35,131 INFO L87 Difference]: Start difference. First operand 140 states and 196 transitions. Second operand has 6 states, 5 states have (on average 13.0) internal successors, (65), 5 states have internal predecessors, (65), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-04 20:49:35,215 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:35,216 INFO L93 Difference]: Finished difference Result 260 states and 369 transitions. [2024-11-04 20:49:35,216 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 20:49:35,217 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 13.0) internal successors, (65), 5 states have internal predecessors, (65), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 116 [2024-11-04 20:49:35,217 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:35,219 INFO L225 Difference]: With dead ends: 260 [2024-11-04 20:49:35,219 INFO L226 Difference]: Without dead ends: 142 [2024-11-04 20:49:35,219 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 230 GetRequests, 225 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 20:49:35,220 INFO L432 NwaCegarLoop]: 141 mSDtfsCounter, 0 mSDsluCounter, 546 mSDsCounter, 0 mSdLazyCounter, 44 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 687 SdHoareTripleChecker+Invalid, 44 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 44 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:35,220 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 687 Invalid, 44 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 44 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 20:49:35,222 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 142 states. [2024-11-04 20:49:35,231 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 142 to 142. [2024-11-04 20:49:35,231 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 92 states have (on average 1.2282608695652173) internal successors, (113), 102 states have internal predecessors, (113), 36 states have call successors, (36), 8 states have call predecessors, (36), 13 states have return successors, (53), 33 states have call predecessors, (53), 34 states have call successors, (53) [2024-11-04 20:49:35,233 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 202 transitions. [2024-11-04 20:49:35,233 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 202 transitions. Word has length 116 [2024-11-04 20:49:35,233 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:35,233 INFO L471 AbstractCegarLoop]: Abstraction has 142 states and 202 transitions. [2024-11-04 20:49:35,234 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 13.0) internal successors, (65), 5 states have internal predecessors, (65), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-04 20:49:35,234 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 202 transitions. [2024-11-04 20:49:35,234 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2024-11-04 20:49:35,235 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:35,236 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:49:35,247 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (15)] Ended with exit code 0 [2024-11-04 20:49:35,436 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:49:35,436 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:35,437 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:35,437 INFO L85 PathProgramCache]: Analyzing trace with hash 1560559311, now seen corresponding path program 1 times [2024-11-04 20:49:35,437 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:35,437 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [380391632] [2024-11-04 20:49:35,437 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:35,437 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:35,437 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:35,438 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:49:35,440 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:49:35,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:35,809 INFO L255 TraceCheckSpWp]: Trace formula consists of 457 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-04 20:49:35,812 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:35,901 INFO L134 CoverageAnalysis]: Checked inductivity of 88 backedges. 58 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-04 20:49:35,901 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:36,057 INFO L134 CoverageAnalysis]: Checked inductivity of 88 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-04 20:49:36,058 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:36,058 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [380391632] [2024-11-04 20:49:36,058 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [380391632] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:36,058 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:36,058 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2024-11-04 20:49:36,058 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1940408237] [2024-11-04 20:49:36,058 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:36,058 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 20:49:36,059 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:36,059 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 20:49:36,059 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-04 20:49:36,059 INFO L87 Difference]: Start difference. First operand 142 states and 202 transitions. Second operand has 7 states, 7 states have (on average 10.285714285714286) internal successors, (72), 7 states have internal predecessors, (72), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-04 20:49:39,618 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:39,619 INFO L93 Difference]: Finished difference Result 269 states and 384 transitions. [2024-11-04 20:49:39,620 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 20:49:39,620 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 10.285714285714286) internal successors, (72), 7 states have internal predecessors, (72), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 118 [2024-11-04 20:49:39,620 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:39,622 INFO L225 Difference]: With dead ends: 269 [2024-11-04 20:49:39,622 INFO L226 Difference]: Without dead ends: 149 [2024-11-04 20:49:39,623 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 235 GetRequests, 227 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=23, Invalid=67, Unknown=0, NotChecked=0, Total=90 [2024-11-04 20:49:39,623 INFO L432 NwaCegarLoop]: 130 mSDtfsCounter, 40 mSDsluCounter, 555 mSDsCounter, 0 mSdLazyCounter, 126 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 685 SdHoareTripleChecker+Invalid, 152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 126 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.5s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:39,624 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 685 Invalid, 152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 126 Invalid, 0 Unknown, 0 Unchecked, 3.5s Time] [2024-11-04 20:49:39,624 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2024-11-04 20:49:39,631 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 143. [2024-11-04 20:49:39,632 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 143 states, 93 states have (on average 1.2258064516129032) internal successors, (114), 103 states have internal predecessors, (114), 36 states have call successors, (36), 8 states have call predecessors, (36), 13 states have return successors, (53), 33 states have call predecessors, (53), 34 states have call successors, (53) [2024-11-04 20:49:39,633 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 143 states to 143 states and 203 transitions. [2024-11-04 20:49:39,634 INFO L78 Accepts]: Start accepts. Automaton has 143 states and 203 transitions. Word has length 118 [2024-11-04 20:49:39,634 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:39,634 INFO L471 AbstractCegarLoop]: Abstraction has 143 states and 203 transitions. [2024-11-04 20:49:39,634 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 10.285714285714286) internal successors, (72), 7 states have internal predecessors, (72), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-04 20:49:39,634 INFO L276 IsEmpty]: Start isEmpty. Operand 143 states and 203 transitions. [2024-11-04 20:49:39,635 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 121 [2024-11-04 20:49:39,635 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:39,635 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:49:39,642 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (16)] Ended with exit code 0 [2024-11-04 20:49:39,836 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:49:39,836 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:39,836 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:39,836 INFO L85 PathProgramCache]: Analyzing trace with hash 718606524, now seen corresponding path program 2 times [2024-11-04 20:49:39,836 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:39,837 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [356067385] [2024-11-04 20:49:39,837 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:39,837 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:39,837 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:39,838 INFO L229 MonitoredProcess]: Starting monitored process 17 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:49:39,839 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (17)] Waiting until timeout for monitored process [2024-11-04 20:49:40,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:40,236 INFO L255 TraceCheckSpWp]: Trace formula consists of 461 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-04 20:49:40,239 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:40,312 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 61 proven. 0 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-04 20:49:40,313 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:40,466 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2024-11-04 20:49:40,466 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:40,466 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [356067385] [2024-11-04 20:49:40,466 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [356067385] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:40,466 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:40,466 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 11 [2024-11-04 20:49:40,466 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [996789662] [2024-11-04 20:49:40,467 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:40,467 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 20:49:40,467 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:40,467 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 20:49:40,467 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-11-04 20:49:40,468 INFO L87 Difference]: Start difference. First operand 143 states and 203 transitions. Second operand has 8 states, 8 states have (on average 9.25) internal successors, (74), 8 states have internal predecessors, (74), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-04 20:49:44,541 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:44,541 INFO L93 Difference]: Finished difference Result 278 states and 395 transitions. [2024-11-04 20:49:44,542 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-04 20:49:44,542 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 9.25) internal successors, (74), 8 states have internal predecessors, (74), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) Word has length 120 [2024-11-04 20:49:44,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:44,544 INFO L225 Difference]: With dead ends: 278 [2024-11-04 20:49:44,544 INFO L226 Difference]: Without dead ends: 157 [2024-11-04 20:49:44,545 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 242 GetRequests, 230 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=42, Invalid=140, Unknown=0, NotChecked=0, Total=182 [2024-11-04 20:49:44,546 INFO L432 NwaCegarLoop]: 128 mSDtfsCounter, 49 mSDsluCounter, 663 mSDsCounter, 0 mSdLazyCounter, 175 mSolverCounterSat, 29 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 62 SdHoareTripleChecker+Valid, 791 SdHoareTripleChecker+Invalid, 204 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 29 IncrementalHoareTripleChecker+Valid, 175 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:44,546 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [62 Valid, 791 Invalid, 204 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [29 Valid, 175 Invalid, 0 Unknown, 0 Unchecked, 4.0s Time] [2024-11-04 20:49:44,546 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2024-11-04 20:49:44,554 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 144. [2024-11-04 20:49:44,555 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 94 states have (on average 1.2234042553191489) internal successors, (115), 104 states have internal predecessors, (115), 36 states have call successors, (36), 8 states have call predecessors, (36), 13 states have return successors, (53), 33 states have call predecessors, (53), 34 states have call successors, (53) [2024-11-04 20:49:44,556 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 204 transitions. [2024-11-04 20:49:44,557 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 204 transitions. Word has length 120 [2024-11-04 20:49:44,557 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:44,557 INFO L471 AbstractCegarLoop]: Abstraction has 144 states and 204 transitions. [2024-11-04 20:49:44,557 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 9.25) internal successors, (74), 8 states have internal predecessors, (74), 4 states have call successors, (13), 2 states have call predecessors, (13), 3 states have return successors, (12), 4 states have call predecessors, (12), 4 states have call successors, (12) [2024-11-04 20:49:44,557 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 204 transitions. [2024-11-04 20:49:44,558 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2024-11-04 20:49:44,558 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:44,558 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:49:44,566 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (17)] Ended with exit code 0 [2024-11-04 20:49:44,759 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:44,759 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:44,760 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:44,760 INFO L85 PathProgramCache]: Analyzing trace with hash 634885234, now seen corresponding path program 1 times [2024-11-04 20:49:44,760 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:44,760 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1176385530] [2024-11-04 20:49:44,760 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:44,760 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:44,760 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:44,763 INFO L229 MonitoredProcess]: Starting monitored process 18 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:49:44,764 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (18)] Waiting until timeout for monitored process [2024-11-04 20:49:45,421 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:45,428 INFO L255 TraceCheckSpWp]: Trace formula consists of 483 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 20:49:45,430 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:45,477 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 50 proven. 0 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2024-11-04 20:49:45,477 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:45,596 INFO L134 CoverageAnalysis]: Checked inductivity of 100 backedges. 12 proven. 5 refuted. 0 times theorem prover too weak. 83 trivial. 0 not checked. [2024-11-04 20:49:45,596 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:45,596 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1176385530] [2024-11-04 20:49:45,597 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1176385530] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:45,597 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:45,597 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 8 [2024-11-04 20:49:45,597 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [890122853] [2024-11-04 20:49:45,597 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:45,597 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 20:49:45,598 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:45,598 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 20:49:45,598 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:49:45,598 INFO L87 Difference]: Start difference. First operand 144 states and 204 transitions. Second operand has 7 states, 6 states have (on average 11.0) internal successors, (66), 6 states have internal predecessors, (66), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-04 20:49:45,678 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:45,678 INFO L93 Difference]: Finished difference Result 272 states and 387 transitions. [2024-11-04 20:49:45,679 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 20:49:45,679 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 11.0) internal successors, (66), 6 states have internal predecessors, (66), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) Word has length 129 [2024-11-04 20:49:45,679 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:45,681 INFO L225 Difference]: With dead ends: 272 [2024-11-04 20:49:45,681 INFO L226 Difference]: Without dead ends: 150 [2024-11-04 20:49:45,682 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 256 GetRequests, 250 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:49:45,682 INFO L432 NwaCegarLoop]: 140 mSDtfsCounter, 0 mSDsluCounter, 679 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 819 SdHoareTripleChecker+Invalid, 59 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:45,683 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 819 Invalid, 59 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 20:49:45,683 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 150 states. [2024-11-04 20:49:45,692 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 150 to 145. [2024-11-04 20:49:45,692 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 145 states, 95 states have (on average 1.2210526315789474) internal successors, (116), 105 states have internal predecessors, (116), 36 states have call successors, (36), 8 states have call predecessors, (36), 13 states have return successors, (50), 33 states have call predecessors, (50), 34 states have call successors, (50) [2024-11-04 20:49:45,693 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 145 states to 145 states and 202 transitions. [2024-11-04 20:49:45,694 INFO L78 Accepts]: Start accepts. Automaton has 145 states and 202 transitions. Word has length 129 [2024-11-04 20:49:45,694 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:45,694 INFO L471 AbstractCegarLoop]: Abstraction has 145 states and 202 transitions. [2024-11-04 20:49:45,694 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 11.0) internal successors, (66), 6 states have internal predecessors, (66), 3 states have call successors, (13), 2 states have call predecessors, (13), 4 states have return successors, (12), 3 states have call predecessors, (12), 3 states have call successors, (12) [2024-11-04 20:49:45,694 INFO L276 IsEmpty]: Start isEmpty. Operand 145 states and 202 transitions. [2024-11-04 20:49:45,695 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2024-11-04 20:49:45,695 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:45,695 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:49:45,706 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (18)] Ended with exit code 0 [2024-11-04 20:49:45,896 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:45,896 INFO L396 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:45,897 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:45,897 INFO L85 PathProgramCache]: Analyzing trace with hash 82933659, now seen corresponding path program 1 times [2024-11-04 20:49:45,897 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:45,897 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [662025836] [2024-11-04 20:49:45,897 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:45,897 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:45,897 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:45,899 INFO L229 MonitoredProcess]: Starting monitored process 19 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:49:45,901 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (19)] Waiting until timeout for monitored process [2024-11-04 20:49:46,341 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:46,345 INFO L255 TraceCheckSpWp]: Trace formula consists of 479 conjuncts, 12 conjuncts are in the unsatisfiable core [2024-11-04 20:49:46,348 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:46,472 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 72 proven. 1 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2024-11-04 20:49:46,472 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:46,747 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 27 proven. 10 refuted. 0 times theorem prover too weak. 67 trivial. 0 not checked. [2024-11-04 20:49:46,747 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:46,747 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [662025836] [2024-11-04 20:49:46,747 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [662025836] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 20:49:46,747 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 20:49:46,747 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 13 [2024-11-04 20:49:46,748 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1871517378] [2024-11-04 20:49:46,748 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 20:49:46,748 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-04 20:49:46,748 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:46,749 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-04 20:49:46,749 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2024-11-04 20:49:46,749 INFO L87 Difference]: Start difference. First operand 145 states and 202 transitions. Second operand has 13 states, 13 states have (on average 7.615384615384615) internal successors, (99), 13 states have internal predecessors, (99), 6 states have call successors, (19), 2 states have call predecessors, (19), 4 states have return successors, (18), 5 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-04 20:49:49,731 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.10s for a HTC check with result INVALID. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [] [2024-11-04 20:49:52,317 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:52,317 INFO L93 Difference]: Finished difference Result 281 states and 394 transitions. [2024-11-04 20:49:52,318 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-04 20:49:52,318 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 7.615384615384615) internal successors, (99), 13 states have internal predecessors, (99), 6 states have call successors, (19), 2 states have call predecessors, (19), 4 states have return successors, (18), 5 states have call predecessors, (18), 6 states have call successors, (18) Word has length 131 [2024-11-04 20:49:52,318 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:52,320 INFO L225 Difference]: With dead ends: 281 [2024-11-04 20:49:52,320 INFO L226 Difference]: Without dead ends: 158 [2024-11-04 20:49:52,321 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 267 GetRequests, 252 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=57, Invalid=215, Unknown=0, NotChecked=0, Total=272 [2024-11-04 20:49:52,322 INFO L432 NwaCegarLoop]: 128 mSDtfsCounter, 84 mSDsluCounter, 914 mSDsCounter, 0 mSdLazyCounter, 270 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 98 SdHoareTripleChecker+Valid, 1042 SdHoareTripleChecker+Invalid, 312 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 270 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.5s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:52,323 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [98 Valid, 1042 Invalid, 312 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 270 Invalid, 0 Unknown, 0 Unchecked, 5.5s Time] [2024-11-04 20:49:52,323 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2024-11-04 20:49:52,329 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 138. [2024-11-04 20:49:52,330 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 90 states have (on average 1.2333333333333334) internal successors, (111), 98 states have internal predecessors, (111), 36 states have call successors, (36), 8 states have call predecessors, (36), 11 states have return successors, (43), 33 states have call predecessors, (43), 34 states have call successors, (43) [2024-11-04 20:49:52,331 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 190 transitions. [2024-11-04 20:49:52,331 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 190 transitions. Word has length 131 [2024-11-04 20:49:52,333 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:52,333 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 190 transitions. [2024-11-04 20:49:52,333 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 7.615384615384615) internal successors, (99), 13 states have internal predecessors, (99), 6 states have call successors, (19), 2 states have call predecessors, (19), 4 states have return successors, (18), 5 states have call predecessors, (18), 6 states have call successors, (18) [2024-11-04 20:49:52,333 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 190 transitions. [2024-11-04 20:49:52,334 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2024-11-04 20:49:52,334 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:52,334 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1] [2024-11-04 20:49:52,342 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (19)] Ended with exit code 0 [2024-11-04 20:49:52,535 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:52,535 INFO L396 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:52,535 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:52,535 INFO L85 PathProgramCache]: Analyzing trace with hash 204048799, now seen corresponding path program 3 times [2024-11-04 20:49:52,536 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:52,536 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [260659230] [2024-11-04 20:49:52,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:52,536 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:52,536 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:52,537 INFO L229 MonitoredProcess]: Starting monitored process 20 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:49:52,538 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (20)] Waiting until timeout for monitored process [2024-11-04 20:49:53,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:53,235 INFO L255 TraceCheckSpWp]: Trace formula consists of 487 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-04 20:49:53,239 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:53,285 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 11 treesize of output 7 [2024-11-04 20:49:53,290 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 11 treesize of output 7 [2024-11-04 20:49:53,679 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 57 proven. 1 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2024-11-04 20:49:53,679 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:54,230 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 1 proven. 15 refuted. 0 times theorem prover too weak. 88 trivial. 0 not checked. [2024-11-04 20:49:54,230 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:54,230 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [260659230] [2024-11-04 20:49:54,230 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [260659230] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 20:49:54,231 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 20:49:54,231 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 8] total 18 [2024-11-04 20:49:54,231 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1810958986] [2024-11-04 20:49:54,231 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 20:49:54,231 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-04 20:49:54,231 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:54,232 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-04 20:49:54,232 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=264, Unknown=0, NotChecked=0, Total=306 [2024-11-04 20:49:54,232 INFO L87 Difference]: Start difference. First operand 138 states and 190 transitions. Second operand has 18 states, 17 states have (on average 6.235294117647059) internal successors, (106), 16 states have internal predecessors, (106), 5 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (24), 5 states have call predecessors, (24), 5 states have call successors, (24) [2024-11-04 20:49:58,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:58,659 INFO L93 Difference]: Finished difference Result 294 states and 427 transitions. [2024-11-04 20:49:58,659 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-04 20:49:58,660 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 6.235294117647059) internal successors, (106), 16 states have internal predecessors, (106), 5 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (24), 5 states have call predecessors, (24), 5 states have call successors, (24) Word has length 131 [2024-11-04 20:49:58,660 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:58,662 INFO L225 Difference]: With dead ends: 294 [2024-11-04 20:49:58,662 INFO L226 Difference]: Without dead ends: 175 [2024-11-04 20:49:58,664 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 280 GetRequests, 253 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 75 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=111, Invalid=701, Unknown=0, NotChecked=0, Total=812 [2024-11-04 20:49:58,664 INFO L432 NwaCegarLoop]: 128 mSDtfsCounter, 63 mSDsluCounter, 1471 mSDsCounter, 0 mSdLazyCounter, 622 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 74 SdHoareTripleChecker+Valid, 1599 SdHoareTripleChecker+Invalid, 662 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 622 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:58,664 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [74 Valid, 1599 Invalid, 662 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 622 Invalid, 0 Unknown, 0 Unchecked, 4.0s Time] [2024-11-04 20:49:58,665 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 175 states. [2024-11-04 20:49:58,676 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 175 to 145. [2024-11-04 20:49:58,676 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 145 states, 96 states have (on average 1.2291666666666667) internal successors, (118), 103 states have internal predecessors, (118), 36 states have call successors, (36), 8 states have call predecessors, (36), 12 states have return successors, (46), 35 states have call predecessors, (46), 34 states have call successors, (46) [2024-11-04 20:49:58,677 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 145 states to 145 states and 200 transitions. [2024-11-04 20:49:58,678 INFO L78 Accepts]: Start accepts. Automaton has 145 states and 200 transitions. Word has length 131 [2024-11-04 20:49:58,678 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:58,678 INFO L471 AbstractCegarLoop]: Abstraction has 145 states and 200 transitions. [2024-11-04 20:49:58,678 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 6.235294117647059) internal successors, (106), 16 states have internal predecessors, (106), 5 states have call successors, (24), 2 states have call predecessors, (24), 3 states have return successors, (24), 5 states have call predecessors, (24), 5 states have call successors, (24) [2024-11-04 20:49:58,678 INFO L276 IsEmpty]: Start isEmpty. Operand 145 states and 200 transitions. [2024-11-04 20:49:58,680 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2024-11-04 20:49:58,680 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:58,680 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1] [2024-11-04 20:49:58,692 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (20)] Ended with exit code 0 [2024-11-04 20:49:58,880 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:58,880 INFO L396 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:58,881 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:58,881 INFO L85 PathProgramCache]: Analyzing trace with hash -1818273441, now seen corresponding path program 1 times [2024-11-04 20:49:58,881 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:58,881 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [144997065] [2024-11-04 20:49:58,881 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:58,881 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:58,881 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:58,882 INFO L229 MonitoredProcess]: Starting monitored process 21 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:49:58,883 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (21)] Waiting until timeout for monitored process [2024-11-04 20:49:59,353 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:59,359 INFO L255 TraceCheckSpWp]: Trace formula consists of 477 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-04 20:49:59,361 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:59,379 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 56 proven. 0 refuted. 0 times theorem prover too weak. 48 trivial. 0 not checked. [2024-11-04 20:49:59,379 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:59,467 INFO L134 CoverageAnalysis]: Checked inductivity of 104 backedges. 1 proven. 12 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2024-11-04 20:49:59,468 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:59,468 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [144997065] [2024-11-04 20:49:59,468 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [144997065] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:49:59,468 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:49:59,468 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 5 [2024-11-04 20:49:59,468 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [525434975] [2024-11-04 20:49:59,468 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:59,468 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-04 20:49:59,469 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:59,469 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-04 20:49:59,469 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-04 20:49:59,469 INFO L87 Difference]: Start difference. First operand 145 states and 200 transitions. Second operand has 5 states, 5 states have (on average 14.0) internal successors, (70), 4 states have internal predecessors, (70), 2 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 3 states have call predecessors, (13), 2 states have call successors, (13) [2024-11-04 20:49:59,499 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:59,499 INFO L93 Difference]: Finished difference Result 264 states and 378 transitions. [2024-11-04 20:49:59,500 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-04 20:49:59,500 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 14.0) internal successors, (70), 4 states have internal predecessors, (70), 2 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 3 states have call predecessors, (13), 2 states have call successors, (13) Word has length 131 [2024-11-04 20:49:59,500 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:59,502 INFO L225 Difference]: With dead ends: 264 [2024-11-04 20:49:59,502 INFO L226 Difference]: Without dead ends: 138 [2024-11-04 20:49:59,503 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 260 GetRequests, 257 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-04 20:49:59,503 INFO L432 NwaCegarLoop]: 144 mSDtfsCounter, 0 mSDsluCounter, 426 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 570 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:59,503 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 570 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:49:59,504 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2024-11-04 20:49:59,511 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 138. [2024-11-04 20:49:59,511 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 90 states have (on average 1.1777777777777778) internal successors, (106), 97 states have internal predecessors, (106), 35 states have call successors, (35), 8 states have call predecessors, (35), 12 states have return successors, (43), 34 states have call predecessors, (43), 33 states have call successors, (43) [2024-11-04 20:49:59,512 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 184 transitions. [2024-11-04 20:49:59,513 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 184 transitions. Word has length 131 [2024-11-04 20:49:59,513 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:59,513 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 184 transitions. [2024-11-04 20:49:59,513 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 14.0) internal successors, (70), 4 states have internal predecessors, (70), 2 states have call successors, (14), 2 states have call predecessors, (14), 3 states have return successors, (13), 3 states have call predecessors, (13), 2 states have call successors, (13) [2024-11-04 20:49:59,514 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 184 transitions. [2024-11-04 20:49:59,514 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 134 [2024-11-04 20:49:59,514 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:59,515 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1] [2024-11-04 20:49:59,522 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (21)] Ended with exit code 0 [2024-11-04 20:49:59,715 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:59,715 INFO L396 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:59,716 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:59,716 INFO L85 PathProgramCache]: Analyzing trace with hash -883566423, now seen corresponding path program 1 times [2024-11-04 20:49:59,716 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:59,716 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [772845537] [2024-11-04 20:49:59,716 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:59,716 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:59,716 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:59,717 INFO L229 MonitoredProcess]: Starting monitored process 22 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:49:59,718 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (22)] Waiting until timeout for monitored process [2024-11-04 20:50:00,496 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:50:00,505 INFO L255 TraceCheckSpWp]: Trace formula consists of 491 conjuncts, 25 conjuncts are in the unsatisfiable core [2024-11-04 20:50:00,508 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:50:00,533 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 11 treesize of output 7 [2024-11-04 20:50:01,602 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 7 treesize of output 3 [2024-11-04 20:50:01,608 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:50:01,667 INFO L134 CoverageAnalysis]: Checked inductivity of 109 backedges. 46 proven. 33 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2024-11-04 20:50:01,667 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:50:02,017 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-04 20:50:02,018 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 29 [2024-11-04 20:50:02,406 INFO L134 CoverageAnalysis]: Checked inductivity of 109 backedges. 0 proven. 35 refuted. 0 times theorem prover too weak. 74 trivial. 0 not checked. [2024-11-04 20:50:02,406 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:50:02,406 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [772845537] [2024-11-04 20:50:02,406 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [772845537] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 20:50:02,406 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 20:50:02,406 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 18 [2024-11-04 20:50:02,406 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2013313327] [2024-11-04 20:50:02,406 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 20:50:02,407 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-04 20:50:02,407 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:50:02,408 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-04 20:50:02,408 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=258, Unknown=0, NotChecked=0, Total=306 [2024-11-04 20:50:02,408 INFO L87 Difference]: Start difference. First operand 138 states and 184 transitions. Second operand has 18 states, 17 states have (on average 7.235294117647059) internal successors, (123), 18 states have internal predecessors, (123), 11 states have call successors, (24), 3 states have call predecessors, (24), 4 states have return successors, (23), 10 states have call predecessors, (23), 11 states have call successors, (23) [2024-11-04 20:50:11,087 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:50:11,087 INFO L93 Difference]: Finished difference Result 393 states and 533 transitions. [2024-11-04 20:50:11,088 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-04 20:50:11,088 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 7.235294117647059) internal successors, (123), 18 states have internal predecessors, (123), 11 states have call successors, (24), 3 states have call predecessors, (24), 4 states have return successors, (23), 10 states have call predecessors, (23), 11 states have call successors, (23) Word has length 133 [2024-11-04 20:50:11,088 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:50:11,091 INFO L225 Difference]: With dead ends: 393 [2024-11-04 20:50:11,091 INFO L226 Difference]: Without dead ends: 281 [2024-11-04 20:50:11,092 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 282 GetRequests, 249 SyntacticMatches, 5 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 161 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=136, Invalid=734, Unknown=0, NotChecked=0, Total=870 [2024-11-04 20:50:11,093 INFO L432 NwaCegarLoop]: 182 mSDtfsCounter, 133 mSDsluCounter, 1422 mSDsCounter, 0 mSdLazyCounter, 975 mSolverCounterSat, 75 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 145 SdHoareTripleChecker+Valid, 1604 SdHoareTripleChecker+Invalid, 1050 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 75 IncrementalHoareTripleChecker+Valid, 975 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 8.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:50:11,093 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [145 Valid, 1604 Invalid, 1050 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [75 Valid, 975 Invalid, 0 Unknown, 0 Unchecked, 8.1s Time] [2024-11-04 20:50:11,094 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 281 states. [2024-11-04 20:50:11,114 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 281 to 240. [2024-11-04 20:50:11,114 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 240 states, 159 states have (on average 1.1886792452830188) internal successors, (189), 170 states have internal predecessors, (189), 59 states have call successors, (59), 14 states have call predecessors, (59), 21 states have return successors, (78), 58 states have call predecessors, (78), 55 states have call successors, (78) [2024-11-04 20:50:11,116 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 240 states to 240 states and 326 transitions. [2024-11-04 20:50:11,117 INFO L78 Accepts]: Start accepts. Automaton has 240 states and 326 transitions. Word has length 133 [2024-11-04 20:50:11,117 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:50:11,117 INFO L471 AbstractCegarLoop]: Abstraction has 240 states and 326 transitions. [2024-11-04 20:50:11,117 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 7.235294117647059) internal successors, (123), 18 states have internal predecessors, (123), 11 states have call successors, (24), 3 states have call predecessors, (24), 4 states have return successors, (23), 10 states have call predecessors, (23), 11 states have call successors, (23) [2024-11-04 20:50:11,117 INFO L276 IsEmpty]: Start isEmpty. Operand 240 states and 326 transitions. [2024-11-04 20:50:11,118 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 145 [2024-11-04 20:50:11,118 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:50:11,119 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1] [2024-11-04 20:50:11,133 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (22)] Ended with exit code 0 [2024-11-04 20:50:11,319 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 22 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:50:11,319 INFO L396 AbstractCegarLoop]: === Iteration 22 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:50:11,320 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:50:11,320 INFO L85 PathProgramCache]: Analyzing trace with hash -249505762, now seen corresponding path program 2 times [2024-11-04 20:50:11,320 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:50:11,320 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1384337002] [2024-11-04 20:50:11,320 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:50:11,320 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:50:11,320 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:50:11,321 INFO L229 MonitoredProcess]: Starting monitored process 23 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:50:11,322 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (23)] Waiting until timeout for monitored process [2024-11-04 20:50:12,788 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:50:12,801 INFO L255 TraceCheckSpWp]: Trace formula consists of 517 conjuncts, 34 conjuncts are in the unsatisfiable core [2024-11-04 20:50:12,806 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:50:12,902 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 34 [2024-11-04 20:50:12,913 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 25 [2024-11-04 20:50:12,918 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 16 treesize of output 1 [2024-11-04 20:50:13,971 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 75 proven. 8 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2024-11-04 20:50:13,972 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:50:14,562 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-04 20:50:14,562 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 29 [2024-11-04 20:50:15,144 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 29 proven. 12 refuted. 0 times theorem prover too weak. 94 trivial. 0 not checked. [2024-11-04 20:50:15,144 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:50:15,145 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1384337002] [2024-11-04 20:50:15,145 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1384337002] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 20:50:15,145 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 20:50:15,145 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 11] total 25 [2024-11-04 20:50:15,145 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [642175397] [2024-11-04 20:50:15,145 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 20:50:15,146 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-04 20:50:15,146 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:50:15,146 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-04 20:50:15,147 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=534, Unknown=0, NotChecked=0, Total=600 [2024-11-04 20:50:15,147 INFO L87 Difference]: Start difference. First operand 240 states and 326 transitions. Second operand has 25 states, 24 states have (on average 4.666666666666667) internal successors, (112), 22 states have internal predecessors, (112), 13 states have call successors, (28), 3 states have call predecessors, (28), 6 states have return successors, (27), 14 states have call predecessors, (27), 13 states have call successors, (27) [2024-11-04 20:50:27,727 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:50:27,728 INFO L93 Difference]: Finished difference Result 712 states and 966 transitions. [2024-11-04 20:50:27,730 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2024-11-04 20:50:27,730 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 24 states have (on average 4.666666666666667) internal successors, (112), 22 states have internal predecessors, (112), 13 states have call successors, (28), 3 states have call predecessors, (28), 6 states have return successors, (27), 14 states have call predecessors, (27), 13 states have call successors, (27) Word has length 144 [2024-11-04 20:50:27,731 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:50:27,734 INFO L225 Difference]: With dead ends: 712 [2024-11-04 20:50:27,734 INFO L226 Difference]: Without dead ends: 495 [2024-11-04 20:50:27,736 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 306 GetRequests, 268 SyntacticMatches, 2 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 228 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=161, Invalid=1245, Unknown=0, NotChecked=0, Total=1406 [2024-11-04 20:50:27,737 INFO L432 NwaCegarLoop]: 148 mSDtfsCounter, 155 mSDsluCounter, 2201 mSDsCounter, 0 mSdLazyCounter, 1527 mSolverCounterSat, 82 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 172 SdHoareTripleChecker+Valid, 2349 SdHoareTripleChecker+Invalid, 1609 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 82 IncrementalHoareTripleChecker+Valid, 1527 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 11.7s IncrementalHoareTripleChecker+Time [2024-11-04 20:50:27,737 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [172 Valid, 2349 Invalid, 1609 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [82 Valid, 1527 Invalid, 0 Unknown, 0 Unchecked, 11.7s Time] [2024-11-04 20:50:27,738 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 495 states. [2024-11-04 20:50:27,782 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 495 to 424. [2024-11-04 20:50:27,783 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 424 states, 287 states have (on average 1.1951219512195121) internal successors, (343), 304 states have internal predecessors, (343), 99 states have call successors, (99), 26 states have call predecessors, (99), 37 states have return successors, (126), 96 states have call predecessors, (126), 91 states have call successors, (126) [2024-11-04 20:50:27,786 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 424 states to 424 states and 568 transitions. [2024-11-04 20:50:27,787 INFO L78 Accepts]: Start accepts. Automaton has 424 states and 568 transitions. Word has length 144 [2024-11-04 20:50:27,787 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:50:27,788 INFO L471 AbstractCegarLoop]: Abstraction has 424 states and 568 transitions. [2024-11-04 20:50:27,788 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 24 states have (on average 4.666666666666667) internal successors, (112), 22 states have internal predecessors, (112), 13 states have call successors, (28), 3 states have call predecessors, (28), 6 states have return successors, (27), 14 states have call predecessors, (27), 13 states have call successors, (27) [2024-11-04 20:50:27,788 INFO L276 IsEmpty]: Start isEmpty. Operand 424 states and 568 transitions. [2024-11-04 20:50:27,789 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 141 [2024-11-04 20:50:27,789 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:50:27,790 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:50:27,812 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (23)] Ended with exit code 0 [2024-11-04 20:50:27,990 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 23 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:50:27,990 INFO L396 AbstractCegarLoop]: === Iteration 23 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:50:27,991 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:50:27,991 INFO L85 PathProgramCache]: Analyzing trace with hash 1980881327, now seen corresponding path program 1 times [2024-11-04 20:50:27,991 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:50:27,991 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1325979958] [2024-11-04 20:50:27,991 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:50:27,991 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:50:27,991 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:50:27,993 INFO L229 MonitoredProcess]: Starting monitored process 24 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:50:27,994 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (24)] Waiting until timeout for monitored process [2024-11-04 20:50:28,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:50:28,438 INFO L255 TraceCheckSpWp]: Trace formula consists of 455 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-04 20:50:28,441 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:50:28,527 INFO L134 CoverageAnalysis]: Checked inductivity of 129 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 109 trivial. 0 not checked. [2024-11-04 20:50:28,527 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:50:28,658 INFO L134 CoverageAnalysis]: Checked inductivity of 129 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 109 trivial. 0 not checked. [2024-11-04 20:50:28,658 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:50:28,658 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1325979958] [2024-11-04 20:50:28,658 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1325979958] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:50:28,659 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:50:28,659 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8, 8] imperfect sequences [] total 8 [2024-11-04 20:50:28,659 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [378172549] [2024-11-04 20:50:28,659 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:50:28,659 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 20:50:28,659 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:50:28,660 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 20:50:28,660 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=14, Invalid=42, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:50:28,660 INFO L87 Difference]: Start difference. First operand 424 states and 568 transitions. Second operand has 8 states, 8 states have (on average 7.25) internal successors, (58), 7 states have internal predecessors, (58), 5 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 4 states have call successors, (13) [2024-11-04 20:50:33,522 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:50:33,523 INFO L93 Difference]: Finished difference Result 810 states and 1082 transitions. [2024-11-04 20:50:33,525 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-04 20:50:33,525 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 7.25) internal successors, (58), 7 states have internal predecessors, (58), 5 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 4 states have call successors, (13) Word has length 140 [2024-11-04 20:50:33,525 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:50:33,531 INFO L225 Difference]: With dead ends: 810 [2024-11-04 20:50:33,531 INFO L226 Difference]: Without dead ends: 437 [2024-11-04 20:50:33,533 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 280 GetRequests, 272 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2024-11-04 20:50:33,534 INFO L432 NwaCegarLoop]: 134 mSDtfsCounter, 33 mSDsluCounter, 731 mSDsCounter, 0 mSdLazyCounter, 94 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 43 SdHoareTripleChecker+Valid, 865 SdHoareTripleChecker+Invalid, 120 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 94 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.8s IncrementalHoareTripleChecker+Time [2024-11-04 20:50:33,534 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [43 Valid, 865 Invalid, 120 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 94 Invalid, 0 Unknown, 0 Unchecked, 4.8s Time] [2024-11-04 20:50:33,535 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 437 states. [2024-11-04 20:50:33,581 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 437 to 437. [2024-11-04 20:50:33,582 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 437 states, 293 states have (on average 1.1911262798634812) internal successors, (349), 311 states have internal predecessors, (349), 104 states have call successors, (104), 27 states have call predecessors, (104), 39 states have return successors, (135), 101 states have call predecessors, (135), 96 states have call successors, (135) [2024-11-04 20:50:33,585 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 437 states to 437 states and 588 transitions. [2024-11-04 20:50:33,587 INFO L78 Accepts]: Start accepts. Automaton has 437 states and 588 transitions. Word has length 140 [2024-11-04 20:50:33,587 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:50:33,587 INFO L471 AbstractCegarLoop]: Abstraction has 437 states and 588 transitions. [2024-11-04 20:50:33,587 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 7.25) internal successors, (58), 7 states have internal predecessors, (58), 5 states have call successors, (15), 3 states have call predecessors, (15), 2 states have return successors, (13), 5 states have call predecessors, (13), 4 states have call successors, (13) [2024-11-04 20:50:33,588 INFO L276 IsEmpty]: Start isEmpty. Operand 437 states and 588 transitions. [2024-11-04 20:50:33,589 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 163 [2024-11-04 20:50:33,589 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:50:33,589 INFO L215 NwaCegarLoop]: trace histogram [6, 6, 6, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 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, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:50:33,600 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (24)] Forceful destruction successful, exit code 0 [2024-11-04 20:50:33,790 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 24 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:50:33,790 INFO L396 AbstractCegarLoop]: === Iteration 24 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:50:33,790 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:50:33,791 INFO L85 PathProgramCache]: Analyzing trace with hash -2057855775, now seen corresponding path program 1 times [2024-11-04 20:50:33,791 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:50:33,791 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [372907535] [2024-11-04 20:50:33,791 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:50:33,791 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:50:33,791 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:50:33,792 INFO L229 MonitoredProcess]: Starting monitored process 25 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:50:33,793 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (25)] Waiting until timeout for monitored process [2024-11-04 20:50:34,797 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:50:34,825 INFO L255 TraceCheckSpWp]: Trace formula consists of 519 conjuncts, 83 conjuncts are in the unsatisfiable core [2024-11-04 20:50:34,831 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:50:34,913 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 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 17 treesize of output 20 [2024-11-04 20:50:34,916 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 8 treesize of output 1 [2024-11-04 20:50:34,919 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 20 treesize of output 9 [2024-11-04 20:50:34,935 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 34 [2024-11-04 20:50:34,941 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-04 20:50:34,944 WARN L214 Elim1Store]: Array PQE input equivalent to false