/usr/bin/java -Xmx16000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/automizer/concurrent/svcomp-Reach-32bit-Automizer_Default-noMmResRef-FA-NoLbe.epf -tc ../../../trunk/examples/toolchains/AutomizerBplInline.xml -i ../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/popl20-more/inc-subseq-array.wvr.bpl -------------------------------------------------------------------------------- This is Ultimate 0.2.1-7cd14b8b9f04096d8ddfd3d9cd8a4ac590fe5404-7cd14b8 [2021-03-10 23:51:58,343 INFO L177 SettingsManager]: Resetting all preferences to default values... [2021-03-10 23:51:58,345 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2021-03-10 23:51:58,375 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2021-03-10 23:51:58,375 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2021-03-10 23:51:58,377 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2021-03-10 23:51:58,379 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2021-03-10 23:51:58,383 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2021-03-10 23:51:58,385 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2021-03-10 23:51:58,388 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2021-03-10 23:51:58,388 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2021-03-10 23:51:58,389 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2021-03-10 23:51:58,390 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2021-03-10 23:51:58,391 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2021-03-10 23:51:58,392 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2021-03-10 23:51:58,393 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2021-03-10 23:51:58,395 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2021-03-10 23:51:58,395 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2021-03-10 23:51:58,397 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2021-03-10 23:51:58,403 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2021-03-10 23:51:58,404 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2021-03-10 23:51:58,405 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2021-03-10 23:51:58,406 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2021-03-10 23:51:58,407 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2021-03-10 23:51:58,412 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2021-03-10 23:51:58,412 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2021-03-10 23:51:58,412 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2021-03-10 23:51:58,413 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2021-03-10 23:51:58,414 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2021-03-10 23:51:58,414 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2021-03-10 23:51:58,414 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2021-03-10 23:51:58,415 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2021-03-10 23:51:58,416 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2021-03-10 23:51:58,417 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2021-03-10 23:51:58,417 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2021-03-10 23:51:58,417 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2021-03-10 23:51:58,418 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2021-03-10 23:51:58,418 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2021-03-10 23:51:58,418 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2021-03-10 23:51:58,418 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2021-03-10 23:51:58,419 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2021-03-10 23:51:58,422 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/automizer/concurrent/svcomp-Reach-32bit-Automizer_Default-noMmResRef-FA-NoLbe.epf [2021-03-10 23:51:58,449 INFO L113 SettingsManager]: Loading preferences was successful [2021-03-10 23:51:58,450 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2021-03-10 23:51:58,450 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2021-03-10 23:51:58,450 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2021-03-10 23:51:58,453 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2021-03-10 23:51:58,453 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2021-03-10 23:51:58,453 INFO L138 SettingsManager]: * Use SBE=true [2021-03-10 23:51:58,453 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2021-03-10 23:51:58,453 INFO L138 SettingsManager]: * sizeof long=4 [2021-03-10 23:51:58,454 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2021-03-10 23:51:58,454 INFO L138 SettingsManager]: * sizeof POINTER=4 [2021-03-10 23:51:58,454 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2021-03-10 23:51:58,454 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2021-03-10 23:51:58,455 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2021-03-10 23:51:58,455 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2021-03-10 23:51:58,455 INFO L138 SettingsManager]: * sizeof long double=12 [2021-03-10 23:51:58,455 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2021-03-10 23:51:58,455 INFO L138 SettingsManager]: * Use constant arrays=true [2021-03-10 23:51:58,455 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2021-03-10 23:51:58,455 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2021-03-10 23:51:58,455 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2021-03-10 23:51:58,455 INFO L138 SettingsManager]: * To the following directory=./dump/ [2021-03-10 23:51:58,456 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2021-03-10 23:51:58,456 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-03-10 23:51:58,456 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2021-03-10 23:51:58,456 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2021-03-10 23:51:58,456 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2021-03-10 23:51:58,456 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2021-03-10 23:51:58,456 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2021-03-10 23:51:58,456 INFO L138 SettingsManager]: * Large block encoding in concurrent analysis=OFF [2021-03-10 23:51:58,457 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2021-03-10 23:51:58,457 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 [2021-03-10 23:51:58,693 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2021-03-10 23:51:58,708 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2021-03-10 23:51:58,710 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2021-03-10 23:51:58,710 INFO L271 PluginConnector]: Initializing Boogie PL CUP Parser... [2021-03-10 23:51:58,711 INFO L275 PluginConnector]: Boogie PL CUP Parser initialized [2021-03-10 23:51:58,712 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/popl20-more/inc-subseq-array.wvr.bpl [2021-03-10 23:51:58,712 INFO L110 BoogieParser]: Parsing: '/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/concurrent/bpl/weaver-benchmarks/generated/popl20-more/inc-subseq-array.wvr.bpl' [2021-03-10 23:51:58,733 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2021-03-10 23:51:58,737 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2021-03-10 23:51:58,738 INFO L113 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2021-03-10 23:51:58,738 INFO L271 PluginConnector]: Initializing Boogie Procedure Inliner... [2021-03-10 23:51:58,738 INFO L275 PluginConnector]: Boogie Procedure Inliner initialized [2021-03-10 23:51:58,746 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.03 11:51:58" (1/1) ... [2021-03-10 23:51:58,751 INFO L185 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.03 11:51:58" (1/1) ... [2021-03-10 23:51:58,755 INFO L132 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2021-03-10 23:51:58,756 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2021-03-10 23:51:58,756 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2021-03-10 23:51:58,756 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2021-03-10 23:51:58,761 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.03 11:51:58" (1/1) ... [2021-03-10 23:51:58,761 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.03 11:51:58" (1/1) ... [2021-03-10 23:51:58,762 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.03 11:51:58" (1/1) ... [2021-03-10 23:51:58,762 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.03 11:51:58" (1/1) ... [2021-03-10 23:51:58,763 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.03 11:51:58" (1/1) ... [2021-03-10 23:51:58,766 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.03 11:51:58" (1/1) ... [2021-03-10 23:51:58,766 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.03 11:51:58" (1/1) ... [2021-03-10 23:51:58,767 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2021-03-10 23:51:58,768 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2021-03-10 23:51:58,768 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2021-03-10 23:51:58,768 INFO L275 PluginConnector]: RCFGBuilder initialized [2021-03-10 23:51:58,770 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.03 11:51:58" (1/1) ... No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2021-03-10 23:51:58,832 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread1 given in one single declaration [2021-03-10 23:51:58,833 INFO L130 BoogieDeclarations]: Found specification of procedure thread1 [2021-03-10 23:51:58,833 INFO L138 BoogieDeclarations]: Found implementation of procedure thread1 [2021-03-10 23:51:58,833 INFO L124 BoogieDeclarations]: Specification and implementation of procedure thread2 given in one single declaration [2021-03-10 23:51:58,833 INFO L130 BoogieDeclarations]: Found specification of procedure thread2 [2021-03-10 23:51:58,833 INFO L138 BoogieDeclarations]: Found implementation of procedure thread2 [2021-03-10 23:51:58,833 INFO L124 BoogieDeclarations]: Specification and implementation of procedure ULTIMATE.start given in one single declaration [2021-03-10 23:51:58,833 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2021-03-10 23:51:58,833 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2021-03-10 23:51:58,834 WARN L209 CfgBuilder]: User set CodeBlockSize to SequenceOfStatements but program contains fork statements. Overwriting the user preferences and setting CodeBlockSize to SingleStatement [2021-03-10 23:51:58,961 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2021-03-10 23:51:58,961 INFO L299 CfgBuilder]: Removed 0 assume(true) statements. [2021-03-10 23:51:58,962 INFO L202 PluginConnector]: Adding new model inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.03 11:51:58 BoogieIcfgContainer [2021-03-10 23:51:58,962 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2021-03-10 23:51:58,963 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2021-03-10 23:51:58,963 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2021-03-10 23:51:58,965 INFO L275 PluginConnector]: TraceAbstraction initialized [2021-03-10 23:51:58,965 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.boogie.parser AST 10.03 11:51:58" (1/2) ... [2021-03-10 23:51:58,965 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@135d3846 and model type inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 10.03 11:51:58, skipping insertion in model container [2021-03-10 23:51:58,966 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 10.03 11:51:58" (2/2) ... [2021-03-10 23:51:58,979 INFO L111 eAbstractionObserver]: Analyzing ICFG inc-subseq-array.wvr.bpl [2021-03-10 23:51:58,983 WARN L142 ceAbstractionStarter]: Switching off computation of Hoare annotation because input is a concurrent program [2021-03-10 23:51:58,983 INFO L153 ceAbstractionStarter]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2021-03-10 23:51:58,986 INFO L165 ceAbstractionStarter]: Appying trace abstraction to program that has 1 error locations. [2021-03-10 23:51:58,986 INFO L323 ceAbstractionStarter]: Constructing petrified ICFG for 1 thread instances. [2021-03-10 23:51:59,020 INFO L149 ThreadInstanceAdder]: Constructed 2 joinOtherThreadTransitions. [2021-03-10 23:51:59,030 INFO L253 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2021-03-10 23:51:59,055 INFO L376 AbstractCegarLoop]: Interprodecural is true [2021-03-10 23:51:59,056 INFO L377 AbstractCegarLoop]: Hoare is true [2021-03-10 23:51:59,056 INFO L378 AbstractCegarLoop]: Compute interpolants for FPandBP [2021-03-10 23:51:59,056 INFO L379 AbstractCegarLoop]: Backedges is STRAIGHT_LINE [2021-03-10 23:51:59,056 INFO L380 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2021-03-10 23:51:59,056 INFO L381 AbstractCegarLoop]: Difference is false [2021-03-10 23:51:59,056 INFO L382 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2021-03-10 23:51:59,056 INFO L386 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2021-03-10 23:51:59,071 INFO L100 iNet2FiniteAutomaton]: Start petriNet2FiniteAutomaton. Operand has 32 places, 28 transitions, 72 flow [2021-03-10 23:51:59,084 INFO L122 iNet2FiniteAutomaton]: Finished petriNet2FiniteAutomaton. Result has 65 states, 63 states have (on average 2.015873015873016) internal successors, (127), 64 states have internal predecessors, (127), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:51:59,085 INFO L276 IsEmpty]: Start isEmpty. Operand has 65 states, 63 states have (on average 2.015873015873016) internal successors, (127), 64 states have internal predecessors, (127), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:51:59,090 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2021-03-10 23:51:59,090 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:51:59,091 INFO L519 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:51:59,091 INFO L428 AbstractCegarLoop]: === Iteration 1 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:51:59,098 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:51:59,099 INFO L82 PathProgramCache]: Analyzing trace with hash 1034289359, now seen corresponding path program 1 times [2021-03-10 23:51:59,104 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:51:59,105 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [692091706] [2021-03-10 23:51:59,105 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:51:59,165 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:51:59,207 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:51:59,207 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [692091706] [2021-03-10 23:51:59,208 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-03-10 23:51:59,208 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-03-10 23:51:59,208 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [851128706] [2021-03-10 23:51:59,212 INFO L460 AbstractCegarLoop]: Interpolant automaton has 3 states [2021-03-10 23:51:59,212 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:51:59,222 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2021-03-10 23:51:59,223 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-03-10 23:51:59,225 INFO L87 Difference]: Start difference. First operand has 65 states, 63 states have (on average 2.015873015873016) internal successors, (127), 64 states have internal predecessors, (127), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Second operand has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:51:59,250 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:51:59,250 INFO L93 Difference]: Finished difference Result 104 states and 211 transitions. [2021-03-10 23:51:59,251 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2021-03-10 23:51:59,252 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 14 [2021-03-10 23:51:59,252 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:51:59,262 INFO L225 Difference]: With dead ends: 104 [2021-03-10 23:51:59,262 INFO L226 Difference]: Without dead ends: 87 [2021-03-10 23:51:59,263 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 6.4ms TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2021-03-10 23:51:59,274 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2021-03-10 23:51:59,296 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 71. [2021-03-10 23:51:59,298 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 71 states, 70 states have (on average 2.0285714285714285) internal successors, (142), 70 states have internal predecessors, (142), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:51:59,300 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 71 states to 71 states and 142 transitions. [2021-03-10 23:51:59,300 INFO L78 Accepts]: Start accepts. Automaton has 71 states and 142 transitions. Word has length 14 [2021-03-10 23:51:59,301 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:51:59,301 INFO L480 AbstractCegarLoop]: Abstraction has 71 states and 142 transitions. [2021-03-10 23:51:59,301 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 3 states have internal predecessors, (14), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:51:59,301 INFO L276 IsEmpty]: Start isEmpty. Operand 71 states and 142 transitions. [2021-03-10 23:51:59,302 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2021-03-10 23:51:59,302 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:51:59,302 INFO L519 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:51:59,302 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2021-03-10 23:51:59,302 INFO L428 AbstractCegarLoop]: === Iteration 2 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:51:59,305 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:51:59,305 INFO L82 PathProgramCache]: Analyzing trace with hash -690736212, now seen corresponding path program 1 times [2021-03-10 23:51:59,305 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:51:59,306 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1213103324] [2021-03-10 23:51:59,306 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:51:59,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:51:59,360 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:51:59,360 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1213103324] [2021-03-10 23:51:59,360 INFO L219 FreeRefinementEngine]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2021-03-10 23:51:59,360 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2021-03-10 23:51:59,360 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1069507938] [2021-03-10 23:51:59,361 INFO L460 AbstractCegarLoop]: Interpolant automaton has 4 states [2021-03-10 23:51:59,361 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:51:59,362 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2021-03-10 23:51:59,362 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2021-03-10 23:51:59,362 INFO L87 Difference]: Start difference. First operand 71 states and 142 transitions. Second operand has 4 states, 4 states have (on average 4.5) internal successors, (18), 3 states have internal predecessors, (18), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:51:59,398 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:51:59,398 INFO L93 Difference]: Finished difference Result 91 states and 175 transitions. [2021-03-10 23:51:59,398 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2021-03-10 23:51:59,398 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 3 states have internal predecessors, (18), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 18 [2021-03-10 23:51:59,399 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:51:59,401 INFO L225 Difference]: With dead ends: 91 [2021-03-10 23:51:59,401 INFO L226 Difference]: Without dead ends: 83 [2021-03-10 23:51:59,403 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 8.4ms TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2021-03-10 23:51:59,404 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states. [2021-03-10 23:51:59,410 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 83. [2021-03-10 23:51:59,412 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 83 states, 82 states have (on average 2.0121951219512195) internal successors, (165), 82 states have internal predecessors, (165), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:51:59,413 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 83 states to 83 states and 165 transitions. [2021-03-10 23:51:59,413 INFO L78 Accepts]: Start accepts. Automaton has 83 states and 165 transitions. Word has length 18 [2021-03-10 23:51:59,413 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:51:59,413 INFO L480 AbstractCegarLoop]: Abstraction has 83 states and 165 transitions. [2021-03-10 23:51:59,414 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 4 states, 4 states have (on average 4.5) internal successors, (18), 3 states have internal predecessors, (18), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:51:59,414 INFO L276 IsEmpty]: Start isEmpty. Operand 83 states and 165 transitions. [2021-03-10 23:51:59,415 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2021-03-10 23:51:59,415 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:51:59,415 INFO L519 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:51:59,415 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2021-03-10 23:51:59,415 INFO L428 AbstractCegarLoop]: === Iteration 3 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:51:59,416 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:51:59,416 INFO L82 PathProgramCache]: Analyzing trace with hash 1451962588, now seen corresponding path program 1 times [2021-03-10 23:51:59,416 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:51:59,416 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1656470004] [2021-03-10 23:51:59,417 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:51:59,448 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:51:59,534 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:51:59,535 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1656470004] [2021-03-10 23:51:59,535 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [898206715] [2021-03-10 23:51:59,536 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:51:59,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:51:59,598 INFO L263 TraceCheckSpWp]: Trace formula consists of 49 conjuncts, 11 conjunts are in the unsatisfiable core [2021-03-10 23:51:59,602 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:51:59,737 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 13 treesize of output 9 [2021-03-10 23:51:59,739 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:51:59,742 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:51:59,743 INFO L550 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:51:59,743 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:14, output treesize:7 [2021-03-10 23:51:59,797 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 11 treesize of output 7 [2021-03-10 23:51:59,799 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:51:59,802 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:51:59,802 INFO L550 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:51:59,803 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:12, output treesize:5 [2021-03-10 23:51:59,815 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:51:59,815 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:51:59,815 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 11 [2021-03-10 23:51:59,815 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1628165458] [2021-03-10 23:51:59,815 INFO L460 AbstractCegarLoop]: Interpolant automaton has 12 states [2021-03-10 23:51:59,815 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:51:59,816 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2021-03-10 23:51:59,816 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=94, Unknown=0, NotChecked=0, Total=132 [2021-03-10 23:51:59,816 INFO L87 Difference]: Start difference. First operand 83 states and 165 transitions. Second operand has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 11 states have internal predecessors, (32), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:51:59,911 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:51:59,911 INFO L93 Difference]: Finished difference Result 154 states and 314 transitions. [2021-03-10 23:51:59,911 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2021-03-10 23:51:59,911 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 11 states have internal predecessors, (32), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 23 [2021-03-10 23:51:59,912 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:51:59,912 INFO L225 Difference]: With dead ends: 154 [2021-03-10 23:51:59,912 INFO L226 Difference]: Without dead ends: 137 [2021-03-10 23:51:59,913 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 83.4ms TimeCoverageRelationStatistics Valid=47, Invalid=109, Unknown=0, NotChecked=0, Total=156 [2021-03-10 23:51:59,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 137 states. [2021-03-10 23:51:59,917 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 137 to 115. [2021-03-10 23:51:59,918 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 114 states have (on average 2.043859649122807) internal successors, (233), 114 states have internal predecessors, (233), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:51:59,918 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 233 transitions. [2021-03-10 23:51:59,918 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 233 transitions. Word has length 23 [2021-03-10 23:51:59,918 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:51:59,918 INFO L480 AbstractCegarLoop]: Abstraction has 115 states and 233 transitions. [2021-03-10 23:51:59,918 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 12 states, 12 states have (on average 2.6666666666666665) internal successors, (32), 11 states have internal predecessors, (32), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:51:59,918 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 233 transitions. [2021-03-10 23:51:59,919 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2021-03-10 23:51:59,919 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:51:59,919 INFO L519 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] [2021-03-10 23:52:00,134 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2021-03-10 23:52:00,135 INFO L428 AbstractCegarLoop]: === Iteration 4 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:00,136 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:00,136 INFO L82 PathProgramCache]: Analyzing trace with hash -1705470663, now seen corresponding path program 2 times [2021-03-10 23:52:00,136 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:00,136 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1570930973] [2021-03-10 23:52:00,136 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:00,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:00,207 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:00,208 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1570930973] [2021-03-10 23:52:00,208 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1537250537] [2021-03-10 23:52:00,208 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:00,245 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-03-10 23:52:00,245 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:00,246 INFO L263 TraceCheckSpWp]: Trace formula consists of 58 conjuncts, 4 conjunts are in the unsatisfiable core [2021-03-10 23:52:00,247 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:00,302 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:00,302 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:00,302 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 3] total 6 [2021-03-10 23:52:00,302 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1246515413] [2021-03-10 23:52:00,303 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2021-03-10 23:52:00,303 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:00,303 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-03-10 23:52:00,303 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2021-03-10 23:52:00,303 INFO L87 Difference]: Start difference. First operand 115 states and 233 transitions. Second operand has 7 states, 7 states have (on average 6.428571428571429) internal successors, (45), 6 states have internal predecessors, (45), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:00,372 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:00,372 INFO L93 Difference]: Finished difference Result 284 states and 566 transitions. [2021-03-10 23:52:00,372 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-03-10 23:52:00,373 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 6.428571428571429) internal successors, (45), 6 states have internal predecessors, (45), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 27 [2021-03-10 23:52:00,373 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:00,376 INFO L225 Difference]: With dead ends: 284 [2021-03-10 23:52:00,376 INFO L226 Difference]: Without dead ends: 264 [2021-03-10 23:52:00,376 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 32 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 29.8ms TimeCoverageRelationStatistics Valid=25, Invalid=31, Unknown=0, NotChecked=0, Total=56 [2021-03-10 23:52:00,377 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 264 states. [2021-03-10 23:52:00,398 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 264 to 230. [2021-03-10 23:52:00,398 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 230 states, 229 states have (on average 2.1222707423580784) internal successors, (486), 229 states have internal predecessors, (486), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:00,399 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 230 states to 230 states and 486 transitions. [2021-03-10 23:52:00,399 INFO L78 Accepts]: Start accepts. Automaton has 230 states and 486 transitions. Word has length 27 [2021-03-10 23:52:00,399 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:00,399 INFO L480 AbstractCegarLoop]: Abstraction has 230 states and 486 transitions. [2021-03-10 23:52:00,399 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 7 states, 7 states have (on average 6.428571428571429) internal successors, (45), 6 states have internal predecessors, (45), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:00,399 INFO L276 IsEmpty]: Start isEmpty. Operand 230 states and 486 transitions. [2021-03-10 23:52:00,400 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-03-10 23:52:00,400 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:00,400 INFO L519 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:00,615 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:00,615 INFO L428 AbstractCegarLoop]: === Iteration 5 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:00,616 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:00,616 INFO L82 PathProgramCache]: Analyzing trace with hash -906793463, now seen corresponding path program 3 times [2021-03-10 23:52:00,616 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:00,616 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [339788601] [2021-03-10 23:52:00,616 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:00,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:00,838 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:00,838 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [339788601] [2021-03-10 23:52:00,839 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1365803668] [2021-03-10 23:52:00,839 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-03-10 23:52:00,872 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2021-03-10 23:52:00,872 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:00,872 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 22 conjunts are in the unsatisfiable core [2021-03-10 23:52:00,873 INFO L286 TraceCheckSpWp]: Computing forward predicates... Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:01,053 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:01,054 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 29 treesize of output 27 [2021-03-10 23:52:01,063 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:01,067 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:01,068 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:01,068 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:30, output treesize:16 [2021-03-10 23:52:01,199 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:01,200 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 20 treesize of output 38 [2021-03-10 23:52:01,221 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 2 xjuncts. [2021-03-10 23:52:01,229 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:01,234 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:01,235 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:29, output treesize:21 [2021-03-10 23:52:01,295 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:01,295 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:01,295 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 27 [2021-03-10 23:52:01,296 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2033023099] [2021-03-10 23:52:01,296 INFO L460 AbstractCegarLoop]: Interpolant automaton has 28 states [2021-03-10 23:52:01,296 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:01,296 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2021-03-10 23:52:01,297 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=132, Invalid=624, Unknown=0, NotChecked=0, Total=756 [2021-03-10 23:52:01,297 INFO L87 Difference]: Start difference. First operand 230 states and 486 transitions. Second operand has 28 states, 28 states have (on average 2.107142857142857) internal successors, (59), 27 states have internal predecessors, (59), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:02,900 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:02,900 INFO L93 Difference]: Finished difference Result 650 states and 1347 transitions. [2021-03-10 23:52:02,901 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2021-03-10 23:52:02,901 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 28 states have (on average 2.107142857142857) internal successors, (59), 27 states have internal predecessors, (59), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 32 [2021-03-10 23:52:02,901 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:02,903 INFO L225 Difference]: With dead ends: 650 [2021-03-10 23:52:02,903 INFO L226 Difference]: Without dead ends: 573 [2021-03-10 23:52:02,904 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 989 ImplicationChecksByTransitivity, 1279.4ms TimeCoverageRelationStatistics Valid=665, Invalid=2875, Unknown=0, NotChecked=0, Total=3540 [2021-03-10 23:52:02,905 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 573 states. [2021-03-10 23:52:02,912 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 573 to 386. [2021-03-10 23:52:02,913 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 386 states, 385 states have (on average 2.1818181818181817) internal successors, (840), 385 states have internal predecessors, (840), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:02,914 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 386 states to 386 states and 840 transitions. [2021-03-10 23:52:02,914 INFO L78 Accepts]: Start accepts. Automaton has 386 states and 840 transitions. Word has length 32 [2021-03-10 23:52:02,914 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:02,914 INFO L480 AbstractCegarLoop]: Abstraction has 386 states and 840 transitions. [2021-03-10 23:52:02,914 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 28 states, 28 states have (on average 2.107142857142857) internal successors, (59), 27 states have internal predecessors, (59), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:02,914 INFO L276 IsEmpty]: Start isEmpty. Operand 386 states and 840 transitions. [2021-03-10 23:52:02,915 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-03-10 23:52:02,915 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:02,916 INFO L519 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:03,137 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:03,137 INFO L428 AbstractCegarLoop]: === Iteration 6 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:03,138 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:03,138 INFO L82 PathProgramCache]: Analyzing trace with hash -1731045687, now seen corresponding path program 4 times [2021-03-10 23:52:03,138 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:03,138 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [641709531] [2021-03-10 23:52:03,138 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:03,146 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:03,320 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-03-10 23:52:03,321 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [641709531] [2021-03-10 23:52:03,321 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2112696709] [2021-03-10 23:52:03,321 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:03,359 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-03-10 23:52:03,360 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:03,360 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 23 conjunts are in the unsatisfiable core [2021-03-10 23:52:03,361 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:03,618 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:03,619 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 26 treesize of output 26 [2021-03-10 23:52:03,623 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:03,630 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:03,631 INFO L550 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-03-10 23:52:03,631 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:44, output treesize:30 [2021-03-10 23:52:03,697 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:03,697 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:03,698 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 10 [2021-03-10 23:52:03,699 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:03,703 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:03,705 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:03,705 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:35, output treesize:5 [2021-03-10 23:52:03,714 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 1 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:03,714 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:03,714 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14] total 23 [2021-03-10 23:52:03,714 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1286174142] [2021-03-10 23:52:03,714 INFO L460 AbstractCegarLoop]: Interpolant automaton has 24 states [2021-03-10 23:52:03,714 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:03,715 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 24 interpolants. [2021-03-10 23:52:03,715 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=444, Unknown=0, NotChecked=0, Total=552 [2021-03-10 23:52:03,715 INFO L87 Difference]: Start difference. First operand 386 states and 840 transitions. Second operand has 24 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 23 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:04,307 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:04,307 INFO L93 Difference]: Finished difference Result 1023 states and 2148 transitions. [2021-03-10 23:52:04,307 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2021-03-10 23:52:04,307 INFO L78 Accepts]: Start accepts. Automaton has has 24 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 23 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 32 [2021-03-10 23:52:04,308 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:04,310 INFO L225 Difference]: With dead ends: 1023 [2021-03-10 23:52:04,310 INFO L226 Difference]: Without dead ends: 878 [2021-03-10 23:52:04,311 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 23 SyntacticMatches, 2 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 501 ImplicationChecksByTransitivity, 543.9ms TimeCoverageRelationStatistics Valid=289, Invalid=1271, Unknown=0, NotChecked=0, Total=1560 [2021-03-10 23:52:04,312 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 878 states. [2021-03-10 23:52:04,319 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 878 to 432. [2021-03-10 23:52:04,319 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 432 states, 431 states have (on average 2.1786542923433876) internal successors, (939), 431 states have internal predecessors, (939), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:04,320 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 432 states to 432 states and 939 transitions. [2021-03-10 23:52:04,321 INFO L78 Accepts]: Start accepts. Automaton has 432 states and 939 transitions. Word has length 32 [2021-03-10 23:52:04,321 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:04,321 INFO L480 AbstractCegarLoop]: Abstraction has 432 states and 939 transitions. [2021-03-10 23:52:04,321 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 24 states, 24 states have (on average 2.2916666666666665) internal successors, (55), 23 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:04,321 INFO L276 IsEmpty]: Start isEmpty. Operand 432 states and 939 transitions. [2021-03-10 23:52:04,322 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-03-10 23:52:04,322 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:04,322 INFO L519 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:04,531 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,5 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:04,531 INFO L428 AbstractCegarLoop]: === Iteration 7 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:04,532 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:04,532 INFO L82 PathProgramCache]: Analyzing trace with hash 1528740313, now seen corresponding path program 5 times [2021-03-10 23:52:04,532 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:04,532 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1483475216] [2021-03-10 23:52:04,532 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:04,569 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:04,834 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:04,835 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1483475216] [2021-03-10 23:52:04,835 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [173369355] [2021-03-10 23:52:04,835 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:04,859 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2021-03-10 23:52:04,859 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:04,860 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 21 conjunts are in the unsatisfiable core [2021-03-10 23:52:04,865 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:05,074 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:05,074 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 24 treesize of output 24 [2021-03-10 23:52:05,079 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:05,086 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:05,087 INFO L550 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-03-10 23:52:05,087 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:38, output treesize:24 [2021-03-10 23:52:05,187 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:05,187 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:05,188 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 10 [2021-03-10 23:52:05,189 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:05,194 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:05,195 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:05,195 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:29, output treesize:5 [2021-03-10 23:52:05,205 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:05,206 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:05,206 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14] total 24 [2021-03-10 23:52:05,206 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1781088506] [2021-03-10 23:52:05,206 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2021-03-10 23:52:05,206 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:05,206 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2021-03-10 23:52:05,207 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=108, Invalid=492, Unknown=0, NotChecked=0, Total=600 [2021-03-10 23:52:05,207 INFO L87 Difference]: Start difference. First operand 432 states and 939 transitions. Second operand has 25 states, 25 states have (on average 2.2) internal successors, (55), 24 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:05,908 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:05,908 INFO L93 Difference]: Finished difference Result 1081 states and 2273 transitions. [2021-03-10 23:52:05,908 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2021-03-10 23:52:05,908 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 2.2) internal successors, (55), 24 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 32 [2021-03-10 23:52:05,908 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:05,911 INFO L225 Difference]: With dead ends: 1081 [2021-03-10 23:52:05,911 INFO L226 Difference]: Without dead ends: 927 [2021-03-10 23:52:05,912 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 63 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 498 ImplicationChecksByTransitivity, 587.2ms TimeCoverageRelationStatistics Valid=295, Invalid=1345, Unknown=0, NotChecked=0, Total=1640 [2021-03-10 23:52:05,913 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 927 states. [2021-03-10 23:52:05,919 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 927 to 450. [2021-03-10 23:52:05,920 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 450 states, 449 states have (on average 2.1848552338530065) internal successors, (981), 449 states have internal predecessors, (981), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:05,921 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 450 states to 450 states and 981 transitions. [2021-03-10 23:52:05,921 INFO L78 Accepts]: Start accepts. Automaton has 450 states and 981 transitions. Word has length 32 [2021-03-10 23:52:05,921 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:05,921 INFO L480 AbstractCegarLoop]: Abstraction has 450 states and 981 transitions. [2021-03-10 23:52:05,921 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 25 states, 25 states have (on average 2.2) internal successors, (55), 24 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:05,921 INFO L276 IsEmpty]: Start isEmpty. Operand 450 states and 981 transitions. [2021-03-10 23:52:05,922 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-03-10 23:52:05,922 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:05,922 INFO L519 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:06,135 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable22 [2021-03-10 23:52:06,135 INFO L428 AbstractCegarLoop]: === Iteration 8 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:06,136 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:06,136 INFO L82 PathProgramCache]: Analyzing trace with hash -897893841, now seen corresponding path program 6 times [2021-03-10 23:52:06,136 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:06,136 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [28202224] [2021-03-10 23:52:06,136 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:06,142 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:06,300 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-03-10 23:52:06,300 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [28202224] [2021-03-10 23:52:06,300 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [230342557] [2021-03-10 23:52:06,300 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:06,320 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2021-03-10 23:52:06,320 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:06,321 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 23 conjunts are in the unsatisfiable core [2021-03-10 23:52:06,322 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:06,541 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:06,541 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 26 treesize of output 26 [2021-03-10 23:52:06,544 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:06,550 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:06,551 INFO L550 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-03-10 23:52:06,552 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:44, output treesize:30 [2021-03-10 23:52:06,616 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:06,617 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:06,618 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:06,618 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 10 [2021-03-10 23:52:06,620 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:06,625 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:06,626 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:06,626 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:35, output treesize:5 [2021-03-10 23:52:06,646 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 2 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:06,647 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:06,647 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14] total 22 [2021-03-10 23:52:06,647 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [398343628] [2021-03-10 23:52:06,647 INFO L460 AbstractCegarLoop]: Interpolant automaton has 23 states [2021-03-10 23:52:06,647 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:06,648 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 23 interpolants. [2021-03-10 23:52:06,648 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=103, Invalid=403, Unknown=0, NotChecked=0, Total=506 [2021-03-10 23:52:06,648 INFO L87 Difference]: Start difference. First operand 450 states and 981 transitions. Second operand has 23 states, 23 states have (on average 2.347826086956522) internal successors, (54), 22 states have internal predecessors, (54), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:07,130 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:07,130 INFO L93 Difference]: Finished difference Result 1039 states and 2202 transitions. [2021-03-10 23:52:07,131 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2021-03-10 23:52:07,131 INFO L78 Accepts]: Start accepts. Automaton has has 23 states, 23 states have (on average 2.347826086956522) internal successors, (54), 22 states have internal predecessors, (54), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 32 [2021-03-10 23:52:07,131 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:07,134 INFO L225 Difference]: With dead ends: 1039 [2021-03-10 23:52:07,134 INFO L226 Difference]: Without dead ends: 929 [2021-03-10 23:52:07,135 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 57 GetRequests, 22 SyntacticMatches, 4 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 334 ImplicationChecksByTransitivity, 426.7ms TimeCoverageRelationStatistics Valid=206, Invalid=850, Unknown=0, NotChecked=0, Total=1056 [2021-03-10 23:52:07,136 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 929 states. [2021-03-10 23:52:07,143 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 929 to 487. [2021-03-10 23:52:07,144 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 487 states, 486 states have (on average 2.1790123456790123) internal successors, (1059), 486 states have internal predecessors, (1059), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:07,145 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 487 states to 487 states and 1059 transitions. [2021-03-10 23:52:07,145 INFO L78 Accepts]: Start accepts. Automaton has 487 states and 1059 transitions. Word has length 32 [2021-03-10 23:52:07,145 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:07,145 INFO L480 AbstractCegarLoop]: Abstraction has 487 states and 1059 transitions. [2021-03-10 23:52:07,145 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 23 states, 23 states have (on average 2.347826086956522) internal successors, (54), 22 states have internal predecessors, (54), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:07,145 INFO L276 IsEmpty]: Start isEmpty. Operand 487 states and 1059 transitions. [2021-03-10 23:52:07,146 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2021-03-10 23:52:07,146 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:07,146 INFO L519 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:07,359 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable26,7 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:07,359 INFO L428 AbstractCegarLoop]: === Iteration 9 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:07,360 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:07,360 INFO L82 PathProgramCache]: Analyzing trace with hash -960521271, now seen corresponding path program 7 times [2021-03-10 23:52:07,360 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:07,360 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1691052986] [2021-03-10 23:52:07,360 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:07,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:07,545 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:07,545 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1691052986] [2021-03-10 23:52:07,545 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [890103843] [2021-03-10 23:52:07,545 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:07,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:07,564 INFO L263 TraceCheckSpWp]: Trace formula consists of 68 conjuncts, 23 conjunts are in the unsatisfiable core [2021-03-10 23:52:07,565 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:07,775 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:07,775 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 26 treesize of output 26 [2021-03-10 23:52:07,778 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:07,785 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:07,787 INFO L550 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-03-10 23:52:07,787 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:44, output treesize:30 [2021-03-10 23:52:07,874 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:07,875 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:07,876 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:07,876 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 10 [2021-03-10 23:52:07,877 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:07,881 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:07,882 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:07,882 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:35, output treesize:5 [2021-03-10 23:52:07,889 INFO L134 CoverageAnalysis]: Checked inductivity of 13 backedges. 0 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:07,890 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:07,890 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 14] total 24 [2021-03-10 23:52:07,891 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2005074132] [2021-03-10 23:52:07,892 INFO L460 AbstractCegarLoop]: Interpolant automaton has 25 states [2021-03-10 23:52:07,892 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:07,892 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2021-03-10 23:52:07,892 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=106, Invalid=494, Unknown=0, NotChecked=0, Total=600 [2021-03-10 23:52:07,893 INFO L87 Difference]: Start difference. First operand 487 states and 1059 transitions. Second operand has 25 states, 25 states have (on average 2.2) internal successors, (55), 24 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:08,394 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:08,395 INFO L93 Difference]: Finished difference Result 1050 states and 2227 transitions. [2021-03-10 23:52:08,401 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2021-03-10 23:52:08,401 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 25 states have (on average 2.2) internal successors, (55), 24 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 32 [2021-03-10 23:52:08,402 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:08,404 INFO L225 Difference]: With dead ends: 1050 [2021-03-10 23:52:08,404 INFO L226 Difference]: Without dead ends: 952 [2021-03-10 23:52:08,405 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 23 SyntacticMatches, 1 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 294 ImplicationChecksByTransitivity, 481.5ms TimeCoverageRelationStatistics Valid=182, Invalid=810, Unknown=0, NotChecked=0, Total=992 [2021-03-10 23:52:08,406 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 952 states. [2021-03-10 23:52:08,416 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 952 to 467. [2021-03-10 23:52:08,417 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 467 states, 466 states have (on average 2.1609442060085837) internal successors, (1007), 466 states have internal predecessors, (1007), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:08,418 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 467 states to 467 states and 1007 transitions. [2021-03-10 23:52:08,418 INFO L78 Accepts]: Start accepts. Automaton has 467 states and 1007 transitions. Word has length 32 [2021-03-10 23:52:08,419 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:08,419 INFO L480 AbstractCegarLoop]: Abstraction has 467 states and 1007 transitions. [2021-03-10 23:52:08,419 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 25 states, 25 states have (on average 2.2) internal successors, (55), 24 states have internal predecessors, (55), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:08,419 INFO L276 IsEmpty]: Start isEmpty. Operand 467 states and 1007 transitions. [2021-03-10 23:52:08,420 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2021-03-10 23:52:08,420 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:08,420 INFO L519 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:08,631 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable30,8 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:08,633 INFO L428 AbstractCegarLoop]: === Iteration 10 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:08,633 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:08,633 INFO L82 PathProgramCache]: Analyzing trace with hash 2010412006, now seen corresponding path program 8 times [2021-03-10 23:52:08,633 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:08,634 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1774675846] [2021-03-10 23:52:08,634 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:08,638 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:08,671 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 15 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:08,671 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1774675846] [2021-03-10 23:52:08,671 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1037409728] [2021-03-10 23:52:08,671 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-03-10 23:52:08,705 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-03-10 23:52:08,706 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:08,706 INFO L263 TraceCheckSpWp]: Trace formula consists of 77 conjuncts, 6 conjunts are in the unsatisfiable core [2021-03-10 23:52:08,707 INFO L286 TraceCheckSpWp]: Computing forward predicates... Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:08,768 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 15 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:08,768 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:08,768 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 4] total 8 [2021-03-10 23:52:08,769 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [633711530] [2021-03-10 23:52:08,769 INFO L460 AbstractCegarLoop]: Interpolant automaton has 9 states [2021-03-10 23:52:08,769 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:08,770 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2021-03-10 23:52:08,770 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2021-03-10 23:52:08,770 INFO L87 Difference]: Start difference. First operand 467 states and 1007 transitions. Second operand has 9 states, 9 states have (on average 6.444444444444445) internal successors, (58), 8 states have internal predecessors, (58), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:08,826 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:08,826 INFO L93 Difference]: Finished difference Result 885 states and 1908 transitions. [2021-03-10 23:52:08,826 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2021-03-10 23:52:08,826 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 6.444444444444445) internal successors, (58), 8 states have internal predecessors, (58), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 36 [2021-03-10 23:52:08,827 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:08,830 INFO L225 Difference]: With dead ends: 885 [2021-03-10 23:52:08,830 INFO L226 Difference]: Without dead ends: 847 [2021-03-10 23:52:08,831 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 12 ImplicationChecksByTransitivity, 32.0ms TimeCoverageRelationStatistics Valid=39, Invalid=51, Unknown=0, NotChecked=0, Total=90 [2021-03-10 23:52:08,832 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 847 states. [2021-03-10 23:52:08,839 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 847 to 716. [2021-03-10 23:52:08,840 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 716 states, 715 states have (on average 2.1846153846153844) internal successors, (1562), 715 states have internal predecessors, (1562), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:08,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 716 states to 716 states and 1562 transitions. [2021-03-10 23:52:08,842 INFO L78 Accepts]: Start accepts. Automaton has 716 states and 1562 transitions. Word has length 36 [2021-03-10 23:52:08,842 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:08,842 INFO L480 AbstractCegarLoop]: Abstraction has 716 states and 1562 transitions. [2021-03-10 23:52:08,842 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 9 states, 9 states have (on average 6.444444444444445) internal successors, (58), 8 states have internal predecessors, (58), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:08,842 INFO L276 IsEmpty]: Start isEmpty. Operand 716 states and 1562 transitions. [2021-03-10 23:52:08,844 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-03-10 23:52:08,844 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:08,844 INFO L519 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:09,062 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable34 [2021-03-10 23:52:09,063 INFO L428 AbstractCegarLoop]: === Iteration 11 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:09,063 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:09,064 INFO L82 PathProgramCache]: Analyzing trace with hash -1466399466, now seen corresponding path program 9 times [2021-03-10 23:52:09,064 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:09,064 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1067968366] [2021-03-10 23:52:09,064 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:09,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:09,437 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:09,437 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1067968366] [2021-03-10 23:52:09,438 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [109903602] [2021-03-10 23:52:09,438 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:09,474 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-03-10 23:52:09,474 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:09,475 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 36 conjunts are in the unsatisfiable core [2021-03-10 23:52:09,476 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:09,772 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:09,772 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 45 treesize of output 53 [2021-03-10 23:52:09,779 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:09,819 INFO L628 ElimStorePlain]: treesize reduction 43, result has 60.2 percent of original size [2021-03-10 23:52:09,822 INFO L550 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:09,822 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:56, output treesize:37 [2021-03-10 23:52:10,104 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:10,106 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:10,106 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:10,108 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:10,108 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:10,120 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:10,120 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 3 disjoint index pairs (out of 10 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 33 treesize of output 41 [2021-03-10 23:52:10,134 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 2 xjuncts. [2021-03-10 23:52:10,146 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:10,152 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:10,152 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:52, output treesize:17 [2021-03-10 23:52:10,212 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:10,212 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:10,212 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 21] total 39 [2021-03-10 23:52:10,212 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1135046966] [2021-03-10 23:52:10,213 INFO L460 AbstractCegarLoop]: Interpolant automaton has 40 states [2021-03-10 23:52:10,213 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:10,213 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2021-03-10 23:52:10,213 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=228, Invalid=1332, Unknown=0, NotChecked=0, Total=1560 [2021-03-10 23:52:10,214 INFO L87 Difference]: Start difference. First operand 716 states and 1562 transitions. Second operand has 40 states, 40 states have (on average 1.9) internal successors, (76), 39 states have internal predecessors, (76), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:14,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:14,815 INFO L93 Difference]: Finished difference Result 2858 states and 6129 transitions. [2021-03-10 23:52:14,815 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 85 states. [2021-03-10 23:52:14,815 INFO L78 Accepts]: Start accepts. Automaton has has 40 states, 40 states have (on average 1.9) internal successors, (76), 39 states have internal predecessors, (76), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-03-10 23:52:14,816 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:14,823 INFO L225 Difference]: With dead ends: 2858 [2021-03-10 23:52:14,823 INFO L226 Difference]: Without dead ends: 2546 [2021-03-10 23:52:14,825 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 136 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 111 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4053 ImplicationChecksByTransitivity, 3321.2ms TimeCoverageRelationStatistics Valid=1710, Invalid=10946, Unknown=0, NotChecked=0, Total=12656 [2021-03-10 23:52:14,828 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2546 states. [2021-03-10 23:52:14,842 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2546 to 740. [2021-03-10 23:52:14,843 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 740 states, 739 states have (on average 2.1502029769959403) internal successors, (1589), 739 states have internal predecessors, (1589), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:14,844 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 740 states to 740 states and 1589 transitions. [2021-03-10 23:52:14,844 INFO L78 Accepts]: Start accepts. Automaton has 740 states and 1589 transitions. Word has length 41 [2021-03-10 23:52:14,844 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:14,844 INFO L480 AbstractCegarLoop]: Abstraction has 740 states and 1589 transitions. [2021-03-10 23:52:14,845 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 40 states, 40 states have (on average 1.9) internal successors, (76), 39 states have internal predecessors, (76), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:14,845 INFO L276 IsEmpty]: Start isEmpty. Operand 740 states and 1589 transitions. [2021-03-10 23:52:14,846 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-03-10 23:52:14,846 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:14,846 INFO L519 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:15,061 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable35,10 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:15,061 INFO L428 AbstractCegarLoop]: === Iteration 12 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:15,062 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:15,062 INFO L82 PathProgramCache]: Analyzing trace with hash 1999894166, now seen corresponding path program 10 times [2021-03-10 23:52:15,062 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:15,062 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [894377047] [2021-03-10 23:52:15,062 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:15,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:15,384 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 32 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-03-10 23:52:15,384 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [894377047] [2021-03-10 23:52:15,384 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1007668345] [2021-03-10 23:52:15,384 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:15,420 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-03-10 23:52:15,420 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:15,421 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 35 conjunts are in the unsatisfiable core [2021-03-10 23:52:15,422 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:15,990 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:15,991 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 42 treesize of output 52 [2021-03-10 23:52:15,995 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:16,039 INFO L628 ElimStorePlain]: treesize reduction 16, result has 84.3 percent of original size [2021-03-10 23:52:16,050 INFO L550 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-03-10 23:52:16,050 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 5 variables, input treesize:60, output treesize:65 [2021-03-10 23:52:16,348 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:16,349 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:16,350 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:16,351 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:16,351 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:16,352 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:16,353 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:16,353 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:16,358 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:16,359 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:16,359 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 3 disjoint index pairs (out of 10 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 13 [2021-03-10 23:52:16,361 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:16,363 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:16,364 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:16,365 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:16,366 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:16,366 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:16,367 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:16,367 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:16,368 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:16,368 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 3 disjoint index pairs (out of 10 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 16 [2021-03-10 23:52:16,370 INFO L550 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:16,374 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:16,375 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:16,375 INFO L247 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:104, output treesize:5 [2021-03-10 23:52:16,384 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 1 proven. 32 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:16,384 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:16,384 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 20] total 35 [2021-03-10 23:52:16,384 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1423736144] [2021-03-10 23:52:16,385 INFO L460 AbstractCegarLoop]: Interpolant automaton has 36 states [2021-03-10 23:52:16,385 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:16,385 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2021-03-10 23:52:16,385 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=176, Invalid=1084, Unknown=0, NotChecked=0, Total=1260 [2021-03-10 23:52:16,385 INFO L87 Difference]: Start difference. First operand 740 states and 1589 transitions. Second operand has 36 states, 36 states have (on average 2.0277777777777777) internal successors, (73), 35 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:18,340 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:18,340 INFO L93 Difference]: Finished difference Result 2305 states and 4887 transitions. [2021-03-10 23:52:18,340 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 50 states. [2021-03-10 23:52:18,341 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 2.0277777777777777) internal successors, (73), 35 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-03-10 23:52:18,341 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:18,346 INFO L225 Difference]: With dead ends: 2305 [2021-03-10 23:52:18,346 INFO L226 Difference]: Without dead ends: 2148 [2021-03-10 23:52:18,347 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 98 GetRequests, 21 SyntacticMatches, 8 SemanticMatches, 69 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1950 ImplicationChecksByTransitivity, 1716.9ms TimeCoverageRelationStatistics Valid=673, Invalid=4297, Unknown=0, NotChecked=0, Total=4970 [2021-03-10 23:52:18,349 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2148 states. [2021-03-10 23:52:18,361 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2148 to 857. [2021-03-10 23:52:18,362 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 857 states, 856 states have (on average 2.1401869158878504) internal successors, (1832), 856 states have internal predecessors, (1832), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:18,363 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 857 states to 857 states and 1832 transitions. [2021-03-10 23:52:18,364 INFO L78 Accepts]: Start accepts. Automaton has 857 states and 1832 transitions. Word has length 41 [2021-03-10 23:52:18,364 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:18,364 INFO L480 AbstractCegarLoop]: Abstraction has 857 states and 1832 transitions. [2021-03-10 23:52:18,364 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 36 states, 36 states have (on average 2.0277777777777777) internal successors, (73), 35 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:18,364 INFO L276 IsEmpty]: Start isEmpty. Operand 857 states and 1832 transitions. [2021-03-10 23:52:18,365 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-03-10 23:52:18,365 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:18,365 INFO L519 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:18,579 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable53,11 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:18,579 INFO L428 AbstractCegarLoop]: === Iteration 13 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:18,579 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:18,580 INFO L82 PathProgramCache]: Analyzing trace with hash -1038925816, now seen corresponding path program 11 times [2021-03-10 23:52:18,580 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:18,580 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [182406340] [2021-03-10 23:52:18,580 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:18,585 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:18,888 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:18,889 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [182406340] [2021-03-10 23:52:18,889 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [50369979] [2021-03-10 23:52:18,889 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:18,911 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2021-03-10 23:52:18,911 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:18,912 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 33 conjunts are in the unsatisfiable core [2021-03-10 23:52:18,913 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:19,464 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:19,464 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 40 treesize of output 50 [2021-03-10 23:52:19,468 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:19,503 INFO L628 ElimStorePlain]: treesize reduction 43, result has 60.9 percent of original size [2021-03-10 23:52:19,516 INFO L550 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-03-10 23:52:19,517 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 5 variables, input treesize:54, output treesize:35 [2021-03-10 23:52:19,632 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:19,633 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:19,634 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:19,634 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:19,635 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:19,635 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:19,636 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:19,637 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:19,638 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 3 disjoint index pairs (out of 10 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 13 [2021-03-10 23:52:19,639 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:19,644 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:19,645 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:19,645 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:40, output treesize:5 [2021-03-10 23:52:19,653 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:19,654 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:19,654 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 20] total 36 [2021-03-10 23:52:19,655 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1225212156] [2021-03-10 23:52:19,655 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2021-03-10 23:52:19,656 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:19,656 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2021-03-10 23:52:19,656 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=179, Invalid=1153, Unknown=0, NotChecked=0, Total=1332 [2021-03-10 23:52:19,656 INFO L87 Difference]: Start difference. First operand 857 states and 1832 transitions. Second operand has 37 states, 37 states have (on average 1.972972972972973) internal successors, (73), 36 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:22,256 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:22,256 INFO L93 Difference]: Finished difference Result 2589 states and 5456 transitions. [2021-03-10 23:52:22,256 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2021-03-10 23:52:22,256 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 37 states have (on average 1.972972972972973) internal successors, (73), 36 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-03-10 23:52:22,257 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:22,262 INFO L225 Difference]: With dead ends: 2589 [2021-03-10 23:52:22,262 INFO L226 Difference]: Without dead ends: 2298 [2021-03-10 23:52:22,263 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 105 GetRequests, 27 SyntacticMatches, 1 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2106 ImplicationChecksByTransitivity, 1796.3ms TimeCoverageRelationStatistics Valid=836, Invalid=5326, Unknown=0, NotChecked=0, Total=6162 [2021-03-10 23:52:22,265 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2298 states. [2021-03-10 23:52:22,277 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2298 to 749. [2021-03-10 23:52:22,278 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 749 states, 748 states have (on average 2.1550802139037435) internal successors, (1612), 748 states have internal predecessors, (1612), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:22,279 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 749 states to 749 states and 1612 transitions. [2021-03-10 23:52:22,279 INFO L78 Accepts]: Start accepts. Automaton has 749 states and 1612 transitions. Word has length 41 [2021-03-10 23:52:22,279 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:22,279 INFO L480 AbstractCegarLoop]: Abstraction has 749 states and 1612 transitions. [2021-03-10 23:52:22,279 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 37 states, 37 states have (on average 1.972972972972973) internal successors, (73), 36 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:22,279 INFO L276 IsEmpty]: Start isEmpty. Operand 749 states and 1612 transitions. [2021-03-10 23:52:22,280 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-03-10 23:52:22,280 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:22,280 INFO L519 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:22,495 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable72 [2021-03-10 23:52:22,495 INFO L428 AbstractCegarLoop]: === Iteration 14 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:22,495 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:22,495 INFO L82 PathProgramCache]: Analyzing trace with hash 1257871970, now seen corresponding path program 12 times [2021-03-10 23:52:22,495 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:22,495 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [340431046] [2021-03-10 23:52:22,495 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:22,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:22,818 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 32 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-03-10 23:52:22,818 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [340431046] [2021-03-10 23:52:22,818 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1146758660] [2021-03-10 23:52:22,818 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:22,848 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2021-03-10 23:52:22,848 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:22,848 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 35 conjunts are in the unsatisfiable core [2021-03-10 23:52:22,849 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:23,422 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:23,422 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 40 treesize of output 50 [2021-03-10 23:52:23,427 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:23,457 INFO L628 ElimStorePlain]: treesize reduction 43, result has 55.2 percent of original size [2021-03-10 23:52:23,462 INFO L550 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-03-10 23:52:23,462 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 4 variables, input treesize:46, output treesize:25 [2021-03-10 23:52:23,592 INFO L354 Elim1Store]: treesize reduction 10, result has 83.6 percent of original size [2021-03-10 23:52:23,592 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 29 treesize of output 63 [2021-03-10 23:52:23,625 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 2 xjuncts. [2021-03-10 23:52:23,650 INFO L628 ElimStorePlain]: treesize reduction 43, result has 36.8 percent of original size [2021-03-10 23:52:23,653 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:23,653 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:38, output treesize:21 [2021-03-10 23:52:23,719 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:23,719 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:23,719 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 39 [2021-03-10 23:52:23,720 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1282367683] [2021-03-10 23:52:23,720 INFO L460 AbstractCegarLoop]: Interpolant automaton has 40 states [2021-03-10 23:52:23,720 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:23,720 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2021-03-10 23:52:23,720 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=205, Invalid=1355, Unknown=0, NotChecked=0, Total=1560 [2021-03-10 23:52:23,721 INFO L87 Difference]: Start difference. First operand 749 states and 1612 transitions. Second operand has 40 states, 40 states have (on average 1.925) internal successors, (77), 39 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:35,479 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:35,479 INFO L93 Difference]: Finished difference Result 3375 states and 7212 transitions. [2021-03-10 23:52:35,480 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 110 states. [2021-03-10 23:52:35,480 INFO L78 Accepts]: Start accepts. Automaton has has 40 states, 40 states have (on average 1.925) internal successors, (77), 39 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-03-10 23:52:35,480 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:35,488 INFO L225 Difference]: With dead ends: 3375 [2021-03-10 23:52:35,488 INFO L226 Difference]: Without dead ends: 3175 [2021-03-10 23:52:35,491 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 164 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 139 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6951 ImplicationChecksByTransitivity, 5872.7ms TimeCoverageRelationStatistics Valid=2545, Invalid=17195, Unknown=0, NotChecked=0, Total=19740 [2021-03-10 23:52:35,494 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3175 states. [2021-03-10 23:52:35,508 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3175 to 878. [2021-03-10 23:52:35,509 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 878 states, 877 states have (on average 2.1584948688711516) internal successors, (1893), 877 states have internal predecessors, (1893), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:35,510 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 878 states to 878 states and 1893 transitions. [2021-03-10 23:52:35,510 INFO L78 Accepts]: Start accepts. Automaton has 878 states and 1893 transitions. Word has length 41 [2021-03-10 23:52:35,510 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:35,510 INFO L480 AbstractCegarLoop]: Abstraction has 878 states and 1893 transitions. [2021-03-10 23:52:35,510 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 40 states, 40 states have (on average 1.925) internal successors, (77), 39 states have internal predecessors, (77), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:35,510 INFO L276 IsEmpty]: Start isEmpty. Operand 878 states and 1893 transitions. [2021-03-10 23:52:35,512 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-03-10 23:52:35,512 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:35,512 INFO L519 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:35,726 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable79 [2021-03-10 23:52:35,726 INFO L428 AbstractCegarLoop]: === Iteration 15 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:35,727 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:35,727 INFO L82 PathProgramCache]: Analyzing trace with hash -2064541460, now seen corresponding path program 13 times [2021-03-10 23:52:35,727 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:35,727 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1732477946] [2021-03-10 23:52:35,727 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:35,734 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:36,050 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 32 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-03-10 23:52:36,051 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1732477946] [2021-03-10 23:52:36,051 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1949654976] [2021-03-10 23:52:36,051 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:36,071 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:36,072 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 35 conjunts are in the unsatisfiable core [2021-03-10 23:52:36,072 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:36,699 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:36,699 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 42 treesize of output 52 [2021-03-10 23:52:36,706 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:36,745 INFO L628 ElimStorePlain]: treesize reduction 47, result has 60.8 percent of original size [2021-03-10 23:52:36,754 INFO L550 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-03-10 23:52:36,754 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 5 variables, input treesize:60, output treesize:41 [2021-03-10 23:52:36,825 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:36,826 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:36,827 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:36,828 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:36,829 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:36,829 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:36,830 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:36,830 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 3 disjoint index pairs (out of 10 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 13 [2021-03-10 23:52:36,835 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:36,841 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:36,842 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:36,842 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:46, output treesize:5 [2021-03-10 23:52:36,853 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 1 proven. 32 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:36,854 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:36,854 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 20] total 35 [2021-03-10 23:52:36,854 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1502939191] [2021-03-10 23:52:36,854 INFO L460 AbstractCegarLoop]: Interpolant automaton has 36 states [2021-03-10 23:52:36,854 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:36,854 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2021-03-10 23:52:36,854 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=173, Invalid=1087, Unknown=0, NotChecked=0, Total=1260 [2021-03-10 23:52:36,855 INFO L87 Difference]: Start difference. First operand 878 states and 1893 transitions. Second operand has 36 states, 36 states have (on average 2.0277777777777777) internal successors, (73), 35 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:38,722 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:38,722 INFO L93 Difference]: Finished difference Result 3209 states and 6883 transitions. [2021-03-10 23:52:38,723 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2021-03-10 23:52:38,723 INFO L78 Accepts]: Start accepts. Automaton has has 36 states, 36 states have (on average 2.0277777777777777) internal successors, (73), 35 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-03-10 23:52:38,723 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:38,730 INFO L225 Difference]: With dead ends: 3209 [2021-03-10 23:52:38,730 INFO L226 Difference]: Without dead ends: 3001 [2021-03-10 23:52:38,731 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 27 SyntacticMatches, 2 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1398 ImplicationChecksByTransitivity, 1520.3ms TimeCoverageRelationStatistics Valid=578, Invalid=3582, Unknown=0, NotChecked=0, Total=4160 [2021-03-10 23:52:38,733 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3001 states. [2021-03-10 23:52:38,746 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3001 to 1070. [2021-03-10 23:52:38,747 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1070 states, 1069 states have (on average 2.1515434985968196) internal successors, (2300), 1069 states have internal predecessors, (2300), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:38,749 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1070 states to 1070 states and 2300 transitions. [2021-03-10 23:52:38,749 INFO L78 Accepts]: Start accepts. Automaton has 1070 states and 2300 transitions. Word has length 41 [2021-03-10 23:52:38,749 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:38,749 INFO L480 AbstractCegarLoop]: Abstraction has 1070 states and 2300 transitions. [2021-03-10 23:52:38,749 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 36 states, 36 states have (on average 2.0277777777777777) internal successors, (73), 35 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:38,749 INFO L276 IsEmpty]: Start isEmpty. Operand 1070 states and 2300 transitions. [2021-03-10 23:52:38,751 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-03-10 23:52:38,751 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:38,751 INFO L519 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:38,966 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable108 [2021-03-10 23:52:38,966 INFO L428 AbstractCegarLoop]: === Iteration 16 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:38,966 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:38,966 INFO L82 PathProgramCache]: Analyzing trace with hash 1195244540, now seen corresponding path program 14 times [2021-03-10 23:52:38,966 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:38,966 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [891036970] [2021-03-10 23:52:38,966 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:38,974 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:39,292 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:39,292 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [891036970] [2021-03-10 23:52:39,292 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [715232871] [2021-03-10 23:52:39,292 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:39,313 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-03-10 23:52:39,313 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:39,314 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 35 conjunts are in the unsatisfiable core [2021-03-10 23:52:39,314 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:39,892 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:39,893 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 42 treesize of output 52 [2021-03-10 23:52:39,897 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:39,936 INFO L628 ElimStorePlain]: treesize reduction 47, result has 60.8 percent of original size [2021-03-10 23:52:39,941 INFO L550 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-03-10 23:52:39,941 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 5 variables, input treesize:60, output treesize:41 [2021-03-10 23:52:40,048 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:40,049 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:40,050 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:40,051 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:40,051 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:40,052 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:40,052 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:40,053 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:40,053 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 3 disjoint index pairs (out of 10 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 35 treesize of output 13 [2021-03-10 23:52:40,054 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:40,060 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:40,061 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:40,061 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:46, output treesize:5 [2021-03-10 23:52:40,071 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:40,071 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:40,071 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 20] total 36 [2021-03-10 23:52:40,071 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1686385498] [2021-03-10 23:52:40,071 INFO L460 AbstractCegarLoop]: Interpolant automaton has 37 states [2021-03-10 23:52:40,071 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:40,072 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 37 interpolants. [2021-03-10 23:52:40,072 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=1158, Unknown=0, NotChecked=0, Total=1332 [2021-03-10 23:52:40,072 INFO L87 Difference]: Start difference. First operand 1070 states and 2300 transitions. Second operand has 37 states, 37 states have (on average 1.972972972972973) internal successors, (73), 36 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:42,479 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:42,479 INFO L93 Difference]: Finished difference Result 3490 states and 7483 transitions. [2021-03-10 23:52:42,480 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2021-03-10 23:52:42,480 INFO L78 Accepts]: Start accepts. Automaton has has 37 states, 37 states have (on average 1.972972972972973) internal successors, (73), 36 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-03-10 23:52:42,481 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:42,490 INFO L225 Difference]: With dead ends: 3490 [2021-03-10 23:52:42,490 INFO L226 Difference]: Without dead ends: 3246 [2021-03-10 23:52:42,490 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 27 SyntacticMatches, 1 SemanticMatches, 64 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1375 ImplicationChecksByTransitivity, 1691.1ms TimeCoverageRelationStatistics Valid=606, Invalid=3684, Unknown=0, NotChecked=0, Total=4290 [2021-03-10 23:52:42,493 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3246 states. [2021-03-10 23:52:42,510 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3246 to 1322. [2021-03-10 23:52:42,512 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1322 states, 1321 states have (on average 2.161998485995458) internal successors, (2856), 1321 states have internal predecessors, (2856), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:42,514 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1322 states to 1322 states and 2856 transitions. [2021-03-10 23:52:42,514 INFO L78 Accepts]: Start accepts. Automaton has 1322 states and 2856 transitions. Word has length 41 [2021-03-10 23:52:42,514 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:42,514 INFO L480 AbstractCegarLoop]: Abstraction has 1322 states and 2856 transitions. [2021-03-10 23:52:42,514 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 37 states, 37 states have (on average 1.972972972972973) internal successors, (73), 36 states have internal predecessors, (73), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:42,514 INFO L276 IsEmpty]: Start isEmpty. Operand 1322 states and 2856 transitions. [2021-03-10 23:52:42,516 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2021-03-10 23:52:42,516 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:42,516 INFO L519 BasicCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:42,731 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable115,15 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:42,731 INFO L428 AbstractCegarLoop]: === Iteration 17 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:42,731 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:42,731 INFO L82 PathProgramCache]: Analyzing trace with hash -920574034, now seen corresponding path program 15 times [2021-03-10 23:52:42,731 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:42,732 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [21012069] [2021-03-10 23:52:42,732 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:42,747 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:43,058 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:43,058 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [21012069] [2021-03-10 23:52:43,058 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [226932157] [2021-03-10 23:52:43,058 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:43,081 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2021-03-10 23:52:43,081 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:43,081 INFO L263 TraceCheckSpWp]: Trace formula consists of 87 conjuncts, 36 conjunts are in the unsatisfiable core [2021-03-10 23:52:43,082 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:43,525 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:43,525 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 40 treesize of output 50 [2021-03-10 23:52:43,532 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:43,574 INFO L628 ElimStorePlain]: treesize reduction 43, result has 60.2 percent of original size [2021-03-10 23:52:43,581 INFO L550 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-03-10 23:52:43,582 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 5 variables, input treesize:56, output treesize:37 [2021-03-10 23:52:43,937 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:43,938 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:43,938 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:43,941 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:43,943 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:43,977 INFO L354 Elim1Store]: treesize reduction 28, result has 45.1 percent of original size [2021-03-10 23:52:43,977 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 5 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 5 case distinctions, treesize of input 42 treesize of output 38 [2021-03-10 23:52:43,983 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:43,988 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:43,989 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:43,990 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:43,993 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:43,994 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:44,024 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:44,024 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 5 disjoint index pairs (out of 10 index pairs), introduced 5 new quantified variables, introduced 5 case distinctions, treesize of input 33 treesize of output 63 [2021-03-10 23:52:44,068 INFO L550 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 3 xjuncts. [2021-03-10 23:52:44,133 INFO L628 ElimStorePlain]: treesize reduction 17, result has 81.9 percent of original size [2021-03-10 23:52:44,144 INFO L550 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-1 vars, End of recursive call: and 3 xjuncts. [2021-03-10 23:52:44,144 INFO L247 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:113, output treesize:36 [2021-03-10 23:52:44,234 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 0 proven. 33 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:44,234 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:44,235 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 21] total 39 [2021-03-10 23:52:44,235 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [848247134] [2021-03-10 23:52:44,235 INFO L460 AbstractCegarLoop]: Interpolant automaton has 40 states [2021-03-10 23:52:44,235 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:44,235 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2021-03-10 23:52:44,235 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=168, Invalid=1392, Unknown=0, NotChecked=0, Total=1560 [2021-03-10 23:52:44,235 INFO L87 Difference]: Start difference. First operand 1322 states and 2856 transitions. Second operand has 40 states, 40 states have (on average 1.9) internal successors, (76), 39 states have internal predecessors, (76), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:47,396 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:47,396 INFO L93 Difference]: Finished difference Result 3408 states and 7345 transitions. [2021-03-10 23:52:47,397 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2021-03-10 23:52:47,397 INFO L78 Accepts]: Start accepts. Automaton has has 40 states, 40 states have (on average 1.9) internal successors, (76), 39 states have internal predecessors, (76), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 41 [2021-03-10 23:52:47,397 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:47,402 INFO L225 Difference]: With dead ends: 3408 [2021-03-10 23:52:47,402 INFO L226 Difference]: Without dead ends: 3247 [2021-03-10 23:52:47,403 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 24 SyntacticMatches, 1 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1179 ImplicationChecksByTransitivity, 2542.3ms TimeCoverageRelationStatistics Valid=656, Invalid=3900, Unknown=0, NotChecked=0, Total=4556 [2021-03-10 23:52:47,405 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3247 states. [2021-03-10 23:52:47,420 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3247 to 1451. [2021-03-10 23:52:47,421 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1451 states, 1450 states have (on average 2.1655172413793102) internal successors, (3140), 1450 states have internal predecessors, (3140), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:47,423 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1451 states to 1451 states and 3140 transitions. [2021-03-10 23:52:47,423 INFO L78 Accepts]: Start accepts. Automaton has 1451 states and 3140 transitions. Word has length 41 [2021-03-10 23:52:47,424 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:47,424 INFO L480 AbstractCegarLoop]: Abstraction has 1451 states and 3140 transitions. [2021-03-10 23:52:47,424 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 40 states, 40 states have (on average 1.9) internal successors, (76), 39 states have internal predecessors, (76), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:47,424 INFO L276 IsEmpty]: Start isEmpty. Operand 1451 states and 3140 transitions. [2021-03-10 23:52:47,426 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 46 [2021-03-10 23:52:47,426 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:47,426 INFO L519 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:47,628 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable123 [2021-03-10 23:52:47,628 INFO L428 AbstractCegarLoop]: === Iteration 18 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:47,628 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:47,628 INFO L82 PathProgramCache]: Analyzing trace with hash -1060291469, now seen corresponding path program 16 times [2021-03-10 23:52:47,628 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:47,628 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2071265536] [2021-03-10 23:52:47,628 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:47,632 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:47,680 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 28 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:47,680 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2071265536] [2021-03-10 23:52:47,680 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1863124366] [2021-03-10 23:52:47,680 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:47,701 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2021-03-10 23:52:47,701 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:47,701 INFO L263 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 8 conjunts are in the unsatisfiable core [2021-03-10 23:52:47,702 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:47,785 INFO L134 CoverageAnalysis]: Checked inductivity of 46 backedges. 28 proven. 18 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:47,785 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:47,785 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 5] total 10 [2021-03-10 23:52:47,785 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [495712397] [2021-03-10 23:52:47,785 INFO L460 AbstractCegarLoop]: Interpolant automaton has 11 states [2021-03-10 23:52:47,786 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:47,786 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2021-03-10 23:52:47,786 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=65, Unknown=0, NotChecked=0, Total=110 [2021-03-10 23:52:47,786 INFO L87 Difference]: Start difference. First operand 1451 states and 3140 transitions. Second operand has 11 states, 11 states have (on average 6.454545454545454) internal successors, (71), 10 states have internal predecessors, (71), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:47,888 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:47,888 INFO L93 Difference]: Finished difference Result 1952 states and 4215 transitions. [2021-03-10 23:52:47,888 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2021-03-10 23:52:47,889 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 11 states have (on average 6.454545454545454) internal successors, (71), 10 states have internal predecessors, (71), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 45 [2021-03-10 23:52:47,889 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:47,892 INFO L225 Difference]: With dead ends: 1952 [2021-03-10 23:52:47,892 INFO L226 Difference]: Without dead ends: 1902 [2021-03-10 23:52:47,892 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 24 ImplicationChecksByTransitivity, 63.6ms TimeCoverageRelationStatistics Valid=56, Invalid=76, Unknown=0, NotChecked=0, Total=132 [2021-03-10 23:52:47,893 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1902 states. [2021-03-10 23:52:47,905 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1902 to 1593. [2021-03-10 23:52:47,907 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1593 states, 1592 states have (on average 2.1777638190954773) internal successors, (3467), 1592 states have internal predecessors, (3467), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:47,910 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1593 states to 1593 states and 3467 transitions. [2021-03-10 23:52:47,910 INFO L78 Accepts]: Start accepts. Automaton has 1593 states and 3467 transitions. Word has length 45 [2021-03-10 23:52:47,910 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:47,910 INFO L480 AbstractCegarLoop]: Abstraction has 1593 states and 3467 transitions. [2021-03-10 23:52:47,910 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 11 states, 11 states have (on average 6.454545454545454) internal successors, (71), 10 states have internal predecessors, (71), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:47,910 INFO L276 IsEmpty]: Start isEmpty. Operand 1593 states and 3467 transitions. [2021-03-10 23:52:47,912 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2021-03-10 23:52:47,912 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:47,912 INFO L519 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:48,119 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable168 [2021-03-10 23:52:48,119 INFO L428 AbstractCegarLoop]: === Iteration 19 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:48,119 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:48,119 INFO L82 PathProgramCache]: Analyzing trace with hash 1067334948, now seen corresponding path program 17 times [2021-03-10 23:52:48,120 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:48,120 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [402411782] [2021-03-10 23:52:48,120 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:48,123 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:48,144 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 15 proven. 18 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2021-03-10 23:52:48,144 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [402411782] [2021-03-10 23:52:48,144 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1585113529] [2021-03-10 23:52:48,144 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:48,167 INFO L228 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2021-03-10 23:52:48,167 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:48,167 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 9 conjunts are in the unsatisfiable core [2021-03-10 23:52:48,168 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:48,233 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 23 proven. 8 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2021-03-10 23:52:48,234 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:48,234 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4] total 5 [2021-03-10 23:52:48,234 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1265851862] [2021-03-10 23:52:48,234 INFO L460 AbstractCegarLoop]: Interpolant automaton has 6 states [2021-03-10 23:52:48,234 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:48,234 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2021-03-10 23:52:48,234 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2021-03-10 23:52:48,235 INFO L87 Difference]: Start difference. First operand 1593 states and 3467 transitions. Second operand has 6 states, 6 states have (on average 6.833333333333333) internal successors, (41), 5 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:48,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:48,255 INFO L93 Difference]: Finished difference Result 2042 states and 4410 transitions. [2021-03-10 23:52:48,255 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2021-03-10 23:52:48,255 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 6.833333333333333) internal successors, (41), 5 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 46 [2021-03-10 23:52:48,255 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:48,258 INFO L225 Difference]: With dead ends: 2042 [2021-03-10 23:52:48,258 INFO L226 Difference]: Without dead ends: 2042 [2021-03-10 23:52:48,258 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 50 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 11.0ms TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2021-03-10 23:52:48,260 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2042 states. [2021-03-10 23:52:48,270 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2042 to 1283. [2021-03-10 23:52:48,271 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1283 states, 1282 states have (on average 2.1731669266770672) internal successors, (2786), 1282 states have internal predecessors, (2786), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:48,273 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1283 states to 1283 states and 2786 transitions. [2021-03-10 23:52:48,273 INFO L78 Accepts]: Start accepts. Automaton has 1283 states and 2786 transitions. Word has length 46 [2021-03-10 23:52:48,273 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:48,273 INFO L480 AbstractCegarLoop]: Abstraction has 1283 states and 2786 transitions. [2021-03-10 23:52:48,273 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 6 states, 6 states have (on average 6.833333333333333) internal successors, (41), 5 states have internal predecessors, (41), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:48,273 INFO L276 IsEmpty]: Start isEmpty. Operand 1283 states and 2786 transitions. [2021-03-10 23:52:48,275 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2021-03-10 23:52:48,275 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:48,275 INFO L519 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:48,484 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable169 [2021-03-10 23:52:48,484 INFO L428 AbstractCegarLoop]: === Iteration 20 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:48,484 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:48,484 INFO L82 PathProgramCache]: Analyzing trace with hash 1691572838, now seen corresponding path program 18 times [2021-03-10 23:52:48,484 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:48,484 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1244434811] [2021-03-10 23:52:48,484 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:48,488 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:48,511 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 28 proven. 16 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2021-03-10 23:52:48,511 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1244434811] [2021-03-10 23:52:48,511 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [635124830] [2021-03-10 23:52:48,511 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2021-03-10 23:52:48,548 INFO L228 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2021-03-10 23:52:48,549 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:48,549 INFO L263 TraceCheckSpWp]: Trace formula consists of 97 conjuncts, 9 conjunts are in the unsatisfiable core [2021-03-10 23:52:48,550 INFO L286 TraceCheckSpWp]: Computing forward predicates... Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:48,627 INFO L134 CoverageAnalysis]: Checked inductivity of 49 backedges. 37 proven. 6 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2021-03-10 23:52:48,628 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:48,628 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 6 [2021-03-10 23:52:48,628 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [515270539] [2021-03-10 23:52:48,628 INFO L460 AbstractCegarLoop]: Interpolant automaton has 7 states [2021-03-10 23:52:48,628 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:48,628 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2021-03-10 23:52:48,628 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2021-03-10 23:52:48,629 INFO L87 Difference]: Start difference. First operand 1283 states and 2786 transitions. Second operand has 7 states, 7 states have (on average 7.142857142857143) internal successors, (50), 6 states have internal predecessors, (50), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:48,653 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:48,653 INFO L93 Difference]: Finished difference Result 1442 states and 3092 transitions. [2021-03-10 23:52:48,653 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2021-03-10 23:52:48,654 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 7.142857142857143) internal successors, (50), 6 states have internal predecessors, (50), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 46 [2021-03-10 23:52:48,654 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:48,655 INFO L225 Difference]: With dead ends: 1442 [2021-03-10 23:52:48,655 INFO L226 Difference]: Without dead ends: 1442 [2021-03-10 23:52:48,656 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 54 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 13.8ms TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2021-03-10 23:52:48,657 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1442 states. [2021-03-10 23:52:48,664 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1442 to 1063. [2021-03-10 23:52:48,666 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1063 states, 1062 states have (on average 2.1534839924670433) internal successors, (2287), 1062 states have internal predecessors, (2287), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:48,667 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1063 states to 1063 states and 2287 transitions. [2021-03-10 23:52:48,667 INFO L78 Accepts]: Start accepts. Automaton has 1063 states and 2287 transitions. Word has length 46 [2021-03-10 23:52:48,668 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:48,668 INFO L480 AbstractCegarLoop]: Abstraction has 1063 states and 2287 transitions. [2021-03-10 23:52:48,668 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 7 states, 7 states have (on average 7.142857142857143) internal successors, (50), 6 states have internal predecessors, (50), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:48,668 INFO L276 IsEmpty]: Start isEmpty. Operand 1063 states and 2287 transitions. [2021-03-10 23:52:48,669 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2021-03-10 23:52:48,669 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:48,669 INFO L519 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:48,883 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable170 [2021-03-10 23:52:48,883 INFO L428 AbstractCegarLoop]: === Iteration 21 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:48,883 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:48,883 INFO L82 PathProgramCache]: Analyzing trace with hash -623804093, now seen corresponding path program 19 times [2021-03-10 23:52:48,884 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:48,884 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1484362616] [2021-03-10 23:52:48,884 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:48,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:49,444 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:49,444 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1484362616] [2021-03-10 23:52:49,444 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [309942053] [2021-03-10 23:52:49,444 INFO L93 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:49,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:49,467 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 47 conjunts are in the unsatisfiable core [2021-03-10 23:52:49,468 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:49,988 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:49,988 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 61 treesize of output 87 [2021-03-10 23:52:49,995 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:50,070 INFO L628 ElimStorePlain]: treesize reduction 86, result has 58.7 percent of original size [2021-03-10 23:52:50,086 INFO L550 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-03-10 23:52:50,087 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 6 variables, input treesize:72, output treesize:48 [2021-03-10 23:52:50,491 INFO L354 Elim1Store]: treesize reduction 66, result has 1.5 percent of original size [2021-03-10 23:52:50,491 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 44 treesize of output 16 [2021-03-10 23:52:50,492 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:50,495 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:50,495 INFO L550 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:50,496 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:45, output treesize:5 [2021-03-10 23:52:50,505 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:50,505 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:50,505 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 26] total 49 [2021-03-10 23:52:50,506 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1353365643] [2021-03-10 23:52:50,506 INFO L460 AbstractCegarLoop]: Interpolant automaton has 50 states [2021-03-10 23:52:50,506 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:50,506 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 50 interpolants. [2021-03-10 23:52:50,506 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=289, Invalid=2161, Unknown=0, NotChecked=0, Total=2450 [2021-03-10 23:52:50,506 INFO L87 Difference]: Start difference. First operand 1063 states and 2287 transitions. Second operand has 50 states, 50 states have (on average 1.72) internal successors, (86), 49 states have internal predecessors, (86), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:54,115 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:52:54,115 INFO L93 Difference]: Finished difference Result 2509 states and 5340 transitions. [2021-03-10 23:52:54,116 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 59 states. [2021-03-10 23:52:54,116 INFO L78 Accepts]: Start accepts. Automaton has has 50 states, 50 states have (on average 1.72) internal successors, (86), 49 states have internal predecessors, (86), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 50 [2021-03-10 23:52:54,116 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:52:54,119 INFO L225 Difference]: With dead ends: 2509 [2021-03-10 23:52:54,119 INFO L226 Difference]: Without dead ends: 2413 [2021-03-10 23:52:54,120 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 119 GetRequests, 29 SyntacticMatches, 2 SemanticMatches, 88 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2594 ImplicationChecksByTransitivity, 2634.1ms TimeCoverageRelationStatistics Valid=812, Invalid=7198, Unknown=0, NotChecked=0, Total=8010 [2021-03-10 23:52:54,121 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2413 states. [2021-03-10 23:52:54,132 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2413 to 1155. [2021-03-10 23:52:54,133 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1155 states, 1154 states have (on average 2.165511265164645) internal successors, (2499), 1154 states have internal predecessors, (2499), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:54,135 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1155 states to 1155 states and 2499 transitions. [2021-03-10 23:52:54,135 INFO L78 Accepts]: Start accepts. Automaton has 1155 states and 2499 transitions. Word has length 50 [2021-03-10 23:52:54,135 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:52:54,135 INFO L480 AbstractCegarLoop]: Abstraction has 1155 states and 2499 transitions. [2021-03-10 23:52:54,135 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 50 states, 50 states have (on average 1.72) internal successors, (86), 49 states have internal predecessors, (86), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:52:54,135 INFO L276 IsEmpty]: Start isEmpty. Operand 1155 states and 2499 transitions. [2021-03-10 23:52:54,136 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2021-03-10 23:52:54,137 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:52:54,137 INFO L519 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:52:54,351 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable171,20 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:54,351 INFO L428 AbstractCegarLoop]: === Iteration 22 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:52:54,351 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:52:54,351 INFO L82 PathProgramCache]: Analyzing trace with hash -231269501, now seen corresponding path program 20 times [2021-03-10 23:52:54,352 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:52:54,352 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [769067770] [2021-03-10 23:52:54,352 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:52:54,357 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:52:54,871 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 0 proven. 61 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2021-03-10 23:52:54,871 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [769067770] [2021-03-10 23:52:54,871 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [840769531] [2021-03-10 23:52:54,871 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:52:54,893 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2021-03-10 23:52:54,893 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:52:54,894 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 47 conjunts are in the unsatisfiable core [2021-03-10 23:52:54,895 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:52:56,047 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:56,047 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 58 treesize of output 86 [2021-03-10 23:52:56,064 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:56,140 INFO L628 ElimStorePlain]: treesize reduction 92, result has 58.9 percent of original size [2021-03-10 23:52:56,156 INFO L550 ElimStorePlain]: Start of recursive call 1: 5 dim-0 vars, 1 dim-1 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2021-03-10 23:52:56,156 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 6 variables, input treesize:76, output treesize:52 [2021-03-10 23:52:56,244 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:56,245 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:56,246 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:56,247 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:56,247 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:56,248 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:56,249 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:56,249 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:56,250 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:52:56,251 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:52:56,254 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 6 disjoint index pairs (out of 15 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 16 [2021-03-10 23:52:56,255 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:52:56,260 INFO L628 ElimStorePlain]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:52:56,261 INFO L550 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2021-03-10 23:52:56,261 INFO L247 ElimStorePlain]: Needed 2 recursive calls to eliminate 3 variables, input treesize:57, output treesize:5 [2021-03-10 23:52:56,272 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 1 proven. 61 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:52:56,272 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:52:56,272 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 26] total 47 [2021-03-10 23:52:56,272 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1546600564] [2021-03-10 23:52:56,272 INFO L460 AbstractCegarLoop]: Interpolant automaton has 48 states [2021-03-10 23:52:56,272 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:52:56,272 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2021-03-10 23:52:56,273 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=244, Invalid=2012, Unknown=0, NotChecked=0, Total=2256 [2021-03-10 23:52:56,273 INFO L87 Difference]: Start difference. First operand 1155 states and 2499 transitions. Second operand has 48 states, 48 states have (on average 1.8958333333333333) internal successors, (91), 47 states have internal predecessors, (91), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:53:02,135 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2021-03-10 23:53:02,135 INFO L93 Difference]: Finished difference Result 2988 states and 6336 transitions. [2021-03-10 23:53:02,135 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 82 states. [2021-03-10 23:53:02,136 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 48 states have (on average 1.8958333333333333) internal successors, (91), 47 states have internal predecessors, (91), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 50 [2021-03-10 23:53:02,136 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2021-03-10 23:53:02,141 INFO L225 Difference]: With dead ends: 2988 [2021-03-10 23:53:02,141 INFO L226 Difference]: Without dead ends: 2875 [2021-03-10 23:53:02,142 INFO L775 BasicCegarLoop]: 0 DeclaredPredicates, 144 GetRequests, 31 SyntacticMatches, 2 SemanticMatches, 111 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4559 ImplicationChecksByTransitivity, 4021.6ms TimeCoverageRelationStatistics Valid=1351, Invalid=11305, Unknown=0, NotChecked=0, Total=12656 [2021-03-10 23:53:02,144 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2875 states. [2021-03-10 23:53:02,158 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2875 to 1493. [2021-03-10 23:53:02,160 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1493 states, 1492 states have (on average 2.148793565683646) internal successors, (3206), 1492 states have internal predecessors, (3206), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:53:02,162 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1493 states to 1493 states and 3206 transitions. [2021-03-10 23:53:02,162 INFO L78 Accepts]: Start accepts. Automaton has 1493 states and 3206 transitions. Word has length 50 [2021-03-10 23:53:02,162 INFO L84 Accepts]: Finished accepts. word is rejected. [2021-03-10 23:53:02,162 INFO L480 AbstractCegarLoop]: Abstraction has 1493 states and 3206 transitions. [2021-03-10 23:53:02,162 INFO L481 AbstractCegarLoop]: Interpolant automaton has has 48 states, 48 states have (on average 1.8958333333333333) internal successors, (91), 47 states have internal predecessors, (91), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:53:02,162 INFO L276 IsEmpty]: Start isEmpty. Operand 1493 states and 3206 transitions. [2021-03-10 23:53:02,164 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2021-03-10 23:53:02,164 INFO L511 BasicCegarLoop]: Found error trace [2021-03-10 23:53:02,164 INFO L519 BasicCegarLoop]: trace histogram [4, 4, 4, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2021-03-10 23:53:02,379 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 21 z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable182 [2021-03-10 23:53:02,379 INFO L428 AbstractCegarLoop]: === Iteration 23 === [ULTIMATE.startErr1INUSE_VIOLATION, ULTIMATE.startErr0INUSE_VIOLATION, ULTIMATE.startErr0ASSERT_VIOLATIONASSERT]=== [2021-03-10 23:53:02,379 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2021-03-10 23:53:02,380 INFO L82 PathProgramCache]: Analyzing trace with hash 1024877813, now seen corresponding path program 21 times [2021-03-10 23:53:02,380 INFO L162 FreeRefinementEngine]: Executing refinement strategy CAMEL [2021-03-10 23:53:02,380 INFO L353 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1873911485] [2021-03-10 23:53:02,380 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2021-03-10 23:53:02,388 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2021-03-10 23:53:02,937 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 0 proven. 62 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:53:02,937 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1873911485] [2021-03-10 23:53:02,937 INFO L353 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2103928042] [2021-03-10 23:53:02,937 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-10 23:53:02,962 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2021-03-10 23:53:02,962 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2021-03-10 23:53:02,963 INFO L263 TraceCheckSpWp]: Trace formula consists of 106 conjuncts, 44 conjunts are in the unsatisfiable core [2021-03-10 23:53:02,964 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2021-03-10 23:53:05,478 WARN L205 SmtUtils]: Spent 394.00 ms on a formula simplification that was a NOOP. DAG size: 48 [2021-03-10 23:53:05,621 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:53:05,621 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 54 treesize of output 82 [2021-03-10 23:53:05,628 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2021-03-10 23:53:05,662 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:53:05,662 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 54 treesize of output 82 [2021-03-10 23:53:05,669 INFO L550 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2021-03-10 23:53:05,908 WARN L205 SmtUtils]: Spent 238.00 ms on a formula simplification. DAG size of input: 121 DAG size of output: 102 [2021-03-10 23:53:05,908 INFO L628 ElimStorePlain]: treesize reduction 122, result has 69.7 percent of original size [2021-03-10 23:53:06,002 INFO L550 ElimStorePlain]: Start of recursive call 1: 14 dim-0 vars, 1 dim-1 vars, End of recursive call: 8 dim-0 vars, and 2 xjuncts. [2021-03-10 23:53:06,003 INFO L247 ElimStorePlain]: Needed 3 recursive calls to eliminate 15 variables, input treesize:163, output treesize:151 [2021-03-10 23:53:11,295 WARN L205 SmtUtils]: Spent 4.31 s on a formula simplification that was a NOOP. DAG size: 67 [2021-03-10 23:53:45,508 WARN L205 SmtUtils]: Spent 17.32 s on a formula simplification. DAG size of input: 68 DAG size of output: 59 [2021-03-10 23:53:45,748 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:53:45,750 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:53:45,760 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:53:45,842 INFO L354 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2021-03-10 23:53:45,842 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 3 disjoint index pairs (out of 15 index pairs), introduced 6 new quantified variables, introduced 12 case distinctions, treesize of input 38 treesize of output 128 [2021-03-10 23:53:46,848 INFO L550 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 5 xjuncts. [2021-03-10 23:53:46,865 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:53:46,868 INFO L173 IndexEqualityManager]: detected equality via solver [2021-03-10 23:53:46,872 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:53:46,879 INFO L190 IndexEqualityManager]: detected not equals via solver [2021-03-10 23:53:46,992 WARN L205 SmtUtils]: Spent 111.00 ms on a formula simplification. DAG size of input: 63 DAG size of output: 55 [2021-03-10 23:53:46,992 INFO L354 Elim1Store]: treesize reduction 16, result has 85.8 percent of original size [2021-03-10 23:53:46,993 INFO L388 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 7 select indices, 7 select index equivalence classes, 3 disjoint index pairs (out of 21 index pairs), introduced 6 new quantified variables, introduced 16 case distinctions, treesize of input 45 treesize of output 115 [2021-03-10 23:53:47,197 INFO L550 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2021-03-10 23:53:47,749 WARN L205 SmtUtils]: Spent 552.00 ms on a formula simplification. DAG size of input: 210 DAG size of output: 73 [2021-03-10 23:53:47,750 INFO L628 ElimStorePlain]: treesize reduction 1648, result has 9.0 percent of original size [2021-03-10 23:53:47,775 INFO L550 ElimStorePlain]: Start of recursive call 1: 9 dim-0 vars, 1 dim-1 vars, End of recursive call: and 5 xjuncts. [2021-03-10 23:53:47,775 INFO L247 ElimStorePlain]: Needed 3 recursive calls to eliminate 10 variables, input treesize:133, output treesize:47 [2021-03-10 23:53:47,906 INFO L134 CoverageAnalysis]: Checked inductivity of 62 backedges. 3 proven. 59 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2021-03-10 23:53:47,907 INFO L219 FreeRefinementEngine]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2021-03-10 23:53:47,907 INFO L232 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 27] total 50 [2021-03-10 23:53:47,907 INFO L155 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1470352865] [2021-03-10 23:53:47,907 INFO L460 AbstractCegarLoop]: Interpolant automaton has 51 states [2021-03-10 23:53:47,907 INFO L142 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2021-03-10 23:53:47,907 INFO L142 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2021-03-10 23:53:47,907 INFO L144 InterpolantAutomaton]: CoverageRelationStatistics Valid=279, Invalid=2268, Unknown=3, NotChecked=0, Total=2550 [2021-03-10 23:53:47,908 INFO L87 Difference]: Start difference. First operand 1493 states and 3206 transitions. Second operand has 51 states, 51 states have (on average 1.8431372549019607) internal successors, (94), 50 states have internal predecessors, (94), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2021-03-10 23:54:12,517 WARN L205 SmtUtils]: Spent 5.34 s on a formula simplification. DAG size of input: 139 DAG size of output: 40 [2021-03-10 23:54:20,341 WARN L205 SmtUtils]: Spent 849.00 ms on a formula simplification. DAG size of input: 144 DAG size of output: 42 [2021-03-10 23:54:28,951 WARN L205 SmtUtils]: Spent 249.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 49 [2021-03-10 23:54:42,456 WARN L205 SmtUtils]: Spent 4.24 s on a formula simplification. DAG size of input: 111 DAG size of output: 66 [2021-03-10 23:54:47,253 WARN L205 SmtUtils]: Spent 260.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 51 [2021-03-10 23:54:59,197 WARN L205 SmtUtils]: Spent 4.47 s on a formula simplification. DAG size of input: 88 DAG size of output: 60 [2021-03-10 23:55:09,882 WARN L205 SmtUtils]: Spent 2.66 s on a formula simplification. DAG size of input: 85 DAG size of output: 55 [2021-03-10 23:55:23,889 WARN L205 SmtUtils]: Spent 8.61 s on a formula simplification. DAG size of input: 135 DAG size of output: 44 [2021-03-10 23:55:33,978 WARN L205 SmtUtils]: Spent 5.01 s on a formula simplification. DAG size of input: 127 DAG size of output: 70 [2021-03-10 23:55:39,028 WARN L205 SmtUtils]: Spent 3.17 s on a formula simplification. DAG size of input: 125 DAG size of output: 64 [2021-03-10 23:55:43,545 WARN L205 SmtUtils]: Spent 132.00 ms on a formula simplification. DAG size of input: 83 DAG size of output: 55 [2021-03-10 23:55:51,904 WARN L205 SmtUtils]: Spent 118.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 44 [2021-03-10 23:55:57,558 WARN L205 SmtUtils]: Spent 332.00 ms on a formula simplification. DAG size of input: 130 DAG size of output: 54 [2021-03-10 23:56:04,895 WARN L205 SmtUtils]: Spent 2.41 s on a formula simplification. DAG size of input: 124 DAG size of output: 65 [2021-03-10 23:56:07,847 WARN L205 SmtUtils]: Spent 1.40 s on a formula simplification. DAG size of input: 127 DAG size of output: 66 [2021-03-10 23:56:20,528 WARN L205 SmtUtils]: Spent 681.00 ms on a formula simplification. DAG size of input: 128 DAG size of output: 51 [2021-03-10 23:56:26,540 WARN L205 SmtUtils]: Spent 236.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 66 [2021-03-10 23:56:31,266 WARN L205 SmtUtils]: Spent 2.22 s on a formula simplification. DAG size of input: 93 DAG size of output: 53 [2021-03-10 23:56:46,383 WARN L205 SmtUtils]: Spent 6.99 s on a formula simplification. DAG size of input: 124 DAG size of output: 61 [2021-03-10 23:56:55,142 WARN L205 SmtUtils]: Spent 1.39 s on a formula simplification. DAG size of input: 90 DAG size of output: 62 [2021-03-10 23:57:00,397 WARN L205 SmtUtils]: Spent 142.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 66 [2021-03-10 23:57:25,909 WARN L205 SmtUtils]: Spent 7.94 s on a formula simplification. DAG size of input: 126 DAG size of output: 63 [2021-03-10 23:57:35,068 WARN L205 SmtUtils]: Spent 2.56 s on a formula simplification. DAG size of input: 132 DAG size of output: 69 [2021-03-10 23:57:52,816 WARN L205 SmtUtils]: Spent 5.47 s on a formula simplification. DAG size of input: 128 DAG size of output: 71 [2021-03-10 23:58:04,407 WARN L205 SmtUtils]: Spent 2.14 s on a formula simplification. DAG size of input: 101 DAG size of output: 54 [2021-03-10 23:58:25,537 WARN L205 SmtUtils]: Spent 537.00 ms on a formula simplification. DAG size of input: 143 DAG size of output: 56 [2021-03-10 23:58:37,612 WARN L205 SmtUtils]: Spent 2.26 s on a formula simplification. DAG size of input: 122 DAG size of output: 76 [2021-03-10 23:58:55,708 WARN L205 SmtUtils]: Spent 2.07 s on a formula simplification. DAG size of input: 131 DAG size of output: 64 [2021-03-10 23:59:19,565 WARN L205 SmtUtils]: Spent 6.96 s on a formula simplification. DAG size of input: 111 DAG size of output: 62 [2021-03-10 23:59:21,082 WARN L205 SmtUtils]: Spent 784.00 ms on a formula simplification. DAG size of input: 148 DAG size of output: 58 [2021-03-10 23:59:48,462 WARN L205 SmtUtils]: Spent 12.96 s on a formula simplification. DAG size of input: 131 DAG size of output: 66 [2021-03-11 00:00:10,808 WARN L205 SmtUtils]: Spent 7.58 s on a formula simplification. DAG size of input: 121 DAG size of output: 67 [2021-03-11 00:00:25,724 WARN L205 SmtUtils]: Spent 2.40 s on a formula simplification. DAG size of input: 136 DAG size of output: 66 [2021-03-11 00:00:38,664 WARN L205 SmtUtils]: Spent 252.00 ms on a formula simplification. DAG size of input: 91 DAG size of output: 63 [2021-03-11 00:00:45,522 WARN L205 SmtUtils]: Spent 178.00 ms on a formula simplification. DAG size of input: 90 DAG size of output: 62 [2021-03-11 00:01:10,101 WARN L205 SmtUtils]: Spent 733.00 ms on a formula simplification. DAG size of input: 142 DAG size of output: 56 [2021-03-11 00:01:36,653 WARN L205 SmtUtils]: Spent 8.51 s on a formula simplification. DAG size of input: 118 DAG size of output: 62 [2021-03-11 00:01:49,488 WARN L205 SmtUtils]: Spent 2.47 s on a formula simplification. DAG size of input: 88 DAG size of output: 58 [2021-03-11 00:01:59,372 WARN L205 SmtUtils]: Spent 2.33 s on a formula simplification. DAG size of input: 87 DAG size of output: 57 [2021-03-11 00:02:11,188 WARN L205 SmtUtils]: Spent 2.08 s on a formula simplification. DAG size of input: 82 DAG size of output: 40 [2021-03-11 00:02:51,128 WARN L205 SmtUtils]: Spent 743.00 ms on a formula simplification. DAG size of input: 147 DAG size of output: 58 [2021-03-11 00:03:06,284 WARN L205 SmtUtils]: Spent 2.35 s on a formula simplification. DAG size of input: 103 DAG size of output: 62 [2021-03-11 00:03:10,412 WARN L205 SmtUtils]: Spent 125.00 ms on a formula simplification. DAG size of input: 51 DAG size of output: 43 [2021-03-11 00:03:17,654 WARN L205 SmtUtils]: Spent 2.24 s on a formula simplification. DAG size of input: 86 DAG size of output: 58 [2021-03-11 00:03:25,339 WARN L205 SmtUtils]: Spent 601.00 ms on a formula simplification. DAG size of input: 85 DAG size of output: 57 [2021-03-11 00:03:38,681 WARN L205 SmtUtils]: Spent 419.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 63 [2021-03-11 00:03:39,729 WARN L205 SmtUtils]: Spent 114.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 38 [2021-03-11 00:04:00,265 WARN L205 SmtUtils]: Spent 5.33 s on a formula simplification. DAG size of input: 106 DAG size of output: 59 [2021-03-11 00:04:25,770 WARN L205 SmtUtils]: Spent 10.18 s on a formula simplification. DAG size of input: 118 DAG size of output: 72 [2021-03-11 00:04:57,365 WARN L205 SmtUtils]: Spent 4.44 s on a formula simplification. DAG size of input: 123 DAG size of output: 68 [2021-03-11 00:05:15,208 WARN L205 SmtUtils]: Spent 107.00 ms on a formula simplification. DAG size of input: 46 DAG size of output: 38 [2021-03-11 00:05:23,497 WARN L205 SmtUtils]: Spent 323.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 65 [2021-03-11 00:05:35,958 WARN L205 SmtUtils]: Spent 2.69 s on a formula simplification. DAG size of input: 92 DAG size of output: 64 [2021-03-11 00:06:10,977 WARN L205 SmtUtils]: Spent 5.55 s on a formula simplification. DAG size of input: 106 DAG size of output: 59 [2021-03-11 00:06:25,177 WARN L205 SmtUtils]: Spent 1.27 s on a formula simplification. DAG size of input: 79 DAG size of output: 38 [2021-03-11 00:06:31,789 WARN L205 SmtUtils]: Spent 187.00 ms on a formula simplification. DAG size of input: 53 DAG size of output: 45 Received shutdown request... [2021-03-11 00:06:37,404 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 118 states. [2021-03-11 00:06:37,605 WARN L517 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable195,22 z3 -smt2 -in SMTLIB2_COMPLIANT=true [2021-03-11 00:06:37,605 WARN L545 AbstractCegarLoop]: Verification canceled [2021-03-11 00:06:37,609 WARN L224 ceAbstractionStarter]: Timeout [2021-03-11 00:06:37,609 INFO L202 PluginConnector]: Adding new model inc-subseq-array.wvr.bpl de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 11.03 12:06:37 BasicIcfg [2021-03-11 00:06:37,609 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2021-03-11 00:06:37,609 INFO L168 Benchmark]: Toolchain (without parser) took 878875.93 ms. Allocated memory was 255.9 MB in the beginning and 524.3 MB in the end (delta: 268.4 MB). Free memory was 236.7 MB in the beginning and 388.9 MB in the end (delta: -152.3 MB). Peak memory consumption was 117.0 MB. Max. memory is 16.0 GB. [2021-03-11 00:06:37,610 INFO L168 Benchmark]: Boogie PL CUP Parser took 0.09 ms. Allocated memory is still 255.9 MB. Free memory was 237.8 MB in the beginning and 237.6 MB in the end (delta: 181.6 kB). There was no memory consumed. Max. memory is 16.0 GB. [2021-03-11 00:06:37,610 INFO L168 Benchmark]: Boogie Procedure Inliner took 17.51 ms. Allocated memory is still 255.9 MB. Free memory was 236.1 MB in the beginning and 234.6 MB in the end (delta: 1.5 MB). Peak memory consumption was 2.1 MB. Max. memory is 16.0 GB. [2021-03-11 00:06:37,610 INFO L168 Benchmark]: Boogie Preprocessor took 11.07 ms. Allocated memory is still 255.9 MB. Free memory was 234.6 MB in the beginning and 233.6 MB in the end (delta: 966.8 kB). Peak memory consumption was 2.1 MB. Max. memory is 16.0 GB. [2021-03-11 00:06:37,610 INFO L168 Benchmark]: RCFGBuilder took 193.94 ms. Allocated memory is still 255.9 MB. Free memory was 233.6 MB in the beginning and 236.8 MB in the end (delta: -3.1 MB). Peak memory consumption was 18.4 MB. Max. memory is 16.0 GB. [2021-03-11 00:06:37,610 INFO L168 Benchmark]: TraceAbstraction took 878646.10 ms. Allocated memory was 255.9 MB in the beginning and 524.3 MB in the end (delta: 268.4 MB). Free memory was 236.1 MB in the beginning and 388.9 MB in the end (delta: -152.8 MB). Peak memory consumption was 115.4 MB. Max. memory is 16.0 GB. [2021-03-11 00:06:37,610 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * Boogie PL CUP Parser took 0.09 ms. Allocated memory is still 255.9 MB. Free memory was 237.8 MB in the beginning and 237.6 MB in the end (delta: 181.6 kB). There was no memory consumed. Max. memory is 16.0 GB. * Boogie Procedure Inliner took 17.51 ms. Allocated memory is still 255.9 MB. Free memory was 236.1 MB in the beginning and 234.6 MB in the end (delta: 1.5 MB). Peak memory consumption was 2.1 MB. Max. memory is 16.0 GB. * Boogie Preprocessor took 11.07 ms. Allocated memory is still 255.9 MB. Free memory was 234.6 MB in the beginning and 233.6 MB in the end (delta: 966.8 kB). Peak memory consumption was 2.1 MB. Max. memory is 16.0 GB. * RCFGBuilder took 193.94 ms. Allocated memory is still 255.9 MB. Free memory was 233.6 MB in the beginning and 236.8 MB in the end (delta: -3.1 MB). Peak memory consumption was 18.4 MB. Max. memory is 16.0 GB. * TraceAbstraction took 878646.10 ms. Allocated memory was 255.9 MB in the beginning and 524.3 MB in the end (delta: 268.4 MB). Free memory was 236.1 MB in the beginning and 388.9 MB in the end (delta: -152.8 MB). Peak memory consumption was 115.4 MB. Max. memory is 16.0 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 62]: Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 62). Cancelled while BasicCegarLoop was constructing difference of abstraction (1493states) and FLOYD_HOARE automaton (currently 118 states, 51 states before enhancement),while ReachableStatesComputation was computing reachable states (2591 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 3 procedures, 26 locations, 1 error locations. Started 1 CEGAR loops. VerificationResult: TIMEOUT, OverallTime: 878551.2ms, OverallIterations: 23, TraceHistogramMax: 4, EmptinessCheckTime: 34.4ms, AutomataDifference: 811776.7ms, DeadEndRemovalTime: 0.0ms, HoareAnnotationTime: 0.0ms, InitialAbstractionConstructionTime: 27.7ms, PartialOrderReductionTime: 0.0ms, HoareTripleCheckerStatistics: 1116 SDtfs, 5070 SDslu, 11865 SDs, 0 SdLazy, 29312 SolverSat, 3147 SolverUnsat, 29 SolverUnknown, 0 SolverNotchecked, 163474.3ms Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1818 GetRequests, 602 SyntacticMatches, 31 SemanticMatches, 1185 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 37162 ImplicationChecksByTransitivity, 687821.6ms Time, 0.0ms BasicInterpolantAutomatonTime, BiggestAbstraction: size=1593occurred in iteration=18, InterpolantAutomatonStates: 764, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0ms DumpTime, AutomataMinimizationStatistics: 343.7ms AutomataMinimizationTime, 22 MinimizatonAttempts, 18921 StatesRemovedByMinimization, 21 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 142.5ms SsaConstructionTime, 442.0ms SatisfiabilityAnalysisTime, 60845.1ms InterpolantComputationTime, 1672 NumberOfCodeBlocks, 1672 NumberOfCodeBlocksAsserted, 78 NumberOfCheckSat, 1628 ConstructedInterpolants, 300 QuantifiedInterpolants, 27384 SizeOfPredicates, 226 NumberOfNonLiveVariables, 1741 ConjunctsInSsa, 542 ConjunctsInUnsatCore, 44 InterpolantComputations, 2 PerfectInterpolantSequences, 262/1315 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Completed graceful shutdown