/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 'cvc5 --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_rend_harness_negated.i -------------------------------------------------------------------------------- This is Ultimate 0.2.5-dev-b75d321-m [2024-11-05 02:30:37,804 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-05 02:30:37,876 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-05 02:30:37,881 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-05 02:30:37,882 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-05 02:30:37,902 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-05 02:30:37,903 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-05 02:30:37,903 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-05 02:30:37,904 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-05 02:30:37,905 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-05 02:30:37,905 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-05 02:30:37,905 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-05 02:30:37,906 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-05 02:30:37,906 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-05 02:30:37,908 INFO L153 SettingsManager]: * Use SBE=true [2024-11-05 02:30:37,908 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-05 02:30:37,908 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-05 02:30:37,908 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-05 02:30:37,908 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-05 02:30:37,908 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-05 02:30:37,909 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-05 02:30:37,910 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-05 02:30:37,911 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-05 02:30:37,911 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-05 02:30:37,911 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-05 02:30:37,911 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-05 02:30:37,911 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-05 02:30:37,911 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-05 02:30:37,912 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-05 02:30:37,912 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-05 02:30:37,912 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-05 02:30:37,912 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-05 02:30:37,912 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-05 02:30:37,912 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-05 02:30:37,913 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-05 02:30:37,913 INFO L153 SettingsManager]: * Trace refinement strategy=WOLF [2024-11-05 02:30:37,913 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-05 02:30:37,913 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-05 02:30:37,913 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-05 02:30:37,913 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-05 02:30:37,913 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-05 02:30:37,915 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 -> cvc5 --incremental --print-success --lang smt [2024-11-05 02:30:38,097 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-05 02:30:38,116 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-05 02:30:38,118 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-05 02:30:38,119 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-05 02:30:38,119 INFO L274 PluginConnector]: CDTParser initialized [2024-11-05 02:30:38,120 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_rend_harness_negated.i [2024-11-05 02:30:39,600 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-05 02:30:39,985 INFO L384 CDTParser]: Found 1 translation units. [2024-11-05 02:30:39,986 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_rend_harness_negated.i [2024-11-05 02:30:40,018 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/813dcafa2/6ce9d67314c34552ae96213772d68071/FLAGce1f9e7af [2024-11-05 02:30:40,032 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/813dcafa2/6ce9d67314c34552ae96213772d68071 [2024-11-05 02:30:40,034 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-05 02:30:40,035 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-11-05 02:30:40,037 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-05 02:30:40,037 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-05 02:30:40,042 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-05 02:30:40,043 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.11 02:30:40" (1/1) ... [2024-11-05 02:30:40,044 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@57a569c9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:40, skipping insertion in model container [2024-11-05 02:30:40,044 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.11 02:30:40" (1/1) ... [2024-11-05 02:30:40,161 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-05 02:30:40,353 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_rend_harness_negated.i[4494,4507] [2024-11-05 02:30:40,359 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_rend_harness_negated.i[4554,4567] [2024-11-05 02:30:40,786 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-05 02:30:40,872 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-05 02:30:40,873 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-05 02:30:40,873 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-05 02:30:40,884 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-05 02:30:40,886 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:40,887 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:40,887 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:40,888 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-05 02:30:40,888 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:40,889 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:40,891 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-05 02:30:40,891 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-05 02:30:40,893 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-05 02:30:40,893 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-05 02:30:40,899 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:40,899 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-05 02:30:40,899 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:40,899 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-05 02:30:40,901 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:40,901 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-05 02:30:40,901 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:40,901 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-05 02:30:40,903 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:40,905 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-05 02:30:40,905 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:40,906 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-05 02:30:40,906 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:40,906 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,114 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-05 02:30:41,114 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-05 02:30:41,115 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-05 02:30:41,115 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-05 02:30:41,197 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:30:41,209 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-05 02:30:41,234 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-05 02:30:41,260 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-05 02:30:41,265 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_rend_harness_negated.i[4494,4507] [2024-11-05 02:30:41,266 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_rend_harness_negated.i[4554,4567] [2024-11-05 02:30:41,291 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-05 02:30:41,311 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-05 02:30:41,312 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-05 02:30:41,312 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-05 02:30:41,318 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-05 02:30:41,323 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,324 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,324 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,324 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-05 02:30:41,324 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,325 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,326 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-05 02:30:41,329 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-05 02:30:41,330 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-05 02:30:41,330 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-05 02:30:41,338 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,339 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-05 02:30:41,339 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,339 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-05 02:30:41,340 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,340 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-05 02:30:41,340 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,340 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-05 02:30:41,344 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,345 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-05 02:30:41,345 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,345 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-05 02:30:41,345 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,345 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,395 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-05 02:30:41,396 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:30:41,397 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-05 02:30:41,397 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-05 02:30:41,422 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-05 02:30:41,431 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-05 02:30:41,438 INFO L200 MainTranslator]: Completed pre-run [2024-11-05 02:30:41,452 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_rend_harness_negated.i[4494,4507] [2024-11-05 02:30:41,453 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_rend_harness_negated.i[4554,4567] [2024-11-05 02:30:41,550 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,550 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,550 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,551 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,551 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,558 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,559 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,560 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,560 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,561 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,561 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,562 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,562 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:30:41,627 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-05 02:30:41,820 WARN L710 CHandler]: The following functions are not defined or handled internally: aws_array_list_ensure_capacity [2024-11-05 02:30:41,831 INFO L204 MainTranslator]: Completed translation [2024-11-05 02:30:41,831 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41 WrapperNode [2024-11-05 02:30:41,831 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-05 02:30:41,832 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-05 02:30:41,832 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-05 02:30:41,832 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-05 02:30:41,838 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (1/1) ... [2024-11-05 02:30:41,924 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (1/1) ... [2024-11-05 02:30:41,976 INFO L138 Inliner]: procedures = 687, calls = 1038, calls flagged for inlining = 52, calls inlined = 6, statements flattened = 138 [2024-11-05 02:30:41,977 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-05 02:30:41,977 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-05 02:30:41,977 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-05 02:30:41,978 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-05 02:30:41,988 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (1/1) ... [2024-11-05 02:30:41,988 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (1/1) ... [2024-11-05 02:30:41,993 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (1/1) ... [2024-11-05 02:30:42,017 INFO L175 MemorySlicer]: Split 21 memory accesses to 3 slices as follows [2, 5, 14]. 67 percent of accesses are in the largest equivalence class. The 7 initializations are split as follows [2, 5, 0]. The 6 writes are split as follows [0, 0, 6]. [2024-11-05 02:30:42,017 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (1/1) ... [2024-11-05 02:30:42,018 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (1/1) ... [2024-11-05 02:30:42,035 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (1/1) ... [2024-11-05 02:30:42,042 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (1/1) ... [2024-11-05 02:30:42,054 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (1/1) ... [2024-11-05 02:30:42,056 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (1/1) ... [2024-11-05 02:30:42,068 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-05 02:30:42,069 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-05 02:30:42,069 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-05 02:30:42,069 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-05 02:30:42,070 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (1/1) ... [2024-11-05 02:30:42,076 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-05 02:30:42,085 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-05 02:30:42,100 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-05 02:30:42,106 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-05 02:30:42,130 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-05 02:30:42,131 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-05 02:30:42,131 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-05 02:30:42,131 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2024-11-05 02:30:42,132 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-05 02:30:42,132 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-05 02:30:42,132 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2024-11-05 02:30:42,132 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2024-11-05 02:30:42,132 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-05 02:30:42,133 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2024-11-05 02:30:42,133 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2024-11-05 02:30:42,133 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-05 02:30:42,133 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-05 02:30:42,133 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-05 02:30:42,133 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2024-11-05 02:30:42,133 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-05 02:30:42,134 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-05 02:30:42,134 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-05 02:30:42,134 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-05 02:30:42,134 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-05 02:30:42,134 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-05 02:30:42,134 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-05 02:30:42,134 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2024-11-05 02:30:42,134 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2024-11-05 02:30:42,134 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2024-11-05 02:30:42,134 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2024-11-05 02:30:42,134 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2024-11-05 02:30:42,134 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2024-11-05 02:30:42,424 INFO L238 CfgBuilder]: Building ICFG [2024-11-05 02:30:42,426 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-05 02:30:42,775 INFO L? ?]: Removed 54 outVars from TransFormulas that were not future-live. [2024-11-05 02:30:42,776 INFO L287 CfgBuilder]: Performing block encoding [2024-11-05 02:30:42,800 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-05 02:30:42,800 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-05 02:30:42,801 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.11 02:30:42 BoogieIcfgContainer [2024-11-05 02:30:42,801 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-05 02:30:42,803 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-05 02:30:42,803 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-05 02:30:42,813 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-05 02:30:42,813 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.11 02:30:40" (1/3) ... [2024-11-05 02:30:42,814 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b4b2820 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.11 02:30:42, skipping insertion in model container [2024-11-05 02:30:42,814 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:30:41" (2/3) ... [2024-11-05 02:30:42,814 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b4b2820 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.11 02:30:42, skipping insertion in model container [2024-11-05 02:30:42,815 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.11 02:30:42" (3/3) ... [2024-11-05 02:30:42,816 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_rend_harness_negated.i [2024-11-05 02:30:42,839 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-05 02:30:42,839 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-05 02:30:42,922 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-05 02:30:42,932 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;@5cc509d4, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-05 02:30:42,932 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-05 02:30:42,936 INFO L276 IsEmpty]: Start isEmpty. Operand has 68 states, 48 states have (on average 1.3541666666666667) internal successors, (65), 49 states have internal predecessors, (65), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2024-11-05 02:30:42,951 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-11-05 02:30:42,951 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:30:42,956 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-05 02:30:42,956 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:30:42,965 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:30:42,965 INFO L85 PathProgramCache]: Analyzing trace with hash -2107862704, now seen corresponding path program 1 times [2024-11-05 02:30:42,978 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:30:42,979 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1968374897] [2024-11-05 02:30:42,979 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:30:42,981 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:30:42,981 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:30:42,988 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:30:42,993 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (2)] Waiting until timeout for monitored process [2024-11-05 02:30:43,178 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:30:43,181 INFO L255 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-05 02:30:43,187 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:30:43,216 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2024-11-05 02:30:43,216 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:30:43,299 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2024-11-05 02:30:43,300 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:30:43,300 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1968374897] [2024-11-05 02:30:43,300 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1968374897] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:30:43,301 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:30:43,301 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-05 02:30:43,302 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2103568390] [2024-11-05 02:30:43,303 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:30:43,306 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-05 02:30:43,306 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:30:43,327 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-05 02:30:43,327 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-05 02:30:43,329 INFO L87 Difference]: Start difference. First operand has 68 states, 48 states have (on average 1.3541666666666667) internal successors, (65), 49 states have internal predecessors, (65), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) Second operand has 2 states, 2 states have (on average 14.5) internal successors, (29), 2 states have internal predecessors, (29), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-05 02:30:43,350 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:30:43,350 INFO L93 Difference]: Finished difference Result 128 states and 184 transitions. [2024-11-05 02:30:43,351 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-05 02:30:43,352 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 14.5) internal successors, (29), 2 states have internal predecessors, (29), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) Word has length 68 [2024-11-05 02:30:43,352 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:30:43,357 INFO L225 Difference]: With dead ends: 128 [2024-11-05 02:30:43,357 INFO L226 Difference]: Without dead ends: 63 [2024-11-05 02:30:43,360 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 134 GetRequests, 134 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-05 02:30:43,364 INFO L432 NwaCegarLoop]: 87 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, 87 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-05 02:30:43,365 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 87 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-05 02:30:43,379 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-11-05 02:30:43,393 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2024-11-05 02:30:43,394 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 44 states have (on average 1.2954545454545454) internal successors, (57), 45 states have internal predecessors, (57), 13 states have call successors, (13), 5 states have call predecessors, (13), 5 states have return successors, (12), 12 states have call predecessors, (12), 12 states have call successors, (12) [2024-11-05 02:30:43,396 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 82 transitions. [2024-11-05 02:30:43,400 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 82 transitions. Word has length 68 [2024-11-05 02:30:43,400 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:30:43,400 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 82 transitions. [2024-11-05 02:30:43,400 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 14.5) internal successors, (29), 2 states have internal predecessors, (29), 2 states have call successors, (8), 2 states have call predecessors, (8), 2 states have return successors, (7), 2 states have call predecessors, (7), 2 states have call successors, (7) [2024-11-05 02:30:43,400 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 82 transitions. [2024-11-05 02:30:43,403 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-11-05 02:30:43,403 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:30:43,403 INFO L215 NwaCegarLoop]: trace histogram [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] [2024-11-05 02:30:43,407 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (2)] Forceful destruction successful, exit code 0 [2024-11-05 02:30:43,604 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:30:43,604 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:30:43,605 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:30:43,605 INFO L85 PathProgramCache]: Analyzing trace with hash 900796622, now seen corresponding path program 1 times [2024-11-05 02:30:43,605 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:30:43,605 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [577919298] [2024-11-05 02:30:43,605 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:30:43,605 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:30:43,605 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:30:43,608 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:30:43,609 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (3)] Waiting until timeout for monitored process [2024-11-05 02:30:43,738 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:30:43,748 WARN L253 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 118 conjuncts are in the unsatisfiable core [2024-11-05 02:30:43,777 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:30:43,890 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:30:44,070 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:30:44,081 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 14 treesize of output 15 [2024-11-05 02:30:44,092 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 14 treesize of output 15 [2024-11-05 02:30:44,320 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:30:44,321 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:30:44,336 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:30:47,926 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2024-11-05 02:30:47,926 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:30:48,647 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2024-11-05 02:30:48,648 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:30:48,648 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [577919298] [2024-11-05 02:30:48,648 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [577919298] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-05 02:30:48,648 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-05 02:30:48,648 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15, 6] imperfect sequences [] total 18 [2024-11-05 02:30:48,648 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [231402083] [2024-11-05 02:30:48,648 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-05 02:30:48,649 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-05 02:30:48,650 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:30:48,650 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-05 02:30:48,651 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=260, Unknown=0, NotChecked=0, Total=306 [2024-11-05 02:30:48,651 INFO L87 Difference]: Start difference. First operand 63 states and 82 transitions. Second operand has 18 states, 15 states have (on average 3.466666666666667) internal successors, (52), 12 states have internal predecessors, (52), 7 states have call successors, (16), 4 states have call predecessors, (16), 4 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-05 02:30:50,710 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:30:50,711 INFO L93 Difference]: Finished difference Result 138 states and 184 transitions. [2024-11-05 02:30:50,713 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-05 02:30:50,714 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 15 states have (on average 3.466666666666667) internal successors, (52), 12 states have internal predecessors, (52), 7 states have call successors, (16), 4 states have call predecessors, (16), 4 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) Word has length 68 [2024-11-05 02:30:50,714 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:30:50,719 INFO L225 Difference]: With dead ends: 138 [2024-11-05 02:30:50,719 INFO L226 Difference]: Without dead ends: 136 [2024-11-05 02:30:50,720 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 113 SyntacticMatches, 6 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 160 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=96, Invalid=554, Unknown=0, NotChecked=0, Total=650 [2024-11-05 02:30:50,721 INFO L432 NwaCegarLoop]: 61 mSDtfsCounter, 64 mSDsluCounter, 642 mSDsCounter, 0 mSdLazyCounter, 338 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 72 SdHoareTripleChecker+Valid, 703 SdHoareTripleChecker+Invalid, 364 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 338 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2024-11-05 02:30:50,721 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [72 Valid, 703 Invalid, 364 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 338 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2024-11-05 02:30:50,726 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2024-11-05 02:30:50,774 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 128. [2024-11-05 02:30:50,775 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 128 states, 88 states have (on average 1.2954545454545454) internal successors, (114), 92 states have internal predecessors, (114), 26 states have call successors, (26), 11 states have call predecessors, (26), 13 states have return successors, (32), 24 states have call predecessors, (32), 24 states have call successors, (32) [2024-11-05 02:30:50,781 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 128 states to 128 states and 172 transitions. [2024-11-05 02:30:50,781 INFO L78 Accepts]: Start accepts. Automaton has 128 states and 172 transitions. Word has length 68 [2024-11-05 02:30:50,782 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:30:50,782 INFO L471 AbstractCegarLoop]: Abstraction has 128 states and 172 transitions. [2024-11-05 02:30:50,785 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 15 states have (on average 3.466666666666667) internal successors, (52), 12 states have internal predecessors, (52), 7 states have call successors, (16), 4 states have call predecessors, (16), 4 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-05 02:30:50,785 INFO L276 IsEmpty]: Start isEmpty. Operand 128 states and 172 transitions. [2024-11-05 02:30:50,787 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-05 02:30:50,787 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:30:50,788 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:30:50,791 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (3)] Forceful destruction successful, exit code 0 [2024-11-05 02:30:50,988 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:30:50,988 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:30:50,989 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:30:50,989 INFO L85 PathProgramCache]: Analyzing trace with hash 1974675530, now seen corresponding path program 1 times [2024-11-05 02:30:50,989 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:30:50,989 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1782775635] [2024-11-05 02:30:50,989 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:30:50,989 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:30:50,990 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:30:50,993 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:30:50,994 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (4)] Waiting until timeout for monitored process [2024-11-05 02:30:51,109 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:30:51,117 WARN L253 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 124 conjuncts are in the unsatisfiable core [2024-11-05 02:30:51,125 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:30:51,140 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:30:51,213 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 12 [2024-11-05 02:30:51,217 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:30:51,223 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 14 treesize of output 15 [2024-11-05 02:30:51,234 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 14 treesize of output 15 [2024-11-05 02:30:51,313 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:30:51,313 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:30:51,332 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:30:54,498 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2024-11-05 02:30:54,499 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:30:55,031 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2024-11-05 02:30:55,031 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:30:55,032 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1782775635] [2024-11-05 02:30:55,032 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1782775635] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-05 02:30:55,032 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-05 02:30:55,032 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [18, 7] imperfect sequences [] total 22 [2024-11-05 02:30:55,032 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1409565047] [2024-11-05 02:30:55,032 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-05 02:30:55,032 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-05 02:30:55,032 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:30:55,033 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-05 02:30:55,033 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=402, Unknown=0, NotChecked=0, Total=462 [2024-11-05 02:30:55,033 INFO L87 Difference]: Start difference. First operand 128 states and 172 transitions. Second operand has 22 states, 19 states have (on average 3.1052631578947367) internal successors, (59), 16 states have internal predecessors, (59), 7 states have call successors, (16), 4 states have call predecessors, (16), 5 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-05 02:30:57,552 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:30:57,552 INFO L93 Difference]: Finished difference Result 159 states and 214 transitions. [2024-11-05 02:30:57,552 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-05 02:30:57,553 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 19 states have (on average 3.1052631578947367) internal successors, (59), 16 states have internal predecessors, (59), 7 states have call successors, (16), 4 states have call predecessors, (16), 5 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) Word has length 70 [2024-11-05 02:30:57,553 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:30:57,555 INFO L225 Difference]: With dead ends: 159 [2024-11-05 02:30:57,555 INFO L226 Difference]: Without dead ends: 157 [2024-11-05 02:30:57,560 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 113 SyntacticMatches, 6 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 231 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=115, Invalid=815, Unknown=0, NotChecked=0, Total=930 [2024-11-05 02:30:57,563 INFO L432 NwaCegarLoop]: 57 mSDtfsCounter, 80 mSDsluCounter, 670 mSDsCounter, 0 mSdLazyCounter, 559 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 90 SdHoareTripleChecker+Valid, 727 SdHoareTripleChecker+Invalid, 598 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 559 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.8s IncrementalHoareTripleChecker+Time [2024-11-05 02:30:57,564 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [90 Valid, 727 Invalid, 598 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 559 Invalid, 0 Unknown, 0 Unchecked, 1.8s Time] [2024-11-05 02:30:57,565 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2024-11-05 02:30:57,614 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 130. [2024-11-05 02:30:57,614 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 90 states have (on average 1.288888888888889) internal successors, (116), 94 states have internal predecessors, (116), 26 states have call successors, (26), 11 states have call predecessors, (26), 13 states have return successors, (32), 24 states have call predecessors, (32), 24 states have call successors, (32) [2024-11-05 02:30:57,616 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 174 transitions. [2024-11-05 02:30:57,618 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 174 transitions. Word has length 70 [2024-11-05 02:30:57,619 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:30:57,619 INFO L471 AbstractCegarLoop]: Abstraction has 130 states and 174 transitions. [2024-11-05 02:30:57,619 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 19 states have (on average 3.1052631578947367) internal successors, (59), 16 states have internal predecessors, (59), 7 states have call successors, (16), 4 states have call predecessors, (16), 5 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-05 02:30:57,619 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 174 transitions. [2024-11-05 02:30:57,621 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-05 02:30:57,621 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:30:57,622 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:30:57,628 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (4)] Ended with exit code 0 [2024-11-05 02:30:57,822 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:30:57,822 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:30:57,823 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:30:57,823 INFO L85 PathProgramCache]: Analyzing trace with hash -1166515017, now seen corresponding path program 1 times [2024-11-05 02:30:57,823 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:30:57,823 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1198883353] [2024-11-05 02:30:57,823 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:30:57,824 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:30:57,824 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:30:57,827 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:30:57,828 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (5)] Waiting until timeout for monitored process [2024-11-05 02:30:57,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:30:57,986 WARN L253 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 127 conjuncts are in the unsatisfiable core [2024-11-05 02:30:57,995 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:30:58,000 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:30:58,079 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 14 treesize of output 15 [2024-11-05 02:30:58,088 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:30:58,098 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 14 treesize of output 15 [2024-11-05 02:30:58,171 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:30:58,171 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:30:58,188 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:02,192 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2024-11-05 02:31:02,192 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:31:02,896 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2024-11-05 02:31:02,896 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:31:02,896 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1198883353] [2024-11-05 02:31:02,896 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1198883353] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-05 02:31:02,896 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-05 02:31:02,897 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [20, 9] imperfect sequences [] total 26 [2024-11-05 02:31:02,897 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [146446008] [2024-11-05 02:31:02,897 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-05 02:31:02,897 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-11-05 02:31:02,897 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:31:02,898 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-11-05 02:31:02,899 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=575, Unknown=0, NotChecked=0, Total=650 [2024-11-05 02:31:02,899 INFO L87 Difference]: Start difference. First operand 130 states and 174 transitions. Second operand has 26 states, 23 states have (on average 2.739130434782609) internal successors, (63), 20 states have internal predecessors, (63), 7 states have call successors, (16), 4 states have call predecessors, (16), 5 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-05 02:31:06,269 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:31:06,269 INFO L93 Difference]: Finished difference Result 173 states and 238 transitions. [2024-11-05 02:31:06,270 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2024-11-05 02:31:06,270 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 23 states have (on average 2.739130434782609) internal successors, (63), 20 states have internal predecessors, (63), 7 states have call successors, (16), 4 states have call predecessors, (16), 5 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) Word has length 72 [2024-11-05 02:31:06,270 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:31:06,272 INFO L225 Difference]: With dead ends: 173 [2024-11-05 02:31:06,272 INFO L226 Difference]: Without dead ends: 171 [2024-11-05 02:31:06,273 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 159 GetRequests, 113 SyntacticMatches, 6 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 409 ImplicationChecksByTransitivity, 2.8s TimeCoverageRelationStatistics Valid=187, Invalid=1535, Unknown=0, NotChecked=0, Total=1722 [2024-11-05 02:31:06,273 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 99 mSDsluCounter, 672 mSDsCounter, 0 mSdLazyCounter, 620 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 109 SdHoareTripleChecker+Valid, 725 SdHoareTripleChecker+Invalid, 672 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 52 IncrementalHoareTripleChecker+Valid, 620 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.1s IncrementalHoareTripleChecker+Time [2024-11-05 02:31:06,274 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [109 Valid, 725 Invalid, 672 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [52 Valid, 620 Invalid, 0 Unknown, 0 Unchecked, 2.1s Time] [2024-11-05 02:31:06,274 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 171 states. [2024-11-05 02:31:06,292 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 171 to 132. [2024-11-05 02:31:06,292 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 132 states, 92 states have (on average 1.2826086956521738) internal successors, (118), 96 states have internal predecessors, (118), 26 states have call successors, (26), 11 states have call predecessors, (26), 13 states have return successors, (32), 24 states have call predecessors, (32), 24 states have call successors, (32) [2024-11-05 02:31:06,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 176 transitions. [2024-11-05 02:31:06,294 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 176 transitions. Word has length 72 [2024-11-05 02:31:06,294 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:31:06,294 INFO L471 AbstractCegarLoop]: Abstraction has 132 states and 176 transitions. [2024-11-05 02:31:06,294 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 23 states have (on average 2.739130434782609) internal successors, (63), 20 states have internal predecessors, (63), 7 states have call successors, (16), 4 states have call predecessors, (16), 5 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-05 02:31:06,294 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 176 transitions. [2024-11-05 02:31:06,296 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-05 02:31:06,296 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:31:06,296 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:31:06,301 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (5)] Forceful destruction successful, exit code 0 [2024-11-05 02:31:06,498 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:06,498 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:31:06,499 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:31:06,499 INFO L85 PathProgramCache]: Analyzing trace with hash 949556601, now seen corresponding path program 1 times [2024-11-05 02:31:06,499 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:31:06,499 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [56944909] [2024-11-05 02:31:06,499 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:31:06,499 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:06,499 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:31:06,502 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:31:06,503 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (6)] Waiting until timeout for monitored process [2024-11-05 02:31:06,626 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:31:06,634 WARN L253 TraceCheckSpWp]: Trace formula consists of 220 conjuncts, 121 conjuncts are in the unsatisfiable core [2024-11-05 02:31:06,641 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:31:06,645 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:31:06,704 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:31:06,716 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 14 treesize of output 15 [2024-11-05 02:31:06,724 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 14 treesize of output 15 [2024-11-05 02:31:06,836 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:31:06,837 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:06,849 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:09,361 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 14 proven. 0 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2024-11-05 02:31:09,362 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:31:09,673 INFO L134 CoverageAnalysis]: Checked inductivity of 45 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2024-11-05 02:31:09,673 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:31:09,673 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [56944909] [2024-11-05 02:31:09,673 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [56944909] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-05 02:31:09,673 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-05 02:31:09,673 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14, 3] imperfect sequences [] total 15 [2024-11-05 02:31:09,673 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [296670679] [2024-11-05 02:31:09,674 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-05 02:31:09,674 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-05 02:31:09,674 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:31:09,675 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-05 02:31:09,675 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=170, Unknown=0, NotChecked=0, Total=210 [2024-11-05 02:31:09,675 INFO L87 Difference]: Start difference. First operand 132 states and 176 transitions. Second operand has 15 states, 13 states have (on average 4.615384615384615) internal successors, (60), 12 states have internal predecessors, (60), 7 states have call successors, (15), 3 states have call predecessors, (15), 4 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-05 02:31:12,101 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:31:12,102 INFO L93 Difference]: Finished difference Result 265 states and 366 transitions. [2024-11-05 02:31:12,103 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-05 02:31:12,105 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 13 states have (on average 4.615384615384615) internal successors, (60), 12 states have internal predecessors, (60), 7 states have call successors, (15), 3 states have call predecessors, (15), 4 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) Word has length 73 [2024-11-05 02:31:12,106 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:31:12,110 INFO L225 Difference]: With dead ends: 265 [2024-11-05 02:31:12,111 INFO L226 Difference]: Without dead ends: 151 [2024-11-05 02:31:12,113 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 126 SyntacticMatches, 6 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 105 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=68, Invalid=312, Unknown=0, NotChecked=0, Total=380 [2024-11-05 02:31:12,114 INFO L432 NwaCegarLoop]: 58 mSDtfsCounter, 59 mSDsluCounter, 507 mSDsCounter, 0 mSdLazyCounter, 400 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 565 SdHoareTripleChecker+Invalid, 426 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 400 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2024-11-05 02:31:12,114 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 565 Invalid, 426 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 400 Invalid, 0 Unknown, 0 Unchecked, 2.0s Time] [2024-11-05 02:31:12,115 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2024-11-05 02:31:12,164 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 136. [2024-11-05 02:31:12,165 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 96 states have (on average 1.2916666666666667) internal successors, (124), 100 states have internal predecessors, (124), 26 states have call successors, (26), 11 states have call predecessors, (26), 13 states have return successors, (32), 24 states have call predecessors, (32), 24 states have call successors, (32) [2024-11-05 02:31:12,167 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 182 transitions. [2024-11-05 02:31:12,169 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 182 transitions. Word has length 73 [2024-11-05 02:31:12,169 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:31:12,169 INFO L471 AbstractCegarLoop]: Abstraction has 136 states and 182 transitions. [2024-11-05 02:31:12,171 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 13 states have (on average 4.615384615384615) internal successors, (60), 12 states have internal predecessors, (60), 7 states have call successors, (15), 3 states have call predecessors, (15), 4 states have return successors, (14), 8 states have call predecessors, (14), 6 states have call successors, (14) [2024-11-05 02:31:12,171 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 182 transitions. [2024-11-05 02:31:12,172 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-05 02:31:12,173 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:31:12,173 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:31:12,179 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (6)] Forceful destruction successful, exit code 0 [2024-11-05 02:31:12,373 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:12,374 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:31:12,374 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:31:12,374 INFO L85 PathProgramCache]: Analyzing trace with hash 509705391, now seen corresponding path program 1 times [2024-11-05 02:31:12,374 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:31:12,374 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [179148564] [2024-11-05 02:31:12,374 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:31:12,374 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:12,375 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:31:12,377 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:31:12,378 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (7)] Waiting until timeout for monitored process [2024-11-05 02:31:12,549 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:31:12,562 WARN L253 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 122 conjuncts are in the unsatisfiable core [2024-11-05 02:31:12,568 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:31:12,573 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:31:12,636 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 14 treesize of output 15 [2024-11-05 02:31:12,649 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:31:12,658 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 14 treesize of output 15 [2024-11-05 02:31:12,792 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:31:12,793 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:12,808 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:13,957 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 34 proven. 0 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-05 02:31:13,957 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:31:14,571 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2024-11-05 02:31:14,571 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:31:14,571 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [179148564] [2024-11-05 02:31:14,571 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [179148564] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:31:14,571 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:31:14,571 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [6] total 17 [2024-11-05 02:31:14,572 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [497079860] [2024-11-05 02:31:14,572 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:31:14,572 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-05 02:31:14,572 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:31:14,572 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-05 02:31:14,573 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=224, Unknown=0, NotChecked=0, Total=272 [2024-11-05 02:31:14,573 INFO L87 Difference]: Start difference. First operand 136 states and 182 transitions. Second operand has 13 states, 12 states have (on average 3.8333333333333335) internal successors, (46), 11 states have internal predecessors, (46), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-05 02:31:16,016 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:31:16,017 INFO L93 Difference]: Finished difference Result 200 states and 267 transitions. [2024-11-05 02:31:16,018 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-05 02:31:16,019 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 3.8333333333333335) internal successors, (46), 11 states have internal predecessors, (46), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) Word has length 74 [2024-11-05 02:31:16,019 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:31:16,020 INFO L225 Difference]: With dead ends: 200 [2024-11-05 02:31:16,020 INFO L226 Difference]: Without dead ends: 140 [2024-11-05 02:31:16,020 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 149 GetRequests, 130 SyntacticMatches, 1 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 107 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2024-11-05 02:31:16,021 INFO L432 NwaCegarLoop]: 62 mSDtfsCounter, 65 mSDsluCounter, 357 mSDsCounter, 0 mSdLazyCounter, 247 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 78 SdHoareTripleChecker+Valid, 419 SdHoareTripleChecker+Invalid, 261 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 247 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.3s IncrementalHoareTripleChecker+Time [2024-11-05 02:31:16,021 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [78 Valid, 419 Invalid, 261 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 247 Invalid, 0 Unknown, 0 Unchecked, 1.3s Time] [2024-11-05 02:31:16,021 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2024-11-05 02:31:16,055 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 138. [2024-11-05 02:31:16,056 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 138 states, 97 states have (on average 1.288659793814433) internal successors, (125), 102 states have internal predecessors, (125), 26 states have call successors, (26), 11 states have call predecessors, (26), 14 states have return successors, (35), 24 states have call predecessors, (35), 24 states have call successors, (35) [2024-11-05 02:31:16,057 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 186 transitions. [2024-11-05 02:31:16,057 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 186 transitions. Word has length 74 [2024-11-05 02:31:16,057 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:31:16,057 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 186 transitions. [2024-11-05 02:31:16,057 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 3.8333333333333335) internal successors, (46), 11 states have internal predecessors, (46), 4 states have call successors, (9), 3 states have call predecessors, (9), 4 states have return successors, (8), 4 states have call predecessors, (8), 4 states have call successors, (8) [2024-11-05 02:31:16,057 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 186 transitions. [2024-11-05 02:31:16,058 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-05 02:31:16,059 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:31:16,063 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:31:16,068 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (7)] Forceful destruction successful, exit code 0 [2024-11-05 02:31:16,263 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:16,264 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:31:16,264 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:31:16,264 INFO L85 PathProgramCache]: Analyzing trace with hash 1404935915, now seen corresponding path program 1 times [2024-11-05 02:31:16,264 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:31:16,264 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1592220497] [2024-11-05 02:31:16,264 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:31:16,265 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:16,265 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:31:16,267 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:31:16,268 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (8)] Waiting until timeout for monitored process [2024-11-05 02:31:16,398 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:31:16,407 WARN L253 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 126 conjuncts are in the unsatisfiable core [2024-11-05 02:31:16,414 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:31:16,423 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:31:16,526 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 14 treesize of output 15 [2024-11-05 02:31:16,549 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 14 treesize of output 15 [2024-11-05 02:31:16,561 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:31:16,658 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 7 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:16,675 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 7 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:17,554 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2024-11-05 02:31:17,554 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:31:18,161 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 2 proven. 20 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-05 02:31:18,162 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:31:18,162 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1592220497] [2024-11-05 02:31:18,162 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1592220497] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:31:18,162 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:31:18,162 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [9] total 18 [2024-11-05 02:31:18,162 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1477189098] [2024-11-05 02:31:18,162 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:31:18,162 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-05 02:31:18,162 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:31:18,163 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-05 02:31:18,163 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=237, Unknown=0, NotChecked=0, Total=306 [2024-11-05 02:31:18,163 INFO L87 Difference]: Start difference. First operand 138 states and 186 transitions. Second operand has 11 states, 11 states have (on average 4.090909090909091) internal successors, (45), 9 states have internal predecessors, (45), 3 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-05 02:31:19,429 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:31:19,429 INFO L93 Difference]: Finished difference Result 205 states and 276 transitions. [2024-11-05 02:31:19,429 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-05 02:31:19,430 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 4.090909090909091) internal successors, (45), 9 states have internal predecessors, (45), 3 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 76 [2024-11-05 02:31:19,430 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:31:19,431 INFO L225 Difference]: With dead ends: 205 [2024-11-05 02:31:19,431 INFO L226 Difference]: Without dead ends: 143 [2024-11-05 02:31:19,431 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 134 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 82 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=75, Invalid=267, Unknown=0, NotChecked=0, Total=342 [2024-11-05 02:31:19,432 INFO L432 NwaCegarLoop]: 62 mSDtfsCounter, 55 mSDsluCounter, 340 mSDsCounter, 0 mSdLazyCounter, 261 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 71 SdHoareTripleChecker+Valid, 402 SdHoareTripleChecker+Invalid, 272 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 11 IncrementalHoareTripleChecker+Valid, 261 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-05 02:31:19,432 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [71 Valid, 402 Invalid, 272 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [11 Valid, 261 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2024-11-05 02:31:19,432 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2024-11-05 02:31:19,453 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 141. [2024-11-05 02:31:19,454 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 141 states, 99 states have (on average 1.2828282828282829) internal successors, (127), 105 states have internal predecessors, (127), 26 states have call successors, (26), 11 states have call predecessors, (26), 15 states have return successors, (37), 24 states have call predecessors, (37), 24 states have call successors, (37) [2024-11-05 02:31:19,454 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 141 states to 141 states and 190 transitions. [2024-11-05 02:31:19,455 INFO L78 Accepts]: Start accepts. Automaton has 141 states and 190 transitions. Word has length 76 [2024-11-05 02:31:19,455 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:31:19,455 INFO L471 AbstractCegarLoop]: Abstraction has 141 states and 190 transitions. [2024-11-05 02:31:19,455 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 11 states have (on average 4.090909090909091) internal successors, (45), 9 states have internal predecessors, (45), 3 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-05 02:31:19,455 INFO L276 IsEmpty]: Start isEmpty. Operand 141 states and 190 transitions. [2024-11-05 02:31:19,456 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-05 02:31:19,456 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:31:19,456 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:31:19,460 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (8)] Forceful destruction successful, exit code 0 [2024-11-05 02:31:19,657 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:19,658 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:31:19,658 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:31:19,658 INFO L85 PathProgramCache]: Analyzing trace with hash -233332627, now seen corresponding path program 1 times [2024-11-05 02:31:19,659 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:31:19,659 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1789855408] [2024-11-05 02:31:19,659 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:31:19,659 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:19,659 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:31:19,660 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:31:19,661 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (9)] Waiting until timeout for monitored process [2024-11-05 02:31:19,807 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:31:19,816 WARN L253 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 140 conjuncts are in the unsatisfiable core [2024-11-05 02:31:19,823 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:31:19,831 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:31:19,838 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-05 02:31:19,845 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 6 treesize of output 5 [2024-11-05 02:31:19,977 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:31:19,992 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 14 treesize of output 15 [2024-11-05 02:31:20,007 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 14 treesize of output 15 [2024-11-05 02:31:20,107 INFO L349 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2024-11-05 02:31:20,107 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 39 [2024-11-05 02:31:20,127 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:31:20,146 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-05 02:31:20,146 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 35 [2024-11-05 02:31:20,180 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2024-11-05 02:31:20,180 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 11 treesize of output 7 [2024-11-05 02:31:20,442 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2024-11-05 02:31:20,442 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 5 new quantified variables, introduced 4 case distinctions, treesize of input 135 treesize of output 93 [2024-11-05 02:31:20,476 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-11-05 02:31:20,476 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 76 treesize of output 71 [2024-11-05 02:31:24,584 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 30 proven. 5 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-05 02:31:24,584 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:31:25,271 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-05 02:31:25,271 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:31:25,271 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1789855408] [2024-11-05 02:31:25,271 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1789855408] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-05 02:31:25,271 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-05 02:31:25,271 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 6] total 19 [2024-11-05 02:31:25,271 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1177732310] [2024-11-05 02:31:25,272 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-05 02:31:25,272 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-05 02:31:25,272 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:31:25,272 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-05 02:31:25,273 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=288, Unknown=0, NotChecked=0, Total=342 [2024-11-05 02:31:25,273 INFO L87 Difference]: Start difference. First operand 141 states and 190 transitions. Second operand has 19 states, 17 states have (on average 4.647058823529412) internal successors, (79), 16 states have internal predecessors, (79), 6 states have call successors, (17), 4 states have call predecessors, (17), 7 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-05 02:31:29,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:31:29,115 INFO L93 Difference]: Finished difference Result 277 states and 372 transitions. [2024-11-05 02:31:29,115 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-05 02:31:29,116 INFO L78 Accepts]: Start accepts. Automaton has has 19 states, 17 states have (on average 4.647058823529412) internal successors, (79), 16 states have internal predecessors, (79), 6 states have call successors, (17), 4 states have call predecessors, (17), 7 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) Word has length 76 [2024-11-05 02:31:29,116 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:31:29,117 INFO L225 Difference]: With dead ends: 277 [2024-11-05 02:31:29,117 INFO L226 Difference]: Without dead ends: 216 [2024-11-05 02:31:29,118 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 130 SyntacticMatches, 3 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 147 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=80, Invalid=472, Unknown=0, NotChecked=0, Total=552 [2024-11-05 02:31:29,119 INFO L432 NwaCegarLoop]: 122 mSDtfsCounter, 111 mSDsluCounter, 1196 mSDsCounter, 0 mSdLazyCounter, 552 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 129 SdHoareTripleChecker+Valid, 1318 SdHoareTripleChecker+Invalid, 561 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 552 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.5s IncrementalHoareTripleChecker+Time [2024-11-05 02:31:29,119 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [129 Valid, 1318 Invalid, 561 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 552 Invalid, 0 Unknown, 0 Unchecked, 3.5s Time] [2024-11-05 02:31:29,119 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 216 states. [2024-11-05 02:31:29,159 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 216 to 147. [2024-11-05 02:31:29,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 147 states, 103 states have (on average 1.2718446601941749) internal successors, (131), 110 states have internal predecessors, (131), 26 states have call successors, (26), 12 states have call predecessors, (26), 17 states have return successors, (40), 24 states have call predecessors, (40), 24 states have call successors, (40) [2024-11-05 02:31:29,161 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 147 states to 147 states and 197 transitions. [2024-11-05 02:31:29,162 INFO L78 Accepts]: Start accepts. Automaton has 147 states and 197 transitions. Word has length 76 [2024-11-05 02:31:29,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:31:29,162 INFO L471 AbstractCegarLoop]: Abstraction has 147 states and 197 transitions. [2024-11-05 02:31:29,162 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 19 states, 17 states have (on average 4.647058823529412) internal successors, (79), 16 states have internal predecessors, (79), 6 states have call successors, (17), 4 states have call predecessors, (17), 7 states have return successors, (16), 6 states have call predecessors, (16), 6 states have call successors, (16) [2024-11-05 02:31:29,162 INFO L276 IsEmpty]: Start isEmpty. Operand 147 states and 197 transitions. [2024-11-05 02:31:29,163 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2024-11-05 02:31:29,163 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:31:29,163 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:31:29,168 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (9)] Ended with exit code 0 [2024-11-05 02:31:29,364 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:29,364 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:31:29,365 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:31:29,365 INFO L85 PathProgramCache]: Analyzing trace with hash -141117224, now seen corresponding path program 1 times [2024-11-05 02:31:29,365 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:31:29,365 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1795834455] [2024-11-05 02:31:29,365 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:31:29,365 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:29,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:31:29,368 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:31:29,369 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (10)] Waiting until timeout for monitored process [2024-11-05 02:31:29,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:31:29,577 WARN L253 TraceCheckSpWp]: Trace formula consists of 226 conjuncts, 129 conjuncts are in the unsatisfiable core [2024-11-05 02:31:29,583 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:31:29,587 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:31:29,664 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 14 treesize of output 15 [2024-11-05 02:31:29,676 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 14 treesize of output 15 [2024-11-05 02:31:29,754 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 7 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:29,772 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 7 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:30,880 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 30 proven. 0 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2024-11-05 02:31:30,880 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:31:31,620 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 2 proven. 20 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-05 02:31:31,620 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:31:31,620 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1795834455] [2024-11-05 02:31:31,620 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1795834455] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:31:31,620 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:31:31,621 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [10] total 21 [2024-11-05 02:31:31,621 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [29876979] [2024-11-05 02:31:31,621 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:31:31,621 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-05 02:31:31,621 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:31:31,622 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-05 02:31:31,622 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=332, Unknown=0, NotChecked=0, Total=420 [2024-11-05 02:31:31,622 INFO L87 Difference]: Start difference. First operand 147 states and 197 transitions. Second operand has 13 states, 13 states have (on average 3.6153846153846154) internal successors, (47), 11 states have internal predecessors, (47), 3 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-05 02:31:33,824 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:31:33,825 INFO L93 Difference]: Finished difference Result 221 states and 297 transitions. [2024-11-05 02:31:33,825 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-05 02:31:33,825 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 13 states have (on average 3.6153846153846154) internal successors, (47), 11 states have internal predecessors, (47), 3 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) Word has length 78 [2024-11-05 02:31:33,825 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:31:33,827 INFO L225 Difference]: With dead ends: 221 [2024-11-05 02:31:33,827 INFO L226 Difference]: Without dead ends: 156 [2024-11-05 02:31:33,827 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 158 GetRequests, 135 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 129 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=125, Invalid=475, Unknown=0, NotChecked=0, Total=600 [2024-11-05 02:31:33,828 INFO L432 NwaCegarLoop]: 85 mSDtfsCounter, 59 mSDsluCounter, 598 mSDsCounter, 0 mSdLazyCounter, 403 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 75 SdHoareTripleChecker+Valid, 683 SdHoareTripleChecker+Invalid, 418 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 403 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.0s IncrementalHoareTripleChecker+Time [2024-11-05 02:31:33,828 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [75 Valid, 683 Invalid, 418 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 403 Invalid, 0 Unknown, 0 Unchecked, 2.0s Time] [2024-11-05 02:31:33,828 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 156 states. [2024-11-05 02:31:33,863 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 156 to 148. [2024-11-05 02:31:33,863 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 148 states, 104 states have (on average 1.2692307692307692) internal successors, (132), 111 states have internal predecessors, (132), 26 states have call successors, (26), 12 states have call predecessors, (26), 17 states have return successors, (40), 24 states have call predecessors, (40), 24 states have call successors, (40) [2024-11-05 02:31:33,865 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 198 transitions. [2024-11-05 02:31:33,866 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 198 transitions. Word has length 78 [2024-11-05 02:31:33,866 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:31:33,866 INFO L471 AbstractCegarLoop]: Abstraction has 148 states and 198 transitions. [2024-11-05 02:31:33,866 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 13 states have (on average 3.6153846153846154) internal successors, (47), 11 states have internal predecessors, (47), 3 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 3 states have call predecessors, (8), 3 states have call successors, (8) [2024-11-05 02:31:33,866 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 198 transitions. [2024-11-05 02:31:33,867 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2024-11-05 02:31:33,867 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:31:33,867 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:31:33,870 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (10)] Forceful destruction successful, exit code 0 [2024-11-05 02:31:34,069 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:34,069 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:31:34,070 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:31:34,070 INFO L85 PathProgramCache]: Analyzing trace with hash 309971753, now seen corresponding path program 1 times [2024-11-05 02:31:34,070 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:31:34,070 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [982158538] [2024-11-05 02:31:34,070 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:31:34,070 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:34,070 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:31:34,073 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:31:34,074 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (11)] Waiting until timeout for monitored process [2024-11-05 02:31:34,247 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:31:34,261 WARN L253 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 146 conjuncts are in the unsatisfiable core [2024-11-05 02:31:34,268 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:31:34,273 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:31:34,282 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 6 treesize of output 5 [2024-11-05 02:31:34,293 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 8 treesize of output 1 [2024-11-05 02:31:34,447 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 14 treesize of output 15 [2024-11-05 02:31:34,459 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:31:34,482 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 14 treesize of output 15 [2024-11-05 02:31:34,590 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2024-11-05 02:31:34,591 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 7 [2024-11-05 02:31:34,608 INFO L349 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2024-11-05 02:31:34,608 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 39 [2024-11-05 02:31:34,643 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-05 02:31:34,644 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 35 [2024-11-05 02:31:34,950 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2024-11-05 02:31:34,950 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 7 disjoint index pairs (out of 6 index pairs), introduced 5 new quantified variables, introduced 4 case distinctions, treesize of input 135 treesize of output 93 [2024-11-05 02:31:34,989 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-11-05 02:31:34,990 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 7 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 76 treesize of output 71 [2024-11-05 02:31:37,441 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 30 proven. 1 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2024-11-05 02:31:37,442 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:31:38,051 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 2 proven. 20 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-05 02:31:38,052 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:31:38,052 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [982158538] [2024-11-05 02:31:38,052 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [982158538] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-05 02:31:38,052 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-05 02:31:38,052 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 6] total 18 [2024-11-05 02:31:38,052 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [865873124] [2024-11-05 02:31:38,052 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-05 02:31:38,056 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-05 02:31:38,057 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:31:38,058 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-05 02:31:38,058 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=246, Unknown=0, NotChecked=0, Total=306 [2024-11-05 02:31:38,058 INFO L87 Difference]: Start difference. First operand 148 states and 198 transitions. Second operand has 18 states, 18 states have (on average 4.722222222222222) internal successors, (85), 16 states have internal predecessors, (85), 4 states have call successors, (17), 4 states have call predecessors, (17), 5 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-05 02:31:41,916 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:31:41,917 INFO L93 Difference]: Finished difference Result 288 states and 389 transitions. [2024-11-05 02:31:41,921 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-05 02:31:41,921 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 4.722222222222222) internal successors, (85), 16 states have internal predecessors, (85), 4 states have call successors, (17), 4 states have call predecessors, (17), 5 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 78 [2024-11-05 02:31:41,921 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:31:41,923 INFO L225 Difference]: With dead ends: 288 [2024-11-05 02:31:41,923 INFO L226 Difference]: Without dead ends: 226 [2024-11-05 02:31:41,923 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 138 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=91, Invalid=415, Unknown=0, NotChecked=0, Total=506 [2024-11-05 02:31:41,924 INFO L432 NwaCegarLoop]: 103 mSDtfsCounter, 151 mSDsluCounter, 792 mSDsCounter, 0 mSdLazyCounter, 643 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 180 SdHoareTripleChecker+Valid, 895 SdHoareTripleChecker+Invalid, 687 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 643 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.6s IncrementalHoareTripleChecker+Time [2024-11-05 02:31:41,924 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [180 Valid, 895 Invalid, 687 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 643 Invalid, 0 Unknown, 0 Unchecked, 3.6s Time] [2024-11-05 02:31:41,928 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 226 states. [2024-11-05 02:31:41,969 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 226 to 151. [2024-11-05 02:31:41,970 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 151 states, 106 states have (on average 1.2641509433962264) internal successors, (134), 114 states have internal predecessors, (134), 26 states have call successors, (26), 12 states have call predecessors, (26), 18 states have return successors, (42), 24 states have call predecessors, (42), 24 states have call successors, (42) [2024-11-05 02:31:41,970 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 202 transitions. [2024-11-05 02:31:41,971 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 202 transitions. Word has length 78 [2024-11-05 02:31:41,971 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:31:41,971 INFO L471 AbstractCegarLoop]: Abstraction has 151 states and 202 transitions. [2024-11-05 02:31:41,971 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 4.722222222222222) internal successors, (85), 16 states have internal predecessors, (85), 4 states have call successors, (17), 4 states have call predecessors, (17), 5 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-05 02:31:41,971 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 202 transitions. [2024-11-05 02:31:41,972 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2024-11-05 02:31:41,972 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:31:41,972 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:31:41,976 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (11)] Ended with exit code 0 [2024-11-05 02:31:42,173 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:42,173 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:31:42,174 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:31:42,174 INFO L85 PathProgramCache]: Analyzing trace with hash -134689386, now seen corresponding path program 1 times [2024-11-05 02:31:42,174 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:31:42,174 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [133112262] [2024-11-05 02:31:42,174 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:31:42,174 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:42,174 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:31:42,177 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:31:42,178 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (12)] Waiting until timeout for monitored process [2024-11-05 02:31:42,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:31:42,382 WARN L253 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 149 conjuncts are in the unsatisfiable core [2024-11-05 02:31:42,390 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:31:42,395 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:31:42,405 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 6 treesize of output 5 [2024-11-05 02:31:42,417 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 8 treesize of output 1 [2024-11-05 02:31:42,593 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 14 treesize of output 15 [2024-11-05 02:31:42,604 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 14 treesize of output 15 [2024-11-05 02:31:42,711 INFO L349 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2024-11-05 02:31:42,712 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 39 [2024-11-05 02:31:42,736 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2024-11-05 02:31:42,737 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 7 [2024-11-05 02:31:42,756 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 13 treesize of output 1 [2024-11-05 02:31:42,763 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:31:42,782 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-05 02:31:42,783 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 35 [2024-11-05 02:31:43,080 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2024-11-05 02:31:43,080 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 7 disjoint index pairs (out of 6 index pairs), introduced 5 new quantified variables, introduced 4 case distinctions, treesize of input 135 treesize of output 93 [2024-11-05 02:31:43,113 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-11-05 02:31:43,114 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 7 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 76 treesize of output 71 [2024-11-05 02:31:45,561 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 30 proven. 1 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2024-11-05 02:31:45,561 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:31:46,235 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 2 proven. 20 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-05 02:31:46,236 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:31:46,236 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [133112262] [2024-11-05 02:31:46,236 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [133112262] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-05 02:31:46,236 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-05 02:31:46,236 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 7] total 21 [2024-11-05 02:31:46,236 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [292162822] [2024-11-05 02:31:46,236 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-05 02:31:46,237 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-05 02:31:46,237 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:31:46,237 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-05 02:31:46,237 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=344, Unknown=0, NotChecked=0, Total=420 [2024-11-05 02:31:46,237 INFO L87 Difference]: Start difference. First operand 151 states and 202 transitions. Second operand has 21 states, 21 states have (on average 4.238095238095238) internal successors, (89), 19 states have internal predecessors, (89), 4 states have call successors, (17), 4 states have call predecessors, (17), 5 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-05 02:31:50,073 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:31:50,073 INFO L93 Difference]: Finished difference Result 305 states and 414 transitions. [2024-11-05 02:31:50,073 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-05 02:31:50,074 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 21 states have (on average 4.238095238095238) internal successors, (89), 19 states have internal predecessors, (89), 4 states have call successors, (17), 4 states have call predecessors, (17), 5 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) Word has length 80 [2024-11-05 02:31:50,074 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:31:50,075 INFO L225 Difference]: With dead ends: 305 [2024-11-05 02:31:50,075 INFO L226 Difference]: Without dead ends: 240 [2024-11-05 02:31:50,076 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 139 SyntacticMatches, 2 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 223 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=153, Invalid=777, Unknown=0, NotChecked=0, Total=930 [2024-11-05 02:31:50,077 INFO L432 NwaCegarLoop]: 97 mSDtfsCounter, 189 mSDsluCounter, 705 mSDsCounter, 0 mSdLazyCounter, 677 mSolverCounterSat, 54 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 218 SdHoareTripleChecker+Valid, 802 SdHoareTripleChecker+Invalid, 731 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 54 IncrementalHoareTripleChecker+Valid, 677 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.1s IncrementalHoareTripleChecker+Time [2024-11-05 02:31:50,077 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [218 Valid, 802 Invalid, 731 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [54 Valid, 677 Invalid, 0 Unknown, 0 Unchecked, 3.1s Time] [2024-11-05 02:31:50,078 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 240 states. [2024-11-05 02:31:50,121 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 240 to 84. [2024-11-05 02:31:50,122 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 59 states have (on average 1.2372881355932204) internal successors, (73), 63 states have internal predecessors, (73), 14 states have call successors, (14), 7 states have call predecessors, (14), 10 states have return successors, (22), 13 states have call predecessors, (22), 13 states have call successors, (22) [2024-11-05 02:31:50,122 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 109 transitions. [2024-11-05 02:31:50,123 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 109 transitions. Word has length 80 [2024-11-05 02:31:50,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:31:50,123 INFO L471 AbstractCegarLoop]: Abstraction has 84 states and 109 transitions. [2024-11-05 02:31:50,123 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 21 states have (on average 4.238095238095238) internal successors, (89), 19 states have internal predecessors, (89), 4 states have call successors, (17), 4 states have call predecessors, (17), 5 states have return successors, (16), 4 states have call predecessors, (16), 4 states have call successors, (16) [2024-11-05 02:31:50,124 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 109 transitions. [2024-11-05 02:31:50,124 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-05 02:31:50,124 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:31:50,125 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:31:50,129 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (12)] Ended with exit code 0 [2024-11-05 02:31:50,327 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:50,327 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:31:50,328 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:31:50,328 INFO L85 PathProgramCache]: Analyzing trace with hash 1636580586, now seen corresponding path program 1 times [2024-11-05 02:31:50,328 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:31:50,328 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [739342219] [2024-11-05 02:31:50,328 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:31:50,328 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:50,329 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:31:50,331 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:31:50,334 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (13)] Waiting until timeout for monitored process [2024-11-05 02:31:50,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:31:50,596 WARN L253 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 143 conjuncts are in the unsatisfiable core [2024-11-05 02:31:50,605 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:31:50,610 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:31:50,693 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:31:50,705 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 14 treesize of output 15 [2024-11-05 02:31:50,719 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 14 treesize of output 15 [2024-11-05 02:31:50,856 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:31:50,857 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:50,873 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:53,036 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 34 proven. 0 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-05 02:31:53,036 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:31:53,779 INFO L134 CoverageAnalysis]: Checked inductivity of 47 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2024-11-05 02:31:53,780 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:31:53,780 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [739342219] [2024-11-05 02:31:53,780 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [739342219] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:31:53,780 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:31:53,780 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [18] imperfect sequences [7] total 23 [2024-11-05 02:31:53,780 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1959539060] [2024-11-05 02:31:53,781 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:31:53,782 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-05 02:31:53,782 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:31:53,782 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-05 02:31:53,782 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=440, Unknown=0, NotChecked=0, Total=506 [2024-11-05 02:31:53,783 INFO L87 Difference]: Start difference. First operand 84 states and 109 transitions. Second operand has 18 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 16 states have internal predecessors, (57), 5 states have call successors, (10), 3 states have call predecessors, (10), 5 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2024-11-05 02:31:57,585 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:31:57,585 INFO L93 Difference]: Finished difference Result 232 states and 311 transitions. [2024-11-05 02:31:57,585 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-05 02:31:57,586 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 16 states have internal predecessors, (57), 5 states have call successors, (10), 3 states have call predecessors, (10), 5 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) Word has length 87 [2024-11-05 02:31:57,586 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:31:57,587 INFO L225 Difference]: With dead ends: 232 [2024-11-05 02:31:57,587 INFO L226 Difference]: Without dead ends: 166 [2024-11-05 02:31:57,587 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 179 GetRequests, 150 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 215 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=109, Invalid=761, Unknown=0, NotChecked=0, Total=870 [2024-11-05 02:31:57,588 INFO L432 NwaCegarLoop]: 83 mSDtfsCounter, 51 mSDsluCounter, 993 mSDsCounter, 0 mSdLazyCounter, 690 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 68 SdHoareTripleChecker+Valid, 1076 SdHoareTripleChecker+Invalid, 705 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 15 IncrementalHoareTripleChecker+Valid, 690 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.3s IncrementalHoareTripleChecker+Time [2024-11-05 02:31:57,588 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [68 Valid, 1076 Invalid, 705 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [15 Valid, 690 Invalid, 0 Unknown, 0 Unchecked, 3.3s Time] [2024-11-05 02:31:57,588 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2024-11-05 02:31:57,646 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 153. [2024-11-05 02:31:57,647 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 153 states, 108 states have (on average 1.2592592592592593) internal successors, (136), 116 states have internal predecessors, (136), 26 states have call successors, (26), 12 states have call predecessors, (26), 18 states have return successors, (42), 24 states have call predecessors, (42), 24 states have call successors, (42) [2024-11-05 02:31:57,648 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 204 transitions. [2024-11-05 02:31:57,648 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 204 transitions. Word has length 87 [2024-11-05 02:31:57,648 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:31:57,648 INFO L471 AbstractCegarLoop]: Abstraction has 153 states and 204 transitions. [2024-11-05 02:31:57,648 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 17 states have (on average 3.3529411764705883) internal successors, (57), 16 states have internal predecessors, (57), 5 states have call successors, (10), 3 states have call predecessors, (10), 5 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2024-11-05 02:31:57,648 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 204 transitions. [2024-11-05 02:31:57,649 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2024-11-05 02:31:57,649 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:31:57,649 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:31:57,656 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (13)] Ended with exit code 0 [2024-11-05 02:31:57,852 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:57,852 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:31:57,852 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:31:57,852 INFO L85 PathProgramCache]: Analyzing trace with hash -868887785, now seen corresponding path program 1 times [2024-11-05 02:31:57,852 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:31:57,853 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1192235573] [2024-11-05 02:31:57,853 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:31:57,853 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:31:57,853 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:31:57,854 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:31:57,856 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (14)] Waiting until timeout for monitored process [2024-11-05 02:31:58,044 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:31:58,050 INFO L255 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 91 conjuncts are in the unsatisfiable core [2024-11-05 02:31:58,056 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:31:58,060 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:31:58,136 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 14 treesize of output 15 [2024-11-05 02:31:58,149 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 14 treesize of output 15 [2024-11-05 02:31:58,163 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:31:58,234 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:31:58,235 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:58,245 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 6 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 35 [2024-11-05 02:31:59,736 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 30 proven. 1 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2024-11-05 02:31:59,736 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:32:00,672 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 774 treesize of output 766 [2024-11-05 02:32:00,875 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 2 proven. 21 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2024-11-05 02:32:00,875 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:32:00,875 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1192235573] [2024-11-05 02:32:00,875 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1192235573] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-05 02:32:00,875 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-05 02:32:00,875 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 25 [2024-11-05 02:32:00,875 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1253638286] [2024-11-05 02:32:00,875 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-05 02:32:00,876 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-05 02:32:00,876 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:32:00,876 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-05 02:32:00,877 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=513, Unknown=0, NotChecked=0, Total=600 [2024-11-05 02:32:00,877 INFO L87 Difference]: Start difference. First operand 153 states and 204 transitions. Second operand has 25 states, 25 states have (on average 3.92) internal successors, (98), 24 states have internal predecessors, (98), 7 states have call successors, (19), 3 states have call predecessors, (19), 5 states have return successors, (18), 6 states have call predecessors, (18), 7 states have call successors, (18) [2024-11-05 02:32:05,117 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:32:05,118 INFO L93 Difference]: Finished difference Result 253 states and 347 transitions. [2024-11-05 02:32:05,118 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-05 02:32:05,119 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 3.92) internal successors, (98), 24 states have internal predecessors, (98), 7 states have call successors, (19), 3 states have call predecessors, (19), 5 states have return successors, (18), 6 states have call predecessors, (18), 7 states have call successors, (18) Word has length 89 [2024-11-05 02:32:05,119 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:32:05,120 INFO L225 Difference]: With dead ends: 253 [2024-11-05 02:32:05,120 INFO L226 Difference]: Without dead ends: 186 [2024-11-05 02:32:05,121 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 183 GetRequests, 153 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 234 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=142, Invalid=850, Unknown=0, NotChecked=0, Total=992 [2024-11-05 02:32:05,122 INFO L432 NwaCegarLoop]: 92 mSDtfsCounter, 129 mSDsluCounter, 1102 mSDsCounter, 0 mSdLazyCounter, 855 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 144 SdHoareTripleChecker+Valid, 1194 SdHoareTripleChecker+Invalid, 888 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 855 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 3.7s IncrementalHoareTripleChecker+Time [2024-11-05 02:32:05,122 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [144 Valid, 1194 Invalid, 888 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 855 Invalid, 0 Unknown, 0 Unchecked, 3.7s Time] [2024-11-05 02:32:05,122 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 186 states. [2024-11-05 02:32:05,219 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 186 to 156. [2024-11-05 02:32:05,220 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 156 states, 110 states have (on average 1.2727272727272727) internal successors, (140), 118 states have internal predecessors, (140), 27 states have call successors, (27), 12 states have call predecessors, (27), 18 states have return successors, (43), 25 states have call predecessors, (43), 25 states have call successors, (43) [2024-11-05 02:32:05,220 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 156 states to 156 states and 210 transitions. [2024-11-05 02:32:05,221 INFO L78 Accepts]: Start accepts. Automaton has 156 states and 210 transitions. Word has length 89 [2024-11-05 02:32:05,221 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:32:05,221 INFO L471 AbstractCegarLoop]: Abstraction has 156 states and 210 transitions. [2024-11-05 02:32:05,221 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 25 states have (on average 3.92) internal successors, (98), 24 states have internal predecessors, (98), 7 states have call successors, (19), 3 states have call predecessors, (19), 5 states have return successors, (18), 6 states have call predecessors, (18), 7 states have call successors, (18) [2024-11-05 02:32:05,221 INFO L276 IsEmpty]: Start isEmpty. Operand 156 states and 210 transitions. [2024-11-05 02:32:05,222 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2024-11-05 02:32:05,222 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:32:05,223 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-05 02:32:05,225 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (14)] Ended with exit code 0 [2024-11-05 02:32:05,425 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt [2024-11-05 02:32:05,426 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:32:05,426 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:32:05,426 INFO L85 PathProgramCache]: Analyzing trace with hash -1161650708, now seen corresponding path program 1 times [2024-11-05 02:32:05,426 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:32:05,426 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1737708933] [2024-11-05 02:32:05,426 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:32:05,426 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:32:05,427 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:32:05,428 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2024-11-05 02:32:05,429 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (15)] Waiting until timeout for monitored process [2024-11-05 02:32:05,628 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:32:05,638 WARN L253 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 162 conjuncts are in the unsatisfiable core [2024-11-05 02:32:05,646 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:32:05,650 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 13 [2024-11-05 02:32:05,658 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 6 treesize of output 5 [2024-11-05 02:32:05,662 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-05 02:32:05,778 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 14 treesize of output 15 [2024-11-05 02:32:05,792 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 14 treesize of output 15 [2024-11-05 02:32:05,802 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-05 02:32:05,892 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-05 02:32:05,892 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 35 [2024-11-05 02:32:05,929 INFO L349 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2024-11-05 02:32:05,929 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 42 treesize of output 39 [2024-11-05 02:32:05,964 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2024-11-05 02:32:05,964 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 11 treesize of output 7 [2024-11-05 02:32:06,214 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2024-11-05 02:32:06,214 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 5 new quantified variables, introduced 4 case distinctions, treesize of input 135 treesize of output 93 [2024-11-05 02:32:06,256 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-11-05 02:32:06,256 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 4 select indices, 4 select index equivalence classes, 6 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 76 treesize of output 71 [2024-11-05 02:32:11,370 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 30 proven. 5 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2024-11-05 02:32:11,370 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:32:12,311 INFO L134 CoverageAnalysis]: Checked inductivity of 48 backedges. 5 proven. 7 refuted. 0 times theorem prover too weak. 36 trivial. 0 not checked. [2024-11-05 02:32:12,311 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:32:12,311 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1737708933] [2024-11-05 02:32:12,312 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1737708933] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-05 02:32:12,312 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-05 02:32:12,312 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 7] total 25 [2024-11-05 02:32:12,312 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1987271778] [2024-11-05 02:32:12,312 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-05 02:32:12,312 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-05 02:32:12,313 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:32:12,313 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-05 02:32:12,314 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=72, Invalid=528, Unknown=0, NotChecked=0, Total=600 [2024-11-05 02:32:12,314 INFO L87 Difference]: Start difference. First operand 156 states and 210 transitions. Second operand has 25 states, 23 states have (on average 4.391304347826087) internal successors, (101), 22 states have internal predecessors, (101), 7 states have call successors, (19), 4 states have call predecessors, (19), 8 states have return successors, (18), 7 states have call predecessors, (18), 7 states have call successors, (18)