/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_pop_front_harness.i -------------------------------------------------------------------------------- This is Ultimate 0.2.5-dev-b75d321-m [2024-11-04 20:47:56,996 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-04 20:47:57,075 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:47:57,079 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-04 20:47:57,080 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-04 20:47:57,101 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-04 20:47:57,101 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-04 20:47:57,102 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-04 20:47:57,102 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-04 20:47:57,102 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-04 20:47:57,103 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-04 20:47:57,103 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-04 20:47:57,104 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-04 20:47:57,104 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-04 20:47:57,105 INFO L153 SettingsManager]: * Use SBE=true [2024-11-04 20:47:57,105 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-04 20:47:57,105 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-04 20:47:57,105 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-04 20:47:57,106 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-04 20:47:57,106 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-04 20:47:57,106 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-04 20:47:57,107 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-04 20:47:57,107 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-04 20:47:57,107 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-04 20:47:57,108 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-04 20:47:57,108 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-04 20:47:57,108 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-04 20:47:57,109 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-04 20:47:57,109 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-04 20:47:57,109 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-04 20:47:57,109 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-04 20:47:57,110 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 20:47:57,110 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-04 20:47:57,110 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-04 20:47:57,111 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-04 20:47:57,111 INFO L153 SettingsManager]: * Trace refinement strategy=WOLF [2024-11-04 20:47:57,111 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-04 20:47:57,111 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-04 20:47:57,112 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-04 20:47:57,112 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-04 20:47:57,112 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-04 20:47:57,112 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:47:57,364 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-04 20:47:57,387 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-04 20:47:57,390 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-04 20:47:57,391 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-04 20:47:57,392 INFO L274 PluginConnector]: CDTParser initialized [2024-11-04 20:47:57,393 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_pop_front_harness.i [2024-11-04 20:47:58,810 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-04 20:47:59,238 INFO L384 CDTParser]: Found 1 translation units. [2024-11-04 20:47:59,239 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_pop_front_harness.i [2024-11-04 20:47:59,278 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4299eed69/79b0b039d1da414f9640b730b5ef631c/FLAG9cf8928f3 [2024-11-04 20:47:59,383 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/4299eed69/79b0b039d1da414f9640b730b5ef631c [2024-11-04 20:47:59,386 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-04 20:47:59,388 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-11-04 20:47:59,389 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-04 20:47:59,389 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-04 20:47:59,393 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-04 20:47:59,394 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 08:47:59" (1/1) ... [2024-11-04 20:47:59,394 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@87effcf and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:47:59, skipping insertion in model container [2024-11-04 20:47:59,394 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 04.11 08:47:59" (1/1) ... [2024-11-04 20:47:59,473 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 20:47:59,777 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_pop_front_harness.i[4499,4512] [2024-11-04 20:47:59,786 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_pop_front_harness.i[4559,4572] [2024-11-04 20:48:00,371 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,480 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,481 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,482 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,495 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,499 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,500 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,500 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,501 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,501 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,502 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,506 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,506 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,511 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,511 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,523 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,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:48:00,524 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,524 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,526 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,528 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,528 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,528 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,530 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,530 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,531 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,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:48:00,531 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,532 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:00,759 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,759 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,760 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,760 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,874 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:00,899 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 20:48:00,920 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-04 20:48:00,955 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-04 20:48:00,960 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_pop_front_harness.i[4499,4512] [2024-11-04 20:48:00,961 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_pop_front_harness.i[4559,4572] [2024-11-04 20:48:00,989 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,011 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,011 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,012 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,024 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,025 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,028 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,029 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,029 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,029 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,030 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,031 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,032 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,033 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,033 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,040 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,041 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,041 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,042 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,043 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,043 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,043 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,043 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,044 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,045 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,047 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,049 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,049 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,050 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,106 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,107 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,107 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,108 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,148 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-04 20:48:01,155 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 20:48:01,160 INFO L200 MainTranslator]: Completed pre-run [2024-11-04 20:48:01,176 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_pop_front_harness.i[4499,4512] [2024-11-04 20:48:01,176 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_pop_front_harness.i[4559,4572] [2024-11-04 20:48:01,227 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,227 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,229 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,229 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,230 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,242 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,242 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,243 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,243 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,244 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,245 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,245 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,246 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-04 20:48:01,324 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-04 20:48:01,503 WARN L710 CHandler]: The following functions are not defined or handled internally: aws_array_list_ensure_capacity [2024-11-04 20:48:01,512 INFO L204 MainTranslator]: Completed translation [2024-11-04 20:48:01,512 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01 WrapperNode [2024-11-04 20:48:01,512 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-04 20:48:01,513 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-04 20:48:01,513 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-04 20:48:01,513 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-04 20:48:01,520 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (1/1) ... [2024-11-04 20:48:01,586 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (1/1) ... [2024-11-04 20:48:01,640 INFO L138 Inliner]: procedures = 687, calls = 1044, calls flagged for inlining = 52, calls inlined = 8, statements flattened = 227 [2024-11-04 20:48:01,643 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-04 20:48:01,644 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-04 20:48:01,644 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-04 20:48:01,644 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-04 20:48:01,654 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (1/1) ... [2024-11-04 20:48:01,654 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (1/1) ... [2024-11-04 20:48:01,664 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (1/1) ... [2024-11-04 20:48:01,701 INFO L175 MemorySlicer]: Split 43 memory accesses to 3 slices as follows [36, 2, 5]. 84 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [0, 2, 5]. The 9 writes are split as follows [9, 0, 0]. [2024-11-04 20:48:01,702 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (1/1) ... [2024-11-04 20:48:01,702 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (1/1) ... [2024-11-04 20:48:01,717 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (1/1) ... [2024-11-04 20:48:01,721 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (1/1) ... [2024-11-04 20:48:01,741 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (1/1) ... [2024-11-04 20:48:01,748 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (1/1) ... [2024-11-04 20:48:01,759 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-04 20:48:01,760 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-04 20:48:01,760 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-04 20:48:01,760 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-04 20:48:01,765 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (1/1) ... [2024-11-04 20:48:01,772 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-04 20:48:01,782 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-04 20:48:01,796 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2024-11-04 20:48:01,798 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2024-11-04 20:48:01,817 INFO L130 BoogieDeclarations]: Found specification of procedure aws_is_mem_zeroed [2024-11-04 20:48:01,818 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_is_mem_zeroed [2024-11-04 20:48:01,818 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_remove [2024-11-04 20:48:01,818 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_remove [2024-11-04 20:48:01,818 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-04 20:48:01,818 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-04 20:48:01,818 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-04 20:48:01,818 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2024-11-04 20:48:01,818 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-04 20:48:01,819 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-04 20:48:01,819 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2024-11-04 20:48:01,819 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2024-11-04 20:48:01,819 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-04 20:48:01,819 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2024-11-04 20:48:01,819 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2024-11-04 20:48:01,819 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-04 20:48:01,820 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-04 20:48:01,820 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-04 20:48:01,820 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2024-11-04 20:48:01,820 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-04 20:48:01,820 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-04 20:48:01,820 INFO L130 BoogieDeclarations]: Found specification of procedure read~intINTTYPE1#0 [2024-11-04 20:48:01,820 INFO L130 BoogieDeclarations]: Found specification of procedure read~intINTTYPE1#1 [2024-11-04 20:48:01,820 INFO L130 BoogieDeclarations]: Found specification of procedure read~intINTTYPE1#2 [2024-11-04 20:48:01,820 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_empty [2024-11-04 20:48:01,821 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_empty [2024-11-04 20:48:01,821 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset#0 [2024-11-04 20:48:01,821 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset#1 [2024-11-04 20:48:01,821 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.C_memset#2 [2024-11-04 20:48:01,821 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset#0 [2024-11-04 20:48:01,821 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset#1 [2024-11-04 20:48:01,821 INFO L138 BoogieDeclarations]: Found implementation of procedure #Ultimate.C_memset#2 [2024-11-04 20:48:01,821 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-04 20:48:01,821 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-04 20:48:01,822 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-04 20:48:01,822 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-04 20:48:01,822 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-04 20:48:01,822 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2024-11-04 20:48:01,822 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2024-11-04 20:48:01,822 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2024-11-04 20:48:01,822 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2024-11-04 20:48:01,822 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2024-11-04 20:48:01,822 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2024-11-04 20:48:01,823 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_prev_is_valid [2024-11-04 20:48:01,823 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_prev_is_valid [2024-11-04 20:48:02,116 INFO L238 CfgBuilder]: Building ICFG [2024-11-04 20:48:02,118 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-04 20:48:02,677 INFO L? ?]: Removed 105 outVars from TransFormulas that were not future-live. [2024-11-04 20:48:02,677 INFO L287 CfgBuilder]: Performing block encoding [2024-11-04 20:48:02,694 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-04 20:48:02,696 INFO L316 CfgBuilder]: Removed 5 assume(true) statements. [2024-11-04 20:48:02,696 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 08:48:02 BoogieIcfgContainer [2024-11-04 20:48:02,696 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-04 20:48:02,699 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-04 20:48:02,699 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-04 20:48:02,703 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-04 20:48:02,722 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 04.11 08:47:59" (1/3) ... [2024-11-04 20:48:02,722 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2622129c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 08:48:02, skipping insertion in model container [2024-11-04 20:48:02,723 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 04.11 08:48:01" (2/3) ... [2024-11-04 20:48:02,723 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2622129c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 04.11 08:48:02, skipping insertion in model container [2024-11-04 20:48:02,723 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 04.11 08:48:02" (3/3) ... [2024-11-04 20:48:02,724 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_pop_front_harness.i [2024-11-04 20:48:02,739 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-04 20:48:02,740 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-04 20:48:02,801 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-04 20:48:02,806 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;@7474f1a, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-04 20:48:02,806 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-04 20:48:02,810 INFO L276 IsEmpty]: Start isEmpty. Operand has 137 states, 89 states have (on average 1.303370786516854) internal successors, (116), 90 states have internal predecessors, (116), 37 states have call successors, (37), 10 states have call predecessors, (37), 10 states have return successors, (37), 37 states have call predecessors, (37), 37 states have call successors, (37) [2024-11-04 20:48:02,823 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-11-04 20:48:02,824 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:02,825 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:02,827 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:02,832 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:02,832 INFO L85 PathProgramCache]: Analyzing trace with hash -1634297944, now seen corresponding path program 1 times [2024-11-04 20:48:02,840 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:02,841 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1761471799] [2024-11-04 20:48:02,841 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:02,842 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:02,843 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:02,845 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:02,847 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (2)] Waiting until timeout for monitored process [2024-11-04 20:48:03,174 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:03,179 INFO L255 TraceCheckSpWp]: Trace formula consists of 275 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-04 20:48:03,189 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:03,219 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 38 proven. 0 refuted. 0 times theorem prover too weak. 154 trivial. 0 not checked. [2024-11-04 20:48:03,220 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:03,337 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 16 proven. 0 refuted. 0 times theorem prover too weak. 176 trivial. 0 not checked. [2024-11-04 20:48:03,338 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:03,338 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1761471799] [2024-11-04 20:48:03,339 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1761471799] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:48:03,339 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:48:03,339 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2, 2] imperfect sequences [] total 2 [2024-11-04 20:48:03,340 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [169352591] [2024-11-04 20:48:03,341 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:03,345 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-04 20:48:03,345 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:03,364 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-04 20:48:03,364 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 20:48:03,368 INFO L87 Difference]: Start difference. First operand has 137 states, 89 states have (on average 1.303370786516854) internal successors, (116), 90 states have internal predecessors, (116), 37 states have call successors, (37), 10 states have call predecessors, (37), 10 states have return successors, (37), 37 states have call predecessors, (37), 37 states have call successors, (37) Second operand has 2 states, 2 states have (on average 22.5) internal successors, (45), 2 states have internal predecessors, (45), 2 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-04 20:48:03,400 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:03,401 INFO L93 Difference]: Finished difference Result 266 states and 401 transitions. [2024-11-04 20:48:03,402 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-04 20:48:03,402 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 22.5) internal successors, (45), 2 states have internal predecessors, (45), 2 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) Word has length 116 [2024-11-04 20:48:03,403 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:03,409 INFO L225 Difference]: With dead ends: 266 [2024-11-04 20:48:03,409 INFO L226 Difference]: Without dead ends: 132 [2024-11-04 20:48:03,413 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 230 GetRequests, 230 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-04 20:48:03,416 INFO L432 NwaCegarLoop]: 183 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, 183 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:03,417 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 183 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:48:03,429 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 132 states. [2024-11-04 20:48:03,453 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 132 to 132. [2024-11-04 20:48:03,454 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 84 states have (on average 1.25) internal successors, (105), 85 states have internal predecessors, (105), 37 states have call successors, (37), 10 states have call predecessors, (37), 10 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2024-11-04 20:48:03,457 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 178 transitions. [2024-11-04 20:48:03,459 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 178 transitions. Word has length 116 [2024-11-04 20:48:03,459 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:03,459 INFO L471 AbstractCegarLoop]: Abstraction has 132 states and 178 transitions. [2024-11-04 20:48:03,460 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 22.5) internal successors, (45), 2 states have internal predecessors, (45), 2 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-04 20:48:03,460 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 178 transitions. [2024-11-04 20:48:03,462 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-11-04 20:48:03,462 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:03,462 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:03,469 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (2)] Ended with exit code 0 [2024-11-04 20:48:03,666 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:03,667 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:03,667 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:03,668 INFO L85 PathProgramCache]: Analyzing trace with hash 851280282, now seen corresponding path program 1 times [2024-11-04 20:48:03,668 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:03,668 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [356720599] [2024-11-04 20:48:03,668 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:03,668 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:03,668 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:03,669 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:03,671 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (3)] Waiting until timeout for monitored process [2024-11-04 20:48:03,931 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:03,935 INFO L255 TraceCheckSpWp]: Trace formula consists of 275 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-04 20:48:03,940 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:03,975 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 102 proven. 0 refuted. 0 times theorem prover too weak. 90 trivial. 0 not checked. [2024-11-04 20:48:03,975 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:04,092 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 178 trivial. 0 not checked. [2024-11-04 20:48:04,093 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:04,093 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [356720599] [2024-11-04 20:48:04,093 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [356720599] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:04,093 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:04,093 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-04 20:48:04,093 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [901228384] [2024-11-04 20:48:04,093 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:04,094 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-04 20:48:04,094 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:04,099 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-04 20:48:04,099 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-04 20:48:04,100 INFO L87 Difference]: Start difference. First operand 132 states and 178 transitions. Second operand has 4 states, 4 states have (on average 11.25) internal successors, (45), 4 states have internal predecessors, (45), 2 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-04 20:48:04,168 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:04,168 INFO L93 Difference]: Finished difference Result 247 states and 338 transitions. [2024-11-04 20:48:04,169 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-04 20:48:04,169 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 11.25) internal successors, (45), 4 states have internal predecessors, (45), 2 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) Word has length 116 [2024-11-04 20:48:04,169 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:04,171 INFO L225 Difference]: With dead ends: 247 [2024-11-04 20:48:04,171 INFO L226 Difference]: Without dead ends: 135 [2024-11-04 20:48:04,173 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 230 GetRequests, 228 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:48:04,174 INFO L432 NwaCegarLoop]: 175 mSDtfsCounter, 1 mSDsluCounter, 342 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 517 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:48:04,175 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 517 Invalid, 16 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:48:04,176 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 135 states. [2024-11-04 20:48:04,195 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 135 to 134. [2024-11-04 20:48:04,195 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 134 states, 86 states have (on average 1.244186046511628) internal successors, (107), 87 states have internal predecessors, (107), 37 states have call successors, (37), 10 states have call predecessors, (37), 10 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2024-11-04 20:48:04,197 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 134 states to 134 states and 180 transitions. [2024-11-04 20:48:04,197 INFO L78 Accepts]: Start accepts. Automaton has 134 states and 180 transitions. Word has length 116 [2024-11-04 20:48:04,198 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:04,199 INFO L471 AbstractCegarLoop]: Abstraction has 134 states and 180 transitions. [2024-11-04 20:48:04,199 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 11.25) internal successors, (45), 4 states have internal predecessors, (45), 2 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-04 20:48:04,199 INFO L276 IsEmpty]: Start isEmpty. Operand 134 states and 180 transitions. [2024-11-04 20:48:04,200 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-11-04 20:48:04,201 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:04,201 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:04,206 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (3)] Ended with exit code 0 [2024-11-04 20:48:04,401 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:04,402 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:04,402 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:04,402 INFO L85 PathProgramCache]: Analyzing trace with hash -911862316, now seen corresponding path program 1 times [2024-11-04 20:48:04,403 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:04,403 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1299183401] [2024-11-04 20:48:04,403 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:04,403 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:04,403 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:04,404 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:04,406 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (4)] Waiting until timeout for monitored process [2024-11-04 20:48:04,647 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:04,652 INFO L255 TraceCheckSpWp]: Trace formula consists of 266 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-04 20:48:04,655 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:04,678 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 106 proven. 0 refuted. 0 times theorem prover too weak. 86 trivial. 0 not checked. [2024-11-04 20:48:04,678 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:04,762 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 178 trivial. 0 not checked. [2024-11-04 20:48:04,762 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:04,763 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1299183401] [2024-11-04 20:48:04,763 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1299183401] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:04,763 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:04,763 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 5 [2024-11-04 20:48:04,763 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [844221593] [2024-11-04 20:48:04,763 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:04,763 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-04 20:48:04,764 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:04,764 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-04 20:48:04,764 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-04 20:48:04,764 INFO L87 Difference]: Start difference. First operand 134 states and 180 transitions. Second operand has 5 states, 5 states have (on average 9.4) internal successors, (47), 5 states have internal predecessors, (47), 2 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-04 20:48:04,827 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:04,831 INFO L93 Difference]: Finished difference Result 251 states and 343 transitions. [2024-11-04 20:48:04,833 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-04 20:48:04,834 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 9.4) internal successors, (47), 5 states have internal predecessors, (47), 2 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) Word has length 116 [2024-11-04 20:48:04,834 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:04,836 INFO L225 Difference]: With dead ends: 251 [2024-11-04 20:48:04,836 INFO L226 Difference]: Without dead ends: 137 [2024-11-04 20:48:04,837 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 230 GetRequests, 227 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:48:04,841 INFO L432 NwaCegarLoop]: 173 mSDtfsCounter, 1 mSDsluCounter, 511 mSDsCounter, 0 mSdLazyCounter, 25 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 684 SdHoareTripleChecker+Invalid, 28 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 25 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:04,842 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 684 Invalid, 28 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 25 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:48:04,842 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2024-11-04 20:48:04,856 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 137. [2024-11-04 20:48:04,860 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 137 states, 89 states have (on average 1.2359550561797752) internal successors, (110), 90 states have internal predecessors, (110), 37 states have call successors, (37), 10 states have call predecessors, (37), 10 states have return successors, (36), 36 states have call predecessors, (36), 36 states have call successors, (36) [2024-11-04 20:48:04,861 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 137 states to 137 states and 183 transitions. [2024-11-04 20:48:04,862 INFO L78 Accepts]: Start accepts. Automaton has 137 states and 183 transitions. Word has length 116 [2024-11-04 20:48:04,862 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:04,862 INFO L471 AbstractCegarLoop]: Abstraction has 137 states and 183 transitions. [2024-11-04 20:48:04,862 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 9.4) internal successors, (47), 5 states have internal predecessors, (47), 2 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 2 states have call predecessors, (15), 2 states have call successors, (15) [2024-11-04 20:48:04,863 INFO L276 IsEmpty]: Start isEmpty. Operand 137 states and 183 transitions. [2024-11-04 20:48:04,867 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 117 [2024-11-04 20:48:04,868 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:04,868 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:04,875 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (4)] Ended with exit code 0 [2024-11-04 20:48:05,068 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:05,069 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:05,070 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:05,070 INFO L85 PathProgramCache]: Analyzing trace with hash -1271238514, now seen corresponding path program 1 times [2024-11-04 20:48:05,070 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:05,070 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1797226458] [2024-11-04 20:48:05,070 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:05,070 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:05,070 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:05,073 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:05,074 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (5)] Waiting until timeout for monitored process [2024-11-04 20:48:05,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:05,470 INFO L255 TraceCheckSpWp]: Trace formula consists of 257 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 20:48:05,473 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:05,514 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 119 proven. 0 refuted. 0 times theorem prover too weak. 73 trivial. 0 not checked. [2024-11-04 20:48:05,514 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:05,645 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 15 proven. 13 refuted. 0 times theorem prover too weak. 164 trivial. 0 not checked. [2024-11-04 20:48:05,646 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:05,646 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1797226458] [2024-11-04 20:48:05,646 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1797226458] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:05,646 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:05,646 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2024-11-04 20:48:05,646 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1504731873] [2024-11-04 20:48:05,646 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:05,647 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 20:48:05,647 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:05,647 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 20:48:05,648 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 20:48:05,648 INFO L87 Difference]: Start difference. First operand 137 states and 183 transitions. Second operand has 6 states, 5 states have (on average 10.4) internal successors, (52), 5 states have internal predecessors, (52), 3 states have call successors, (16), 2 states have call predecessors, (16), 4 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-11-04 20:48:05,759 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:05,759 INFO L93 Difference]: Finished difference Result 256 states and 345 transitions. [2024-11-04 20:48:05,759 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 20:48:05,760 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 10.4) internal successors, (52), 5 states have internal predecessors, (52), 3 states have call successors, (16), 2 states have call predecessors, (16), 4 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) Word has length 116 [2024-11-04 20:48:05,760 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:05,763 INFO L225 Difference]: With dead ends: 256 [2024-11-04 20:48:05,763 INFO L226 Difference]: Without dead ends: 139 [2024-11-04 20:48:05,764 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:48:05,764 INFO L432 NwaCegarLoop]: 167 mSDtfsCounter, 0 mSDsluCounter, 640 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 807 SdHoareTripleChecker+Invalid, 79 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:05,765 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 807 Invalid, 79 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 20:48:05,765 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2024-11-04 20:48:05,773 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 139. [2024-11-04 20:48:05,773 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 90 states have (on average 1.2333333333333334) internal successors, (111), 92 states have internal predecessors, (111), 37 states have call successors, (37), 10 states have call predecessors, (37), 11 states have return successors, (40), 36 states have call predecessors, (40), 36 states have call successors, (40) [2024-11-04 20:48:05,775 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 188 transitions. [2024-11-04 20:48:05,775 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 188 transitions. Word has length 116 [2024-11-04 20:48:05,775 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:05,775 INFO L471 AbstractCegarLoop]: Abstraction has 139 states and 188 transitions. [2024-11-04 20:48:05,776 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 10.4) internal successors, (52), 5 states have internal predecessors, (52), 3 states have call successors, (16), 2 states have call predecessors, (16), 4 states have return successors, (15), 3 states have call predecessors, (15), 3 states have call successors, (15) [2024-11-04 20:48:05,776 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 188 transitions. [2024-11-04 20:48:05,777 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 119 [2024-11-04 20:48:05,777 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:05,777 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:05,785 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (5)] Ended with exit code 0 [2024-11-04 20:48:05,978 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:05,978 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:05,979 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:05,979 INFO L85 PathProgramCache]: Analyzing trace with hash 383901392, now seen corresponding path program 1 times [2024-11-04 20:48:05,979 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:05,979 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1809862157] [2024-11-04 20:48:05,979 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:05,979 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:05,979 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:05,980 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:05,981 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (6)] Waiting until timeout for monitored process [2024-11-04 20:48:06,227 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:06,230 INFO L255 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-04 20:48:06,233 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:06,341 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 112 proven. 0 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2024-11-04 20:48:06,341 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:06,601 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2024-11-04 20:48:06,602 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:06,602 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1809862157] [2024-11-04 20:48:06,602 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1809862157] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:06,602 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:06,602 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 9 [2024-11-04 20:48:06,602 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [91871363] [2024-11-04 20:48:06,602 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:06,603 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 20:48:06,603 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:06,604 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 20:48:06,604 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2024-11-04 20:48:06,604 INFO L87 Difference]: Start difference. First operand 139 states and 188 transitions. Second operand has 7 states, 7 states have (on average 7.285714285714286) internal successors, (51), 7 states have internal predecessors, (51), 4 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) [2024-11-04 20:48:06,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:06,826 INFO L93 Difference]: Finished difference Result 263 states and 358 transitions. [2024-11-04 20:48:06,827 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 20:48:06,827 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 7.285714285714286) internal successors, (51), 7 states have internal predecessors, (51), 4 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) Word has length 118 [2024-11-04 20:48:06,827 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:06,829 INFO L225 Difference]: With dead ends: 263 [2024-11-04 20:48:06,829 INFO L226 Difference]: Without dead ends: 144 [2024-11-04 20:48:06,830 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:48:06,831 INFO L432 NwaCegarLoop]: 164 mSDtfsCounter, 46 mSDsluCounter, 709 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 51 SdHoareTripleChecker+Valid, 873 SdHoareTripleChecker+Invalid, 152 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:06,831 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [51 Valid, 873 Invalid, 152 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-04 20:48:06,831 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 144 states. [2024-11-04 20:48:06,854 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 144 to 142. [2024-11-04 20:48:06,855 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 92 states have (on average 1.2282608695652173) internal successors, (113), 95 states have internal predecessors, (113), 37 states have call successors, (37), 10 states have call predecessors, (37), 12 states have return successors, (42), 36 states have call predecessors, (42), 36 states have call successors, (42) [2024-11-04 20:48:06,856 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 192 transitions. [2024-11-04 20:48:06,857 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 192 transitions. Word has length 118 [2024-11-04 20:48:06,857 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:06,857 INFO L471 AbstractCegarLoop]: Abstraction has 142 states and 192 transitions. [2024-11-04 20:48:06,857 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 7.285714285714286) internal successors, (51), 7 states have internal predecessors, (51), 4 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) [2024-11-04 20:48:06,857 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 192 transitions. [2024-11-04 20:48:06,858 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 121 [2024-11-04 20:48:06,859 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:06,859 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:06,863 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (6)] Ended with exit code 0 [2024-11-04 20:48:07,059 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:07,060 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:07,060 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:07,060 INFO L85 PathProgramCache]: Analyzing trace with hash -1545770691, now seen corresponding path program 1 times [2024-11-04 20:48:07,060 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:07,060 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1843230984] [2024-11-04 20:48:07,061 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:07,061 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:07,061 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:07,062 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:07,063 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (7)] Waiting until timeout for monitored process [2024-11-04 20:48:07,293 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:07,296 INFO L255 TraceCheckSpWp]: Trace formula consists of 277 conjuncts, 9 conjuncts are in the unsatisfiable core [2024-11-04 20:48:07,299 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:07,398 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 112 proven. 0 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2024-11-04 20:48:07,398 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:07,623 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 172 trivial. 0 not checked. [2024-11-04 20:48:07,624 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:07,624 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1843230984] [2024-11-04 20:48:07,624 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1843230984] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:07,624 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:07,624 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 11 [2024-11-04 20:48:07,624 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1011335472] [2024-11-04 20:48:07,624 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:07,625 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 20:48:07,625 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:07,625 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 20:48:07,625 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=25, Invalid=85, Unknown=0, NotChecked=0, Total=110 [2024-11-04 20:48:07,626 INFO L87 Difference]: Start difference. First operand 142 states and 192 transitions. Second operand has 8 states, 8 states have (on average 6.625) internal successors, (53), 8 states have internal predecessors, (53), 4 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) [2024-11-04 20:48:07,919 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:07,919 INFO L93 Difference]: Finished difference Result 275 states and 376 transitions. [2024-11-04 20:48:07,919 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-04 20:48:07,920 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 8 states have (on average 6.625) internal successors, (53), 8 states have internal predecessors, (53), 4 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) Word has length 120 [2024-11-04 20:48:07,920 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:07,922 INFO L225 Difference]: With dead ends: 275 [2024-11-04 20:48:07,922 INFO L226 Difference]: Without dead ends: 153 [2024-11-04 20:48:07,922 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 241 GetRequests, 229 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:48:07,923 INFO L432 NwaCegarLoop]: 162 mSDtfsCounter, 55 mSDsluCounter, 855 mSDsCounter, 0 mSdLazyCounter, 151 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 60 SdHoareTripleChecker+Valid, 1017 SdHoareTripleChecker+Invalid, 200 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 151 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:07,923 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [60 Valid, 1017 Invalid, 200 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 151 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-04 20:48:07,924 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 153 states. [2024-11-04 20:48:07,939 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 153 to 144. [2024-11-04 20:48:07,939 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 94 states have (on average 1.2340425531914894) internal successors, (116), 97 states have internal predecessors, (116), 37 states have call successors, (37), 10 states have call predecessors, (37), 12 states have return successors, (42), 36 states have call predecessors, (42), 36 states have call successors, (42) [2024-11-04 20:48:07,941 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 195 transitions. [2024-11-04 20:48:07,941 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 195 transitions. Word has length 120 [2024-11-04 20:48:07,942 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:07,942 INFO L471 AbstractCegarLoop]: Abstraction has 144 states and 195 transitions. [2024-11-04 20:48:07,942 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 8 states have (on average 6.625) internal successors, (53), 8 states have internal predecessors, (53), 4 states have call successors, (16), 2 states have call predecessors, (16), 3 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) [2024-11-04 20:48:07,942 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 195 transitions. [2024-11-04 20:48:07,943 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 122 [2024-11-04 20:48:07,943 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:07,943 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:07,948 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:48:08,144 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:08,144 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:08,144 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:08,144 INFO L85 PathProgramCache]: Analyzing trace with hash 1786998227, now seen corresponding path program 1 times [2024-11-04 20:48:08,145 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:08,145 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1117754564] [2024-11-04 20:48:08,145 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:08,145 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:08,145 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:08,146 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:08,147 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (8)] Waiting until timeout for monitored process [2024-11-04 20:48:08,370 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:08,374 INFO L255 TraceCheckSpWp]: Trace formula consists of 279 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-04 20:48:08,378 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:08,478 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 108 proven. 0 refuted. 0 times theorem prover too weak. 84 trivial. 0 not checked. [2024-11-04 20:48:08,478 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:08,571 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 188 trivial. 0 not checked. [2024-11-04 20:48:08,572 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:08,572 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1117754564] [2024-11-04 20:48:08,572 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1117754564] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:08,572 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:08,572 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [3] total 8 [2024-11-04 20:48:08,572 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1862671696] [2024-11-04 20:48:08,572 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:08,573 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 20:48:08,573 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:08,573 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 20:48:08,573 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:48:08,574 INFO L87 Difference]: Start difference. First operand 144 states and 195 transitions. Second operand has 7 states, 7 states have (on average 7.571428571428571) internal successors, (53), 7 states have internal predecessors, (53), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) [2024-11-04 20:48:08,769 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:08,769 INFO L93 Difference]: Finished difference Result 275 states and 378 transitions. [2024-11-04 20:48:08,770 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 20:48:08,770 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 7.571428571428571) internal successors, (53), 7 states have internal predecessors, (53), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) Word has length 121 [2024-11-04 20:48:08,770 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:08,772 INFO L225 Difference]: With dead ends: 275 [2024-11-04 20:48:08,772 INFO L226 Difference]: Without dead ends: 151 [2024-11-04 20:48:08,773 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 241 GetRequests, 234 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:48:08,773 INFO L432 NwaCegarLoop]: 161 mSDtfsCounter, 50 mSDsluCounter, 547 mSDsCounter, 0 mSdLazyCounter, 96 mSolverCounterSat, 41 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 708 SdHoareTripleChecker+Invalid, 137 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 96 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:08,774 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 708 Invalid, 137 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 96 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-04 20:48:08,774 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2024-11-04 20:48:08,784 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 145. [2024-11-04 20:48:08,785 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 145 states, 95 states have (on average 1.231578947368421) internal successors, (117), 98 states have internal predecessors, (117), 37 states have call successors, (37), 10 states have call predecessors, (37), 12 states have return successors, (42), 36 states have call predecessors, (42), 36 states have call successors, (42) [2024-11-04 20:48:08,786 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 145 states to 145 states and 196 transitions. [2024-11-04 20:48:08,787 INFO L78 Accepts]: Start accepts. Automaton has 145 states and 196 transitions. Word has length 121 [2024-11-04 20:48:08,788 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:08,788 INFO L471 AbstractCegarLoop]: Abstraction has 145 states and 196 transitions. [2024-11-04 20:48:08,788 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 7.571428571428571) internal successors, (53), 7 states have internal predecessors, (53), 4 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (15), 4 states have call predecessors, (15), 4 states have call successors, (15) [2024-11-04 20:48:08,788 INFO L276 IsEmpty]: Start isEmpty. Operand 145 states and 196 transitions. [2024-11-04 20:48:08,790 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 130 [2024-11-04 20:48:08,790 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:08,790 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:08,796 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (8)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:08,991 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:08,991 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:08,992 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:08,992 INFO L85 PathProgramCache]: Analyzing trace with hash -203374091, now seen corresponding path program 1 times [2024-11-04 20:48:08,992 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:08,992 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [233592098] [2024-11-04 20:48:08,992 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:08,992 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:08,992 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:08,995 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:08,997 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (9)] Waiting until timeout for monitored process [2024-11-04 20:48:09,426 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:09,430 INFO L255 TraceCheckSpWp]: Trace formula consists of 299 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 20:48:09,432 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:09,501 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 119 proven. 0 refuted. 0 times theorem prover too weak. 73 trivial. 0 not checked. [2024-11-04 20:48:09,502 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:09,618 INFO L134 CoverageAnalysis]: Checked inductivity of 192 backedges. 15 proven. 13 refuted. 0 times theorem prover too weak. 164 trivial. 0 not checked. [2024-11-04 20:48:09,619 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:09,619 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [233592098] [2024-11-04 20:48:09,619 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [233592098] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:09,619 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:09,619 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 8 [2024-11-04 20:48:09,619 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [580115694] [2024-11-04 20:48:09,620 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:09,620 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 20:48:09,620 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:09,621 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 20:48:09,621 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:48:09,621 INFO L87 Difference]: Start difference. First operand 145 states and 196 transitions. Second operand has 7 states, 6 states have (on average 10.5) internal successors, (63), 6 states have internal predecessors, (63), 3 states have call successors, (17), 2 states have call predecessors, (17), 4 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2024-11-04 20:48:09,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:09,732 INFO L93 Difference]: Finished difference Result 276 states and 376 transitions. [2024-11-04 20:48:09,732 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 20:48:09,732 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 10.5) internal successors, (63), 6 states have internal predecessors, (63), 3 states have call successors, (17), 2 states have call predecessors, (17), 4 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) Word has length 129 [2024-11-04 20:48:09,732 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:09,734 INFO L225 Difference]: With dead ends: 276 [2024-11-04 20:48:09,734 INFO L226 Difference]: Without dead ends: 151 [2024-11-04 20:48:09,735 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 256 GetRequests, 250 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:48:09,735 INFO L432 NwaCegarLoop]: 166 mSDtfsCounter, 0 mSDsluCounter, 799 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 965 SdHoareTripleChecker+Invalid, 99 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:09,736 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 965 Invalid, 99 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 20:48:09,736 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2024-11-04 20:48:09,744 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 146. [2024-11-04 20:48:09,744 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 96 states have (on average 1.2291666666666667) internal successors, (118), 99 states have internal predecessors, (118), 37 states have call successors, (37), 10 states have call predecessors, (37), 12 states have return successors, (42), 36 states have call predecessors, (42), 36 states have call successors, (42) [2024-11-04 20:48:09,746 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 197 transitions. [2024-11-04 20:48:09,746 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 197 transitions. Word has length 129 [2024-11-04 20:48:09,746 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:09,746 INFO L471 AbstractCegarLoop]: Abstraction has 146 states and 197 transitions. [2024-11-04 20:48:09,747 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 10.5) internal successors, (63), 6 states have internal predecessors, (63), 3 states have call successors, (17), 2 states have call predecessors, (17), 4 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2024-11-04 20:48:09,747 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 197 transitions. [2024-11-04 20:48:09,748 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 132 [2024-11-04 20:48:09,748 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:09,748 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:09,756 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (9)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:09,948 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:09,949 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:09,949 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:09,949 INFO L85 PathProgramCache]: Analyzing trace with hash 1018173218, now seen corresponding path program 1 times [2024-11-04 20:48:09,949 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:09,949 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [922480685] [2024-11-04 20:48:09,949 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:09,949 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:09,950 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:09,951 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:09,952 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (10)] Waiting until timeout for monitored process [2024-11-04 20:48:10,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:10,363 INFO L255 TraceCheckSpWp]: Trace formula consists of 303 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-04 20:48:10,365 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:10,394 INFO L134 CoverageAnalysis]: Checked inductivity of 193 backedges. 108 proven. 0 refuted. 0 times theorem prover too weak. 85 trivial. 0 not checked. [2024-11-04 20:48:10,394 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:10,498 INFO L134 CoverageAnalysis]: Checked inductivity of 193 backedges. 20 proven. 8 refuted. 0 times theorem prover too weak. 165 trivial. 0 not checked. [2024-11-04 20:48:10,498 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:10,498 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [922480685] [2024-11-04 20:48:10,498 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [922480685] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:10,498 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:10,498 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 7 [2024-11-04 20:48:10,499 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [214537050] [2024-11-04 20:48:10,499 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:10,499 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2024-11-04 20:48:10,499 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:10,500 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2024-11-04 20:48:10,500 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2024-11-04 20:48:10,500 INFO L87 Difference]: Start difference. First operand 146 states and 197 transitions. Second operand has 6 states, 5 states have (on average 14.0) internal successors, (70), 5 states have internal predecessors, (70), 3 states have call successors, (17), 2 states have call predecessors, (17), 4 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2024-11-04 20:48:10,584 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:10,584 INFO L93 Difference]: Finished difference Result 271 states and 365 transitions. [2024-11-04 20:48:10,585 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-04 20:48:10,585 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 14.0) internal successors, (70), 5 states have internal predecessors, (70), 3 states have call successors, (17), 2 states have call predecessors, (17), 4 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) Word has length 131 [2024-11-04 20:48:10,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:10,587 INFO L225 Difference]: With dead ends: 271 [2024-11-04 20:48:10,588 INFO L226 Difference]: Without dead ends: 148 [2024-11-04 20:48:10,588 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 260 GetRequests, 255 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:48:10,589 INFO L432 NwaCegarLoop]: 167 mSDtfsCounter, 0 mSDsluCounter, 640 mSDsCounter, 0 mSdLazyCounter, 79 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 807 SdHoareTripleChecker+Invalid, 79 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 79 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:10,589 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 807 Invalid, 79 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 79 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 20:48:10,590 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 148 states. [2024-11-04 20:48:10,599 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 148 to 148. [2024-11-04 20:48:10,599 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 97 states have (on average 1.2268041237113403) internal successors, (119), 101 states have internal predecessors, (119), 37 states have call successors, (37), 10 states have call predecessors, (37), 13 states have return successors, (45), 36 states have call predecessors, (45), 36 states have call successors, (45) [2024-11-04 20:48:10,600 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 201 transitions. [2024-11-04 20:48:10,601 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 201 transitions. Word has length 131 [2024-11-04 20:48:10,601 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:10,602 INFO L471 AbstractCegarLoop]: Abstraction has 148 states and 201 transitions. [2024-11-04 20:48:10,602 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 14.0) internal successors, (70), 5 states have internal predecessors, (70), 3 states have call successors, (17), 2 states have call predecessors, (17), 4 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2024-11-04 20:48:10,602 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 201 transitions. [2024-11-04 20:48:10,603 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 134 [2024-11-04 20:48:10,603 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:10,603 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:10,611 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:48:10,803 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:10,804 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:10,804 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:10,804 INFO L85 PathProgramCache]: Analyzing trace with hash -912485276, now seen corresponding path program 1 times [2024-11-04 20:48:10,804 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:10,804 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1771167005] [2024-11-04 20:48:10,804 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:10,804 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:10,805 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:10,807 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:10,808 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (11)] Waiting until timeout for monitored process [2024-11-04 20:48:11,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:11,035 INFO L255 TraceCheckSpWp]: Trace formula consists of 319 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-04 20:48:11,039 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:11,129 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 116 proven. 0 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2024-11-04 20:48:11,129 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:11,309 INFO L134 CoverageAnalysis]: Checked inductivity of 195 backedges. 12 proven. 10 refuted. 0 times theorem prover too weak. 173 trivial. 0 not checked. [2024-11-04 20:48:11,309 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:11,309 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1771167005] [2024-11-04 20:48:11,309 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1771167005] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:11,309 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:11,309 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 10 [2024-11-04 20:48:11,310 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [91426592] [2024-11-04 20:48:11,310 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:11,310 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-04 20:48:11,310 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:11,311 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-04 20:48:11,311 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2024-11-04 20:48:11,311 INFO L87 Difference]: Start difference. First operand 148 states and 201 transitions. Second operand has 8 states, 7 states have (on average 10.571428571428571) internal successors, (74), 8 states have internal predecessors, (74), 5 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-04 20:48:11,525 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:11,525 INFO L93 Difference]: Finished difference Result 278 states and 374 transitions. [2024-11-04 20:48:11,526 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2024-11-04 20:48:11,526 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 10.571428571428571) internal successors, (74), 8 states have internal predecessors, (74), 5 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) Word has length 133 [2024-11-04 20:48:11,526 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:11,528 INFO L225 Difference]: With dead ends: 278 [2024-11-04 20:48:11,528 INFO L226 Difference]: Without dead ends: 150 [2024-11-04 20:48:11,529 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 266 GetRequests, 256 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2024-11-04 20:48:11,529 INFO L432 NwaCegarLoop]: 164 mSDtfsCounter, 51 mSDsluCounter, 859 mSDsCounter, 0 mSdLazyCounter, 112 mSolverCounterSat, 48 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 1023 SdHoareTripleChecker+Invalid, 160 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 48 IncrementalHoareTripleChecker+Valid, 112 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:11,529 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 1023 Invalid, 160 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [48 Valid, 112 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-04 20:48:11,530 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 150 states. [2024-11-04 20:48:11,537 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 150 to 148. [2024-11-04 20:48:11,538 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 97 states have (on average 1.2164948453608246) internal successors, (118), 101 states have internal predecessors, (118), 37 states have call successors, (37), 10 states have call predecessors, (37), 13 states have return successors, (45), 36 states have call predecessors, (45), 36 states have call successors, (45) [2024-11-04 20:48:11,539 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 200 transitions. [2024-11-04 20:48:11,539 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 200 transitions. Word has length 133 [2024-11-04 20:48:11,540 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:11,540 INFO L471 AbstractCegarLoop]: Abstraction has 148 states and 200 transitions. [2024-11-04 20:48:11,540 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 10.571428571428571) internal successors, (74), 8 states have internal predecessors, (74), 5 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-04 20:48:11,540 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 200 transitions. [2024-11-04 20:48:11,541 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 136 [2024-11-04 20:48:11,541 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:11,541 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:11,546 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:48:11,742 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:11,742 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:11,742 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:11,742 INFO L85 PathProgramCache]: Analyzing trace with hash 607048337, now seen corresponding path program 2 times [2024-11-04 20:48:11,743 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:11,743 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [329069299] [2024-11-04 20:48:11,743 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:11,743 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:11,743 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:11,746 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:11,746 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (12)] Waiting until timeout for monitored process [2024-11-04 20:48:11,983 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:11,986 INFO L255 TraceCheckSpWp]: Trace formula consists of 323 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-04 20:48:11,989 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:12,076 INFO L134 CoverageAnalysis]: Checked inductivity of 198 backedges. 119 proven. 0 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2024-11-04 20:48:12,076 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:12,305 INFO L134 CoverageAnalysis]: Checked inductivity of 198 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 173 trivial. 0 not checked. [2024-11-04 20:48:12,305 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:12,306 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [329069299] [2024-11-04 20:48:12,306 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [329069299] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:12,306 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:12,306 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [9] total 12 [2024-11-04 20:48:12,306 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1403791908] [2024-11-04 20:48:12,306 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:12,307 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2024-11-04 20:48:12,307 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:12,308 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-04 20:48:12,308 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=105, Unknown=0, NotChecked=0, Total=132 [2024-11-04 20:48:12,308 INFO L87 Difference]: Start difference. First operand 148 states and 200 transitions. Second operand has 9 states, 8 states have (on average 9.5) internal successors, (76), 9 states have internal predecessors, (76), 5 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-04 20:48:12,625 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:12,626 INFO L93 Difference]: Finished difference Result 278 states and 373 transitions. [2024-11-04 20:48:12,626 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-04 20:48:12,626 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 8 states have (on average 9.5) internal successors, (76), 9 states have internal predecessors, (76), 5 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) Word has length 135 [2024-11-04 20:48:12,627 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:12,628 INFO L225 Difference]: With dead ends: 278 [2024-11-04 20:48:12,628 INFO L226 Difference]: Without dead ends: 149 [2024-11-04 20:48:12,629 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 273 GetRequests, 259 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=50, Invalid=190, Unknown=0, NotChecked=0, Total=240 [2024-11-04 20:48:12,630 INFO L432 NwaCegarLoop]: 161 mSDtfsCounter, 60 mSDsluCounter, 997 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 50 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 65 SdHoareTripleChecker+Valid, 1158 SdHoareTripleChecker+Invalid, 199 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 50 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:12,631 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [65 Valid, 1158 Invalid, 199 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [50 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-04 20:48:12,632 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 149 states. [2024-11-04 20:48:12,646 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 149 to 144. [2024-11-04 20:48:12,647 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 144 states, 94 states have (on average 1.2127659574468086) internal successors, (114), 97 states have internal predecessors, (114), 37 states have call successors, (37), 10 states have call predecessors, (37), 12 states have return successors, (43), 36 states have call predecessors, (43), 36 states have call successors, (43) [2024-11-04 20:48:12,648 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 144 states to 144 states and 194 transitions. [2024-11-04 20:48:12,649 INFO L78 Accepts]: Start accepts. Automaton has 144 states and 194 transitions. Word has length 135 [2024-11-04 20:48:12,649 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:12,650 INFO L471 AbstractCegarLoop]: Abstraction has 144 states and 194 transitions. [2024-11-04 20:48:12,651 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 8 states have (on average 9.5) internal successors, (76), 9 states have internal predecessors, (76), 5 states have call successors, (17), 2 states have call predecessors, (17), 3 states have return successors, (16), 4 states have call predecessors, (16), 5 states have call successors, (16) [2024-11-04 20:48:12,651 INFO L276 IsEmpty]: Start isEmpty. Operand 144 states and 194 transitions. [2024-11-04 20:48:12,653 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 145 [2024-11-04 20:48:12,653 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:12,653 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:12,658 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (12)] Ended with exit code 0 [2024-11-04 20:48:12,854 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:12,854 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:12,854 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:12,854 INFO L85 PathProgramCache]: Analyzing trace with hash -414762403, now seen corresponding path program 1 times [2024-11-04 20:48:12,854 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:12,855 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [510100485] [2024-11-04 20:48:12,855 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:12,855 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:12,855 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:12,857 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:12,858 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (13)] Waiting until timeout for monitored process [2024-11-04 20:48:13,317 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:13,330 INFO L255 TraceCheckSpWp]: Trace formula consists of 345 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-04 20:48:13,332 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:13,375 INFO L134 CoverageAnalysis]: Checked inductivity of 207 backedges. 109 proven. 0 refuted. 0 times theorem prover too weak. 98 trivial. 0 not checked. [2024-11-04 20:48:13,376 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:13,478 INFO L134 CoverageAnalysis]: Checked inductivity of 207 backedges. 21 proven. 8 refuted. 0 times theorem prover too weak. 178 trivial. 0 not checked. [2024-11-04 20:48:13,478 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:13,478 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [510100485] [2024-11-04 20:48:13,478 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [510100485] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:13,478 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:13,478 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [7] total 8 [2024-11-04 20:48:13,479 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1443919401] [2024-11-04 20:48:13,479 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:13,479 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2024-11-04 20:48:13,479 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:13,479 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-04 20:48:13,480 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-04 20:48:13,480 INFO L87 Difference]: Start difference. First operand 144 states and 194 transitions. Second operand has 7 states, 6 states have (on average 11.333333333333334) internal successors, (68), 6 states have internal predecessors, (68), 3 states have call successors, (17), 2 states have call predecessors, (17), 4 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2024-11-04 20:48:13,577 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:13,577 INFO L93 Difference]: Finished difference Result 265 states and 355 transitions. [2024-11-04 20:48:13,578 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-04 20:48:13,578 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 11.333333333333334) internal successors, (68), 6 states have internal predecessors, (68), 3 states have call successors, (17), 2 states have call predecessors, (17), 4 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) Word has length 144 [2024-11-04 20:48:13,578 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:13,580 INFO L225 Difference]: With dead ends: 265 [2024-11-04 20:48:13,580 INFO L226 Difference]: Without dead ends: 144 [2024-11-04 20:48:13,580 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 286 GetRequests, 280 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:48:13,581 INFO L432 NwaCegarLoop]: 165 mSDtfsCounter, 0 mSDsluCounter, 795 mSDsCounter, 0 mSdLazyCounter, 97 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 960 SdHoareTripleChecker+Invalid, 98 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 97 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:13,581 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 960 Invalid, 98 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 97 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-04 20:48:13,581 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 144 states. [2024-11-04 20:48:13,587 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 144 to 142. [2024-11-04 20:48:13,588 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 142 states, 93 states have (on average 1.2150537634408602) internal successors, (113), 95 states have internal predecessors, (113), 37 states have call successors, (37), 10 states have call predecessors, (37), 11 states have return successors, (39), 36 states have call predecessors, (39), 36 states have call successors, (39) [2024-11-04 20:48:13,589 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 189 transitions. [2024-11-04 20:48:13,589 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 189 transitions. Word has length 144 [2024-11-04 20:48:13,590 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:13,590 INFO L471 AbstractCegarLoop]: Abstraction has 142 states and 189 transitions. [2024-11-04 20:48:13,590 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 11.333333333333334) internal successors, (68), 6 states have internal predecessors, (68), 3 states have call successors, (17), 2 states have call predecessors, (17), 4 states have return successors, (16), 3 states have call predecessors, (16), 3 states have call successors, (16) [2024-11-04 20:48:13,590 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 189 transitions. [2024-11-04 20:48:13,591 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 147 [2024-11-04 20:48:13,591 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:13,591 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 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, 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:48:13,615 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (13)] Ended with exit code 0 [2024-11-04 20:48:13,792 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:13,792 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:13,793 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:13,793 INFO L85 PathProgramCache]: Analyzing trace with hash -2117607862, now seen corresponding path program 3 times [2024-11-04 20:48:13,793 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:13,793 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1328215307] [2024-11-04 20:48:13,793 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:13,793 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:13,793 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:13,794 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:13,795 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (14)] Waiting until timeout for monitored process [2024-11-04 20:48:14,242 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:14,266 INFO L255 TraceCheckSpWp]: Trace formula consists of 349 conjuncts, 32 conjuncts are in the unsatisfiable core [2024-11-04 20:48:14,270 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:14,366 INFO L349 Elim1Store]: treesize reduction 21, result has 25.0 percent of original size [2024-11-04 20:48:14,366 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 1 case distinctions, treesize of input 16 treesize of output 17 [2024-11-04 20:48:14,385 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:48:14,400 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 58 treesize of output 23 [2024-11-04 20:48:14,406 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 1 [2024-11-04 20:48:15,305 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 123 proven. 1 refuted. 0 times theorem prover too weak. 87 trivial. 0 not checked. [2024-11-04 20:48:15,305 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:15,708 INFO L349 Elim1Store]: treesize reduction 4, result has 63.6 percent of original size [2024-11-04 20:48:15,708 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 24 treesize of output 23 [2024-11-04 20:48:15,796 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 1 proven. 15 refuted. 0 times theorem prover too weak. 195 trivial. 0 not checked. [2024-11-04 20:48:15,796 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:15,796 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1328215307] [2024-11-04 20:48:15,796 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1328215307] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 20:48:15,796 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 20:48:15,796 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 8] total 19 [2024-11-04 20:48:15,797 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1526339605] [2024-11-04 20:48:15,797 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 20:48:15,797 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-04 20:48:15,797 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:15,798 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-04 20:48:15,798 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=44, Invalid=298, Unknown=0, NotChecked=0, Total=342 [2024-11-04 20:48:15,798 INFO L87 Difference]: Start difference. First operand 142 states and 189 transitions. Second operand has 19 states, 19 states have (on average 6.157894736842105) internal successors, (117), 17 states have internal predecessors, (117), 6 states have call successors, (32), 2 states have call predecessors, (32), 3 states have return successors, (32), 7 states have call predecessors, (32), 6 states have call successors, (32) [2024-11-04 20:48:18,604 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:18,604 INFO L93 Difference]: Finished difference Result 289 states and 398 transitions. [2024-11-04 20:48:18,604 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2024-11-04 20:48:18,605 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 19 states have (on average 6.157894736842105) internal successors, (117), 17 states have internal predecessors, (117), 6 states have call successors, (32), 2 states have call predecessors, (32), 3 states have return successors, (32), 7 states have call predecessors, (32), 6 states have call successors, (32) Word has length 146 [2024-11-04 20:48:18,605 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:18,607 INFO L225 Difference]: With dead ends: 289 [2024-11-04 20:48:18,607 INFO L226 Difference]: Without dead ends: 167 [2024-11-04 20:48:18,608 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 310 GetRequests, 277 SyntacticMatches, 5 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 93 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=113, Invalid=757, Unknown=0, NotChecked=0, Total=870 [2024-11-04 20:48:18,609 INFO L432 NwaCegarLoop]: 151 mSDtfsCounter, 90 mSDsluCounter, 1490 mSDsCounter, 0 mSdLazyCounter, 873 mSolverCounterSat, 58 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 94 SdHoareTripleChecker+Valid, 1641 SdHoareTripleChecker+Invalid, 931 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 58 IncrementalHoareTripleChecker+Valid, 873 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.3s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:18,609 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [94 Valid, 1641 Invalid, 931 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [58 Valid, 873 Invalid, 0 Unknown, 0 Unchecked, 2.3s Time] [2024-11-04 20:48:18,610 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 167 states. [2024-11-04 20:48:18,623 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 167 to 147. [2024-11-04 20:48:18,623 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 147 states, 97 states have (on average 1.2164948453608246) internal successors, (118), 99 states have internal predecessors, (118), 37 states have call successors, (37), 10 states have call predecessors, (37), 12 states have return successors, (42), 37 states have call predecessors, (42), 36 states have call successors, (42) [2024-11-04 20:48:18,624 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 147 states to 147 states and 197 transitions. [2024-11-04 20:48:18,624 INFO L78 Accepts]: Start accepts. Automaton has 147 states and 197 transitions. Word has length 146 [2024-11-04 20:48:18,625 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:18,625 INFO L471 AbstractCegarLoop]: Abstraction has 147 states and 197 transitions. [2024-11-04 20:48:18,625 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 19 states have (on average 6.157894736842105) internal successors, (117), 17 states have internal predecessors, (117), 6 states have call successors, (32), 2 states have call predecessors, (32), 3 states have return successors, (32), 7 states have call predecessors, (32), 6 states have call successors, (32) [2024-11-04 20:48:18,626 INFO L276 IsEmpty]: Start isEmpty. Operand 147 states and 197 transitions. [2024-11-04 20:48:18,627 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 147 [2024-11-04 20:48:18,627 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:18,627 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 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, 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:48:18,648 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (14)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:18,827 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:18,827 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:18,828 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:18,828 INFO L85 PathProgramCache]: Analyzing trace with hash -1236283894, now seen corresponding path program 1 times [2024-11-04 20:48:18,828 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:18,828 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1007029412] [2024-11-04 20:48:18,828 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:18,828 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:18,828 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:18,830 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:18,831 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (15)] Waiting until timeout for monitored process [2024-11-04 20:48:19,066 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:19,068 INFO L255 TraceCheckSpWp]: Trace formula consists of 339 conjuncts, 4 conjuncts are in the unsatisfiable core [2024-11-04 20:48:19,071 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:19,092 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 122 proven. 0 refuted. 0 times theorem prover too weak. 89 trivial. 0 not checked. [2024-11-04 20:48:19,092 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:19,198 INFO L134 CoverageAnalysis]: Checked inductivity of 211 backedges. 1 proven. 12 refuted. 0 times theorem prover too weak. 198 trivial. 0 not checked. [2024-11-04 20:48:19,198 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:19,198 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1007029412] [2024-11-04 20:48:19,198 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1007029412] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-04 20:48:19,198 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-04 20:48:19,198 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [5] total 5 [2024-11-04 20:48:19,198 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1047405196] [2024-11-04 20:48:19,199 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-04 20:48:19,199 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-04 20:48:19,199 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:19,199 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-04 20:48:19,199 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-04 20:48:19,200 INFO L87 Difference]: Start difference. First operand 147 states and 197 transitions. Second operand has 5 states, 5 states have (on average 15.0) internal successors, (75), 4 states have internal predecessors, (75), 2 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 3 states have call predecessors, (17), 2 states have call successors, (17) [2024-11-04 20:48:19,264 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:19,264 INFO L93 Difference]: Finished difference Result 273 states and 373 transitions. [2024-11-04 20:48:19,265 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2024-11-04 20:48:19,265 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 15.0) internal successors, (75), 4 states have internal predecessors, (75), 2 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 3 states have call predecessors, (17), 2 states have call successors, (17) Word has length 146 [2024-11-04 20:48:19,265 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:19,266 INFO L225 Difference]: With dead ends: 273 [2024-11-04 20:48:19,266 INFO L226 Difference]: Without dead ends: 146 [2024-11-04 20:48:19,267 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 290 GetRequests, 287 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:48:19,268 INFO L432 NwaCegarLoop]: 180 mSDtfsCounter, 0 mSDsluCounter, 529 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 709 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:19,268 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 709 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-04 20:48:19,269 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 146 states. [2024-11-04 20:48:19,282 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 146 to 146. [2024-11-04 20:48:19,283 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 146 states, 96 states have (on average 1.1979166666666667) internal successors, (115), 98 states have internal predecessors, (115), 37 states have call successors, (37), 10 states have call predecessors, (37), 12 states have return successors, (42), 37 states have call predecessors, (42), 36 states have call successors, (42) [2024-11-04 20:48:19,284 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 194 transitions. [2024-11-04 20:48:19,284 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 194 transitions. Word has length 146 [2024-11-04 20:48:19,284 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:19,285 INFO L471 AbstractCegarLoop]: Abstraction has 146 states and 194 transitions. [2024-11-04 20:48:19,285 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 15.0) internal successors, (75), 4 states have internal predecessors, (75), 2 states have call successors, (18), 2 states have call predecessors, (18), 3 states have return successors, (17), 3 states have call predecessors, (17), 2 states have call successors, (17) [2024-11-04 20:48:19,285 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 194 transitions. [2024-11-04 20:48:19,286 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 149 [2024-11-04 20:48:19,286 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:19,286 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 4, 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, 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:48:19,291 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (15)] Forceful destruction successful, exit code 0 [2024-11-04 20:48:19,486 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:19,487 INFO L396 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:19,487 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:19,487 INFO L85 PathProgramCache]: Analyzing trace with hash -39271282, now seen corresponding path program 1 times [2024-11-04 20:48:19,487 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:19,487 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1657306857] [2024-11-04 20:48:19,487 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:19,487 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:19,487 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:19,488 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-04 20:48:19,490 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (16)] Waiting until timeout for monitored process [2024-11-04 20:48:19,925 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:19,929 INFO L255 TraceCheckSpWp]: Trace formula consists of 353 conjuncts, 35 conjuncts are in the unsatisfiable core [2024-11-04 20:48:19,934 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:20,001 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 24 treesize of output 32 [2024-11-04 20:48:20,015 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 8 treesize of output 1 [2024-11-04 20:48:20,032 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 1 [2024-11-04 20:48:21,421 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 110 proven. 34 refuted. 0 times theorem prover too weak. 72 trivial. 0 not checked. [2024-11-04 20:48:21,422 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:22,452 INFO L349 Elim1Store]: treesize reduction 17, result has 63.0 percent of original size [2024-11-04 20:48:22,452 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 86 treesize of output 95 [2024-11-04 20:48:22,472 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-04 20:48:22,473 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 87 treesize of output 89 [2024-11-04 20:48:22,489 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 62 treesize of output 60 [2024-11-04 20:48:22,596 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 24 treesize of output 22 [2024-11-04 20:48:22,670 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 10 proven. 35 refuted. 0 times theorem prover too weak. 171 trivial. 0 not checked. [2024-11-04 20:48:22,670 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:22,670 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1657306857] [2024-11-04 20:48:22,670 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1657306857] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 20:48:22,670 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 20:48:22,670 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 16] total 31 [2024-11-04 20:48:22,670 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1827120141] [2024-11-04 20:48:22,671 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 20:48:22,671 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2024-11-04 20:48:22,671 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:22,672 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2024-11-04 20:48:22,673 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=824, Unknown=0, NotChecked=0, Total=930 [2024-11-04 20:48:22,674 INFO L87 Difference]: Start difference. First operand 146 states and 194 transitions. Second operand has 31 states, 31 states have (on average 4.580645161290323) internal successors, (142), 29 states have internal predecessors, (142), 15 states have call successors, (33), 3 states have call predecessors, (33), 6 states have return successors, (32), 15 states have call predecessors, (32), 14 states have call successors, (32) [2024-11-04 20:48:27,393 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:48:27,394 INFO L93 Difference]: Finished difference Result 451 states and 604 transitions. [2024-11-04 20:48:27,394 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2024-11-04 20:48:27,394 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 31 states have (on average 4.580645161290323) internal successors, (142), 29 states have internal predecessors, (142), 15 states have call successors, (33), 3 states have call predecessors, (33), 6 states have return successors, (32), 15 states have call predecessors, (32), 14 states have call successors, (32) Word has length 148 [2024-11-04 20:48:27,395 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:48:27,419 INFO L225 Difference]: With dead ends: 451 [2024-11-04 20:48:27,420 INFO L226 Difference]: Without dead ends: 332 [2024-11-04 20:48:27,421 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 329 GetRequests, 267 SyntacticMatches, 10 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 566 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=373, Invalid=2489, Unknown=0, NotChecked=0, Total=2862 [2024-11-04 20:48:27,422 INFO L432 NwaCegarLoop]: 174 mSDtfsCounter, 294 mSDsluCounter, 2344 mSDsCounter, 0 mSdLazyCounter, 1819 mSolverCounterSat, 140 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 300 SdHoareTripleChecker+Valid, 2518 SdHoareTripleChecker+Invalid, 1959 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 140 IncrementalHoareTripleChecker+Valid, 1819 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.6s IncrementalHoareTripleChecker+Time [2024-11-04 20:48:27,423 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [300 Valid, 2518 Invalid, 1959 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [140 Valid, 1819 Invalid, 0 Unknown, 0 Unchecked, 3.6s Time] [2024-11-04 20:48:27,423 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 332 states. [2024-11-04 20:48:27,456 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 332 to 280. [2024-11-04 20:48:27,457 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 280 states, 194 states have (on average 1.2216494845360826) internal successors, (237), 197 states have internal predecessors, (237), 63 states have call successors, (63), 18 states have call predecessors, (63), 22 states have return successors, (80), 64 states have call predecessors, (80), 61 states have call successors, (80) [2024-11-04 20:48:27,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 280 states to 280 states and 380 transitions. [2024-11-04 20:48:27,459 INFO L78 Accepts]: Start accepts. Automaton has 280 states and 380 transitions. Word has length 148 [2024-11-04 20:48:27,461 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:48:27,461 INFO L471 AbstractCegarLoop]: Abstraction has 280 states and 380 transitions. [2024-11-04 20:48:27,461 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 31 states have (on average 4.580645161290323) internal successors, (142), 29 states have internal predecessors, (142), 15 states have call successors, (33), 3 states have call predecessors, (33), 6 states have return successors, (32), 15 states have call predecessors, (32), 14 states have call successors, (32) [2024-11-04 20:48:27,461 INFO L276 IsEmpty]: Start isEmpty. Operand 280 states and 380 transitions. [2024-11-04 20:48:27,463 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 149 [2024-11-04 20:48:27,463 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:48:27,463 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 4, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-04 20:48:27,474 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:48:27,663 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:27,664 INFO L396 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:48:27,664 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:48:27,665 INFO L85 PathProgramCache]: Analyzing trace with hash 904936916, now seen corresponding path program 1 times [2024-11-04 20:48:27,665 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:48:27,665 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1335505465] [2024-11-04 20:48:27,665 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:48:27,665 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:48:27,665 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:48:27,667 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:48:27,670 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:48:28,143 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:48:28,148 INFO L255 TraceCheckSpWp]: Trace formula consists of 362 conjuncts, 31 conjuncts are in the unsatisfiable core [2024-11-04 20:48:28,154 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:48:28,217 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 24 treesize of output 32 [2024-11-04 20:48:28,221 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 40 treesize of output 21 [2024-11-04 20:48:28,224 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 12 treesize of output 1 [2024-11-04 20:48:29,714 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 117 proven. 25 refuted. 0 times theorem prover too weak. 74 trivial. 0 not checked. [2024-11-04 20:48:29,714 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:48:32,677 INFO L349 Elim1Store]: treesize reduction 4, result has 63.6 percent of original size [2024-11-04 20:48:32,677 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 30 treesize of output 25 [2024-11-04 20:48:32,804 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 10 proven. 33 refuted. 0 times theorem prover too weak. 173 trivial. 0 not checked. [2024-11-04 20:48:32,805 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:48:32,805 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1335505465] [2024-11-04 20:48:32,805 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1335505465] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-04 20:48:32,805 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-04 20:48:32,805 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 10] total 22 [2024-11-04 20:48:32,805 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1005565554] [2024-11-04 20:48:32,805 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-04 20:48:32,806 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-04 20:48:32,806 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:48:32,806 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-04 20:48:32,807 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=387, Unknown=0, NotChecked=0, Total=462 [2024-11-04 20:48:32,807 INFO L87 Difference]: Start difference. First operand 280 states and 380 transitions. Second operand has 22 states, 22 states have (on average 6.2727272727272725) internal successors, (138), 20 states have internal predecessors, (138), 11 states have call successors, (33), 4 states have call predecessors, (33), 6 states have return successors, (32), 11 states have call predecessors, (32), 10 states have call successors, (32) [2024-11-04 20:48:36,993 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 20:48:41,131 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 20:48:45,234 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 20:48:49,245 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 20:48:53,856 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 20:49:03,101 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 20:49:07,333 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, BitVec], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-04 20:49:10,947 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-04 20:49:10,947 INFO L93 Difference]: Finished difference Result 591 states and 783 transitions. [2024-11-04 20:49:10,947 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2024-11-04 20:49:10,948 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 22 states have (on average 6.2727272727272725) internal successors, (138), 20 states have internal predecessors, (138), 11 states have call successors, (33), 4 states have call predecessors, (33), 6 states have return successors, (32), 11 states have call predecessors, (32), 10 states have call successors, (32) Word has length 148 [2024-11-04 20:49:10,948 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-04 20:49:10,950 INFO L225 Difference]: With dead ends: 591 [2024-11-04 20:49:10,951 INFO L226 Difference]: Without dead ends: 384 [2024-11-04 20:49:10,952 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 313 GetRequests, 268 SyntacticMatches, 11 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 290 ImplicationChecksByTransitivity, 2.6s TimeCoverageRelationStatistics Valid=211, Invalid=1049, Unknown=0, NotChecked=0, Total=1260 [2024-11-04 20:49:10,952 INFO L432 NwaCegarLoop]: 175 mSDtfsCounter, 151 mSDsluCounter, 1883 mSDsCounter, 0 mSdLazyCounter, 1181 mSolverCounterSat, 116 mSolverCounterUnsat, 7 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 36.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 155 SdHoareTripleChecker+Valid, 2058 SdHoareTripleChecker+Invalid, 1304 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 116 IncrementalHoareTripleChecker+Valid, 1181 IncrementalHoareTripleChecker+Invalid, 7 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 36.6s IncrementalHoareTripleChecker+Time [2024-11-04 20:49:10,952 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [155 Valid, 2058 Invalid, 1304 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [116 Valid, 1181 Invalid, 7 Unknown, 0 Unchecked, 36.6s Time] [2024-11-04 20:49:10,953 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 384 states. [2024-11-04 20:49:10,993 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 384 to 370. [2024-11-04 20:49:10,994 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 370 states, 265 states have (on average 1.2226415094339622) internal successors, (324), 272 states have internal predecessors, (324), 71 states have call successors, (71), 24 states have call predecessors, (71), 33 states have return successors, (95), 73 states have call predecessors, (95), 68 states have call successors, (95) [2024-11-04 20:49:10,996 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 370 states to 370 states and 490 transitions. [2024-11-04 20:49:10,997 INFO L78 Accepts]: Start accepts. Automaton has 370 states and 490 transitions. Word has length 148 [2024-11-04 20:49:10,997 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-04 20:49:10,997 INFO L471 AbstractCegarLoop]: Abstraction has 370 states and 490 transitions. [2024-11-04 20:49:10,998 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 22 states have (on average 6.2727272727272725) internal successors, (138), 20 states have internal predecessors, (138), 11 states have call successors, (33), 4 states have call predecessors, (33), 6 states have return successors, (32), 11 states have call predecessors, (32), 10 states have call successors, (32) [2024-11-04 20:49:10,998 INFO L276 IsEmpty]: Start isEmpty. Operand 370 states and 490 transitions. [2024-11-04 20:49:11,000 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 149 [2024-11-04 20:49:11,000 INFO L207 NwaCegarLoop]: Found error trace [2024-11-04 20:49:11,001 INFO L215 NwaCegarLoop]: trace histogram [9, 9, 9, 4, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 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:11,011 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (17)] Forceful destruction successful, exit code 0 [2024-11-04 20:49:11,202 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:11,202 INFO L396 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-04 20:49:11,202 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-04 20:49:11,202 INFO L85 PathProgramCache]: Analyzing trace with hash 95590290, now seen corresponding path program 1 times [2024-11-04 20:49:11,202 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-04 20:49:11,203 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1299159420] [2024-11-04 20:49:11,203 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-04 20:49:11,203 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2024-11-04 20:49:11,203 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2024-11-04 20:49:11,204 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:11,205 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:11,709 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-04 20:49:11,715 INFO L255 TraceCheckSpWp]: Trace formula consists of 359 conjuncts, 30 conjuncts are in the unsatisfiable core [2024-11-04 20:49:11,719 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-04 20:49:12,042 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-04 20:49:12,042 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 14 treesize of output 15 [2024-11-04 20:49:18,082 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 52 proven. 0 refuted. 0 times theorem prover too weak. 164 trivial. 0 not checked. [2024-11-04 20:49:18,082 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-04 20:49:20,641 INFO L349 Elim1Store]: treesize reduction 19, result has 62.0 percent of original size [2024-11-04 20:49:20,641 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 198 treesize of output 185 [2024-11-04 20:49:20,765 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-04 20:49:20,766 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 103 treesize of output 119 [2024-11-04 20:49:20,785 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 68 treesize of output 64 [2024-11-04 20:49:21,019 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 6 treesize of output 4 [2024-11-04 20:49:21,266 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 6 treesize of output 4 [2024-11-04 20:49:21,311 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-04 20:49:21,311 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 24 treesize of output 28 [2024-11-04 20:49:21,332 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 31 treesize of output 23 [2024-11-04 20:49:21,386 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-04 20:49:21,387 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 33 treesize of output 37 [2024-11-04 20:49:21,798 INFO L134 CoverageAnalysis]: Checked inductivity of 216 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 196 trivial. 0 not checked. [2024-11-04 20:49:21,798 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-04 20:49:21,798 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1299159420] [2024-11-04 20:49:21,798 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1299159420] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-04 20:49:21,798 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-04 20:49:21,798 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12, 11] imperfect sequences [] total 21 [2024-11-04 20:49:21,799 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [897855996] [2024-11-04 20:49:21,799 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-04 20:49:21,799 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-04 20:49:21,799 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-04 20:49:21,800 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-04 20:49:21,800 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=355, Unknown=0, NotChecked=0, Total=420 [2024-11-04 20:49:21,800 INFO L87 Difference]: Start difference. First operand 370 states and 490 transitions. Second operand has 21 states, 21 states have (on average 5.095238095238095) internal successors, (107), 21 states have internal predecessors, (107), 11 states have call successors, (31), 3 states have call predecessors, (31), 4 states have return successors, (30), 11 states have call predecessors, (30), 10 states have call successors, (30)