./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/recursified_nla-digbench/recursified_egcd3-ll.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 8be7027f Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/recursified_nla-digbench/recursified_egcd3-ll.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 31cf2fabf53e081c3004f39943d7e98ce7bd9dc5e02db94d5bcffe73b0927449 --- Real Ultimate output --- This is Ultimate 0.2.5-wip.dk.perfect-tracechecks-8be7027-m [2024-11-11 21:03:30,403 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-11 21:03:30,461 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2024-11-11 21:03:30,474 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-11 21:03:30,476 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-11 21:03:30,490 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-11 21:03:30,490 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-11 21:03:30,491 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-11 21:03:30,491 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-11 21:03:30,491 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-11 21:03:30,491 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-11 21:03:30,492 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-11 21:03:30,492 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-11 21:03:30,492 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-11 21:03:30,493 INFO L153 SettingsManager]: * Use SBE=true [2024-11-11 21:03:30,494 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-11 21:03:30,494 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-11 21:03:30,494 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-11 21:03:30,494 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-11 21:03:30,496 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-11 21:03:30,496 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-11 21:03:30,498 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-11 21:03:30,498 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-11 21:03:30,498 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-11 21:03:30,499 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-11 21:03:30,499 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-11 21:03:30,499 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-11 21:03:30,499 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-11 21:03:30,499 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-11 21:03:30,499 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-11 21:03:30,499 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-11 21:03:30,499 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-11 21:03:30,500 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-11 21:03:30,500 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-11 21:03:30,500 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-11 21:03:30,500 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-11 21:03:30,500 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-11 21:03:30,500 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-11 21:03:30,500 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-11 21:03:30,500 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2024-11-11 21:03:30,501 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2024-11-11 21:03:30,502 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-11 21:03:30,502 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.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 31cf2fabf53e081c3004f39943d7e98ce7bd9dc5e02db94d5bcffe73b0927449 [2024-11-11 21:03:30,708 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-11 21:03:30,730 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-11 21:03:30,733 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-11 21:03:30,734 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-11 21:03:30,734 INFO L274 PluginConnector]: CDTParser initialized [2024-11-11 21:03:30,735 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_nla-digbench/recursified_egcd3-ll.c [2024-11-11 21:03:31,948 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-11 21:03:32,111 INFO L384 CDTParser]: Found 1 translation units. [2024-11-11 21:03:32,111 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_egcd3-ll.c [2024-11-11 21:03:32,122 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/69b0eee2b/58551c68454d40cb9b77c3d10823b929/FLAG9970e2c9f [2024-11-11 21:03:32,537 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/69b0eee2b/58551c68454d40cb9b77c3d10823b929 [2024-11-11 21:03:32,539 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-11 21:03:32,541 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-11 21:03:32,543 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-11 21:03:32,543 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-11 21:03:32,547 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-11 21:03:32,548 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,550 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@371195b0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32, skipping insertion in model container [2024-11-11 21:03:32,550 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,572 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-11 21:03:32,706 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_egcd3-ll.c[1052,1065] [2024-11-11 21:03:32,727 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-11 21:03:32,736 INFO L200 MainTranslator]: Completed pre-run [2024-11-11 21:03:32,744 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_nla-digbench/recursified_egcd3-ll.c[1052,1065] [2024-11-11 21:03:32,761 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-11 21:03:32,774 INFO L204 MainTranslator]: Completed translation [2024-11-11 21:03:32,774 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32 WrapperNode [2024-11-11 21:03:32,774 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-11 21:03:32,775 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-11 21:03:32,775 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-11 21:03:32,775 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-11 21:03:32,780 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,788 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,804 INFO L138 Inliner]: procedures = 18, calls = 127, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 95 [2024-11-11 21:03:32,805 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-11 21:03:32,807 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-11 21:03:32,807 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-11 21:03:32,807 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-11 21:03:32,815 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,815 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,818 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,835 INFO L175 MemorySlicer]: Split 77 memory accesses to 13 slices as follows [2, 6, 9, 6, 6, 5, 6, 6, 5, 7, 5, 7, 7]. 12 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]. The 22 writes are split as follows [0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1]. [2024-11-11 21:03:32,836 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,837 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,848 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,850 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,855 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,857 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,860 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-11 21:03:32,861 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-11 21:03:32,861 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-11 21:03:32,861 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-11 21:03:32,862 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (1/1) ... [2024-11-11 21:03:32,868 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2024-11-11 21:03:32,875 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 21:03:32,886 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-11 21:03:32,888 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-11 21:03:32,920 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-11 21:03:32,920 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2024-11-11 21:03:32,920 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2024-11-11 21:03:32,920 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-11 21:03:32,920 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-11 21:03:32,920 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-11-11 21:03:32,921 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-11-11 21:03:32,921 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-11-11 21:03:32,921 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2024-11-11 21:03:32,921 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2024-11-11 21:03:32,921 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#7 [2024-11-11 21:03:32,921 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#8 [2024-11-11 21:03:32,921 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#9 [2024-11-11 21:03:32,921 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#10 [2024-11-11 21:03:32,922 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#11 [2024-11-11 21:03:32,922 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#12 [2024-11-11 21:03:32,922 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_47_to_56_0 [2024-11-11 21:03:32,922 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_47_to_56_0 [2024-11-11 21:03:32,922 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_33_to_70_0 [2024-11-11 21:03:32,922 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_33_to_70_0 [2024-11-11 21:03:32,922 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-11 21:03:32,922 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_40_to_59_0 [2024-11-11 21:03:32,923 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_40_to_59_0 [2024-11-11 21:03:32,923 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-11 21:03:32,923 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-11 21:03:32,923 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-11-11 21:03:32,923 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-11-11 21:03:32,923 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-11-11 21:03:32,923 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2024-11-11 21:03:32,923 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2024-11-11 21:03:32,923 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#7 [2024-11-11 21:03:32,923 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#8 [2024-11-11 21:03:32,923 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#9 [2024-11-11 21:03:32,924 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#10 [2024-11-11 21:03:32,924 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#11 [2024-11-11 21:03:32,924 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#12 [2024-11-11 21:03:32,924 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-11 21:03:32,924 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-11 21:03:32,924 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-11 21:03:32,924 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-11 21:03:32,924 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-11-11 21:03:32,924 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-11-11 21:03:32,924 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-11-11 21:03:32,924 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2024-11-11 21:03:32,924 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2024-11-11 21:03:32,925 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#7 [2024-11-11 21:03:32,925 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#8 [2024-11-11 21:03:32,925 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#9 [2024-11-11 21:03:32,925 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#10 [2024-11-11 21:03:32,925 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#11 [2024-11-11 21:03:32,925 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#12 [2024-11-11 21:03:32,925 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2024-11-11 21:03:32,925 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2024-11-11 21:03:32,925 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-11 21:03:33,045 INFO L238 CfgBuilder]: Building ICFG [2024-11-11 21:03:33,047 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-11 21:03:33,347 INFO L? ?]: Removed 12 outVars from TransFormulas that were not future-live. [2024-11-11 21:03:33,347 INFO L287 CfgBuilder]: Performing block encoding [2024-11-11 21:03:33,360 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-11 21:03:33,361 INFO L316 CfgBuilder]: Removed 3 assume(true) statements. [2024-11-11 21:03:33,361 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.11 09:03:33 BoogieIcfgContainer [2024-11-11 21:03:33,362 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-11 21:03:33,363 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-11 21:03:33,363 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-11 21:03:33,367 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-11 21:03:33,367 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 11.11 09:03:32" (1/3) ... [2024-11-11 21:03:33,368 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@10860445 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.11 09:03:33, skipping insertion in model container [2024-11-11 21:03:33,368 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 11.11 09:03:32" (2/3) ... [2024-11-11 21:03:33,368 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@10860445 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 11.11 09:03:33, skipping insertion in model container [2024-11-11 21:03:33,368 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 11.11 09:03:33" (3/3) ... [2024-11-11 21:03:33,369 INFO L112 eAbstractionObserver]: Analyzing ICFG recursified_egcd3-ll.c [2024-11-11 21:03:33,382 INFO L214 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-11 21:03:33,382 INFO L154 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2024-11-11 21:03:33,429 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-11 21:03:33,437 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;@2a848cbb, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-11 21:03:33,437 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2024-11-11 21:03:33,441 INFO L276 IsEmpty]: Start isEmpty. Operand has 53 states, 33 states have (on average 1.2727272727272727) internal successors, (42), 37 states have internal predecessors, (42), 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-11 21:03:33,447 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2024-11-11 21:03:33,447 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 21:03:33,448 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 21:03:33,448 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 21:03:33,454 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 21:03:33,454 INFO L85 PathProgramCache]: Analyzing trace with hash -909827079, now seen corresponding path program 1 times [2024-11-11 21:03:33,462 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 21:03:33,462 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1271007062] [2024-11-11 21:03:33,462 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:03:33,463 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 21:03:33,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:33,655 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 21:03:33,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:33,667 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-11 21:03:33,668 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:33,712 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-11 21:03:33,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:33,731 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-11 21:03:33,731 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 21:03:33,732 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1271007062] [2024-11-11 21:03:33,732 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1271007062] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 21:03:33,732 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 21:03:33,733 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2024-11-11 21:03:33,734 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1464228164] [2024-11-11 21:03:33,734 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 21:03:33,737 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2024-11-11 21:03:33,737 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 21:03:33,755 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2024-11-11 21:03:33,756 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-11 21:03:33,757 INFO L87 Difference]: Start difference. First operand has 53 states, 33 states have (on average 1.2727272727272727) internal successors, (42), 37 states have internal predecessors, (42), 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 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-11 21:03:33,933 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 21:03:33,933 INFO L93 Difference]: Finished difference Result 109 states and 154 transitions. [2024-11-11 21:03:33,935 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2024-11-11 21:03:33,936 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2024-11-11 21:03:33,937 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 21:03:33,945 INFO L225 Difference]: With dead ends: 109 [2024-11-11 21:03:33,945 INFO L226 Difference]: Without dead ends: 55 [2024-11-11 21:03:33,948 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2024-11-11 21:03:33,952 INFO L435 NwaCegarLoop]: 31 mSDtfsCounter, 24 mSDsluCounter, 4 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 35 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-11 21:03:33,953 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [28 Valid, 35 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-11 21:03:33,968 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2024-11-11 21:03:33,989 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 49. [2024-11-11 21:03:33,990 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 49 states, 30 states have (on average 1.1333333333333333) internal successors, (34), 34 states have internal predecessors, (34), 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-11 21:03:33,994 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 49 states to 49 states and 59 transitions. [2024-11-11 21:03:33,995 INFO L78 Accepts]: Start accepts. Automaton has 49 states and 59 transitions. Word has length 24 [2024-11-11 21:03:33,996 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 21:03:33,996 INFO L471 AbstractCegarLoop]: Abstraction has 49 states and 59 transitions. [2024-11-11 21:03:33,996 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-11 21:03:33,996 INFO L276 IsEmpty]: Start isEmpty. Operand 49 states and 59 transitions. [2024-11-11 21:03:33,999 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2024-11-11 21:03:34,000 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 21:03:34,000 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 21:03:34,000 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-11 21:03:34,001 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 21:03:34,001 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 21:03:34,002 INFO L85 PathProgramCache]: Analyzing trace with hash 665195867, now seen corresponding path program 1 times [2024-11-11 21:03:34,002 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 21:03:34,002 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [874396379] [2024-11-11 21:03:34,002 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:03:34,003 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 21:03:34,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:34,362 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 21:03:34,363 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:34,365 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-11 21:03:34,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:34,426 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-11 21:03:34,429 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:34,501 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-11 21:03:34,501 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 21:03:34,501 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [874396379] [2024-11-11 21:03:34,502 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [874396379] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 21:03:34,502 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 21:03:34,502 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [11] imperfect sequences [] total 11 [2024-11-11 21:03:34,502 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1695735996] [2024-11-11 21:03:34,502 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 21:03:34,503 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2024-11-11 21:03:34,503 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 21:03:34,504 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2024-11-11 21:03:34,504 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=91, Unknown=0, NotChecked=0, Total=110 [2024-11-11 21:03:34,505 INFO L87 Difference]: Start difference. First operand 49 states and 59 transitions. Second operand has 11 states, 9 states have (on average 2.0) internal successors, (18), 9 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-11 21:03:35,069 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 21:03:35,070 INFO L93 Difference]: Finished difference Result 63 states and 75 transitions. [2024-11-11 21:03:35,070 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-11 21:03:35,070 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.0) internal successors, (18), 9 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Word has length 25 [2024-11-11 21:03:35,070 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 21:03:35,072 INFO L225 Difference]: With dead ends: 63 [2024-11-11 21:03:35,073 INFO L226 Difference]: Without dead ends: 55 [2024-11-11 21:03:35,073 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 21 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=51, Invalid=255, Unknown=0, NotChecked=0, Total=306 [2024-11-11 21:03:35,075 INFO L435 NwaCegarLoop]: 19 mSDtfsCounter, 29 mSDsluCounter, 82 mSDsCounter, 0 mSdLazyCounter, 435 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 448 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 435 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-11 21:03:35,076 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 101 Invalid, 448 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 435 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-11 21:03:35,076 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 55 states. [2024-11-11 21:03:35,084 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 55 to 51. [2024-11-11 21:03:35,088 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 31 states have (on average 1.1290322580645162) internal successors, (35), 35 states have internal predecessors, (35), 13 states have call successors, (13), 5 states have call predecessors, (13), 6 states have return successors, (13), 12 states have call predecessors, (13), 12 states have call successors, (13) [2024-11-11 21:03:35,089 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 61 transitions. [2024-11-11 21:03:35,089 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 61 transitions. Word has length 25 [2024-11-11 21:03:35,089 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 21:03:35,089 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 61 transitions. [2024-11-11 21:03:35,090 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.0) internal successors, (18), 9 states have internal predecessors, (18), 4 states have call successors, (4), 3 states have call predecessors, (4), 3 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-11 21:03:35,090 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 61 transitions. [2024-11-11 21:03:35,090 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2024-11-11 21:03:35,090 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 21:03:35,090 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 21:03:35,090 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-11 21:03:35,091 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 21:03:35,091 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 21:03:35,091 INFO L85 PathProgramCache]: Analyzing trace with hash 977283434, now seen corresponding path program 1 times [2024-11-11 21:03:35,091 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 21:03:35,091 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [619501532] [2024-11-11 21:03:35,091 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:03:35,091 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 21:03:35,134 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 21:03:35,137 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1434769756] [2024-11-11 21:03:35,137 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:03:35,137 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:03:35,137 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 21:03:35,139 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 21:03:35,140 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-11 21:03:35,281 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:35,286 INFO L256 TraceCheckSpWp]: Trace formula consists of 528 conjuncts, 123 conjuncts are in the unsatisfiable core [2024-11-11 21:03:35,292 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 21:03:35,325 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:03:35,339 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:03:35,344 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:03:35,350 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:03:35,541 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-11 21:03:35,546 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-11-11 21:03:35,595 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-11 21:03:35,596 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-11 21:03:35,596 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 21:03:35,596 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [619501532] [2024-11-11 21:03:35,596 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 21:03:35,597 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1434769756] [2024-11-11 21:03:35,597 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1434769756] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 21:03:35,597 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 21:03:35,597 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2024-11-11 21:03:35,597 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1557953092] [2024-11-11 21:03:35,597 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 21:03:35,597 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-11 21:03:35,597 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 21:03:35,599 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-11 21:03:35,600 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=21, Invalid=111, Unknown=0, NotChecked=0, Total=132 [2024-11-11 21:03:35,600 INFO L87 Difference]: Start difference. First operand 51 states and 61 transitions. Second operand has 12 states, 10 states have (on average 1.8) internal successors, (18), 8 states have internal predecessors, (18), 5 states have call successors, (6), 5 states have call predecessors, (6), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-11 21:03:35,921 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 21:03:35,921 INFO L93 Difference]: Finished difference Result 86 states and 103 transitions. [2024-11-11 21:03:35,922 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2024-11-11 21:03:35,922 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 1.8) internal successors, (18), 8 states have internal predecessors, (18), 5 states have call successors, (6), 5 states have call predecessors, (6), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 29 [2024-11-11 21:03:35,922 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 21:03:35,923 INFO L225 Difference]: With dead ends: 86 [2024-11-11 21:03:35,924 INFO L226 Difference]: Without dead ends: 82 [2024-11-11 21:03:35,924 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 33 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=43, Invalid=229, Unknown=0, NotChecked=0, Total=272 [2024-11-11 21:03:35,925 INFO L435 NwaCegarLoop]: 44 mSDtfsCounter, 36 mSDsluCounter, 333 mSDsCounter, 0 mSdLazyCounter, 270 mSolverCounterSat, 19 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 377 SdHoareTripleChecker+Invalid, 289 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 270 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-11 21:03:35,926 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [36 Valid, 377 Invalid, 289 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 270 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-11 21:03:35,929 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2024-11-11 21:03:35,940 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 81. [2024-11-11 21:03:35,940 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 50 states have (on average 1.12) internal successors, (56), 56 states have internal predecessors, (56), 21 states have call successors, (21), 9 states have call predecessors, (21), 9 states have return successors, (21), 19 states have call predecessors, (21), 20 states have call successors, (21) [2024-11-11 21:03:35,941 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 98 transitions. [2024-11-11 21:03:35,941 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 98 transitions. Word has length 29 [2024-11-11 21:03:35,941 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 21:03:35,942 INFO L471 AbstractCegarLoop]: Abstraction has 81 states and 98 transitions. [2024-11-11 21:03:35,942 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 1.8) internal successors, (18), 8 states have internal predecessors, (18), 5 states have call successors, (6), 5 states have call predecessors, (6), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2024-11-11 21:03:35,942 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 98 transitions. [2024-11-11 21:03:35,943 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2024-11-11 21:03:35,943 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 21:03:35,943 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 21:03:35,959 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-11 21:03:36,147 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:03:36,148 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 21:03:36,148 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 21:03:36,148 INFO L85 PathProgramCache]: Analyzing trace with hash -227438513, now seen corresponding path program 1 times [2024-11-11 21:03:36,148 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 21:03:36,148 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [708483639] [2024-11-11 21:03:36,149 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:03:36,150 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 21:03:36,189 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 21:03:36,191 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1842313625] [2024-11-11 21:03:36,192 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:03:36,192 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:03:36,192 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 21:03:36,193 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 21:03:36,194 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-11 21:03:36,337 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:36,341 INFO L256 TraceCheckSpWp]: Trace formula consists of 547 conjuncts, 125 conjuncts are in the unsatisfiable core [2024-11-11 21:03:36,345 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 21:03:36,353 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:03:36,362 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:03:36,368 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:03:36,373 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:03:36,625 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-11 21:03:36,627 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-11-11 21:03:36,669 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-11 21:03:36,670 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 21:03:36,805 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 21:03:36,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [708483639] [2024-11-11 21:03:36,806 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 21:03:36,806 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1842313625] [2024-11-11 21:03:36,806 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1842313625] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 21:03:36,806 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-11 21:03:36,806 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13] total 13 [2024-11-11 21:03:36,806 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1385804707] [2024-11-11 21:03:36,806 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-11 21:03:36,807 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2024-11-11 21:03:36,807 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 21:03:36,807 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2024-11-11 21:03:36,807 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=174, Unknown=0, NotChecked=0, Total=210 [2024-11-11 21:03:36,807 INFO L87 Difference]: Start difference. First operand 81 states and 98 transitions. Second operand has 13 states, 11 states have (on average 2.0) internal successors, (22), 9 states have internal predecessors, (22), 6 states have call successors, (7), 6 states have call predecessors, (7), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-11 21:03:37,233 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 21:03:37,234 INFO L93 Difference]: Finished difference Result 94 states and 109 transitions. [2024-11-11 21:03:37,234 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-11 21:03:37,235 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 11 states have (on average 2.0) internal successors, (22), 9 states have internal predecessors, (22), 6 states have call successors, (7), 6 states have call predecessors, (7), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 35 [2024-11-11 21:03:37,235 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 21:03:37,236 INFO L225 Difference]: With dead ends: 94 [2024-11-11 21:03:37,237 INFO L226 Difference]: Without dead ends: 92 [2024-11-11 21:03:37,238 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 24 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=71, Invalid=349, Unknown=0, NotChecked=0, Total=420 [2024-11-11 21:03:37,238 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 33 mSDsluCounter, 340 mSDsCounter, 0 mSdLazyCounter, 318 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 33 SdHoareTripleChecker+Valid, 383 SdHoareTripleChecker+Invalid, 340 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 318 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-11 21:03:37,239 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [33 Valid, 383 Invalid, 340 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 318 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-11 21:03:37,239 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2024-11-11 21:03:37,252 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 89. [2024-11-11 21:03:37,252 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 89 states, 56 states have (on average 1.125) internal successors, (63), 62 states have internal predecessors, (63), 21 states have call successors, (21), 11 states have call predecessors, (21), 11 states have return successors, (21), 19 states have call predecessors, (21), 20 states have call successors, (21) [2024-11-11 21:03:37,253 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 105 transitions. [2024-11-11 21:03:37,254 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 105 transitions. Word has length 35 [2024-11-11 21:03:37,254 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 21:03:37,254 INFO L471 AbstractCegarLoop]: Abstraction has 89 states and 105 transitions. [2024-11-11 21:03:37,254 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 11 states have (on average 2.0) internal successors, (22), 9 states have internal predecessors, (22), 6 states have call successors, (7), 6 states have call predecessors, (7), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-11 21:03:37,254 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 105 transitions. [2024-11-11 21:03:37,255 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2024-11-11 21:03:37,255 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 21:03:37,255 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 21:03:37,269 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2024-11-11 21:03:37,459 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable3 [2024-11-11 21:03:37,460 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 21:03:37,460 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 21:03:37,460 INFO L85 PathProgramCache]: Analyzing trace with hash 524026268, now seen corresponding path program 1 times [2024-11-11 21:03:37,460 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 21:03:37,460 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1564761439] [2024-11-11 21:03:37,460 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:03:37,461 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 21:03:37,489 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:37,846 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 21:03:37,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:37,863 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-11 21:03:37,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:37,894 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-11 21:03:37,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:38,125 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2024-11-11 21:03:38,129 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:38,153 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2024-11-11 21:03:38,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:38,226 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-11 21:03:38,227 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 21:03:38,228 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1564761439] [2024-11-11 21:03:38,228 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1564761439] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 21:03:38,228 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1644753326] [2024-11-11 21:03:38,228 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:03:38,228 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:03:38,228 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 21:03:38,230 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 21:03:38,232 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-11 21:03:38,366 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:38,368 INFO L256 TraceCheckSpWp]: Trace formula consists of 533 conjuncts, 36 conjuncts are in the unsatisfiable core [2024-11-11 21:03:38,372 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 21:03:38,467 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 23 treesize of output 15 [2024-11-11 21:03:38,470 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:03:38,513 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:03:38,547 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 27 treesize of output 19 [2024-11-11 21:03:38,549 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:03:38,638 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-11 21:03:38,656 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 1 proven. 8 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 21:03:38,656 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 21:03:39,227 INFO L134 CoverageAnalysis]: Checked inductivity of 9 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-11 21:03:39,228 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1644753326] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 21:03:39,228 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 21:03:39,228 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 18, 17] total 40 [2024-11-11 21:03:39,228 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1840892198] [2024-11-11 21:03:39,228 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 21:03:39,228 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 40 states [2024-11-11 21:03:39,228 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 21:03:39,229 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2024-11-11 21:03:39,230 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=140, Invalid=1420, Unknown=0, NotChecked=0, Total=1560 [2024-11-11 21:03:39,230 INFO L87 Difference]: Start difference. First operand 89 states and 105 transitions. Second operand has 40 states, 32 states have (on average 1.8125) internal successors, (58), 34 states have internal predecessors, (58), 14 states have call successors, (16), 11 states have call predecessors, (16), 11 states have return successors, (14), 8 states have call predecessors, (14), 13 states have call successors, (14) [2024-11-11 21:03:43,243 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 21:03:44,316 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 21:03:44,316 INFO L93 Difference]: Finished difference Result 113 states and 135 transitions. [2024-11-11 21:03:44,316 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2024-11-11 21:03:44,317 INFO L78 Accepts]: Start accepts. Automaton has has 40 states, 32 states have (on average 1.8125) internal successors, (58), 34 states have internal predecessors, (58), 14 states have call successors, (16), 11 states have call predecessors, (16), 11 states have return successors, (14), 8 states have call predecessors, (14), 13 states have call successors, (14) Word has length 38 [2024-11-11 21:03:44,317 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 21:03:44,318 INFO L225 Difference]: With dead ends: 113 [2024-11-11 21:03:44,318 INFO L226 Difference]: Without dead ends: 105 [2024-11-11 21:03:44,319 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 114 GetRequests, 55 SyntacticMatches, 4 SemanticMatches, 55 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 527 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=364, Invalid=2828, Unknown=0, NotChecked=0, Total=3192 [2024-11-11 21:03:44,319 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 185 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 1023 mSolverCounterSat, 146 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 186 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 1170 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 146 IncrementalHoareTripleChecker+Valid, 1023 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.6s IncrementalHoareTripleChecker+Time [2024-11-11 21:03:44,319 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [186 Valid, 112 Invalid, 1170 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [146 Valid, 1023 Invalid, 1 Unknown, 0 Unchecked, 4.6s Time] [2024-11-11 21:03:44,320 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 105 states. [2024-11-11 21:03:44,332 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 105 to 101. [2024-11-11 21:03:44,332 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 63 states have (on average 1.1111111111111112) internal successors, (70), 69 states have internal predecessors, (70), 22 states have call successors, (22), 12 states have call predecessors, (22), 15 states have return successors, (29), 21 states have call predecessors, (29), 21 states have call successors, (29) [2024-11-11 21:03:44,333 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 121 transitions. [2024-11-11 21:03:44,333 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 121 transitions. Word has length 38 [2024-11-11 21:03:44,333 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 21:03:44,333 INFO L471 AbstractCegarLoop]: Abstraction has 101 states and 121 transitions. [2024-11-11 21:03:44,334 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 40 states, 32 states have (on average 1.8125) internal successors, (58), 34 states have internal predecessors, (58), 14 states have call successors, (16), 11 states have call predecessors, (16), 11 states have return successors, (14), 8 states have call predecessors, (14), 13 states have call successors, (14) [2024-11-11 21:03:44,334 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 121 transitions. [2024-11-11 21:03:44,337 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2024-11-11 21:03:44,337 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 21:03:44,337 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 21:03:44,351 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-11 21:03:44,538 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:03:44,538 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 21:03:44,539 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 21:03:44,539 INFO L85 PathProgramCache]: Analyzing trace with hash -349777783, now seen corresponding path program 1 times [2024-11-11 21:03:44,539 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 21:03:44,539 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1169914965] [2024-11-11 21:03:44,539 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:03:44,539 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 21:03:44,579 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 21:03:44,581 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [330910703] [2024-11-11 21:03:44,581 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:03:44,581 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:03:44,582 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 21:03:44,583 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 21:03:44,584 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-11 21:03:44,785 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:03:44,790 INFO L256 TraceCheckSpWp]: Trace formula consists of 777 conjuncts, 276 conjuncts are in the unsatisfiable core [2024-11-11 21:03:44,797 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 21:03:44,804 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:03:44,807 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:03:44,849 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:03:44,852 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:03:44,856 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:03:44,861 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:03:44,955 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:03:44,978 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:03:45,292 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 40 treesize of output 28 [2024-11-11 21:03:45,331 INFO L349 Elim1Store]: treesize reduction 20, result has 58.3 percent of original size [2024-11-11 21:03:45,332 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 66 treesize of output 73 [2024-11-11 21:03:45,359 INFO L349 Elim1Store]: treesize reduction 20, result has 58.3 percent of original size [2024-11-11 21:03:45,359 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 62 treesize of output 69 [2024-11-11 21:03:45,428 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:03:45,436 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:03:45,867 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 21:03:45,867 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 86 treesize of output 138 [2024-11-11 21:03:46,653 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 21:03:46,653 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 86 treesize of output 122 [2024-11-11 21:03:46,673 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 21:03:46,673 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 62 treesize of output 78 [2024-11-11 21:03:46,678 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-11-11 21:03:46,817 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 1 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 21:03:46,817 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 21:03:52,617 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 21:03:52,618 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1169914965] [2024-11-11 21:03:52,618 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 21:03:52,618 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [330910703] [2024-11-11 21:03:52,618 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [330910703] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 21:03:52,618 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-11 21:03:52,618 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27] total 27 [2024-11-11 21:03:52,618 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [731719086] [2024-11-11 21:03:52,618 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-11 21:03:52,618 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-11 21:03:52,619 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 21:03:52,619 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-11 21:03:52,620 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=124, Invalid=1281, Unknown=1, NotChecked=0, Total=1406 [2024-11-11 21:03:52,620 INFO L87 Difference]: Start difference. First operand 101 states and 121 transitions. Second operand has 27 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 20 states have internal predecessors, (29), 8 states have call successors, (8), 8 states have call predecessors, (8), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-11 21:03:56,639 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 21:04:00,495 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 21:04:00,496 INFO L93 Difference]: Finished difference Result 179 states and 212 transitions. [2024-11-11 21:04:00,496 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 31 states. [2024-11-11 21:04:00,496 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 20 states have internal predecessors, (29), 8 states have call successors, (8), 8 states have call predecessors, (8), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Word has length 40 [2024-11-11 21:04:00,496 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 21:04:00,498 INFO L225 Difference]: With dead ends: 179 [2024-11-11 21:04:00,498 INFO L226 Difference]: Without dead ends: 173 [2024-11-11 21:04:00,498 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 17 SyntacticMatches, 3 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 657 ImplicationChecksByTransitivity, 8.3s TimeCoverageRelationStatistics Valid=247, Invalid=2722, Unknown=1, NotChecked=0, Total=2970 [2024-11-11 21:04:00,499 INFO L435 NwaCegarLoop]: 40 mSDtfsCounter, 134 mSDsluCounter, 360 mSDsCounter, 0 mSdLazyCounter, 1528 mSolverCounterSat, 41 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 141 SdHoareTripleChecker+Valid, 400 SdHoareTripleChecker+Invalid, 1570 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 41 IncrementalHoareTripleChecker+Valid, 1528 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.8s IncrementalHoareTripleChecker+Time [2024-11-11 21:04:00,499 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [141 Valid, 400 Invalid, 1570 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [41 Valid, 1528 Invalid, 1 Unknown, 0 Unchecked, 5.8s Time] [2024-11-11 21:04:00,500 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2024-11-11 21:04:00,524 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 140. [2024-11-11 21:04:00,524 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 140 states, 88 states have (on average 1.1136363636363635) internal successors, (98), 96 states have internal predecessors, (98), 31 states have call successors, (31), 17 states have call predecessors, (31), 20 states have return successors, (41), 29 states have call predecessors, (41), 30 states have call successors, (41) [2024-11-11 21:04:00,525 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 170 transitions. [2024-11-11 21:04:00,526 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 170 transitions. Word has length 40 [2024-11-11 21:04:00,526 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 21:04:00,526 INFO L471 AbstractCegarLoop]: Abstraction has 140 states and 170 transitions. [2024-11-11 21:04:00,526 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 20 states have internal predecessors, (29), 8 states have call successors, (8), 8 states have call predecessors, (8), 3 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-11 21:04:00,526 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 170 transitions. [2024-11-11 21:04:00,527 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2024-11-11 21:04:00,527 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 21:04:00,527 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 21:04:00,541 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-11 21:04:00,730 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:04:00,730 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 21:04:00,730 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 21:04:00,730 INFO L85 PathProgramCache]: Analyzing trace with hash 318259314, now seen corresponding path program 1 times [2024-11-11 21:04:00,731 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 21:04:00,731 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1456699878] [2024-11-11 21:04:00,731 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:04:00,731 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 21:04:00,761 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 21:04:00,763 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1036690543] [2024-11-11 21:04:00,763 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:04:00,763 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:04:00,763 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 21:04:00,766 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 21:04:00,766 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2024-11-11 21:04:00,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:00,915 INFO L256 TraceCheckSpWp]: Trace formula consists of 564 conjuncts, 77 conjuncts are in the unsatisfiable core [2024-11-11 21:04:00,918 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 21:04:00,921 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:00,922 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:04:00,925 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:00,928 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:01,040 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-11 21:04:01,042 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-11-11 21:04:01,070 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-11 21:04:01,070 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 21:04:01,145 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-11 21:04:01,145 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 21:04:01,145 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1456699878] [2024-11-11 21:04:01,145 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 21:04:01,145 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1036690543] [2024-11-11 21:04:01,145 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1036690543] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-11 21:04:01,145 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-11 21:04:01,145 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [10] imperfect sequences [11] total 11 [2024-11-11 21:04:01,146 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1651464401] [2024-11-11 21:04:01,146 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 21:04:01,146 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2024-11-11 21:04:01,146 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 21:04:01,146 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2024-11-11 21:04:01,146 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2024-11-11 21:04:01,147 INFO L87 Difference]: Start difference. First operand 140 states and 170 transitions. Second operand has 10 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (8), 4 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-11 21:04:01,340 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 21:04:01,340 INFO L93 Difference]: Finished difference Result 208 states and 255 transitions. [2024-11-11 21:04:01,340 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2024-11-11 21:04:01,340 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (8), 4 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 41 [2024-11-11 21:04:01,340 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 21:04:01,342 INFO L225 Difference]: With dead ends: 208 [2024-11-11 21:04:01,342 INFO L226 Difference]: Without dead ends: 206 [2024-11-11 21:04:01,342 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 65 SyntacticMatches, 6 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2024-11-11 21:04:01,343 INFO L435 NwaCegarLoop]: 48 mSDtfsCounter, 25 mSDsluCounter, 316 mSDsCounter, 0 mSdLazyCounter, 188 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 25 SdHoareTripleChecker+Valid, 364 SdHoareTripleChecker+Invalid, 201 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 188 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-11 21:04:01,343 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [25 Valid, 364 Invalid, 201 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 188 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-11 21:04:01,344 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 206 states. [2024-11-11 21:04:01,410 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 206 to 203. [2024-11-11 21:04:01,411 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 203 states, 126 states have (on average 1.119047619047619) internal successors, (141), 140 states have internal predecessors, (141), 49 states have call successors, (49), 24 states have call predecessors, (49), 27 states have return successors, (59), 44 states have call predecessors, (59), 48 states have call successors, (59) [2024-11-11 21:04:01,414 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 203 states to 203 states and 249 transitions. [2024-11-11 21:04:01,415 INFO L78 Accepts]: Start accepts. Automaton has 203 states and 249 transitions. Word has length 41 [2024-11-11 21:04:01,415 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 21:04:01,416 INFO L471 AbstractCegarLoop]: Abstraction has 203 states and 249 transitions. [2024-11-11 21:04:01,416 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 2.875) internal successors, (23), 7 states have internal predecessors, (23), 5 states have call successors, (8), 4 states have call predecessors, (8), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2024-11-11 21:04:01,416 INFO L276 IsEmpty]: Start isEmpty. Operand 203 states and 249 transitions. [2024-11-11 21:04:01,417 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2024-11-11 21:04:01,419 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 21:04:01,419 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 21:04:01,433 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2024-11-11 21:04:01,619 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:04:01,620 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 21:04:01,620 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 21:04:01,621 INFO L85 PathProgramCache]: Analyzing trace with hash 2002789422, now seen corresponding path program 1 times [2024-11-11 21:04:01,621 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 21:04:01,621 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1511816976] [2024-11-11 21:04:01,621 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:04:01,621 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 21:04:01,652 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 21:04:01,654 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [533945611] [2024-11-11 21:04:01,654 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:04:01,654 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:04:01,654 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 21:04:01,655 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 21:04:01,656 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2024-11-11 21:04:01,858 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:01,864 INFO L256 TraceCheckSpWp]: Trace formula consists of 796 conjuncts, 272 conjuncts are in the unsatisfiable core [2024-11-11 21:04:01,871 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 21:04:01,877 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:04:01,881 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:04:01,924 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:01,928 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:01,932 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:01,937 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:01,942 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:02,047 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 27 treesize of output 19 [2024-11-11 21:04:02,051 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:02,061 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:02,097 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:02,432 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:02,438 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 40 treesize of output 28 [2024-11-11 21:04:02,459 INFO L349 Elim1Store]: treesize reduction 20, result has 58.3 percent of original size [2024-11-11 21:04:02,459 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 51 treesize of output 62 [2024-11-11 21:04:02,498 INFO L349 Elim1Store]: treesize reduction 29, result has 34.1 percent of original size [2024-11-11 21:04:02,498 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 26 treesize of output 29 [2024-11-11 21:04:04,176 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 21:04:04,177 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 86 treesize of output 138 [2024-11-11 21:04:04,228 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 21:04:04,229 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 76 treesize of output 160 [2024-11-11 21:04:04,246 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-11 21:04:04,246 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 86 treesize of output 66 [2024-11-11 21:04:04,413 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 1 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-11 21:04:04,413 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 21:04:04,590 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 21:04:04,590 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1511816976] [2024-11-11 21:04:04,590 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 21:04:04,590 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [533945611] [2024-11-11 21:04:04,590 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [533945611] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 21:04:04,590 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2024-11-11 21:04:04,590 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27] total 27 [2024-11-11 21:04:04,590 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [321785768] [2024-11-11 21:04:04,590 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2024-11-11 21:04:04,591 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-11 21:04:04,591 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 21:04:04,591 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-11 21:04:04,592 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=88, Invalid=724, Unknown=0, NotChecked=0, Total=812 [2024-11-11 21:04:04,592 INFO L87 Difference]: Start difference. First operand 203 states and 249 transitions. Second operand has 27 states, 23 states have (on average 1.434782608695652) internal successors, (33), 20 states have internal predecessors, (33), 8 states have call successors, (9), 9 states have call predecessors, (9), 4 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-11 21:04:08,617 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 21:04:12,659 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 21:04:12,659 INFO L93 Difference]: Finished difference Result 237 states and 277 transitions. [2024-11-11 21:04:12,660 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2024-11-11 21:04:12,660 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 23 states have (on average 1.434782608695652) internal successors, (33), 20 states have internal predecessors, (33), 8 states have call successors, (9), 9 states have call predecessors, (9), 4 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) Word has length 46 [2024-11-11 21:04:12,660 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 21:04:12,662 INFO L225 Difference]: With dead ends: 237 [2024-11-11 21:04:12,662 INFO L226 Difference]: Without dead ends: 235 [2024-11-11 21:04:12,662 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 68 GetRequests, 20 SyntacticMatches, 4 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 436 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=196, Invalid=1874, Unknown=0, NotChecked=0, Total=2070 [2024-11-11 21:04:12,663 INFO L435 NwaCegarLoop]: 42 mSDtfsCounter, 114 mSDsluCounter, 443 mSDsCounter, 0 mSdLazyCounter, 1600 mSolverCounterSat, 32 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.7s Time, 0 mProtectedPredicate, 0 mProtectedAction, 121 SdHoareTripleChecker+Valid, 485 SdHoareTripleChecker+Invalid, 1633 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 32 IncrementalHoareTripleChecker+Valid, 1600 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.8s IncrementalHoareTripleChecker+Time [2024-11-11 21:04:12,663 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [121 Valid, 485 Invalid, 1633 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [32 Valid, 1600 Invalid, 1 Unknown, 0 Unchecked, 5.8s Time] [2024-11-11 21:04:12,664 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2024-11-11 21:04:12,718 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 227. [2024-11-11 21:04:12,718 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 227 states, 144 states have (on average 1.1180555555555556) internal successors, (161), 158 states have internal predecessors, (161), 49 states have call successors, (49), 30 states have call predecessors, (49), 33 states have return successors, (59), 44 states have call predecessors, (59), 48 states have call successors, (59) [2024-11-11 21:04:12,719 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 227 states to 227 states and 269 transitions. [2024-11-11 21:04:12,720 INFO L78 Accepts]: Start accepts. Automaton has 227 states and 269 transitions. Word has length 46 [2024-11-11 21:04:12,720 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 21:04:12,720 INFO L471 AbstractCegarLoop]: Abstraction has 227 states and 269 transitions. [2024-11-11 21:04:12,720 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 23 states have (on average 1.434782608695652) internal successors, (33), 20 states have internal predecessors, (33), 8 states have call successors, (9), 9 states have call predecessors, (9), 4 states have return successors, (4), 3 states have call predecessors, (4), 4 states have call successors, (4) [2024-11-11 21:04:12,720 INFO L276 IsEmpty]: Start isEmpty. Operand 227 states and 269 transitions. [2024-11-11 21:04:12,721 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-11 21:04:12,721 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 21:04:12,721 INFO L218 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 21:04:12,737 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2024-11-11 21:04:12,922 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:04:12,922 INFO L396 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 21:04:12,922 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 21:04:12,922 INFO L85 PathProgramCache]: Analyzing trace with hash -1094986925, now seen corresponding path program 1 times [2024-11-11 21:04:12,922 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 21:04:12,923 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [50698017] [2024-11-11 21:04:12,923 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:04:12,923 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 21:04:12,955 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 21:04:12,957 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1533322628] [2024-11-11 21:04:12,957 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:04:12,957 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:04:12,957 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 21:04:12,959 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 21:04:12,960 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2024-11-11 21:04:13,125 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:13,128 INFO L256 TraceCheckSpWp]: Trace formula consists of 579 conjuncts, 67 conjuncts are in the unsatisfiable core [2024-11-11 21:04:13,130 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 21:04:13,133 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:04:13,136 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:13,138 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:04:13,150 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:13,153 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:13,267 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-11 21:04:13,270 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 7 [2024-11-11 21:04:13,292 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-11 21:04:13,292 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 21:04:13,372 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2024-11-11 21:04:13,372 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 21:04:13,372 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [50698017] [2024-11-11 21:04:13,372 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2024-11-11 21:04:13,372 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1533322628] [2024-11-11 21:04:13,372 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1533322628] provided 1 perfect and 1 imperfect interpolant sequences [2024-11-11 21:04:13,372 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-11 21:04:13,372 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [9] total 13 [2024-11-11 21:04:13,372 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1149740973] [2024-11-11 21:04:13,372 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 21:04:13,372 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-11 21:04:13,373 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 21:04:13,373 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-11 21:04:13,373 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=126, Unknown=0, NotChecked=0, Total=156 [2024-11-11 21:04:13,373 INFO L87 Difference]: Start difference. First operand 227 states and 269 transitions. Second operand has 8 states, 6 states have (on average 4.0) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (9), 3 states have call predecessors, (9), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-11 21:04:13,590 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 21:04:13,590 INFO L93 Difference]: Finished difference Result 268 states and 321 transitions. [2024-11-11 21:04:13,590 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-11 21:04:13,591 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 4.0) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (9), 3 states have call predecessors, (9), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 47 [2024-11-11 21:04:13,591 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 21:04:13,592 INFO L225 Difference]: With dead ends: 268 [2024-11-11 21:04:13,593 INFO L226 Difference]: Without dead ends: 266 [2024-11-11 21:04:13,593 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 74 SyntacticMatches, 7 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 23 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=44, Invalid=196, Unknown=0, NotChecked=0, Total=240 [2024-11-11 21:04:13,595 INFO L435 NwaCegarLoop]: 50 mSDtfsCounter, 16 mSDsluCounter, 243 mSDsCounter, 0 mSdLazyCounter, 108 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 293 SdHoareTripleChecker+Invalid, 118 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 108 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-11 21:04:13,595 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [16 Valid, 293 Invalid, 118 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 108 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-11 21:04:13,596 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 266 states. [2024-11-11 21:04:13,672 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 266 to 239. [2024-11-11 21:04:13,673 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 239 states, 153 states have (on average 1.1045751633986929) internal successors, (169), 167 states have internal predecessors, (169), 49 states have call successors, (49), 33 states have call predecessors, (49), 36 states have return successors, (59), 44 states have call predecessors, (59), 48 states have call successors, (59) [2024-11-11 21:04:13,675 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 239 states to 239 states and 277 transitions. [2024-11-11 21:04:13,675 INFO L78 Accepts]: Start accepts. Automaton has 239 states and 277 transitions. Word has length 47 [2024-11-11 21:04:13,677 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 21:04:13,677 INFO L471 AbstractCegarLoop]: Abstraction has 239 states and 277 transitions. [2024-11-11 21:04:13,677 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 4.0) internal successors, (24), 6 states have internal predecessors, (24), 4 states have call successors, (9), 3 states have call predecessors, (9), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2024-11-11 21:04:13,677 INFO L276 IsEmpty]: Start isEmpty. Operand 239 states and 277 transitions. [2024-11-11 21:04:13,678 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 52 [2024-11-11 21:04:13,679 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 21:04:13,679 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 21:04:13,694 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2024-11-11 21:04:13,879 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:04:13,880 INFO L396 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 21:04:13,880 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 21:04:13,880 INFO L85 PathProgramCache]: Analyzing trace with hash -1612394486, now seen corresponding path program 2 times [2024-11-11 21:04:13,880 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 21:04:13,880 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [623204780] [2024-11-11 21:04:13,880 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:04:13,881 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 21:04:13,915 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:15,008 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 21:04:15,009 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:15,010 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-11 21:04:15,010 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:15,025 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2024-11-11 21:04:15,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:15,103 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2024-11-11 21:04:15,106 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:15,191 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 21 proven. 3 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-11 21:04:15,191 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 21:04:15,191 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [623204780] [2024-11-11 21:04:15,191 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [623204780] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-11 21:04:15,191 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1440990499] [2024-11-11 21:04:15,191 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-11 21:04:15,191 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:04:15,191 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 21:04:15,193 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 21:04:15,200 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2024-11-11 21:04:15,541 INFO L229 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2024-11-11 21:04:15,541 INFO L230 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-11 21:04:15,557 INFO L256 TraceCheckSpWp]: Trace formula consists of 1026 conjuncts, 128 conjuncts are in the unsatisfiable core [2024-11-11 21:04:15,564 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 21:04:15,569 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:15,571 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:04:15,572 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:15,574 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:04:15,576 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:15,593 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:15,680 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 40 treesize of output 28 [2024-11-11 21:04:15,683 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 21 [2024-11-11 21:04:15,685 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 17 [2024-11-11 21:04:15,697 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:15,722 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:15,803 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 27 treesize of output 19 [2024-11-11 21:04:15,806 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 21 [2024-11-11 21:04:15,808 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 17 [2024-11-11 21:04:15,854 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 29 treesize of output 21 [2024-11-11 21:04:15,857 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 1 [2024-11-11 21:04:15,881 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 21 treesize of output 13 [2024-11-11 21:04:15,883 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 17 treesize of output 9 [2024-11-11 21:04:15,898 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-11 21:04:15,898 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2024-11-11 21:04:16,189 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 10 proven. 15 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-11 21:04:16,189 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1440990499] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-11 21:04:16,189 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-11 21:04:16,190 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 18, 14] total 27 [2024-11-11 21:04:16,190 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1124110414] [2024-11-11 21:04:16,190 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-11 21:04:16,190 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 27 states [2024-11-11 21:04:16,190 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 21:04:16,190 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 27 interpolants. [2024-11-11 21:04:16,191 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=79, Invalid=623, Unknown=0, NotChecked=0, Total=702 [2024-11-11 21:04:16,191 INFO L87 Difference]: Start difference. First operand 239 states and 277 transitions. Second operand has 27 states, 26 states have (on average 2.3076923076923075) internal successors, (60), 22 states have internal predecessors, (60), 8 states have call successors, (16), 9 states have call predecessors, (16), 6 states have return successors, (7), 6 states have call predecessors, (7), 4 states have call successors, (7) [2024-11-11 21:04:20,316 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 21:04:28,526 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.04s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 21:04:33,318 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.02s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-11 21:04:33,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 21:04:33,815 INFO L93 Difference]: Finished difference Result 348 states and 406 transitions. [2024-11-11 21:04:33,816 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-11 21:04:33,816 INFO L78 Accepts]: Start accepts. Automaton has has 27 states, 26 states have (on average 2.3076923076923075) internal successors, (60), 22 states have internal predecessors, (60), 8 states have call successors, (16), 9 states have call predecessors, (16), 6 states have return successors, (7), 6 states have call predecessors, (7), 4 states have call successors, (7) Word has length 51 [2024-11-11 21:04:33,816 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 21:04:33,817 INFO L225 Difference]: With dead ends: 348 [2024-11-11 21:04:33,817 INFO L226 Difference]: Without dead ends: 270 [2024-11-11 21:04:33,818 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 139 GetRequests, 86 SyntacticMatches, 15 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 270 ImplicationChecksByTransitivity, 4.8s TimeCoverageRelationStatistics Valid=216, Invalid=1343, Unknown=1, NotChecked=0, Total=1560 [2024-11-11 21:04:33,819 INFO L435 NwaCegarLoop]: 26 mSDtfsCounter, 102 mSDsluCounter, 212 mSDsCounter, 0 mSdLazyCounter, 1444 mSolverCounterSat, 66 mSolverCounterUnsat, 3 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 13.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 114 SdHoareTripleChecker+Valid, 238 SdHoareTripleChecker+Invalid, 1513 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 66 IncrementalHoareTripleChecker+Valid, 1444 IncrementalHoareTripleChecker+Invalid, 3 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 13.2s IncrementalHoareTripleChecker+Time [2024-11-11 21:04:33,819 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [114 Valid, 238 Invalid, 1513 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [66 Valid, 1444 Invalid, 3 Unknown, 0 Unchecked, 13.2s Time] [2024-11-11 21:04:33,819 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 270 states. [2024-11-11 21:04:33,883 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 270 to 251. [2024-11-11 21:04:33,883 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 251 states, 164 states have (on average 1.0914634146341464) internal successors, (179), 176 states have internal predecessors, (179), 48 states have call successors, (48), 38 states have call predecessors, (48), 38 states have return successors, (52), 42 states have call predecessors, (52), 47 states have call successors, (52) [2024-11-11 21:04:33,884 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 251 states to 251 states and 279 transitions. [2024-11-11 21:04:33,884 INFO L78 Accepts]: Start accepts. Automaton has 251 states and 279 transitions. Word has length 51 [2024-11-11 21:04:33,885 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 21:04:33,885 INFO L471 AbstractCegarLoop]: Abstraction has 251 states and 279 transitions. [2024-11-11 21:04:33,885 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 27 states, 26 states have (on average 2.3076923076923075) internal successors, (60), 22 states have internal predecessors, (60), 8 states have call successors, (16), 9 states have call predecessors, (16), 6 states have return successors, (7), 6 states have call predecessors, (7), 4 states have call successors, (7) [2024-11-11 21:04:33,885 INFO L276 IsEmpty]: Start isEmpty. Operand 251 states and 279 transitions. [2024-11-11 21:04:33,886 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 77 [2024-11-11 21:04:33,886 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 21:04:33,886 INFO L218 NwaCegarLoop]: trace histogram [7, 6, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 21:04:33,895 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Ended with exit code 0 [2024-11-11 21:04:34,086 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2024-11-11 21:04:34,086 INFO L396 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 21:04:34,087 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 21:04:34,087 INFO L85 PathProgramCache]: Analyzing trace with hash 63953117, now seen corresponding path program 1 times [2024-11-11 21:04:34,087 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 21:04:34,087 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1636469644] [2024-11-11 21:04:34,087 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:04:34,087 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 21:04:34,116 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:35,161 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 21:04:35,162 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:35,164 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-11 21:04:35,164 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:35,176 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 22 [2024-11-11 21:04:35,184 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:35,385 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 2 [2024-11-11 21:04:35,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:35,389 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 8 [2024-11-11 21:04:35,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:35,392 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 14 [2024-11-11 21:04:35,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:35,395 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2024-11-11 21:04:35,397 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:35,399 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 60 [2024-11-11 21:04:35,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:35,401 INFO L368 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 66 [2024-11-11 21:04:35,402 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:35,403 INFO L134 CoverageAnalysis]: Checked inductivity of 87 backedges. 23 proven. 0 refuted. 0 times theorem prover too weak. 64 trivial. 0 not checked. [2024-11-11 21:04:35,404 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-11 21:04:35,404 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1636469644] [2024-11-11 21:04:35,404 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1636469644] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-11 21:04:35,404 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-11 21:04:35,404 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2024-11-11 21:04:35,404 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1903862490] [2024-11-11 21:04:35,404 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-11 21:04:35,405 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-11 21:04:35,405 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-11 21:04:35,405 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-11 21:04:35,405 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=22, Invalid=110, Unknown=0, NotChecked=0, Total=132 [2024-11-11 21:04:35,406 INFO L87 Difference]: Start difference. First operand 251 states and 279 transitions. Second operand has 12 states, 10 states have (on average 3.5) internal successors, (35), 9 states have internal predecessors, (35), 6 states have call successors, (14), 4 states have call predecessors, (14), 2 states have return successors, (9), 4 states have call predecessors, (9), 5 states have call successors, (9) [2024-11-11 21:04:35,905 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-11 21:04:35,906 INFO L93 Difference]: Finished difference Result 446 states and 517 transitions. [2024-11-11 21:04:35,906 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2024-11-11 21:04:35,906 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 3.5) internal successors, (35), 9 states have internal predecessors, (35), 6 states have call successors, (14), 4 states have call predecessors, (14), 2 states have return successors, (9), 4 states have call predecessors, (9), 5 states have call successors, (9) Word has length 76 [2024-11-11 21:04:35,906 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-11 21:04:35,909 INFO L225 Difference]: With dead ends: 446 [2024-11-11 21:04:35,909 INFO L226 Difference]: Without dead ends: 290 [2024-11-11 21:04:35,910 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 49 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=66, Invalid=314, Unknown=0, NotChecked=0, Total=380 [2024-11-11 21:04:35,910 INFO L435 NwaCegarLoop]: 39 mSDtfsCounter, 37 mSDsluCounter, 186 mSDsCounter, 0 mSdLazyCounter, 370 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 225 SdHoareTripleChecker+Invalid, 392 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 370 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2024-11-11 21:04:35,911 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 225 Invalid, 392 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 370 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2024-11-11 21:04:35,911 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 290 states. [2024-11-11 21:04:35,996 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 290 to 284. [2024-11-11 21:04:35,997 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 284 states, 185 states have (on average 1.0810810810810811) internal successors, (200), 197 states have internal predecessors, (200), 51 states have call successors, (51), 41 states have call predecessors, (51), 47 states have return successors, (67), 45 states have call predecessors, (67), 50 states have call successors, (67) [2024-11-11 21:04:35,998 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 284 states to 284 states and 318 transitions. [2024-11-11 21:04:35,998 INFO L78 Accepts]: Start accepts. Automaton has 284 states and 318 transitions. Word has length 76 [2024-11-11 21:04:35,998 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-11 21:04:35,998 INFO L471 AbstractCegarLoop]: Abstraction has 284 states and 318 transitions. [2024-11-11 21:04:35,999 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 3.5) internal successors, (35), 9 states have internal predecessors, (35), 6 states have call successors, (14), 4 states have call predecessors, (14), 2 states have return successors, (9), 4 states have call predecessors, (9), 5 states have call successors, (9) [2024-11-11 21:04:35,999 INFO L276 IsEmpty]: Start isEmpty. Operand 284 states and 318 transitions. [2024-11-11 21:04:35,999 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2024-11-11 21:04:35,999 INFO L210 NwaCegarLoop]: Found error trace [2024-11-11 21:04:36,000 INFO L218 NwaCegarLoop]: trace histogram [5, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-11 21:04:36,000 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10 [2024-11-11 21:04:36,000 INFO L396 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-11 21:04:36,000 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-11 21:04:36,000 INFO L85 PathProgramCache]: Analyzing trace with hash 457812220, now seen corresponding path program 1 times [2024-11-11 21:04:36,000 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-11 21:04:36,000 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1567339458] [2024-11-11 21:04:36,000 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:04:36,001 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-11 21:04:36,050 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unknown [2024-11-11 21:04:36,052 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1825391948] [2024-11-11 21:04:36,052 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-11 21:04:36,052 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-11 21:04:36,053 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-11 21:04:36,056 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-11 21:04:36,057 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2024-11-11 21:04:36,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-11 21:04:36,302 INFO L256 TraceCheckSpWp]: Trace formula consists of 852 conjuncts, 218 conjuncts are in the unsatisfiable core [2024-11-11 21:04:36,307 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2024-11-11 21:04:36,387 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:36,397 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:36,406 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:36,415 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:36,425 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:36,442 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:36,500 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:36,519 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:36,797 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:36,829 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:36,939 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:37,147 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:37,157 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 15 treesize of output 11 [2024-11-11 21:04:37,227 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:04:58,880 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 35 treesize of output 27 [2024-11-11 21:05:03,173 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-11 21:05:07,380 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 28 [2024-11-11 21:05:07,434 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 11 [2024-11-11 21:05:07,646 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 33 treesize of output 25