/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_end_harness_negated.i -------------------------------------------------------------------------------- This is Ultimate 0.2.5-dev-b75d321-m [2024-11-05 02:27:24,265 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-05 02:27:24,324 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:27:24,329 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-05 02:27:24,329 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-05 02:27:24,359 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-05 02:27:24,359 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-05 02:27:24,360 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-05 02:27:24,360 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-05 02:27:24,361 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-05 02:27:24,361 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-05 02:27:24,362 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-05 02:27:24,363 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-05 02:27:24,363 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-05 02:27:24,364 INFO L153 SettingsManager]: * Use SBE=true [2024-11-05 02:27:24,364 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-05 02:27:24,364 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-05 02:27:24,365 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-05 02:27:24,365 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-05 02:27:24,365 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-05 02:27:24,366 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-05 02:27:24,366 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-05 02:27:24,367 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-05 02:27:24,367 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-05 02:27:24,367 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-05 02:27:24,368 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-05 02:27:24,368 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-05 02:27:24,368 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-05 02:27:24,369 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-05 02:27:24,369 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-05 02:27:24,369 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-05 02:27:24,370 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-05 02:27:24,370 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-05 02:27:24,370 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-05 02:27:24,371 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-05 02:27:24,371 INFO L153 SettingsManager]: * Trace refinement strategy=WOLF [2024-11-05 02:27:24,371 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-05 02:27:24,372 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-05 02:27:24,372 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-05 02:27:24,372 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-05 02:27:24,373 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-05 02:27:24,373 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:27:24,600 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-05 02:27:24,621 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-05 02:27:24,624 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-05 02:27:24,625 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-05 02:27:24,626 INFO L274 PluginConnector]: CDTParser initialized [2024-11-05 02:27:24,627 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_end_harness_negated.i [2024-11-05 02:27:26,132 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-05 02:27:26,555 INFO L384 CDTParser]: Found 1 translation units. [2024-11-05 02:27:26,555 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/aws-c-common/aws_linked_list_end_harness_negated.i [2024-11-05 02:27:26,587 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/32d9b3441/c8adbb6082b44d8ba40499518780fd84/FLAG30c1eba89 [2024-11-05 02:27:26,605 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/32d9b3441/c8adbb6082b44d8ba40499518780fd84 [2024-11-05 02:27:26,608 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-05 02:27:26,610 INFO L133 ToolchainWalker]: Walking toolchain with 5 elements. [2024-11-05 02:27:26,612 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-05 02:27:26,612 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-05 02:27:26,619 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-05 02:27:26,620 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.11 02:27:26" (1/1) ... [2024-11-05 02:27:26,621 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@1fb2ea05 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:26, skipping insertion in model container [2024-11-05 02:27:26,621 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.11 02:27:26" (1/1) ... [2024-11-05 02:27:26,719 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-05 02:27:27,034 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_end_harness_negated.i[4493,4506] [2024-11-05 02:27:27,049 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_end_harness_negated.i[4553,4566] [2024-11-05 02:27:27,834 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:27:27,929 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:27:27,930 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:27:27,931 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:27:27,941 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:27:27,944 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:27,945 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:27,945 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:27,946 WARN L1070 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-05 02:27:27,946 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:27,947 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:27,951 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:27:27,952 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:27:27,954 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:27:27,955 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:27:27,963 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:27,964 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:27:27,964 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:27,965 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:27:27,966 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:27,967 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:27:27,967 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:27,968 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:27:27,969 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:27,970 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:27:27,970 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:27,971 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:27:27,971 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:27,972 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,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:27:28,325 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:27:28,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:27:28,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:27:28,502 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:27:28,528 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-05 02:27:28,566 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-05 02:27:28,597 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-05 02:27:28,603 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_end_harness_negated.i[4493,4506] [2024-11-05 02:27:28,604 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_end_harness_negated.i[4553,4566] [2024-11-05 02:27:28,626 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:27:28,638 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:27:28,639 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:27:28,639 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:27:28,644 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:27:28,645 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,646 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,646 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,646 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:27:28,647 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,647 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,649 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:27:28,649 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:27:28,650 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:27:28,651 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:27:28,655 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,655 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:27:28,655 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,656 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:27:28,657 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,657 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:27:28,657 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,657 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:27:28,658 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,659 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:27:28,659 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,661 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:27:28,661 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,662 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,709 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:27:28,710 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:27:28,711 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:27:28,711 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:27:28,753 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:27:28,762 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-05 02:27:28,769 INFO L200 MainTranslator]: Completed pre-run [2024-11-05 02:27:28,781 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_end_harness_negated.i[4493,4506] [2024-11-05 02:27:28,781 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_end_harness_negated.i[4553,4566] [2024-11-05 02:27:28,822 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,823 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,823 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,823 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,824 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,830 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,831 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,832 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,832 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,833 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,833 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,834 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,834 WARN L1674 CHandler]: Possible shadowing of function index [2024-11-05 02:27:28,914 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-05 02:27:29,204 WARN L710 CHandler]: The following functions are not defined or handled internally: aws_array_list_ensure_capacity [2024-11-05 02:27:29,213 INFO L204 MainTranslator]: Completed translation [2024-11-05 02:27:29,214 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:29 WrapperNode [2024-11-05 02:27:29,214 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-05 02:27:29,215 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-05 02:27:29,215 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-05 02:27:29,215 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-05 02:27:29,223 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:27:29" (1/1) ... [2024-11-05 02:27:29,321 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:27:29" (1/1) ... [2024-11-05 02:27:29,403 INFO L138 Inliner]: procedures = 687, calls = 1038, calls flagged for inlining = 52, calls inlined = 6, statements flattened = 138 [2024-11-05 02:27:29,403 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-05 02:27:29,404 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-05 02:27:29,404 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-05 02:27:29,404 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-05 02:27:29,417 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:29" (1/1) ... [2024-11-05 02:27:29,418 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:29" (1/1) ... [2024-11-05 02:27:29,424 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:29" (1/1) ... [2024-11-05 02:27:29,454 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:27:29,455 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:29" (1/1) ... [2024-11-05 02:27:29,456 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:29" (1/1) ... [2024-11-05 02:27:29,477 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:29" (1/1) ... [2024-11-05 02:27:29,481 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:29" (1/1) ... [2024-11-05 02:27:29,493 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:29" (1/1) ... [2024-11-05 02:27:29,500 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:29" (1/1) ... [2024-11-05 02:27:29,513 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-05 02:27:29,514 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-05 02:27:29,514 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-05 02:27:29,514 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-05 02:27:29,515 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:29" (1/1) ... [2024-11-05 02:27:29,522 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-05 02:27:29,536 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-05 02:27:29,552 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:27:29,556 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:27:29,584 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-05 02:27:29,584 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2024-11-05 02:27:29,584 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2024-11-05 02:27:29,585 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#2 [2024-11-05 02:27:29,585 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-05 02:27:29,585 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-05 02:27:29,585 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_node_next_is_valid [2024-11-05 02:27:29,585 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_node_next_is_valid [2024-11-05 02:27:29,585 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-05 02:27:29,585 INFO L130 BoogieDeclarations]: Found specification of procedure aws_linked_list_is_valid [2024-11-05 02:27:29,585 INFO L138 BoogieDeclarations]: Found implementation of procedure aws_linked_list_is_valid [2024-11-05 02:27:29,586 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-05 02:27:29,586 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2024-11-05 02:27:29,586 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2024-11-05 02:27:29,587 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#2 [2024-11-05 02:27:29,587 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-05 02:27:29,587 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-05 02:27:29,587 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-05 02:27:29,587 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-05 02:27:29,587 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-05 02:27:29,587 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2024-11-05 02:27:29,587 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2024-11-05 02:27:29,587 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#2 [2024-11-05 02:27:29,587 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2024-11-05 02:27:29,587 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2024-11-05 02:27:29,587 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#2 [2024-11-05 02:27:29,588 INFO L130 BoogieDeclarations]: Found specification of procedure nondet_uint64_t [2024-11-05 02:27:29,588 INFO L138 BoogieDeclarations]: Found implementation of procedure nondet_uint64_t [2024-11-05 02:27:29,901 INFO L238 CfgBuilder]: Building ICFG [2024-11-05 02:27:29,903 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-05 02:27:30,291 INFO L? ?]: Removed 54 outVars from TransFormulas that were not future-live. [2024-11-05 02:27:30,291 INFO L287 CfgBuilder]: Performing block encoding [2024-11-05 02:27:30,319 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-05 02:27:30,319 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-05 02:27:30,320 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.11 02:27:30 BoogieIcfgContainer [2024-11-05 02:27:30,320 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-05 02:27:30,323 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-05 02:27:30,324 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-05 02:27:30,327 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-05 02:27:30,327 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.11 02:27:26" (1/3) ... [2024-11-05 02:27:30,328 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3de884f7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.11 02:27:30, skipping insertion in model container [2024-11-05 02:27:30,328 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.11 02:27:29" (2/3) ... [2024-11-05 02:27:30,329 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@3de884f7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.11 02:27:30, skipping insertion in model container [2024-11-05 02:27:30,330 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.11 02:27:30" (3/3) ... [2024-11-05 02:27:30,331 INFO L112 eAbstractionObserver]: Analyzing ICFG aws_linked_list_end_harness_negated.i [2024-11-05 02:27:30,348 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-05 02:27:30,348 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-05 02:27:30,418 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-05 02:27:30,430 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;@4179f967, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-05 02:27:30,430 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-05 02:27:30,437 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:27:30,449 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-11-05 02:27:30,449 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:27:30,451 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:27:30,452 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:27:30,458 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:27:30,459 INFO L85 PathProgramCache]: Analyzing trace with hash -2107862704, now seen corresponding path program 1 times [2024-11-05 02:27:30,468 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:27:30,468 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [219801576] [2024-11-05 02:27:30,469 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:27:30,470 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:27:30,471 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:27:30,475 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:27:30,477 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:27:30,735 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:27:30,740 INFO L255 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-05 02:27:30,751 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:27:30,786 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:27:30,787 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:27:30,858 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:27:30,859 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:27:30,859 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [219801576] [2024-11-05 02:27:30,860 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [219801576] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:27:30,860 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:27:30,860 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [2] total 2 [2024-11-05 02:27:30,862 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1340357525] [2024-11-05 02:27:30,862 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:27:30,867 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-05 02:27:30,867 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:27:30,891 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-05 02:27:30,892 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-05 02:27:30,895 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:27:30,925 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:27:30,925 INFO L93 Difference]: Finished difference Result 128 states and 184 transitions. [2024-11-05 02:27:30,927 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-05 02:27:30,928 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:27:30,928 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:27:30,936 INFO L225 Difference]: With dead ends: 128 [2024-11-05 02:27:30,936 INFO L226 Difference]: Without dead ends: 63 [2024-11-05 02:27:30,940 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:27:30,945 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:27:30,945 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:27:30,963 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2024-11-05 02:27:30,987 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 63. [2024-11-05 02:27:30,988 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:27:30,992 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 82 transitions. [2024-11-05 02:27:30,994 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 82 transitions. Word has length 68 [2024-11-05 02:27:30,998 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:27:30,998 INFO L471 AbstractCegarLoop]: Abstraction has 63 states and 82 transitions. [2024-11-05 02:27:30,999 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:27:30,999 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 82 transitions. [2024-11-05 02:27:31,004 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2024-11-05 02:27:31,004 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:27:31,005 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:27:31,010 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (2)] Ended with exit code 0 [2024-11-05 02:27:31,205 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:27:31,206 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:27:31,207 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:27:31,207 INFO L85 PathProgramCache]: Analyzing trace with hash 900796622, now seen corresponding path program 1 times [2024-11-05 02:27:31,207 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:27:31,207 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [2090250877] [2024-11-05 02:27:31,207 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:27:31,208 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:27:31,208 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:27:31,211 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:27:31,212 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:27:31,387 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:27:31,402 WARN L253 TraceCheckSpWp]: Trace formula consists of 207 conjuncts, 118 conjuncts are in the unsatisfiable core [2024-11-05 02:27:31,424 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:27:31,511 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:27:31,741 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:27:31,758 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:27:31,789 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:27:31,971 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:27:31,972 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:27:32,002 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:27:35,875 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:27:35,876 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:27:36,447 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:27:36,448 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:27:36,448 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [2090250877] [2024-11-05 02:27:36,448 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [2090250877] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-05 02:27:36,448 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-05 02:27:36,448 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [15, 6] imperfect sequences [] total 18 [2024-11-05 02:27:36,448 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1693751801] [2024-11-05 02:27:36,448 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-05 02:27:36,450 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-05 02:27:36,450 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:27:36,451 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-05 02:27:36,451 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=46, Invalid=260, Unknown=0, NotChecked=0, Total=306 [2024-11-05 02:27:36,452 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:27:38,539 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:27:38,539 INFO L93 Difference]: Finished difference Result 138 states and 184 transitions. [2024-11-05 02:27:38,542 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2024-11-05 02:27:38,542 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:27:38,543 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:27:38,548 INFO L225 Difference]: With dead ends: 138 [2024-11-05 02:27:38,548 INFO L226 Difference]: Without dead ends: 136 [2024-11-05 02:27:38,549 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 143 GetRequests, 113 SyntacticMatches, 6 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 160 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=96, Invalid=554, Unknown=0, NotChecked=0, Total=650 [2024-11-05 02:27:38,551 INFO L432 NwaCegarLoop]: 61 mSDtfsCounter, 64 mSDsluCounter, 642 mSDsCounter, 0 mSdLazyCounter, 338 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s 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:27:38,551 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:27:38,552 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2024-11-05 02:27:38,583 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 128. [2024-11-05 02:27:38,583 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:27:38,585 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 128 states to 128 states and 172 transitions. [2024-11-05 02:27:38,586 INFO L78 Accepts]: Start accepts. Automaton has 128 states and 172 transitions. Word has length 68 [2024-11-05 02:27:38,586 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:27:38,586 INFO L471 AbstractCegarLoop]: Abstraction has 128 states and 172 transitions. [2024-11-05 02:27:38,587 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:27:38,587 INFO L276 IsEmpty]: Start isEmpty. Operand 128 states and 172 transitions. [2024-11-05 02:27:38,589 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2024-11-05 02:27:38,589 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:27:38,589 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:27:38,593 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (3)] Ended with exit code 0 [2024-11-05 02:27:38,790 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:27:38,790 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:27:38,791 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:27:38,791 INFO L85 PathProgramCache]: Analyzing trace with hash 1974675530, now seen corresponding path program 1 times [2024-11-05 02:27:38,791 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:27:38,791 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [709803536] [2024-11-05 02:27:38,791 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:27:38,792 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:27:38,792 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:27:38,793 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:27:38,794 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:27:38,949 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:27:38,964 WARN L253 TraceCheckSpWp]: Trace formula consists of 214 conjuncts, 124 conjuncts are in the unsatisfiable core [2024-11-05 02:27:38,979 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:27:38,990 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:27:39,119 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:27:39,124 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:27:39,131 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:27:39,147 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:27:39,225 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:27:39,225 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:27:39,246 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:27:42,412 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:27:42,412 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:27:42,956 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:27:42,956 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:27:42,956 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [709803536] [2024-11-05 02:27:42,956 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [709803536] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-05 02:27:42,956 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-05 02:27:42,957 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [18, 7] imperfect sequences [] total 22 [2024-11-05 02:27:42,957 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1555853447] [2024-11-05 02:27:42,957 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-05 02:27:42,957 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2024-11-05 02:27:42,958 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:27:42,958 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2024-11-05 02:27:42,959 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=402, Unknown=0, NotChecked=0, Total=462 [2024-11-05 02:27:42,959 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:27:45,674 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:27:45,675 INFO L93 Difference]: Finished difference Result 159 states and 214 transitions. [2024-11-05 02:27:45,675 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-05 02:27:45,676 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:27:45,676 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:27:45,678 INFO L225 Difference]: With dead ends: 159 [2024-11-05 02:27:45,678 INFO L226 Difference]: Without dead ends: 157 [2024-11-05 02:27:45,679 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 148 GetRequests, 113 SyntacticMatches, 6 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 231 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=115, Invalid=815, Unknown=0, NotChecked=0, Total=930 [2024-11-05 02:27:45,680 INFO L432 NwaCegarLoop]: 57 mSDtfsCounter, 80 mSDsluCounter, 670 mSDsCounter, 0 mSdLazyCounter, 559 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.8s 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.9s IncrementalHoareTripleChecker+Time [2024-11-05 02:27:45,680 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.9s Time] [2024-11-05 02:27:45,681 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 157 states. [2024-11-05 02:27:45,704 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 157 to 130. [2024-11-05 02:27:45,704 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:27:45,707 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 174 transitions. [2024-11-05 02:27:45,708 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 174 transitions. Word has length 70 [2024-11-05 02:27:45,708 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:27:45,708 INFO L471 AbstractCegarLoop]: Abstraction has 130 states and 174 transitions. [2024-11-05 02:27:45,708 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:27:45,708 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 174 transitions. [2024-11-05 02:27:45,710 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 73 [2024-11-05 02:27:45,710 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:27:45,711 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:27:45,714 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:27:45,912 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:27:45,913 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:27:45,913 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:27:45,913 INFO L85 PathProgramCache]: Analyzing trace with hash -1166515017, now seen corresponding path program 1 times [2024-11-05 02:27:45,913 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:27:45,913 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [183374442] [2024-11-05 02:27:45,913 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:27:45,914 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:27:45,914 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:27:45,915 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:27:45,916 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:27:46,069 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:27:46,080 WARN L253 TraceCheckSpWp]: Trace formula consists of 218 conjuncts, 127 conjuncts are in the unsatisfiable core [2024-11-05 02:27:46,093 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:27:46,101 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:27:46,171 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:27:46,179 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:27:46,191 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:27:46,258 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:27:46,258 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:27:46,276 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:27:49,584 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:27:49,584 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:27:50,258 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:27:50,259 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:27:50,259 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [183374442] [2024-11-05 02:27:50,259 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [183374442] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-05 02:27:50,259 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-05 02:27:50,259 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [20, 9] imperfect sequences [] total 26 [2024-11-05 02:27:50,259 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2116075793] [2024-11-05 02:27:50,259 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-05 02:27:50,260 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2024-11-05 02:27:50,260 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:27:50,261 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2024-11-05 02:27:50,262 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=575, Unknown=0, NotChecked=0, Total=650 [2024-11-05 02:27:50,262 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:27:53,605 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:27:53,605 INFO L93 Difference]: Finished difference Result 173 states and 238 transitions. [2024-11-05 02:27:53,606 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2024-11-05 02:27:53,606 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:27:53,606 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:27:53,608 INFO L225 Difference]: With dead ends: 173 [2024-11-05 02:27:53,608 INFO L226 Difference]: Without dead ends: 171 [2024-11-05 02:27:53,611 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 159 GetRequests, 113 SyntacticMatches, 6 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 409 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=187, Invalid=1535, Unknown=0, NotChecked=0, Total=1722 [2024-11-05 02:27:53,611 INFO L432 NwaCegarLoop]: 53 mSDtfsCounter, 99 mSDsluCounter, 672 mSDsCounter, 0 mSdLazyCounter, 620 mSolverCounterSat, 52 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.0s 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:27:53,612 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:27:53,613 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 171 states. [2024-11-05 02:27:53,637 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 171 to 132. [2024-11-05 02:27:53,637 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:27:53,639 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 132 states to 132 states and 176 transitions. [2024-11-05 02:27:53,639 INFO L78 Accepts]: Start accepts. Automaton has 132 states and 176 transitions. Word has length 72 [2024-11-05 02:27:53,639 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:27:53,639 INFO L471 AbstractCegarLoop]: Abstraction has 132 states and 176 transitions. [2024-11-05 02:27:53,640 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:27:53,640 INFO L276 IsEmpty]: Start isEmpty. Operand 132 states and 176 transitions. [2024-11-05 02:27:53,641 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2024-11-05 02:27:53,641 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:27:53,641 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:27:53,647 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (5)] Ended with exit code 0 [2024-11-05 02:27:53,842 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:27:53,842 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:27:53,843 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:27:53,843 INFO L85 PathProgramCache]: Analyzing trace with hash 949556601, now seen corresponding path program 1 times [2024-11-05 02:27:53,843 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:27:53,843 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1469913722] [2024-11-05 02:27:53,843 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:27:53,843 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:27:53,843 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:27:53,845 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:27:53,846 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:27:53,997 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:27:54,011 WARN L253 TraceCheckSpWp]: Trace formula consists of 220 conjuncts, 121 conjuncts are in the unsatisfiable core [2024-11-05 02:27:54,019 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:27:54,033 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:27:54,111 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:27:54,123 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:27:54,134 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:27:54,209 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:27:54,209 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:27:54,225 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:27:56,761 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:27:56,761 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:27:57,089 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:27:57,089 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:27:57,089 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1469913722] [2024-11-05 02:27:57,090 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1469913722] provided 2 perfect and 0 imperfect interpolant sequences [2024-11-05 02:27:57,090 INFO L185 FreeRefinementEngine]: Found 2 perfect and 0 imperfect interpolant sequences. [2024-11-05 02:27:57,090 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [14, 3] imperfect sequences [] total 15 [2024-11-05 02:27:57,090 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [62580046] [2024-11-05 02:27:57,090 INFO L85 oduleStraightlineAll]: Using 2 perfect interpolants to construct interpolant automaton [2024-11-05 02:27:57,090 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2024-11-05 02:27:57,090 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:27:57,091 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2024-11-05 02:27:57,091 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=40, Invalid=170, Unknown=0, NotChecked=0, Total=210 [2024-11-05 02:27:57,091 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:27:59,878 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:27:59,879 INFO L93 Difference]: Finished difference Result 265 states and 366 transitions. [2024-11-05 02:27:59,879 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2024-11-05 02:27:59,880 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:27:59,880 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:27:59,882 INFO L225 Difference]: With dead ends: 265 [2024-11-05 02:27:59,882 INFO L226 Difference]: Without dead ends: 151 [2024-11-05 02:27:59,884 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:27:59,886 INFO L432 NwaCegarLoop]: 58 mSDtfsCounter, 59 mSDsluCounter, 507 mSDsCounter, 0 mSdLazyCounter, 400 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.2s 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.3s IncrementalHoareTripleChecker+Time [2024-11-05 02:27:59,887 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.3s Time] [2024-11-05 02:27:59,888 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 151 states. [2024-11-05 02:27:59,924 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 151 to 136. [2024-11-05 02:27:59,925 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:27:59,926 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 182 transitions. [2024-11-05 02:27:59,926 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 182 transitions. Word has length 73 [2024-11-05 02:27:59,926 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:27:59,926 INFO L471 AbstractCegarLoop]: Abstraction has 136 states and 182 transitions. [2024-11-05 02:27:59,927 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:27:59,927 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 182 transitions. [2024-11-05 02:27:59,928 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2024-11-05 02:27:59,928 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:27:59,928 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:27:59,931 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (6)] Ended with exit code 0 [2024-11-05 02:28:00,128 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:28:00,129 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:28:00,129 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:28:00,129 INFO L85 PathProgramCache]: Analyzing trace with hash 509705391, now seen corresponding path program 1 times [2024-11-05 02:28:00,130 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:28:00,130 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [38801020] [2024-11-05 02:28:00,130 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:28:00,130 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:28:00,130 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:28:00,131 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:28:00,132 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:28:00,270 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:28:00,277 WARN L253 TraceCheckSpWp]: Trace formula consists of 215 conjuncts, 122 conjuncts are in the unsatisfiable core [2024-11-05 02:28:00,285 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:28:00,292 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:28:00,356 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:28:00,367 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:28:00,376 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:28:00,488 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:28:00,488 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:28:00,506 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:28:01,549 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:28:01,549 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:28:02,093 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:28:02,093 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:28:02,093 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [38801020] [2024-11-05 02:28:02,093 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [38801020] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:28:02,093 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:28:02,094 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [6] total 17 [2024-11-05 02:28:02,094 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1200652821] [2024-11-05 02:28:02,094 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:28:02,094 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-05 02:28:02,094 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:28:02,095 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-05 02:28:02,095 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=224, Unknown=0, NotChecked=0, Total=272 [2024-11-05 02:28:02,095 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:28:03,686 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:28:03,686 INFO L93 Difference]: Finished difference Result 200 states and 267 transitions. [2024-11-05 02:28:03,687 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-05 02:28:03,687 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:28:03,687 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:28:03,689 INFO L225 Difference]: With dead ends: 200 [2024-11-05 02:28:03,690 INFO L226 Difference]: Without dead ends: 140 [2024-11-05 02:28:03,691 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:28:03,692 INFO L432 NwaCegarLoop]: 62 mSDtfsCounter, 65 mSDsluCounter, 357 mSDsCounter, 0 mSdLazyCounter, 247 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s 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.4s IncrementalHoareTripleChecker+Time [2024-11-05 02:28:03,692 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.4s Time] [2024-11-05 02:28:03,693 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2024-11-05 02:28:03,720 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 138. [2024-11-05 02:28:03,721 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:28:03,722 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 138 states to 138 states and 186 transitions. [2024-11-05 02:28:03,722 INFO L78 Accepts]: Start accepts. Automaton has 138 states and 186 transitions. Word has length 74 [2024-11-05 02:28:03,722 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:28:03,723 INFO L471 AbstractCegarLoop]: Abstraction has 138 states and 186 transitions. [2024-11-05 02:28:03,723 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:28:03,723 INFO L276 IsEmpty]: Start isEmpty. Operand 138 states and 186 transitions. [2024-11-05 02:28:03,724 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-05 02:28:03,724 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:28:03,725 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:28:03,728 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (7)] Ended with exit code 0 [2024-11-05 02:28:03,925 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:28:03,926 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:28:03,926 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:28:03,926 INFO L85 PathProgramCache]: Analyzing trace with hash 1404935915, now seen corresponding path program 1 times [2024-11-05 02:28:03,926 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:28:03,926 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1821492714] [2024-11-05 02:28:03,926 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:28:03,927 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:28:03,927 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:28:03,928 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:28:03,930 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:28:04,088 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:28:04,097 WARN L253 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 126 conjuncts are in the unsatisfiable core [2024-11-05 02:28:04,106 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:28:04,112 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:28:04,198 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:28:04,215 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:28:04,224 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:28:04,295 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:28:04,317 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:28:05,155 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:28:05,155 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:28:05,803 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:28:05,803 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:28:05,803 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1821492714] [2024-11-05 02:28:05,803 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1821492714] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:28:05,803 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:28:05,804 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [9] total 18 [2024-11-05 02:28:05,804 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1018031905] [2024-11-05 02:28:05,804 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:28:05,804 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-05 02:28:05,804 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:28:05,805 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-05 02:28:05,805 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=69, Invalid=237, Unknown=0, NotChecked=0, Total=306 [2024-11-05 02:28:05,805 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:28:07,558 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:28:07,558 INFO L93 Difference]: Finished difference Result 205 states and 276 transitions. [2024-11-05 02:28:07,559 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-05 02:28:07,559 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:28:07,559 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:28:07,560 INFO L225 Difference]: With dead ends: 205 [2024-11-05 02:28:07,560 INFO L226 Difference]: Without dead ends: 143 [2024-11-05 02:28:07,561 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 134 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 82 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=75, Invalid=267, Unknown=0, NotChecked=0, Total=342 [2024-11-05 02:28:07,562 INFO L432 NwaCegarLoop]: 62 mSDtfsCounter, 55 mSDsluCounter, 340 mSDsCounter, 0 mSdLazyCounter, 261 mSolverCounterSat, 11 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.6s 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.7s IncrementalHoareTripleChecker+Time [2024-11-05 02:28:07,562 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.7s Time] [2024-11-05 02:28:07,562 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 143 states. [2024-11-05 02:28:07,588 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 143 to 141. [2024-11-05 02:28:07,588 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:28:07,589 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 141 states to 141 states and 190 transitions. [2024-11-05 02:28:07,590 INFO L78 Accepts]: Start accepts. Automaton has 141 states and 190 transitions. Word has length 76 [2024-11-05 02:28:07,590 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:28:07,590 INFO L471 AbstractCegarLoop]: Abstraction has 141 states and 190 transitions. [2024-11-05 02:28:07,590 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:28:07,590 INFO L276 IsEmpty]: Start isEmpty. Operand 141 states and 190 transitions. [2024-11-05 02:28:07,591 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-05 02:28:07,591 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:28:07,592 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:28:07,595 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:28:07,794 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:28:07,794 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:28:07,795 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:28:07,795 INFO L85 PathProgramCache]: Analyzing trace with hash -233332627, now seen corresponding path program 1 times [2024-11-05 02:28:07,795 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:28:07,795 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1096966975] [2024-11-05 02:28:07,795 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:28:07,795 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:28:07,795 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:28:07,796 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:28:07,797 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:28:07,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:28:07,971 WARN L253 TraceCheckSpWp]: Trace formula consists of 241 conjuncts, 140 conjuncts are in the unsatisfiable core [2024-11-05 02:28:07,978 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:28:07,983 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:28:07,992 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:28:07,998 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:28:08,136 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:28:08,147 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:28:08,162 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:28:08,274 INFO L349 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2024-11-05 02:28:08,275 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:28:08,311 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:28:08,339 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-05 02:28:08,340 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:28:08,374 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2024-11-05 02:28:08,375 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:28:08,646 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2024-11-05 02:28:08,646 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:28:08,680 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-11-05 02:28:08,680 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:28:12,380 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:28:12,381 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:28:12,958 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:28:12,958 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:28:12,959 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1096966975] [2024-11-05 02:28:12,959 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1096966975] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-05 02:28:12,959 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-05 02:28:12,959 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 6] total 19 [2024-11-05 02:28:12,959 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [488369820] [2024-11-05 02:28:12,959 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-05 02:28:12,959 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 19 states [2024-11-05 02:28:12,959 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:28:12,960 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 19 interpolants. [2024-11-05 02:28:12,960 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=54, Invalid=288, Unknown=0, NotChecked=0, Total=342 [2024-11-05 02:28:12,960 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:28:16,928 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:28:16,928 INFO L93 Difference]: Finished difference Result 277 states and 372 transitions. [2024-11-05 02:28:16,929 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-05 02:28:16,929 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:28:16,929 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:28:16,931 INFO L225 Difference]: With dead ends: 277 [2024-11-05 02:28:16,931 INFO L226 Difference]: Without dead ends: 216 [2024-11-05 02:28:16,932 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 155 GetRequests, 130 SyntacticMatches, 3 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 147 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=80, Invalid=472, Unknown=0, NotChecked=0, Total=552 [2024-11-05 02:28:16,932 INFO L432 NwaCegarLoop]: 122 mSDtfsCounter, 111 mSDsluCounter, 1196 mSDsCounter, 0 mSdLazyCounter, 552 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s 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.6s IncrementalHoareTripleChecker+Time [2024-11-05 02:28:16,933 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.6s Time] [2024-11-05 02:28:16,933 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 216 states. [2024-11-05 02:28:16,979 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 216 to 147. [2024-11-05 02:28:16,980 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:28:16,981 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 147 states to 147 states and 197 transitions. [2024-11-05 02:28:16,981 INFO L78 Accepts]: Start accepts. Automaton has 147 states and 197 transitions. Word has length 76 [2024-11-05 02:28:16,982 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:28:16,982 INFO L471 AbstractCegarLoop]: Abstraction has 147 states and 197 transitions. [2024-11-05 02:28:16,982 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:28:16,983 INFO L276 IsEmpty]: Start isEmpty. Operand 147 states and 197 transitions. [2024-11-05 02:28:16,984 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2024-11-05 02:28:16,984 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:28:16,984 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:28:16,988 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:28:17,184 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:28:17,185 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:28:17,185 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:28:17,185 INFO L85 PathProgramCache]: Analyzing trace with hash -141117224, now seen corresponding path program 1 times [2024-11-05 02:28:17,185 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:28:17,185 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1719396731] [2024-11-05 02:28:17,186 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:28:17,186 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:28:17,186 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:28:17,187 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:28:17,188 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:28:17,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:28:17,369 WARN L253 TraceCheckSpWp]: Trace formula consists of 226 conjuncts, 129 conjuncts are in the unsatisfiable core [2024-11-05 02:28:17,376 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:28:17,380 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:28:17,463 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:28:17,472 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:28:17,552 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:28:17,573 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:28:18,613 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:28:18,613 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:28:19,421 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:28:19,421 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:28:19,421 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1719396731] [2024-11-05 02:28:19,421 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1719396731] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:28:19,421 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:28:19,422 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [13] imperfect sequences [10] total 21 [2024-11-05 02:28:19,422 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [11831658] [2024-11-05 02:28:19,422 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:28:19,422 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-05 02:28:19,422 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:28:19,423 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-05 02:28:19,423 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=332, Unknown=0, NotChecked=0, Total=420 [2024-11-05 02:28:19,423 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:28:22,063 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:28:22,064 INFO L93 Difference]: Finished difference Result 221 states and 297 transitions. [2024-11-05 02:28:22,064 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-05 02:28:22,064 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:28:22,064 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:28:22,065 INFO L225 Difference]: With dead ends: 221 [2024-11-05 02:28:22,065 INFO L226 Difference]: Without dead ends: 156 [2024-11-05 02:28:22,066 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:28:22,066 INFO L432 NwaCegarLoop]: 85 mSDtfsCounter, 59 mSDsluCounter, 598 mSDsCounter, 0 mSdLazyCounter, 403 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.3s 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.4s IncrementalHoareTripleChecker+Time [2024-11-05 02:28:22,067 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.4s Time] [2024-11-05 02:28:22,067 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 156 states. [2024-11-05 02:28:22,103 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 156 to 148. [2024-11-05 02:28:22,104 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:28:22,105 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 148 states to 148 states and 198 transitions. [2024-11-05 02:28:22,105 INFO L78 Accepts]: Start accepts. Automaton has 148 states and 198 transitions. Word has length 78 [2024-11-05 02:28:22,105 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:28:22,106 INFO L471 AbstractCegarLoop]: Abstraction has 148 states and 198 transitions. [2024-11-05 02:28:22,106 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:28:22,106 INFO L276 IsEmpty]: Start isEmpty. Operand 148 states and 198 transitions. [2024-11-05 02:28:22,107 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2024-11-05 02:28:22,107 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:28:22,107 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:28:22,112 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (10)] Ended with exit code 0 [2024-11-05 02:28:22,309 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:28:22,310 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:28:22,310 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:28:22,310 INFO L85 PathProgramCache]: Analyzing trace with hash 309971753, now seen corresponding path program 1 times [2024-11-05 02:28:22,310 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:28:22,310 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [287747268] [2024-11-05 02:28:22,310 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:28:22,311 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:28:22,311 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:28:22,312 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:28:22,313 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:28:22,511 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:28:22,521 WARN L253 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 146 conjuncts are in the unsatisfiable core [2024-11-05 02:28:22,529 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:28:22,536 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:28:22,551 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:28:22,558 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:28:22,730 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:28:22,744 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:28:22,764 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:28:22,901 INFO L349 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2024-11-05 02:28:22,902 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:28:22,935 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2024-11-05 02:28:22,936 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:28:22,953 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-05 02:28:22,953 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:28:23,290 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2024-11-05 02:28:23,290 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:28:23,319 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-11-05 02:28:23,319 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:28:25,438 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:28:25,438 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:28:26,091 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:28:26,091 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:28:26,091 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [287747268] [2024-11-05 02:28:26,091 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [287747268] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-05 02:28:26,091 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-05 02:28:26,091 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 6] total 18 [2024-11-05 02:28:26,092 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1634745473] [2024-11-05 02:28:26,092 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-05 02:28:26,092 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-05 02:28:26,092 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:28:26,093 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-05 02:28:26,093 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=246, Unknown=0, NotChecked=0, Total=306 [2024-11-05 02:28:26,093 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:28:29,731 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:28:29,731 INFO L93 Difference]: Finished difference Result 288 states and 389 transitions. [2024-11-05 02:28:29,732 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-05 02:28:29,732 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:28:29,733 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:28:29,734 INFO L225 Difference]: With dead ends: 288 [2024-11-05 02:28:29,734 INFO L226 Difference]: Without dead ends: 226 [2024-11-05 02:28:29,735 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 161 GetRequests, 138 SyntacticMatches, 2 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=91, Invalid=415, Unknown=0, NotChecked=0, Total=506 [2024-11-05 02:28:29,735 INFO L432 NwaCegarLoop]: 103 mSDtfsCounter, 151 mSDsluCounter, 792 mSDsCounter, 0 mSdLazyCounter, 643 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.2s 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.4s IncrementalHoareTripleChecker+Time [2024-11-05 02:28:29,736 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.4s Time] [2024-11-05 02:28:29,736 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 226 states. [2024-11-05 02:28:29,775 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 226 to 151. [2024-11-05 02:28:29,775 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:28:29,776 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 151 states to 151 states and 202 transitions. [2024-11-05 02:28:29,776 INFO L78 Accepts]: Start accepts. Automaton has 151 states and 202 transitions. Word has length 78 [2024-11-05 02:28:29,776 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:28:29,776 INFO L471 AbstractCegarLoop]: Abstraction has 151 states and 202 transitions. [2024-11-05 02:28:29,777 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:28:29,777 INFO L276 IsEmpty]: Start isEmpty. Operand 151 states and 202 transitions. [2024-11-05 02:28:29,778 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2024-11-05 02:28:29,778 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:28:29,778 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:28:29,782 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:28:29,978 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:28:29,979 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:28:29,979 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:28:29,979 INFO L85 PathProgramCache]: Analyzing trace with hash -134689386, now seen corresponding path program 1 times [2024-11-05 02:28:29,979 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:28:29,979 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [554301102] [2024-11-05 02:28:29,979 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:28:29,980 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:28:29,980 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:28:29,981 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:28:29,982 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:28:30,183 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:28:30,192 WARN L253 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 149 conjuncts are in the unsatisfiable core [2024-11-05 02:28:30,200 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:28:30,204 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:28:30,210 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:28:30,220 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:28:30,404 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:28:30,414 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:28:30,510 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2024-11-05 02:28:30,511 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:28:30,531 INFO L349 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2024-11-05 02:28:30,532 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:28:30,562 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:28:30,572 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:28:30,592 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-05 02:28:30,592 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:28:30,902 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2024-11-05 02:28:30,903 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:28:30,947 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-11-05 02:28:30,948 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:28:33,562 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:28:33,562 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:28:34,275 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:28:34,275 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:28:34,276 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [554301102] [2024-11-05 02:28:34,276 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [554301102] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-05 02:28:34,276 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-05 02:28:34,276 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 7] total 21 [2024-11-05 02:28:34,276 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2014752418] [2024-11-05 02:28:34,276 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-05 02:28:34,276 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2024-11-05 02:28:34,276 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:28:34,277 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2024-11-05 02:28:34,277 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=76, Invalid=344, Unknown=0, NotChecked=0, Total=420 [2024-11-05 02:28:34,277 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:28:37,991 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:28:37,991 INFO L93 Difference]: Finished difference Result 305 states and 414 transitions. [2024-11-05 02:28:37,992 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2024-11-05 02:28:37,992 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:28:37,992 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:28:37,994 INFO L225 Difference]: With dead ends: 305 [2024-11-05 02:28:37,994 INFO L226 Difference]: Without dead ends: 240 [2024-11-05 02:28:37,995 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 170 GetRequests, 139 SyntacticMatches, 2 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 223 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=153, Invalid=777, Unknown=0, NotChecked=0, Total=930 [2024-11-05 02:28:37,995 INFO L432 NwaCegarLoop]: 97 mSDtfsCounter, 189 mSDsluCounter, 705 mSDsCounter, 0 mSdLazyCounter, 677 mSolverCounterSat, 54 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.8s 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.0s IncrementalHoareTripleChecker+Time [2024-11-05 02:28:37,996 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.0s Time] [2024-11-05 02:28:37,996 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 240 states. [2024-11-05 02:28:38,038 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 240 to 84. [2024-11-05 02:28:38,039 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:28:38,039 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 109 transitions. [2024-11-05 02:28:38,040 INFO L78 Accepts]: Start accepts. Automaton has 84 states and 109 transitions. Word has length 80 [2024-11-05 02:28:38,040 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:28:38,040 INFO L471 AbstractCegarLoop]: Abstraction has 84 states and 109 transitions. [2024-11-05 02:28:38,040 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:28:38,040 INFO L276 IsEmpty]: Start isEmpty. Operand 84 states and 109 transitions. [2024-11-05 02:28:38,041 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 88 [2024-11-05 02:28:38,041 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:28:38,041 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:28:38,045 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:28:38,242 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:28:38,242 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:28:38,242 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:28:38,242 INFO L85 PathProgramCache]: Analyzing trace with hash 1636580586, now seen corresponding path program 1 times [2024-11-05 02:28:38,243 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:28:38,243 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1164230321] [2024-11-05 02:28:38,243 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:28:38,243 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:28:38,243 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:28:38,246 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:28:38,247 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:28:38,478 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:28:38,487 WARN L253 TraceCheckSpWp]: Trace formula consists of 248 conjuncts, 143 conjuncts are in the unsatisfiable core [2024-11-05 02:28:38,495 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:28:38,499 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:28:38,562 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:28:38,572 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:28:38,581 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:28:38,678 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:28:38,679 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:28:38,692 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:28:40,485 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:28:40,485 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:28:41,280 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:28:41,281 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:28:41,281 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1164230321] [2024-11-05 02:28:41,281 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1164230321] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-05 02:28:41,281 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-05 02:28:41,281 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [18] imperfect sequences [7] total 23 [2024-11-05 02:28:41,281 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1176084857] [2024-11-05 02:28:41,281 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-05 02:28:41,281 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2024-11-05 02:28:41,282 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:28:41,282 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2024-11-05 02:28:41,282 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=66, Invalid=440, Unknown=0, NotChecked=0, Total=506 [2024-11-05 02:28:41,282 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:28:45,421 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:28:45,421 INFO L93 Difference]: Finished difference Result 232 states and 311 transitions. [2024-11-05 02:28:45,421 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 21 states. [2024-11-05 02:28:45,422 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:28:45,422 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:28:45,423 INFO L225 Difference]: With dead ends: 232 [2024-11-05 02:28:45,423 INFO L226 Difference]: Without dead ends: 166 [2024-11-05 02:28:45,424 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 179 GetRequests, 150 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 215 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=109, Invalid=761, Unknown=0, NotChecked=0, Total=870 [2024-11-05 02:28:45,424 INFO L432 NwaCegarLoop]: 83 mSDtfsCounter, 51 mSDsluCounter, 993 mSDsCounter, 0 mSdLazyCounter, 690 mSolverCounterSat, 15 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s 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.6s IncrementalHoareTripleChecker+Time [2024-11-05 02:28:45,424 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.6s Time] [2024-11-05 02:28:45,425 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2024-11-05 02:28:45,491 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 153. [2024-11-05 02:28:45,492 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:28:45,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 153 states to 153 states and 204 transitions. [2024-11-05 02:28:45,493 INFO L78 Accepts]: Start accepts. Automaton has 153 states and 204 transitions. Word has length 87 [2024-11-05 02:28:45,493 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:28:45,494 INFO L471 AbstractCegarLoop]: Abstraction has 153 states and 204 transitions. [2024-11-05 02:28:45,494 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:28:45,494 INFO L276 IsEmpty]: Start isEmpty. Operand 153 states and 204 transitions. [2024-11-05 02:28:45,495 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2024-11-05 02:28:45,495 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:28:45,495 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:28:45,499 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:28:45,695 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:28:45,696 INFO L396 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:28:45,696 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:28:45,696 INFO L85 PathProgramCache]: Analyzing trace with hash -868887785, now seen corresponding path program 1 times [2024-11-05 02:28:45,696 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:28:45,696 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [1505492474] [2024-11-05 02:28:45,696 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:28:45,696 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:28:45,697 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:28:45,697 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:28:45,698 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:28:45,914 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:28:45,921 INFO L255 TraceCheckSpWp]: Trace formula consists of 252 conjuncts, 91 conjuncts are in the unsatisfiable core [2024-11-05 02:28:45,927 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:28:45,931 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:28:45,995 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:28:46,004 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:28:46,015 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:28:46,083 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-05 02:28:46,083 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:28:46,096 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:28:47,487 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:28:47,487 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-05 02:28:48,407 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 1490 treesize of output 1474 [2024-11-05 02:28:48,598 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:28:48,598 INFO L136 FreeRefinementEngine]: Strategy FIXED_PREFERENCES found an infeasible trace [2024-11-05 02:28:48,598 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModulePreferences [1505492474] [2024-11-05 02:28:48,598 INFO L158 FreeRefinementEngine]: IpTcStrategyModulePreferences [1505492474] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-05 02:28:48,599 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-05 02:28:48,599 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 25 [2024-11-05 02:28:48,599 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [11908975] [2024-11-05 02:28:48,599 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-05 02:28:48,599 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2024-11-05 02:28:48,599 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FIXED_PREFERENCES [2024-11-05 02:28:48,600 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2024-11-05 02:28:48,600 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=87, Invalid=513, Unknown=0, NotChecked=0, Total=600 [2024-11-05 02:28:48,600 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:28:52,753 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-05 02:28:52,753 INFO L93 Difference]: Finished difference Result 253 states and 347 transitions. [2024-11-05 02:28:52,754 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2024-11-05 02:28:52,754 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:28:52,754 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-05 02:28:52,756 INFO L225 Difference]: With dead ends: 253 [2024-11-05 02:28:52,756 INFO L226 Difference]: Without dead ends: 186 [2024-11-05 02:28:52,757 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:28:52,758 INFO L432 NwaCegarLoop]: 92 mSDtfsCounter, 129 mSDsluCounter, 1102 mSDsCounter, 0 mSdLazyCounter, 855 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 3.4s 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.6s IncrementalHoareTripleChecker+Time [2024-11-05 02:28:52,758 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.6s Time] [2024-11-05 02:28:52,759 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 186 states. [2024-11-05 02:28:52,830 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 186 to 156. [2024-11-05 02:28:52,831 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:28:52,832 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 156 states to 156 states and 210 transitions. [2024-11-05 02:28:52,832 INFO L78 Accepts]: Start accepts. Automaton has 156 states and 210 transitions. Word has length 89 [2024-11-05 02:28:52,832 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-05 02:28:52,832 INFO L471 AbstractCegarLoop]: Abstraction has 156 states and 210 transitions. [2024-11-05 02:28:52,832 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:28:52,833 INFO L276 IsEmpty]: Start isEmpty. Operand 156 states and 210 transitions. [2024-11-05 02:28:52,833 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 90 [2024-11-05 02:28:52,833 INFO L207 NwaCegarLoop]: Found error trace [2024-11-05 02:28:52,834 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:28:52,836 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 --incremental --print-success --lang smt (14)] Forceful destruction successful, exit code 0 [2024-11-05 02:28:53,034 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:28:53,034 INFO L396 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-05 02:28:53,035 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-05 02:28:53,035 INFO L85 PathProgramCache]: Analyzing trace with hash -1161650708, now seen corresponding path program 1 times [2024-11-05 02:28:53,035 INFO L118 FreeRefinementEngine]: Executing refinement strategy FIXED_PREFERENCES [2024-11-05 02:28:53,035 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModulePreferences [450675946] [2024-11-05 02:28:53,035 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-05 02:28:53,035 INFO L173 SolverBuilder]: Constructing external solver with command: cvc5 --incremental --print-success --lang smt [2024-11-05 02:28:53,035 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc5 [2024-11-05 02:28:53,036 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:28:53,038 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:28:53,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-05 02:28:53,288 WARN L253 TraceCheckSpWp]: Trace formula consists of 274 conjuncts, 162 conjuncts are in the unsatisfiable core [2024-11-05 02:28:53,299 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-05 02:28:53,308 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:28:53,319 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:28:53,328 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:28:53,457 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:28:53,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:28:53,497 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:28:53,599 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-05 02:28:53,599 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:28:53,621 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2024-11-05 02:28:53,622 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:28:53,645 INFO L349 Elim1Store]: treesize reduction 13, result has 45.8 percent of original size [2024-11-05 02:28:53,646 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:28:53,938 INFO L349 Elim1Store]: treesize reduction 25, result has 21.9 percent of original size [2024-11-05 02:28:53,938 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:28:53,974 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-11-05 02:28:53,974 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