./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/heap-manipulation/dancing.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c3fed411 Calling Ultimate with: /usr/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/heap-manipulation/dancing.i -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.graphml --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 c2e0266b63b958a771d0226973905d5a39a7a28d05d194ae66381394d9ab520a --- Real Ultimate output --- This is Ultimate 0.2.2-tmp.no-commuhash-c3fed41 [2021-12-17 07:54:20,591 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-12-17 07:54:20,593 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-12-17 07:54:20,617 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-12-17 07:54:20,618 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-12-17 07:54:20,618 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-12-17 07:54:20,619 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-12-17 07:54:20,620 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-12-17 07:54:20,621 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-12-17 07:54:20,622 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-12-17 07:54:20,623 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-12-17 07:54:20,625 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-12-17 07:54:20,625 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-12-17 07:54:20,626 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-12-17 07:54:20,627 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-12-17 07:54:20,628 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-12-17 07:54:20,628 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-12-17 07:54:20,629 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-12-17 07:54:20,630 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-12-17 07:54:20,631 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-12-17 07:54:20,632 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-12-17 07:54:20,645 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-12-17 07:54:20,647 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-12-17 07:54:20,648 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-12-17 07:54:20,659 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-12-17 07:54:20,659 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-12-17 07:54:20,659 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-12-17 07:54:20,661 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-12-17 07:54:20,661 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-12-17 07:54:20,661 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-12-17 07:54:20,662 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-12-17 07:54:20,663 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-12-17 07:54:20,664 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-12-17 07:54:20,665 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-12-17 07:54:20,665 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-12-17 07:54:20,666 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-12-17 07:54:20,666 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-12-17 07:54:20,666 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-12-17 07:54:20,666 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-12-17 07:54:20,668 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-12-17 07:54:20,669 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-12-17 07:54:20,670 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2021-12-17 07:54:20,702 INFO L113 SettingsManager]: Loading preferences was successful [2021-12-17 07:54:20,702 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-12-17 07:54:20,702 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-12-17 07:54:20,703 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-12-17 07:54:20,703 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2021-12-17 07:54:20,703 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2021-12-17 07:54:20,704 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-12-17 07:54:20,704 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-12-17 07:54:20,704 INFO L138 SettingsManager]: * Use SBE=true [2021-12-17 07:54:20,704 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-12-17 07:54:20,704 INFO L138 SettingsManager]: * sizeof long=4 [2021-12-17 07:54:20,704 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-12-17 07:54:20,705 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-12-17 07:54:20,705 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-12-17 07:54:20,705 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-12-17 07:54:20,705 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-12-17 07:54:20,705 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-12-17 07:54:20,705 INFO L138 SettingsManager]: * sizeof long double=12 [2021-12-17 07:54:20,705 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-12-17 07:54:20,706 INFO L138 SettingsManager]: * Use constant arrays=true [2021-12-17 07:54:20,706 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-12-17 07:54:20,706 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-12-17 07:54:20,706 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-12-17 07:54:20,706 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-12-17 07:54:20,706 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-17 07:54:20,706 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-12-17 07:54:20,707 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-12-17 07:54:20,707 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-12-17 07:54:20,707 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-12-17 07:54:20,707 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-12-17 07:54:20,707 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2021-12-17 07:54:20,707 INFO L138 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2021-12-17 07:54:20,707 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-12-17 07:54:20,708 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2021-12-17 07:54:20,708 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode 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.graphml 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 -> c2e0266b63b958a771d0226973905d5a39a7a28d05d194ae66381394d9ab520a [2021-12-17 07:54:20,900 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-12-17 07:54:20,932 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-12-17 07:54:20,934 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-12-17 07:54:20,935 INFO L271 PluginConnector]: Initializing CDTParser... [2021-12-17 07:54:20,935 INFO L275 PluginConnector]: CDTParser initialized [2021-12-17 07:54:20,936 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/heap-manipulation/dancing.i [2021-12-17 07:54:20,987 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/526dc260c/1419cb1d40084c1eb2c505d03899a0fc/FLAG51bf6e7b2 [2021-12-17 07:54:21,337 INFO L306 CDTParser]: Found 1 translation units. [2021-12-17 07:54:21,338 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/dancing.i [2021-12-17 07:54:21,348 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/526dc260c/1419cb1d40084c1eb2c505d03899a0fc/FLAG51bf6e7b2 [2021-12-17 07:54:21,732 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/526dc260c/1419cb1d40084c1eb2c505d03899a0fc [2021-12-17 07:54:21,735 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-12-17 07:54:21,737 INFO L131 ToolchainWalker]: Walking toolchain with 6 elements. [2021-12-17 07:54:21,750 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2021-12-17 07:54:21,750 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2021-12-17 07:54:21,753 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2021-12-17 07:54:21,754 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.12 07:54:21" (1/1) ... [2021-12-17 07:54:21,757 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@a81b0d4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:21, skipping insertion in model container [2021-12-17 07:54:21,758 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.12 07:54:21" (1/1) ... [2021-12-17 07:54:21,764 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2021-12-17 07:54:21,801 INFO L178 MainTranslator]: Built tables and reachable declarations [2021-12-17 07:54:21,995 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/dancing.i[938,951] [2021-12-17 07:54:22,100 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-17 07:54:22,109 INFO L203 MainTranslator]: Completed pre-run [2021-12-17 07:54:22,131 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/heap-manipulation/dancing.i[938,951] [2021-12-17 07:54:22,166 INFO L209 PostProcessor]: Analyzing one entry point: main [2021-12-17 07:54:22,187 INFO L208 MainTranslator]: Completed translation [2021-12-17 07:54:22,188 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:22 WrapperNode [2021-12-17 07:54:22,188 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2021-12-17 07:54:22,189 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-12-17 07:54:22,190 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-12-17 07:54:22,190 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-12-17 07:54:22,197 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:22" (1/1) ... [2021-12-17 07:54:22,225 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:22" (1/1) ... [2021-12-17 07:54:22,253 INFO L137 Inliner]: procedures = 124, calls = 40, calls flagged for inlining = 5, calls inlined = 5, statements flattened = 90 [2021-12-17 07:54:22,254 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-12-17 07:54:22,255 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-12-17 07:54:22,255 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-12-17 07:54:22,255 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-12-17 07:54:22,262 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:22" (1/1) ... [2021-12-17 07:54:22,263 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:22" (1/1) ... [2021-12-17 07:54:22,271 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:22" (1/1) ... [2021-12-17 07:54:22,272 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:22" (1/1) ... [2021-12-17 07:54:22,289 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:22" (1/1) ... [2021-12-17 07:54:22,295 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:22" (1/1) ... [2021-12-17 07:54:22,301 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:22" (1/1) ... [2021-12-17 07:54:22,303 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-12-17 07:54:22,307 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-12-17 07:54:22,308 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-12-17 07:54:22,308 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-12-17 07:54:22,309 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:22" (1/1) ... [2021-12-17 07:54:22,317 INFO L168 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-12-17 07:54:22,328 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-17 07:54:22,352 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2021-12-17 07:54:22,355 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2021-12-17 07:54:22,410 INFO L130 BoogieDeclarations]: Found specification of procedure is_list_containing_x [2021-12-17 07:54:22,411 INFO L138 BoogieDeclarations]: Found implementation of procedure is_list_containing_x [2021-12-17 07:54:22,411 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2021-12-17 07:54:22,411 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2021-12-17 07:54:22,411 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2021-12-17 07:54:22,411 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2021-12-17 07:54:22,411 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2021-12-17 07:54:22,412 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2021-12-17 07:54:22,412 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2021-12-17 07:54:22,412 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2021-12-17 07:54:22,415 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2021-12-17 07:54:22,415 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-12-17 07:54:22,415 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-12-17 07:54:22,494 INFO L236 CfgBuilder]: Building ICFG [2021-12-17 07:54:22,495 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2021-12-17 07:54:22,678 INFO L277 CfgBuilder]: Performing block encoding [2021-12-17 07:54:22,683 INFO L296 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-12-17 07:54:22,683 INFO L301 CfgBuilder]: Removed 1 assume(true) statements. [2021-12-17 07:54:22,684 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.12 07:54:22 BoogieIcfgContainer [2021-12-17 07:54:22,684 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-12-17 07:54:22,686 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-12-17 07:54:22,686 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-12-17 07:54:22,688 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-12-17 07:54:22,688 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 17.12 07:54:21" (1/3) ... [2021-12-17 07:54:22,689 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@619ef0ac and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.12 07:54:22, skipping insertion in model container [2021-12-17 07:54:22,689 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.12 07:54:22" (2/3) ... [2021-12-17 07:54:22,689 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@619ef0ac and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 17.12 07:54:22, skipping insertion in model container [2021-12-17 07:54:22,689 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 17.12 07:54:22" (3/3) ... [2021-12-17 07:54:22,690 INFO L111 eAbstractionObserver]: Analyzing ICFG dancing.i [2021-12-17 07:54:22,694 INFO L204 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-12-17 07:54:22,694 INFO L163 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2021-12-17 07:54:22,724 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2021-12-17 07:54:22,729 INFO L339 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, mHoare=true, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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, mLoopAccelerationTechnique=FAST_UPR [2021-12-17 07:54:22,729 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2021-12-17 07:54:22,740 INFO L276 IsEmpty]: Start isEmpty. Operand has 41 states, 31 states have (on average 1.4516129032258065) internal successors, (45), 32 states have internal predecessors, (45), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2021-12-17 07:54:22,744 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2021-12-17 07:54:22,744 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:22,745 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-17 07:54:22,745 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:22,757 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:22,758 INFO L85 PathProgramCache]: Analyzing trace with hash 1472755522, now seen corresponding path program 1 times [2021-12-17 07:54:22,764 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:22,764 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [15694402] [2021-12-17 07:54:22,764 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:22,765 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:22,835 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:22,873 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:22,876 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:22,886 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-17 07:54:22,887 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:22,887 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [15694402] [2021-12-17 07:54:22,888 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [15694402] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-17 07:54:22,888 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-17 07:54:22,888 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2021-12-17 07:54:22,890 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [467739921] [2021-12-17 07:54:22,891 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-17 07:54:22,894 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2021-12-17 07:54:22,895 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:22,917 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2021-12-17 07:54:22,918 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-12-17 07:54:22,920 INFO L87 Difference]: Start difference. First operand has 41 states, 31 states have (on average 1.4516129032258065) internal successors, (45), 32 states have internal predecessors, (45), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 2 states, 2 states have (on average 8.5) internal successors, (17), 2 states have internal predecessors, (17), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-17 07:54:22,939 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:22,939 INFO L93 Difference]: Finished difference Result 77 states and 107 transitions. [2021-12-17 07:54:22,941 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2021-12-17 07:54:22,942 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 8.5) internal successors, (17), 2 states have internal predecessors, (17), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 20 [2021-12-17 07:54:22,942 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:22,948 INFO L225 Difference]: With dead ends: 77 [2021-12-17 07:54:22,948 INFO L226 Difference]: Without dead ends: 37 [2021-12-17 07:54:22,951 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2021-12-17 07:54:22,954 INFO L933 BasicCegarLoop]: 54 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 54 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:22,955 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [0 Valid, 54 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-17 07:54:22,967 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2021-12-17 07:54:22,983 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2021-12-17 07:54:22,985 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 28 states have (on average 1.3928571428571428) internal successors, (39), 29 states have internal predecessors, (39), 6 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2021-12-17 07:54:22,987 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 50 transitions. [2021-12-17 07:54:22,988 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 50 transitions. Word has length 20 [2021-12-17 07:54:22,988 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:22,989 INFO L470 AbstractCegarLoop]: Abstraction has 37 states and 50 transitions. [2021-12-17 07:54:22,989 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 8.5) internal successors, (17), 2 states have internal predecessors, (17), 1 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-17 07:54:22,989 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 50 transitions. [2021-12-17 07:54:22,993 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2021-12-17 07:54:22,993 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:22,994 INFO L514 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-17 07:54:22,994 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-12-17 07:54:22,995 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:22,997 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:22,998 INFO L85 PathProgramCache]: Analyzing trace with hash -751028367, now seen corresponding path program 1 times [2021-12-17 07:54:22,998 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:22,998 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [660377839] [2021-12-17 07:54:22,998 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:22,998 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:23,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:23,130 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:23,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:23,138 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-17 07:54:23,139 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:23,139 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [660377839] [2021-12-17 07:54:23,140 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [660377839] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-17 07:54:23,140 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-17 07:54:23,140 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-17 07:54:23,140 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [622988853] [2021-12-17 07:54:23,140 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-17 07:54:23,141 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-17 07:54:23,142 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:23,142 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-17 07:54:23,142 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-17 07:54:23,143 INFO L87 Difference]: Start difference. First operand 37 states and 50 transitions. Second operand has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-17 07:54:23,186 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:23,186 INFO L93 Difference]: Finished difference Result 45 states and 58 transitions. [2021-12-17 07:54:23,186 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-17 07:54:23,186 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 20 [2021-12-17 07:54:23,187 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:23,187 INFO L225 Difference]: With dead ends: 45 [2021-12-17 07:54:23,188 INFO L226 Difference]: Without dead ends: 43 [2021-12-17 07:54:23,188 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2021-12-17 07:54:23,189 INFO L933 BasicCegarLoop]: 48 mSDtfsCounter, 6 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 17 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 183 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 17 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:23,189 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 183 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 17 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-17 07:54:23,190 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 43 states. [2021-12-17 07:54:23,195 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 43 to 42. [2021-12-17 07:54:23,196 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 31 states have (on average 1.3548387096774193) internal successors, (42), 33 states have internal predecessors, (42), 7 states have call successors, (7), 3 states have call predecessors, (7), 3 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2021-12-17 07:54:23,197 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 55 transitions. [2021-12-17 07:54:23,197 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 55 transitions. Word has length 20 [2021-12-17 07:54:23,198 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:23,198 INFO L470 AbstractCegarLoop]: Abstraction has 42 states and 55 transitions. [2021-12-17 07:54:23,198 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 4.25) internal successors, (17), 4 states have internal predecessors, (17), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2021-12-17 07:54:23,198 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 55 transitions. [2021-12-17 07:54:23,199 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2021-12-17 07:54:23,199 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:23,199 INFO L514 BasicCegarLoop]: 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] [2021-12-17 07:54:23,200 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2021-12-17 07:54:23,200 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:23,200 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:23,200 INFO L85 PathProgramCache]: Analyzing trace with hash 789210768, now seen corresponding path program 1 times [2021-12-17 07:54:23,201 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:23,201 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [100600162] [2021-12-17 07:54:23,201 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:23,201 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:23,222 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:23,260 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:23,263 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:23,266 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-17 07:54:23,268 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:23,271 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-17 07:54:23,271 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:23,271 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [100600162] [2021-12-17 07:54:23,271 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [100600162] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-17 07:54:23,271 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-17 07:54:23,271 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2021-12-17 07:54:23,271 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [450436676] [2021-12-17 07:54:23,271 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-17 07:54:23,272 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2021-12-17 07:54:23,272 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:23,272 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-12-17 07:54:23,272 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2021-12-17 07:54:23,272 INFO L87 Difference]: Start difference. First operand 42 states and 55 transitions. Second operand has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-17 07:54:23,305 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:23,305 INFO L93 Difference]: Finished difference Result 86 states and 116 transitions. [2021-12-17 07:54:23,306 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-17 07:54:23,306 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Word has length 26 [2021-12-17 07:54:23,307 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:23,307 INFO L225 Difference]: With dead ends: 86 [2021-12-17 07:54:23,307 INFO L226 Difference]: Without dead ends: 63 [2021-12-17 07:54:23,308 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 9 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2021-12-17 07:54:23,308 INFO L933 BasicCegarLoop]: 50 mSDtfsCounter, 15 mSDsluCounter, 91 mSDsCounter, 0 mSdLazyCounter, 14 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 141 SdHoareTripleChecker+Invalid, 18 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 14 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:23,309 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [17 Valid, 141 Invalid, 18 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 14 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-17 07:54:23,309 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 63 states. [2021-12-17 07:54:23,314 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 63 to 54. [2021-12-17 07:54:23,314 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 54 states, 42 states have (on average 1.380952380952381) internal successors, (58), 44 states have internal predecessors, (58), 8 states have call successors, (8), 3 states have call predecessors, (8), 3 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2021-12-17 07:54:23,315 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 54 states to 54 states and 73 transitions. [2021-12-17 07:54:23,315 INFO L78 Accepts]: Start accepts. Automaton has 54 states and 73 transitions. Word has length 26 [2021-12-17 07:54:23,315 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:23,315 INFO L470 AbstractCegarLoop]: Abstraction has 54 states and 73 transitions. [2021-12-17 07:54:23,315 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 4 states have internal predecessors, (18), 2 states have call successors, (3), 2 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2021-12-17 07:54:23,315 INFO L276 IsEmpty]: Start isEmpty. Operand 54 states and 73 transitions. [2021-12-17 07:54:23,316 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2021-12-17 07:54:23,316 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:23,316 INFO L514 BasicCegarLoop]: 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] [2021-12-17 07:54:23,316 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2021-12-17 07:54:23,317 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:23,317 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:23,317 INFO L85 PathProgramCache]: Analyzing trace with hash 860755832, now seen corresponding path program 1 times [2021-12-17 07:54:23,317 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:23,317 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [662685980] [2021-12-17 07:54:23,317 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:23,317 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:23,342 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:23,384 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-17 07:54:23,391 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:23,429 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 19 [2021-12-17 07:54:23,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:23,437 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-17 07:54:23,438 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:23,438 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [662685980] [2021-12-17 07:54:23,438 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [662685980] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-17 07:54:23,438 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1347704555] [2021-12-17 07:54:23,438 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:23,438 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:23,438 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-17 07:54:23,452 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) [2021-12-17 07:54:23,501 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2021-12-17 07:54:23,581 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:23,583 INFO L263 TraceCheckSpWp]: Trace formula consists of 235 conjuncts, 8 conjunts are in the unsatisfiable core [2021-12-17 07:54:23,587 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-17 07:54:23,742 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 4 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-12-17 07:54:23,742 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-17 07:54:23,889 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-17 07:54:23,890 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1347704555] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-17 07:54:23,890 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-17 07:54:23,890 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7, 7] total 16 [2021-12-17 07:54:23,890 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1551356644] [2021-12-17 07:54:23,890 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-17 07:54:23,891 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2021-12-17 07:54:23,891 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:23,891 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2021-12-17 07:54:23,892 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=42, Invalid=198, Unknown=0, NotChecked=0, Total=240 [2021-12-17 07:54:23,892 INFO L87 Difference]: Start difference. First operand 54 states and 73 transitions. Second operand has 16 states, 16 states have (on average 2.625) internal successors, (42), 16 states have internal predecessors, (42), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (5), 1 states have call predecessors, (5), 4 states have call successors, (5) [2021-12-17 07:54:24,114 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:24,114 INFO L93 Difference]: Finished difference Result 118 states and 165 transitions. [2021-12-17 07:54:24,114 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-12-17 07:54:24,115 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.625) internal successors, (42), 16 states have internal predecessors, (42), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (5), 1 states have call predecessors, (5), 4 states have call successors, (5) Word has length 29 [2021-12-17 07:54:24,115 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:24,118 INFO L225 Difference]: With dead ends: 118 [2021-12-17 07:54:24,119 INFO L226 Difference]: Without dead ends: 82 [2021-12-17 07:54:24,120 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=76, Invalid=304, Unknown=0, NotChecked=0, Total=380 [2021-12-17 07:54:24,121 INFO L933 BasicCegarLoop]: 80 mSDtfsCounter, 132 mSDsluCounter, 286 mSDsCounter, 0 mSdLazyCounter, 177 mSolverCounterSat, 57 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 134 SdHoareTripleChecker+Valid, 366 SdHoareTripleChecker+Invalid, 234 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 57 IncrementalHoareTripleChecker+Valid, 177 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:24,121 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [134 Valid, 366 Invalid, 234 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [57 Valid, 177 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-17 07:54:24,122 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 82 states. [2021-12-17 07:54:24,129 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 82 to 63. [2021-12-17 07:54:24,130 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 63 states, 48 states have (on average 1.375) internal successors, (66), 52 states have internal predecessors, (66), 10 states have call successors, (10), 3 states have call predecessors, (10), 4 states have return successors, (12), 7 states have call predecessors, (12), 9 states have call successors, (12) [2021-12-17 07:54:24,131 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 63 states to 63 states and 88 transitions. [2021-12-17 07:54:24,131 INFO L78 Accepts]: Start accepts. Automaton has 63 states and 88 transitions. Word has length 29 [2021-12-17 07:54:24,131 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:24,131 INFO L470 AbstractCegarLoop]: Abstraction has 63 states and 88 transitions. [2021-12-17 07:54:24,132 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.625) internal successors, (42), 16 states have internal predecessors, (42), 4 states have call successors, (6), 2 states have call predecessors, (6), 4 states have return successors, (5), 1 states have call predecessors, (5), 4 states have call successors, (5) [2021-12-17 07:54:24,132 INFO L276 IsEmpty]: Start isEmpty. Operand 63 states and 88 transitions. [2021-12-17 07:54:24,133 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2021-12-17 07:54:24,133 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:24,133 INFO L514 BasicCegarLoop]: 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] [2021-12-17 07:54:24,174 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2021-12-17 07:54:24,359 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:24,359 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:24,360 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:24,360 INFO L85 PathProgramCache]: Analyzing trace with hash 162961828, now seen corresponding path program 1 times [2021-12-17 07:54:24,360 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:24,360 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1041949313] [2021-12-17 07:54:24,360 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:24,361 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:24,384 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:24,421 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-17 07:54:24,422 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:24,425 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2021-12-17 07:54:24,428 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:24,443 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-17 07:54:24,444 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:24,444 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1041949313] [2021-12-17 07:54:24,444 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1041949313] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-17 07:54:24,444 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-17 07:54:24,444 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2021-12-17 07:54:24,445 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [22007880] [2021-12-17 07:54:24,445 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-17 07:54:24,445 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2021-12-17 07:54:24,445 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:24,446 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-12-17 07:54:24,446 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2021-12-17 07:54:24,446 INFO L87 Difference]: Start difference. First operand 63 states and 88 transitions. Second operand has 7 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-17 07:54:24,508 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:24,509 INFO L93 Difference]: Finished difference Result 75 states and 105 transitions. [2021-12-17 07:54:24,509 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-17 07:54:24,509 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 31 [2021-12-17 07:54:24,510 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:24,510 INFO L225 Difference]: With dead ends: 75 [2021-12-17 07:54:24,511 INFO L226 Difference]: Without dead ends: 73 [2021-12-17 07:54:24,511 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=53, Unknown=0, NotChecked=0, Total=72 [2021-12-17 07:54:24,512 INFO L933 BasicCegarLoop]: 53 mSDtfsCounter, 7 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 38 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 301 SdHoareTripleChecker+Invalid, 42 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 38 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:24,512 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 301 Invalid, 42 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 38 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-17 07:54:24,513 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2021-12-17 07:54:24,520 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 71. [2021-12-17 07:54:24,520 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 53 states have (on average 1.3396226415094339) internal successors, (71), 58 states have internal predecessors, (71), 11 states have call successors, (11), 4 states have call predecessors, (11), 6 states have return successors, (19), 8 states have call predecessors, (19), 10 states have call successors, (19) [2021-12-17 07:54:24,521 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 101 transitions. [2021-12-17 07:54:24,521 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 101 transitions. Word has length 31 [2021-12-17 07:54:24,522 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:24,522 INFO L470 AbstractCegarLoop]: Abstraction has 71 states and 101 transitions. [2021-12-17 07:54:24,522 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 4.0) internal successors, (24), 5 states have internal predecessors, (24), 2 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2021-12-17 07:54:24,522 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 101 transitions. [2021-12-17 07:54:24,524 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2021-12-17 07:54:24,524 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:24,524 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-17 07:54:24,524 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4 [2021-12-17 07:54:24,524 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:24,525 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:24,525 INFO L85 PathProgramCache]: Analyzing trace with hash 786337177, now seen corresponding path program 1 times [2021-12-17 07:54:24,525 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:24,525 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1622304651] [2021-12-17 07:54:24,525 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:24,526 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:24,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:24,587 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-17 07:54:24,590 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:24,602 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 20 [2021-12-17 07:54:24,605 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:24,611 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:24,612 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:24,615 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2021-12-17 07:54:24,615 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:24,616 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1622304651] [2021-12-17 07:54:24,616 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1622304651] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-17 07:54:24,616 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [590084954] [2021-12-17 07:54:24,616 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:24,616 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:24,617 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-17 07:54:24,636 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) [2021-12-17 07:54:24,651 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2021-12-17 07:54:24,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:24,759 INFO L263 TraceCheckSpWp]: Trace formula consists of 273 conjuncts, 48 conjunts are in the unsatisfiable core [2021-12-17 07:54:24,766 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-17 07:54:24,869 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:24,875 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2021-12-17 07:54:24,884 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:24,885 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2021-12-17 07:54:24,892 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:24,893 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 18 [2021-12-17 07:54:24,898 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:24,900 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 18 [2021-12-17 07:54:25,065 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 7 [2021-12-17 07:54:25,068 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 7 [2021-12-17 07:54:25,138 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 9 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-17 07:54:25,138 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-17 07:54:25,184 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 10 treesize of output 4 [2021-12-17 07:54:25,308 INFO L354 Elim1Store]: treesize reduction 21, result has 47.5 percent of original size [2021-12-17 07:54:25,308 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1 new quantified variables, introduced 2 case distinctions, treesize of input 25 treesize of output 31 [2021-12-17 07:54:25,312 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 36 treesize of output 24 [2021-12-17 07:54:25,315 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2021-12-17 07:54:25,322 INFO L354 Elim1Store]: treesize reduction 39, result has 2.5 percent of original size [2021-12-17 07:54:25,322 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 25 treesize of output 1 [2021-12-17 07:54:25,346 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2021-12-17 07:54:25,346 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [590084954] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-17 07:54:25,346 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-17 07:54:25,346 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 8, 7] total 16 [2021-12-17 07:54:25,346 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1393934460] [2021-12-17 07:54:25,347 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-17 07:54:25,347 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2021-12-17 07:54:25,347 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:25,347 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2021-12-17 07:54:25,348 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=36, Invalid=204, Unknown=0, NotChecked=0, Total=240 [2021-12-17 07:54:25,348 INFO L87 Difference]: Start difference. First operand 71 states and 101 transitions. Second operand has 16 states, 16 states have (on average 3.4375) internal successors, (55), 15 states have internal predecessors, (55), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2021-12-17 07:54:25,779 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:25,780 INFO L93 Difference]: Finished difference Result 269 states and 401 transitions. [2021-12-17 07:54:25,780 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2021-12-17 07:54:25,780 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 3.4375) internal successors, (55), 15 states have internal predecessors, (55), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) Word has length 37 [2021-12-17 07:54:25,781 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:25,783 INFO L225 Difference]: With dead ends: 269 [2021-12-17 07:54:25,783 INFO L226 Difference]: Without dead ends: 198 [2021-12-17 07:54:25,784 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 102 GetRequests, 73 SyntacticMatches, 1 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 101 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=162, Invalid=708, Unknown=0, NotChecked=0, Total=870 [2021-12-17 07:54:25,784 INFO L933 BasicCegarLoop]: 103 mSDtfsCounter, 193 mSDsluCounter, 832 mSDsCounter, 0 mSdLazyCounter, 327 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 199 SdHoareTripleChecker+Valid, 935 SdHoareTripleChecker+Invalid, 431 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 327 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 55 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:25,785 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [199 Valid, 935 Invalid, 431 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 327 Invalid, 0 Unknown, 55 Unchecked, 0.2s Time] [2021-12-17 07:54:25,785 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 198 states. [2021-12-17 07:54:25,797 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 198 to 90. [2021-12-17 07:54:25,797 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 90 states, 69 states have (on average 1.3333333333333333) internal successors, (92), 74 states have internal predecessors, (92), 13 states have call successors, (13), 5 states have call predecessors, (13), 7 states have return successors, (20), 10 states have call predecessors, (20), 12 states have call successors, (20) [2021-12-17 07:54:25,798 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 125 transitions. [2021-12-17 07:54:25,798 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 125 transitions. Word has length 37 [2021-12-17 07:54:25,799 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:25,799 INFO L470 AbstractCegarLoop]: Abstraction has 90 states and 125 transitions. [2021-12-17 07:54:25,799 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 3.4375) internal successors, (55), 15 states have internal predecessors, (55), 4 states have call successors, (8), 3 states have call predecessors, (8), 4 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2021-12-17 07:54:25,799 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 125 transitions. [2021-12-17 07:54:25,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2021-12-17 07:54:25,800 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:25,800 INFO L514 BasicCegarLoop]: 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] [2021-12-17 07:54:25,839 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2021-12-17 07:54:26,040 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable5 [2021-12-17 07:54:26,040 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:26,040 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:26,041 INFO L85 PathProgramCache]: Analyzing trace with hash -1693334873, now seen corresponding path program 1 times [2021-12-17 07:54:26,041 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:26,041 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1280233758] [2021-12-17 07:54:26,041 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:26,041 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:26,052 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,098 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:26,101 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,107 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-17 07:54:26,108 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,119 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2021-12-17 07:54:26,121 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,126 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2021-12-17 07:54:26,126 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:26,126 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1280233758] [2021-12-17 07:54:26,127 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1280233758] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-17 07:54:26,127 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-17 07:54:26,127 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-17 07:54:26,127 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [852579269] [2021-12-17 07:54:26,127 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-17 07:54:26,128 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-17 07:54:26,128 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:26,128 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-17 07:54:26,128 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-17 07:54:26,129 INFO L87 Difference]: Start difference. First operand 90 states and 125 transitions. Second operand has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-17 07:54:26,205 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:26,206 INFO L93 Difference]: Finished difference Result 133 states and 181 transitions. [2021-12-17 07:54:26,206 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-17 07:54:26,206 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 35 [2021-12-17 07:54:26,206 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:26,207 INFO L225 Difference]: With dead ends: 133 [2021-12-17 07:54:26,207 INFO L226 Difference]: Without dead ends: 102 [2021-12-17 07:54:26,208 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2021-12-17 07:54:26,208 INFO L933 BasicCegarLoop]: 50 mSDtfsCounter, 20 mSDsluCounter, 119 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 20 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 61 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:26,209 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [20 Valid, 169 Invalid, 61 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-17 07:54:26,209 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 102 states. [2021-12-17 07:54:26,215 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 102 to 92. [2021-12-17 07:54:26,215 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 92 states, 71 states have (on average 1.323943661971831) internal successors, (94), 76 states have internal predecessors, (94), 13 states have call successors, (13), 5 states have call predecessors, (13), 7 states have return successors, (20), 10 states have call predecessors, (20), 12 states have call successors, (20) [2021-12-17 07:54:26,216 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 127 transitions. [2021-12-17 07:54:26,216 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 127 transitions. Word has length 35 [2021-12-17 07:54:26,217 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:26,217 INFO L470 AbstractCegarLoop]: Abstraction has 92 states and 127 transitions. [2021-12-17 07:54:26,217 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.0) internal successors, (25), 5 states have internal predecessors, (25), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2021-12-17 07:54:26,217 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 127 transitions. [2021-12-17 07:54:26,218 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 36 [2021-12-17 07:54:26,218 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:26,218 INFO L514 BasicCegarLoop]: 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] [2021-12-17 07:54:26,218 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2021-12-17 07:54:26,218 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:26,219 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:26,219 INFO L85 PathProgramCache]: Analyzing trace with hash -1474480155, now seen corresponding path program 1 times [2021-12-17 07:54:26,219 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:26,219 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1904116831] [2021-12-17 07:54:26,219 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:26,219 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:26,230 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,253 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:26,255 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,257 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-17 07:54:26,258 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,260 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2021-12-17 07:54:26,261 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,271 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2021-12-17 07:54:26,271 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:26,272 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1904116831] [2021-12-17 07:54:26,272 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1904116831] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-17 07:54:26,272 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-17 07:54:26,272 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2021-12-17 07:54:26,272 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [436842676] [2021-12-17 07:54:26,272 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-17 07:54:26,273 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-17 07:54:26,273 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:26,273 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-17 07:54:26,273 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2021-12-17 07:54:26,273 INFO L87 Difference]: Start difference. First operand 92 states and 127 transitions. Second operand has 6 states, 5 states have (on average 5.4) internal successors, (27), 4 states have internal predecessors, (27), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2021-12-17 07:54:26,294 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:26,294 INFO L93 Difference]: Finished difference Result 99 states and 133 transitions. [2021-12-17 07:54:26,294 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-17 07:54:26,294 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 5.4) internal successors, (27), 4 states have internal predecessors, (27), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 35 [2021-12-17 07:54:26,295 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:26,295 INFO L225 Difference]: With dead ends: 99 [2021-12-17 07:54:26,295 INFO L226 Difference]: Without dead ends: 92 [2021-12-17 07:54:26,296 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2021-12-17 07:54:26,296 INFO L933 BasicCegarLoop]: 51 mSDtfsCounter, 5 mSDsluCounter, 192 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 243 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:26,296 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 243 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-17 07:54:26,297 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2021-12-17 07:54:26,301 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 80. [2021-12-17 07:54:26,301 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 63 states have (on average 1.3333333333333333) internal successors, (84), 66 states have internal predecessors, (84), 10 states have call successors, (10), 4 states have call predecessors, (10), 6 states have return successors, (15), 9 states have call predecessors, (15), 9 states have call successors, (15) [2021-12-17 07:54:26,301 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 109 transitions. [2021-12-17 07:54:26,302 INFO L78 Accepts]: Start accepts. Automaton has 80 states and 109 transitions. Word has length 35 [2021-12-17 07:54:26,302 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:26,302 INFO L470 AbstractCegarLoop]: Abstraction has 80 states and 109 transitions. [2021-12-17 07:54:26,302 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 5.4) internal successors, (27), 4 states have internal predecessors, (27), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2021-12-17 07:54:26,302 INFO L276 IsEmpty]: Start isEmpty. Operand 80 states and 109 transitions. [2021-12-17 07:54:26,303 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2021-12-17 07:54:26,303 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:26,303 INFO L514 BasicCegarLoop]: 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, 1, 1, 1, 1, 1, 1, 1] [2021-12-17 07:54:26,303 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2021-12-17 07:54:26,303 INFO L402 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:26,303 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:26,304 INFO L85 PathProgramCache]: Analyzing trace with hash 1846747895, now seen corresponding path program 1 times [2021-12-17 07:54:26,304 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:26,304 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1880531057] [2021-12-17 07:54:26,304 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:26,304 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:26,312 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,327 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:26,329 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,331 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 16 [2021-12-17 07:54:26,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,334 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2021-12-17 07:54:26,335 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,353 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-12-17 07:54:26,354 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:26,354 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1880531057] [2021-12-17 07:54:26,354 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1880531057] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-17 07:54:26,354 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-17 07:54:26,354 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2021-12-17 07:54:26,354 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1805974857] [2021-12-17 07:54:26,354 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-17 07:54:26,355 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2021-12-17 07:54:26,355 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:26,355 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2021-12-17 07:54:26,355 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2021-12-17 07:54:26,356 INFO L87 Difference]: Start difference. First operand 80 states and 109 transitions. Second operand has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2021-12-17 07:54:26,415 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:26,416 INFO L93 Difference]: Finished difference Result 130 states and 171 transitions. [2021-12-17 07:54:26,416 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2021-12-17 07:54:26,416 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 36 [2021-12-17 07:54:26,416 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:26,417 INFO L225 Difference]: With dead ends: 130 [2021-12-17 07:54:26,417 INFO L226 Difference]: Without dead ends: 62 [2021-12-17 07:54:26,417 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2021-12-17 07:54:26,418 INFO L933 BasicCegarLoop]: 42 mSDtfsCounter, 16 mSDsluCounter, 105 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 16 SdHoareTripleChecker+Valid, 147 SdHoareTripleChecker+Invalid, 52 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:26,418 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [16 Valid, 147 Invalid, 52 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-17 07:54:26,418 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 62 states. [2021-12-17 07:54:26,421 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 62 to 60. [2021-12-17 07:54:26,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 46 states have (on average 1.3043478260869565) internal successors, (60), 48 states have internal predecessors, (60), 8 states have call successors, (8), 4 states have call predecessors, (8), 5 states have return successors, (11), 7 states have call predecessors, (11), 7 states have call successors, (11) [2021-12-17 07:54:26,422 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 79 transitions. [2021-12-17 07:54:26,422 INFO L78 Accepts]: Start accepts. Automaton has 60 states and 79 transitions. Word has length 36 [2021-12-17 07:54:26,422 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:26,422 INFO L470 AbstractCegarLoop]: Abstraction has 60 states and 79 transitions. [2021-12-17 07:54:26,423 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2021-12-17 07:54:26,423 INFO L276 IsEmpty]: Start isEmpty. Operand 60 states and 79 transitions. [2021-12-17 07:54:26,423 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2021-12-17 07:54:26,423 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:26,423 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 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] [2021-12-17 07:54:26,424 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8 [2021-12-17 07:54:26,424 INFO L402 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:26,424 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:26,424 INFO L85 PathProgramCache]: Analyzing trace with hash -827934680, now seen corresponding path program 1 times [2021-12-17 07:54:26,424 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:26,424 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [693551838] [2021-12-17 07:54:26,424 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:26,425 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:26,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,518 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-17 07:54:26,521 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,551 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:26,553 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,569 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 29 [2021-12-17 07:54:26,571 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,574 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:26,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,577 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 1 proven. 22 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2021-12-17 07:54:26,577 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:26,577 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [693551838] [2021-12-17 07:54:26,577 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [693551838] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-17 07:54:26,577 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [20789628] [2021-12-17 07:54:26,577 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:26,578 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:26,578 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-17 07:54:26,592 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) [2021-12-17 07:54:26,595 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2021-12-17 07:54:26,693 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:26,696 INFO L263 TraceCheckSpWp]: Trace formula consists of 357 conjuncts, 39 conjunts are in the unsatisfiable core [2021-12-17 07:54:26,698 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-17 07:54:26,715 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-17 07:54:26,757 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-17 07:54:26,757 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2021-12-17 07:54:26,804 INFO L354 Elim1Store]: treesize reduction 30, result has 38.8 percent of original size [2021-12-17 07:54:26,805 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 40 treesize of output 55 [2021-12-17 07:54:26,809 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2021-12-17 07:54:26,817 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2021-12-17 07:54:26,839 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 25 [2021-12-17 07:54:26,869 INFO L354 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2021-12-17 07:54:26,870 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 3 new quantified variables, introduced 1 case distinctions, treesize of input 55 treesize of output 46 [2021-12-17 07:54:26,872 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 18 [2021-12-17 07:54:26,952 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 20 proven. 7 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2021-12-17 07:54:26,952 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-17 07:54:27,132 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:54:27,133 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 258 treesize of output 255 [2021-12-17 07:54:27,137 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 314 treesize of output 298 [2021-12-17 07:54:27,141 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 298 treesize of output 290 [2021-12-17 07:54:27,190 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2021-12-17 07:54:27,202 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 26 [2021-12-17 07:54:27,309 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 8 [2021-12-17 07:54:27,314 INFO L134 CoverageAnalysis]: Checked inductivity of 32 backedges. 0 proven. 23 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2021-12-17 07:54:27,314 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [20789628] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-17 07:54:27,314 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-17 07:54:27,315 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12, 12] total 22 [2021-12-17 07:54:27,315 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1604609640] [2021-12-17 07:54:27,315 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-17 07:54:27,315 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2021-12-17 07:54:27,315 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:27,316 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2021-12-17 07:54:27,316 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=67, Invalid=395, Unknown=0, NotChecked=0, Total=462 [2021-12-17 07:54:27,316 INFO L87 Difference]: Start difference. First operand 60 states and 79 transitions. Second operand has 22 states, 20 states have (on average 2.9) internal successors, (58), 22 states have internal predecessors, (58), 6 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 6 states have call successors, (8) [2021-12-17 07:54:27,661 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:27,661 INFO L93 Difference]: Finished difference Result 142 states and 202 transitions. [2021-12-17 07:54:27,661 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2021-12-17 07:54:27,661 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 20 states have (on average 2.9) internal successors, (58), 22 states have internal predecessors, (58), 6 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 6 states have call successors, (8) Word has length 46 [2021-12-17 07:54:27,662 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:27,662 INFO L225 Difference]: With dead ends: 142 [2021-12-17 07:54:27,663 INFO L226 Difference]: Without dead ends: 101 [2021-12-17 07:54:27,663 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 118 GetRequests, 85 SyntacticMatches, 4 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 217 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=163, Invalid=767, Unknown=0, NotChecked=0, Total=930 [2021-12-17 07:54:27,664 INFO L933 BasicCegarLoop]: 68 mSDtfsCounter, 164 mSDsluCounter, 381 mSDsCounter, 0 mSdLazyCounter, 349 mSolverCounterSat, 88 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 169 SdHoareTripleChecker+Valid, 449 SdHoareTripleChecker+Invalid, 496 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 88 IncrementalHoareTripleChecker+Valid, 349 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 59 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:27,664 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [169 Valid, 449 Invalid, 496 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [88 Valid, 349 Invalid, 0 Unknown, 59 Unchecked, 0.2s Time] [2021-12-17 07:54:27,664 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 101 states. [2021-12-17 07:54:27,669 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 101 to 78. [2021-12-17 07:54:27,670 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 78 states, 59 states have (on average 1.305084745762712) internal successors, (77), 62 states have internal predecessors, (77), 12 states have call successors, (12), 4 states have call predecessors, (12), 6 states have return successors, (21), 11 states have call predecessors, (21), 11 states have call successors, (21) [2021-12-17 07:54:27,670 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 78 states to 78 states and 110 transitions. [2021-12-17 07:54:27,670 INFO L78 Accepts]: Start accepts. Automaton has 78 states and 110 transitions. Word has length 46 [2021-12-17 07:54:27,670 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:27,670 INFO L470 AbstractCegarLoop]: Abstraction has 78 states and 110 transitions. [2021-12-17 07:54:27,671 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 20 states have (on average 2.9) internal successors, (58), 22 states have internal predecessors, (58), 6 states have call successors, (9), 2 states have call predecessors, (9), 4 states have return successors, (8), 3 states have call predecessors, (8), 6 states have call successors, (8) [2021-12-17 07:54:27,671 INFO L276 IsEmpty]: Start isEmpty. Operand 78 states and 110 transitions. [2021-12-17 07:54:27,671 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2021-12-17 07:54:27,671 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:27,671 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-17 07:54:27,715 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2021-12-17 07:54:27,890 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:27,890 INFO L402 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:27,890 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:27,891 INFO L85 PathProgramCache]: Analyzing trace with hash 828672736, now seen corresponding path program 1 times [2021-12-17 07:54:27,891 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:27,891 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1329089649] [2021-12-17 07:54:27,891 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:27,891 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:27,904 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:27,927 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-17 07:54:27,928 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:27,931 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:27,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:27,935 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2021-12-17 07:54:27,937 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:27,961 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:27,963 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:27,976 INFO L134 CoverageAnalysis]: Checked inductivity of 30 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2021-12-17 07:54:27,976 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:27,976 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1329089649] [2021-12-17 07:54:27,976 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1329089649] provided 1 perfect and 0 imperfect interpolant sequences [2021-12-17 07:54:27,976 INFO L186 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2021-12-17 07:54:27,976 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2021-12-17 07:54:27,977 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [357442058] [2021-12-17 07:54:27,977 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2021-12-17 07:54:27,977 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2021-12-17 07:54:27,977 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:27,977 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2021-12-17 07:54:27,978 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2021-12-17 07:54:27,978 INFO L87 Difference]: Start difference. First operand 78 states and 110 transitions. Second operand has 8 states, 7 states have (on average 3.857142857142857) internal successors, (27), 5 states have internal predecessors, (27), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) [2021-12-17 07:54:28,016 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:28,016 INFO L93 Difference]: Finished difference Result 97 states and 138 transitions. [2021-12-17 07:54:28,017 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2021-12-17 07:54:28,017 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 3.857142857142857) internal successors, (27), 5 states have internal predecessors, (27), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) Word has length 44 [2021-12-17 07:54:28,017 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:28,018 INFO L225 Difference]: With dead ends: 97 [2021-12-17 07:54:28,018 INFO L226 Difference]: Without dead ends: 95 [2021-12-17 07:54:28,018 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 10 SyntacticMatches, 1 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2021-12-17 07:54:28,019 INFO L933 BasicCegarLoop]: 52 mSDtfsCounter, 7 mSDsluCounter, 293 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 4 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 345 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 4 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:28,019 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 345 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [4 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-17 07:54:28,019 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 95 states. [2021-12-17 07:54:28,023 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 95 to 81. [2021-12-17 07:54:28,024 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 61 states have (on average 1.2950819672131149) internal successors, (79), 64 states have internal predecessors, (79), 12 states have call successors, (12), 4 states have call predecessors, (12), 7 states have return successors, (28), 12 states have call predecessors, (28), 11 states have call successors, (28) [2021-12-17 07:54:28,024 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 119 transitions. [2021-12-17 07:54:28,025 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 119 transitions. Word has length 44 [2021-12-17 07:54:28,025 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:28,025 INFO L470 AbstractCegarLoop]: Abstraction has 81 states and 119 transitions. [2021-12-17 07:54:28,025 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 3.857142857142857) internal successors, (27), 5 states have internal predecessors, (27), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 3 states have call predecessors, (4), 1 states have call successors, (4) [2021-12-17 07:54:28,025 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 119 transitions. [2021-12-17 07:54:28,026 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2021-12-17 07:54:28,026 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:28,026 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 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] [2021-12-17 07:54:28,026 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable10 [2021-12-17 07:54:28,026 INFO L402 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:28,026 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:28,026 INFO L85 PathProgramCache]: Analyzing trace with hash 803799756, now seen corresponding path program 1 times [2021-12-17 07:54:28,027 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:28,027 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1160114403] [2021-12-17 07:54:28,027 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:28,027 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:28,041 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:28,222 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-17 07:54:28,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:28,259 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:28,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:28,262 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2021-12-17 07:54:28,264 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:28,313 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:28,315 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:28,344 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 8 proven. 14 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2021-12-17 07:54:28,345 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:28,345 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1160114403] [2021-12-17 07:54:28,345 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1160114403] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-17 07:54:28,345 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [628709728] [2021-12-17 07:54:28,345 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:28,345 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:28,345 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-17 07:54:28,346 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) [2021-12-17 07:54:28,380 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2021-12-17 07:54:28,471 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:28,473 INFO L263 TraceCheckSpWp]: Trace formula consists of 292 conjuncts, 76 conjunts are in the unsatisfiable core [2021-12-17 07:54:28,476 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-17 07:54:28,547 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:28,549 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2021-12-17 07:54:28,551 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:28,552 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 23 [2021-12-17 07:54:28,557 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:28,559 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2021-12-17 07:54:28,562 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:28,563 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 23 treesize of output 23 [2021-12-17 07:54:29,117 INFO L173 IndexEqualityManager]: detected equality via solver [2021-12-17 07:54:29,124 INFO L354 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2021-12-17 07:54:29,125 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 61 treesize of output 50 [2021-12-17 07:54:29,131 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 33 [2021-12-17 07:54:31,944 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 23 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2021-12-17 07:54:31,944 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-17 07:54:32,402 INFO L173 IndexEqualityManager]: detected equality via solver [2021-12-17 07:54:32,406 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:54:32,407 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 182 treesize of output 174 [2021-12-17 07:54:32,410 INFO L173 IndexEqualityManager]: detected equality via solver [2021-12-17 07:54:32,414 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:54:32,414 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 182 treesize of output 109 [2021-12-17 07:54:32,453 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:54:32,453 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 5 new quantified variables, introduced 6 case distinctions, treesize of input 810 treesize of output 794 [2021-12-17 07:54:32,476 INFO L173 IndexEqualityManager]: detected equality via solver [2021-12-17 07:54:32,477 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 1036 treesize of output 974 [2021-12-17 07:54:32,492 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 966 treesize of output 940 [2021-12-17 07:54:32,505 INFO L173 IndexEqualityManager]: detected equality via solver [2021-12-17 07:54:32,513 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:54:32,514 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 1270 treesize of output 1120 [2021-12-17 07:54:33,383 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2021-12-17 07:54:33,426 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2021-12-17 07:54:33,503 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2021-12-17 07:54:34,329 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 4 [2021-12-17 07:54:34,341 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 26 [2021-12-17 07:54:34,879 INFO L354 Elim1Store]: treesize reduction 14, result has 57.6 percent of original size [2021-12-17 07:54:34,880 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 139 treesize of output 127 [2021-12-17 07:54:35,272 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 15 proven. 4 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2021-12-17 07:54:35,272 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [628709728] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-17 07:54:35,272 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-17 07:54:35,272 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17, 15] total 43 [2021-12-17 07:54:35,272 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [745971505] [2021-12-17 07:54:35,272 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-17 07:54:35,273 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 43 states [2021-12-17 07:54:35,273 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:35,273 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2021-12-17 07:54:35,274 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=153, Invalid=1647, Unknown=6, NotChecked=0, Total=1806 [2021-12-17 07:54:35,274 INFO L87 Difference]: Start difference. First operand 81 states and 119 transitions. Second operand has 43 states, 40 states have (on average 2.05) internal successors, (82), 42 states have internal predecessors, (82), 12 states have call successors, (12), 4 states have call predecessors, (12), 7 states have return successors, (11), 9 states have call predecessors, (11), 11 states have call successors, (11) [2021-12-17 07:54:45,289 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:45,289 INFO L93 Difference]: Finished difference Result 221 states and 325 transitions. [2021-12-17 07:54:45,290 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2021-12-17 07:54:45,290 INFO L78 Accepts]: Start accepts. Automaton has has 43 states, 40 states have (on average 2.05) internal successors, (82), 42 states have internal predecessors, (82), 12 states have call successors, (12), 4 states have call predecessors, (12), 7 states have return successors, (11), 9 states have call predecessors, (11), 11 states have call successors, (11) Word has length 43 [2021-12-17 07:54:45,290 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:45,291 INFO L225 Difference]: With dead ends: 221 [2021-12-17 07:54:45,291 INFO L226 Difference]: Without dead ends: 150 [2021-12-17 07:54:45,292 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 150 GetRequests, 79 SyntacticMatches, 2 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1139 ImplicationChecksByTransitivity, 12.7s TimeCoverageRelationStatistics Valid=449, Invalid=4495, Unknown=26, NotChecked=0, Total=4970 [2021-12-17 07:54:45,293 INFO L933 BasicCegarLoop]: 50 mSDtfsCounter, 185 mSDsluCounter, 948 mSDsCounter, 0 mSdLazyCounter, 788 mSolverCounterSat, 149 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 188 SdHoareTripleChecker+Valid, 998 SdHoareTripleChecker+Invalid, 1197 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 149 IncrementalHoareTripleChecker+Valid, 788 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 260 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:45,293 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [188 Valid, 998 Invalid, 1197 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [149 Valid, 788 Invalid, 0 Unknown, 260 Unchecked, 0.7s Time] [2021-12-17 07:54:45,293 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 150 states. [2021-12-17 07:54:45,305 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 150 to 108. [2021-12-17 07:54:45,306 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 108 states, 78 states have (on average 1.2692307692307692) internal successors, (99), 86 states have internal predecessors, (99), 15 states have call successors, (15), 6 states have call predecessors, (15), 14 states have return successors, (38), 15 states have call predecessors, (38), 14 states have call successors, (38) [2021-12-17 07:54:45,306 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 108 states to 108 states and 152 transitions. [2021-12-17 07:54:45,307 INFO L78 Accepts]: Start accepts. Automaton has 108 states and 152 transitions. Word has length 43 [2021-12-17 07:54:45,307 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:45,307 INFO L470 AbstractCegarLoop]: Abstraction has 108 states and 152 transitions. [2021-12-17 07:54:45,307 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 43 states, 40 states have (on average 2.05) internal successors, (82), 42 states have internal predecessors, (82), 12 states have call successors, (12), 4 states have call predecessors, (12), 7 states have return successors, (11), 9 states have call predecessors, (11), 11 states have call successors, (11) [2021-12-17 07:54:45,307 INFO L276 IsEmpty]: Start isEmpty. Operand 108 states and 152 transitions. [2021-12-17 07:54:45,308 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 44 [2021-12-17 07:54:45,308 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:45,308 INFO L514 BasicCegarLoop]: trace histogram [4, 4, 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] [2021-12-17 07:54:45,331 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2021-12-17 07:54:45,508 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:45,509 INFO L402 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:45,509 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:45,509 INFO L85 PathProgramCache]: Analyzing trace with hash -13848694, now seen corresponding path program 1 times [2021-12-17 07:54:45,509 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:45,509 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [284377926] [2021-12-17 07:54:45,510 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:45,510 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:45,537 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:45,602 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-17 07:54:45,604 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:45,607 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:45,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:45,610 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2021-12-17 07:54:45,611 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:45,613 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:45,616 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:45,618 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2021-12-17 07:54:45,618 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:45,618 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [284377926] [2021-12-17 07:54:45,618 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [284377926] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-17 07:54:45,618 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1858790615] [2021-12-17 07:54:45,618 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:45,619 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:45,619 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-17 07:54:45,636 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) [2021-12-17 07:54:45,643 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2021-12-17 07:54:45,729 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:45,731 INFO L263 TraceCheckSpWp]: Trace formula consists of 283 conjuncts, 43 conjunts are in the unsatisfiable core [2021-12-17 07:54:45,733 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-17 07:54:45,777 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:45,778 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2021-12-17 07:54:45,781 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:45,782 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 16 [2021-12-17 07:54:45,970 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 24 treesize of output 12 [2021-12-17 07:54:46,011 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 19 proven. 1 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2021-12-17 07:54:46,011 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-17 07:54:46,077 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 10 treesize of output 4 [2021-12-17 07:54:46,206 INFO L354 Elim1Store]: treesize reduction 21, result has 47.5 percent of original size [2021-12-17 07:54:46,207 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1 new quantified variables, introduced 2 case distinctions, treesize of input 23 treesize of output 29 [2021-12-17 07:54:46,210 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 [2021-12-17 07:54:46,212 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 7 [2021-12-17 07:54:46,273 INFO L134 CoverageAnalysis]: Checked inductivity of 28 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 27 trivial. 0 not checked. [2021-12-17 07:54:46,273 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1858790615] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-17 07:54:46,273 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-17 07:54:46,273 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9, 9] total 23 [2021-12-17 07:54:46,273 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [872089421] [2021-12-17 07:54:46,273 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-17 07:54:46,274 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 23 states [2021-12-17 07:54:46,274 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:46,275 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2021-12-17 07:54:46,275 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=65, Invalid=441, Unknown=0, NotChecked=0, Total=506 [2021-12-17 07:54:46,275 INFO L87 Difference]: Start difference. First operand 108 states and 152 transitions. Second operand has 23 states, 23 states have (on average 2.608695652173913) internal successors, (60), 23 states have internal predecessors, (60), 6 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2021-12-17 07:54:46,861 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:46,861 INFO L93 Difference]: Finished difference Result 248 states and 352 transitions. [2021-12-17 07:54:46,861 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2021-12-17 07:54:46,861 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.608695652173913) internal successors, (60), 23 states have internal predecessors, (60), 6 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) Word has length 43 [2021-12-17 07:54:46,862 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:46,862 INFO L225 Difference]: With dead ends: 248 [2021-12-17 07:54:46,863 INFO L226 Difference]: Without dead ends: 188 [2021-12-17 07:54:46,863 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 80 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 245 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=285, Invalid=1047, Unknown=0, NotChecked=0, Total=1332 [2021-12-17 07:54:46,864 INFO L933 BasicCegarLoop]: 85 mSDtfsCounter, 160 mSDsluCounter, 719 mSDsCounter, 0 mSdLazyCounter, 429 mSolverCounterSat, 65 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 163 SdHoareTripleChecker+Valid, 804 SdHoareTripleChecker+Invalid, 535 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 65 IncrementalHoareTripleChecker+Valid, 429 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 41 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:46,864 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [163 Valid, 804 Invalid, 535 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [65 Valid, 429 Invalid, 0 Unknown, 41 Unchecked, 0.2s Time] [2021-12-17 07:54:46,864 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 188 states. [2021-12-17 07:54:46,873 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 188 to 162. [2021-12-17 07:54:46,873 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 162 states, 120 states have (on average 1.2666666666666666) internal successors, (152), 127 states have internal predecessors, (152), 24 states have call successors, (24), 12 states have call predecessors, (24), 17 states have return successors, (52), 22 states have call predecessors, (52), 22 states have call successors, (52) [2021-12-17 07:54:46,874 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 162 states to 162 states and 228 transitions. [2021-12-17 07:54:46,874 INFO L78 Accepts]: Start accepts. Automaton has 162 states and 228 transitions. Word has length 43 [2021-12-17 07:54:46,875 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:46,875 INFO L470 AbstractCegarLoop]: Abstraction has 162 states and 228 transitions. [2021-12-17 07:54:46,875 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 23 states, 23 states have (on average 2.608695652173913) internal successors, (60), 23 states have internal predecessors, (60), 6 states have call successors, (9), 3 states have call predecessors, (9), 3 states have return successors, (8), 6 states have call predecessors, (8), 6 states have call successors, (8) [2021-12-17 07:54:46,875 INFO L276 IsEmpty]: Start isEmpty. Operand 162 states and 228 transitions. [2021-12-17 07:54:46,876 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2021-12-17 07:54:46,876 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:46,876 INFO L514 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-17 07:54:46,893 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2021-12-17 07:54:47,093 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2021-12-17 07:54:47,093 INFO L402 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:47,093 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:47,095 INFO L85 PathProgramCache]: Analyzing trace with hash 1865771786, now seen corresponding path program 1 times [2021-12-17 07:54:47,095 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:47,095 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [295716320] [2021-12-17 07:54:47,096 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:47,096 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:47,107 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:47,130 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2021-12-17 07:54:47,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:47,154 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:47,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:47,157 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 26 [2021-12-17 07:54:47,158 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:47,159 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 36 [2021-12-17 07:54:47,160 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:47,162 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 4 proven. 6 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2021-12-17 07:54:47,162 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:47,162 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [295716320] [2021-12-17 07:54:47,162 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [295716320] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-17 07:54:47,162 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2103788109] [2021-12-17 07:54:47,162 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:47,162 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:47,163 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-17 07:54:47,176 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) [2021-12-17 07:54:47,177 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2021-12-17 07:54:47,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:47,277 INFO L263 TraceCheckSpWp]: Trace formula consists of 315 conjuncts, 5 conjunts are in the unsatisfiable core [2021-12-17 07:54:47,279 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-17 07:54:47,372 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 9 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2021-12-17 07:54:47,373 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-17 07:54:47,462 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2021-12-17 07:54:47,462 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2103788109] provided 0 perfect and 2 imperfect interpolant sequences [2021-12-17 07:54:47,462 INFO L186 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2021-12-17 07:54:47,462 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 6, 6] total 14 [2021-12-17 07:54:47,463 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1179456922] [2021-12-17 07:54:47,463 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2021-12-17 07:54:47,463 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2021-12-17 07:54:47,463 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:47,464 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2021-12-17 07:54:47,464 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=28, Invalid=154, Unknown=0, NotChecked=0, Total=182 [2021-12-17 07:54:47,464 INFO L87 Difference]: Start difference. First operand 162 states and 228 transitions. Second operand has 14 states, 14 states have (on average 4.285714285714286) internal successors, (60), 14 states have internal predecessors, (60), 6 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 5 states have call predecessors, (9), 6 states have call successors, (9) [2021-12-17 07:54:47,606 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:47,606 INFO L93 Difference]: Finished difference Result 228 states and 312 transitions. [2021-12-17 07:54:47,606 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-12-17 07:54:47,607 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 4.285714285714286) internal successors, (60), 14 states have internal predecessors, (60), 6 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 5 states have call predecessors, (9), 6 states have call successors, (9) Word has length 46 [2021-12-17 07:54:47,607 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:47,607 INFO L225 Difference]: With dead ends: 228 [2021-12-17 07:54:47,607 INFO L226 Difference]: Without dead ends: 162 [2021-12-17 07:54:47,608 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 111 GetRequests, 94 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=76, Invalid=266, Unknown=0, NotChecked=0, Total=342 [2021-12-17 07:54:47,609 INFO L933 BasicCegarLoop]: 35 mSDtfsCounter, 163 mSDsluCounter, 181 mSDsCounter, 0 mSdLazyCounter, 138 mSolverCounterSat, 44 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 163 SdHoareTripleChecker+Valid, 216 SdHoareTripleChecker+Invalid, 182 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 44 IncrementalHoareTripleChecker+Valid, 138 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:47,609 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [163 Valid, 216 Invalid, 182 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [44 Valid, 138 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2021-12-17 07:54:47,609 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 162 states. [2021-12-17 07:54:47,619 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 162 to 155. [2021-12-17 07:54:47,619 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 155 states, 115 states have (on average 1.2260869565217392) internal successors, (141), 121 states have internal predecessors, (141), 22 states have call successors, (22), 12 states have call predecessors, (22), 17 states have return successors, (48), 21 states have call predecessors, (48), 20 states have call successors, (48) [2021-12-17 07:54:47,621 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 155 states to 155 states and 211 transitions. [2021-12-17 07:54:47,621 INFO L78 Accepts]: Start accepts. Automaton has 155 states and 211 transitions. Word has length 46 [2021-12-17 07:54:47,621 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:47,621 INFO L470 AbstractCegarLoop]: Abstraction has 155 states and 211 transitions. [2021-12-17 07:54:47,622 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 4.285714285714286) internal successors, (60), 14 states have internal predecessors, (60), 6 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 5 states have call predecessors, (9), 6 states have call successors, (9) [2021-12-17 07:54:47,622 INFO L276 IsEmpty]: Start isEmpty. Operand 155 states and 211 transitions. [2021-12-17 07:54:47,623 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2021-12-17 07:54:47,623 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:47,624 INFO L514 BasicCegarLoop]: trace histogram [5, 5, 4, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-17 07:54:47,644 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2021-12-17 07:54:47,843 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:47,844 INFO L402 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:47,844 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:47,844 INFO L85 PathProgramCache]: Analyzing trace with hash 1255123037, now seen corresponding path program 1 times [2021-12-17 07:54:47,844 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:47,844 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [828540491] [2021-12-17 07:54:47,844 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:47,844 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:47,867 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:47,891 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 9 [2021-12-17 07:54:47,893 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:47,905 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:47,907 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:47,915 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 30 [2021-12-17 07:54:47,918 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:47,921 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:47,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:47,924 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:47,924 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:47,926 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 0 proven. 14 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2021-12-17 07:54:47,926 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:47,926 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [828540491] [2021-12-17 07:54:47,926 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [828540491] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-17 07:54:47,926 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [361140010] [2021-12-17 07:54:47,927 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:47,927 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:47,927 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-17 07:54:47,928 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) [2021-12-17 07:54:47,929 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2021-12-17 07:54:48,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:48,080 INFO L263 TraceCheckSpWp]: Trace formula consists of 395 conjuncts, 59 conjunts are in the unsatisfiable core [2021-12-17 07:54:48,083 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-17 07:54:48,099 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2021-12-17 07:54:48,118 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:48,119 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2021-12-17 07:54:48,122 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:48,122 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 18 [2021-12-17 07:54:48,127 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:48,128 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 23 [2021-12-17 07:54:48,130 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:48,131 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 18 [2021-12-17 07:54:48,189 INFO L354 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2021-12-17 07:54:48,189 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2021-12-17 07:54:48,230 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:48,238 INFO L354 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2021-12-17 07:54:48,238 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 27 [2021-12-17 07:54:48,242 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:48,258 INFO L354 Elim1Store]: treesize reduction 11, result has 45.0 percent of original size [2021-12-17 07:54:48,258 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 19 treesize of output 27 [2021-12-17 07:54:48,428 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 7 [2021-12-17 07:54:48,429 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 7 [2021-12-17 07:54:48,474 INFO L134 CoverageAnalysis]: Checked inductivity of 57 backedges. 32 proven. 5 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2021-12-17 07:54:48,474 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-17 07:54:48,545 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 10 treesize of output 4 [2021-12-17 07:54:48,696 WARN L838 $PredicateComparison]: unable to prove that (and (forall ((v_ArrVal_1027 (Array Int Int)) (v_ArrVal_1025 (Array Int Int))) (= (select (select (store (store |c_#memory_$Pointer$.offset| |c_ULTIMATE.start_main_~n~0#1.base| v_ArrVal_1025) |c_ULTIMATE.start_main_~tail~0#1.base| v_ArrVal_1027) |c_ULTIMATE.start_main_~x~0#1.base|) (+ |c_ULTIMATE.start_main_~x~0#1.offset| 4)) 0)) (forall ((v_ArrVal_1026 (Array Int Int)) (v_ArrVal_1024 (Array Int Int))) (= (select (select (store (store |c_#memory_$Pointer$.base| |c_ULTIMATE.start_main_~n~0#1.base| v_ArrVal_1024) |c_ULTIMATE.start_main_~tail~0#1.base| v_ArrVal_1026) |c_ULTIMATE.start_main_~x~0#1.base|) (+ |c_ULTIMATE.start_main_~x~0#1.offset| 4)) 0))) is different from false [2021-12-17 07:54:48,795 INFO L354 Elim1Store]: treesize reduction 21, result has 47.5 percent of original size [2021-12-17 07:54:48,795 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1 new quantified variables, introduced 2 case distinctions, treesize of input 63 treesize of output 69 [2021-12-17 07:54:48,806 INFO L354 Elim1Store]: treesize reduction 21, result has 47.5 percent of original size [2021-12-17 07:54:48,806 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1 new quantified variables, introduced 2 case distinctions, treesize of input 69 treesize of output 74 [2021-12-17 07:54:48,812 INFO L354 Elim1Store]: treesize reduction 9, result has 10.0 percent of original size [2021-12-17 07:54:48,813 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1150 treesize of output 1092 [2021-12-17 07:54:48,820 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1092 treesize of output 1060 [2021-12-17 07:54:48,830 INFO L354 Elim1Store]: treesize reduction 9, result has 10.0 percent of original size [2021-12-17 07:54:48,830 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 1170 treesize of output 1154 [2021-12-17 07:54:48,838 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1154 treesize of output 1150 [2021-12-17 07:54:48,912 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1061 treesize of output 1053 [2021-12-17 07:54:48,929 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1053 treesize of output 1037 [2021-12-17 07:54:48,938 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1037 treesize of output 909 [2021-12-17 07:54:48,951 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 909 treesize of output 845 [2021-12-17 07:54:48,956 WARN L312 FreeRefinementEngine]: Interpolation failed due to KNOWN_DEPENDING: BigInteger out of long range [2021-12-17 07:54:48,957 INFO L186 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2021-12-17 07:54:48,957 INFO L199 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6] total 6 [2021-12-17 07:54:48,957 INFO L115 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1302994621] [2021-12-17 07:54:48,957 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2021-12-17 07:54:48,957 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2021-12-17 07:54:48,957 INFO L103 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-12-17 07:54:48,958 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-12-17 07:54:48,958 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=259, Unknown=3, NotChecked=32, Total=342 [2021-12-17 07:54:48,958 INFO L87 Difference]: Start difference. First operand 155 states and 211 transitions. Second operand has 6 states, 6 states have (on average 4.666666666666667) internal successors, (28), 4 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-17 07:54:48,980 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-12-17 07:54:48,980 INFO L93 Difference]: Finished difference Result 279 states and 381 transitions. [2021-12-17 07:54:48,981 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-12-17 07:54:48,981 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 4.666666666666667) internal successors, (28), 4 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) Word has length 54 [2021-12-17 07:54:48,981 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-12-17 07:54:48,982 INFO L225 Difference]: With dead ends: 279 [2021-12-17 07:54:48,982 INFO L226 Difference]: Without dead ends: 155 [2021-12-17 07:54:48,982 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 121 GetRequests, 101 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 28 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=52, Invalid=291, Unknown=3, NotChecked=34, Total=380 [2021-12-17 07:54:48,983 INFO L933 BasicCegarLoop]: 51 mSDtfsCounter, 1 mSDsluCounter, 192 mSDsCounter, 0 mSdLazyCounter, 15 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 243 SdHoareTripleChecker+Invalid, 15 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 15 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2021-12-17 07:54:48,983 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [1 Valid, 243 Invalid, 15 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 15 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2021-12-17 07:54:48,983 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 155 states. [2021-12-17 07:54:48,990 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 155 to 154. [2021-12-17 07:54:48,991 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 114 states have (on average 1.2105263157894737) internal successors, (138), 120 states have internal predecessors, (138), 22 states have call successors, (22), 12 states have call predecessors, (22), 17 states have return successors, (48), 21 states have call predecessors, (48), 20 states have call successors, (48) [2021-12-17 07:54:48,992 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 208 transitions. [2021-12-17 07:54:48,992 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 208 transitions. Word has length 54 [2021-12-17 07:54:48,992 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-12-17 07:54:48,992 INFO L470 AbstractCegarLoop]: Abstraction has 154 states and 208 transitions. [2021-12-17 07:54:48,992 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 4.666666666666667) internal successors, (28), 4 states have internal predecessors, (28), 2 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (4), 4 states have call predecessors, (4), 2 states have call successors, (4) [2021-12-17 07:54:48,992 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 208 transitions. [2021-12-17 07:54:48,993 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 64 [2021-12-17 07:54:48,993 INFO L506 BasicCegarLoop]: Found error trace [2021-12-17 07:54:48,993 INFO L514 BasicCegarLoop]: trace histogram [6, 6, 4, 4, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-12-17 07:54:49,029 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2021-12-17 07:54:49,230 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable14,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:49,231 INFO L402 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2021-12-17 07:54:49,231 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-12-17 07:54:49,231 INFO L85 PathProgramCache]: Analyzing trace with hash -79956808, now seen corresponding path program 2 times [2021-12-17 07:54:49,231 INFO L121 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-12-17 07:54:49,231 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [246450316] [2021-12-17 07:54:49,231 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-12-17 07:54:49,232 INFO L126 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2021-12-17 07:54:49,259 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:49,564 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2021-12-17 07:54:49,567 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:49,574 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:49,575 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:49,584 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:49,584 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:49,586 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 39 [2021-12-17 07:54:49,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:49,592 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:49,593 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:49,598 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 3 [2021-12-17 07:54:49,599 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-12-17 07:54:49,604 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2021-12-17 07:54:49,605 INFO L139 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2021-12-17 07:54:49,605 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [246450316] [2021-12-17 07:54:49,605 INFO L160 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [246450316] provided 0 perfect and 1 imperfect interpolant sequences [2021-12-17 07:54:49,605 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1958252402] [2021-12-17 07:54:49,605 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2021-12-17 07:54:49,605 INFO L168 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-12-17 07:54:49,605 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2021-12-17 07:54:49,606 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) [2021-12-17 07:54:49,607 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2021-12-17 07:54:49,749 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-12-17 07:54:49,749 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-12-17 07:54:49,754 INFO L263 TraceCheckSpWp]: Trace formula consists of 479 conjuncts, 123 conjunts are in the unsatisfiable core [2021-12-17 07:54:49,758 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-12-17 07:54:49,917 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:49,919 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:49,920 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 16 [2021-12-17 07:54:49,923 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:54:49,925 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 24 [2021-12-17 07:54:49,928 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2021-12-17 07:54:50,396 INFO L173 IndexEqualityManager]: detected equality via solver [2021-12-17 07:54:50,411 INFO L354 Elim1Store]: treesize reduction 83, result has 1.2 percent of original size [2021-12-17 07:54:50,411 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 7 select indices, 7 select index equivalence classes, 1 disjoint index pairs (out of 21 index pairs), introduced 9 new quantified variables, introduced 21 case distinctions, treesize of input 98 treesize of output 1 [2021-12-17 07:54:50,431 INFO L134 CoverageAnalysis]: Checked inductivity of 90 backedges. 50 proven. 16 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2021-12-17 07:54:50,431 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2021-12-17 07:54:50,466 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 10 treesize of output 4 [2021-12-17 07:54:51,129 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:54:51,130 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 7851 treesize of output 7153 [2021-12-17 07:54:52,856 INFO L354 Elim1Store]: treesize reduction 2892, result has 18.2 percent of original size [2021-12-17 07:54:52,857 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 13 select indices, 13 select index equivalence classes, 0 disjoint index pairs (out of 78 index pairs), introduced 15 new quantified variables, introduced 93 case distinctions, treesize of input 141993 treesize of output 134824 [2021-12-17 07:54:55,599 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:54:55,600 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 0 disjoint index pairs (out of 10 index pairs), introduced 6 new quantified variables, introduced 10 case distinctions, treesize of input 126693 treesize of output 121127 [2021-12-17 07:54:59,189 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:54:59,191 INFO L388 Elim1Store]: Elim1 did not use preprocessing 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 74357 treesize of output 74371 [2021-12-17 07:54:59,859 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:54:59,860 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 7 new quantified variables, introduced 15 case distinctions, treesize of input 104721 treesize of output 99676 [2021-12-17 07:55:25,934 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:55:25,969 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:55:25,969 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 38 treesize of output 38 [2021-12-17 07:55:26,677 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:55:26,725 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:55:26,726 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 38 treesize of output 38 [2021-12-17 07:55:27,588 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:55:27,627 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:55:27,628 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 38 treesize of output 38 [2021-12-17 07:55:29,335 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:55:29,393 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:55:29,397 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 0 disjoint index pairs (out of 6 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 44 treesize of output 75 [2021-12-17 07:55:36,205 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:55:36,241 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:55:36,241 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 38 treesize of output 38 [2021-12-17 07:55:54,321 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:55:54,321 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 36 treesize of output 71 [2021-12-17 07:55:55,155 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:55:55,156 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 36 treesize of output 71 [2021-12-17 07:55:55,945 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:55:55,945 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 36 treesize of output 71 [2021-12-17 07:55:57,581 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:55:57,582 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 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 42 treesize of output 116 [2021-12-17 07:56:06,602 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-12-17 07:56:06,664 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-12-17 07:56:06,665 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 36 treesize of output 32 [2021-12-17 07:57:41,403 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 4 [2021-12-17 07:57:45,316 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 4 [2021-12-17 07:57:47,510 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 4 [2021-12-17 07:57:49,796 WARN L234 Elim1Store]: Array PQE input equivalent to true [2021-12-17 07:57:49,851 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 4 [2021-12-17 07:57:52,314 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 4 Killed by 15