java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC_wBE.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig28.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-62c3406-m [2018-06-26 21:24:30,131 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-26 21:24:30,133 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-26 21:24:30,146 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-26 21:24:30,146 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-26 21:24:30,147 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-26 21:24:30,148 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-26 21:24:30,153 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-26 21:24:30,155 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-26 21:24:30,155 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-26 21:24:30,156 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-26 21:24:30,156 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-26 21:24:30,157 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-26 21:24:30,158 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-26 21:24:30,159 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-26 21:24:30,160 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-26 21:24:30,162 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-26 21:24:30,164 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-26 21:24:30,166 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-26 21:24:30,167 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-26 21:24:30,168 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-26 21:24:30,169 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-26 21:24:30,172 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-26 21:24:30,172 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-26 21:24:30,172 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-26 21:24:30,173 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-26 21:24:30,174 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-26 21:24:30,175 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-26 21:24:30,175 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-26 21:24:30,176 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-26 21:24:30,177 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-26 21:24:30,177 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-26 21:24:30,177 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-06-26 21:24:30,178 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-26 21:24:30,178 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-26 21:24:30,179 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-26 21:24:30,179 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-26 21:24:30,195 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-26 21:24:30,195 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-26 21:24:30,195 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-26 21:24:30,196 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-26 21:24:30,197 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-26 21:24:30,197 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-26 21:24:30,197 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-26 21:24:30,197 INFO L133 SettingsManager]: * Use SBE=true [2018-06-26 21:24:30,197 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-26 21:24:30,198 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-26 21:24:30,198 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-26 21:24:30,198 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-26 21:24:30,198 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 21:24:30,198 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-26 21:24:30,199 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-26 21:24:30,199 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-26 21:24:30,199 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-26 21:24:30,199 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-26 21:24:30,199 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-26 21:24:30,199 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-26 21:24:30,200 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-26 21:24:30,202 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-26 21:24:30,202 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-26 21:24:30,249 INFO ]: Repository-Root is: /tmp [2018-06-26 21:24:30,266 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-26 21:24:30,270 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-26 21:24:30,271 INFO ]: Initializing SmtParser... [2018-06-26 21:24:30,271 INFO ]: SmtParser initialized [2018-06-26 21:24:30,272 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig28.c.smt2 [2018-06-26 21:24:30,273 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-26 21:24:30,365 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig28.c.smt2 unknown [2018-06-26 21:24:30,613 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig28.c.smt2 [2018-06-26 21:24:30,618 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-26 21:24:30,624 INFO ]: Walking toolchain with 5 elements. [2018-06-26 21:24:30,624 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-26 21:24:30,624 INFO ]: Initializing ChcToBoogie... [2018-06-26 21:24:30,624 INFO ]: ChcToBoogie initialized [2018-06-26 21:24:30,628 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 09:24:30" (1/1) ... [2018-06-26 21:24:30,681 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:24:30 Unit [2018-06-26 21:24:30,681 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-26 21:24:30,682 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-26 21:24:30,682 INFO ]: Initializing Boogie Preprocessor... [2018-06-26 21:24:30,682 INFO ]: Boogie Preprocessor initialized [2018-06-26 21:24:30,705 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:24:30" (1/1) ... [2018-06-26 21:24:30,705 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:24:30" (1/1) ... [2018-06-26 21:24:30,711 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:24:30" (1/1) ... [2018-06-26 21:24:30,711 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:24:30" (1/1) ... [2018-06-26 21:24:30,715 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:24:30" (1/1) ... [2018-06-26 21:24:30,717 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:24:30" (1/1) ... [2018-06-26 21:24:30,718 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:24:30" (1/1) ... [2018-06-26 21:24:30,720 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-26 21:24:30,720 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-26 21:24:30,720 INFO ]: Initializing RCFGBuilder... [2018-06-26 21:24:30,720 INFO ]: RCFGBuilder initialized [2018-06-26 21:24:30,721 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:24:30" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 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 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 21:24:30,748 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-26 21:24:30,748 INFO ]: Found specification of procedure gotoProc [2018-06-26 21:24:30,748 INFO ]: Found implementation of procedure gotoProc [2018-06-26 21:24:30,748 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-26 21:24:30,748 INFO ]: Found specification of procedure Ultimate.START [2018-06-26 21:24:30,749 INFO ]: Found implementation of procedure Ultimate.START [2018-06-26 21:24:30,922 INFO ]: Using library mode [2018-06-26 21:24:30,923 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 09:24:30 BoogieIcfgContainer [2018-06-26 21:24:30,923 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-26 21:24:30,923 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-26 21:24:30,923 INFO ]: Initializing BlockEncodingV2... [2018-06-26 21:24:30,925 INFO ]: BlockEncodingV2 initialized [2018-06-26 21:24:30,926 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 09:24:30" (1/1) ... [2018-06-26 21:24:30,960 INFO ]: Initial Icfg 10 locations, 10 edges [2018-06-26 21:24:30,961 INFO ]: Using Remove infeasible edges [2018-06-26 21:24:30,962 INFO ]: Using Maximize final states [2018-06-26 21:24:30,962 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-26 21:24:30,962 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-26 21:24:30,964 INFO ]: Using Remove sink states [2018-06-26 21:24:30,965 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-26 21:24:30,965 INFO ]: Using Use SBE [2018-06-26 21:24:30,987 WARN ]: expecting exponential blowup for input size 24 [2018-06-26 21:24:55,380 INFO ]: SBE split 1 edges [2018-06-26 21:24:55,391 INFO ]: Removed 2 edges and 2 locations because of local infeasibility [2018-06-26 21:24:55,393 INFO ]: 0 new accepting states [2018-06-26 21:24:55,440 INFO ]: Removed 4 edges and 2 locations by large block encoding [2018-06-26 21:24:55,442 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 21:24:55,453 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-26 21:24:55,454 INFO ]: 0 new accepting states [2018-06-26 21:24:55,454 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-26 21:24:55,454 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 21:24:55,465 INFO ]: Encoded RCFG 6 locations, 155 edges [2018-06-26 21:24:55,465 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 09:24:55 BasicIcfg [2018-06-26 21:24:55,465 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-26 21:24:55,467 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-26 21:24:55,467 INFO ]: Initializing TraceAbstraction... [2018-06-26 21:24:55,470 INFO ]: TraceAbstraction initialized [2018-06-26 21:24:55,470 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 09:24:30" (1/4) ... [2018-06-26 21:24:55,471 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2a4d3e55 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 26.06 09:24:55, skipping insertion in model container [2018-06-26 21:24:55,471 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:24:30" (2/4) ... [2018-06-26 21:24:55,471 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2a4d3e55 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.06 09:24:55, skipping insertion in model container [2018-06-26 21:24:55,471 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 09:24:30" (3/4) ... [2018-06-26 21:24:55,471 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@2a4d3e55 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 09:24:55, skipping insertion in model container [2018-06-26 21:24:55,471 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 09:24:55" (4/4) ... [2018-06-26 21:24:55,473 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-26 21:24:55,482 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-26 21:24:55,488 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-26 21:24:55,521 INFO ]: Using default assertion order modulation [2018-06-26 21:24:55,521 INFO ]: Interprodecural is true [2018-06-26 21:24:55,521 INFO ]: Hoare is false [2018-06-26 21:24:55,521 INFO ]: Compute interpolants for FPandBP [2018-06-26 21:24:55,521 INFO ]: Backedges is TWOTRACK [2018-06-26 21:24:55,521 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-26 21:24:55,521 INFO ]: Difference is false [2018-06-26 21:24:55,521 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-26 21:24:55,521 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-26 21:24:55,530 INFO ]: Start isEmpty. Operand 6 states. [2018-06-26 21:24:55,542 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-26 21:24:55,543 INFO ]: Found error trace [2018-06-26 21:24:55,543 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-26 21:24:55,543 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:24:55,549 INFO ]: Analyzing trace with hash 40015362, now seen corresponding path program 1 times [2018-06-26 21:24:55,551 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:24:55,551 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:24:55,585 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:55,585 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:24:55,585 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:55,624 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:24:55,675 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:24:55,677 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:24:55,677 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:24:55,678 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:24:55,688 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:24:55,688 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:24:55,690 INFO ]: Start difference. First operand 6 states. Second operand 3 states. [2018-06-26 21:24:57,109 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:24:57,109 INFO ]: Finished difference Result 7 states and 172 transitions. [2018-06-26 21:24:57,109 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:24:57,110 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-26 21:24:57,110 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:24:57,119 INFO ]: With dead ends: 7 [2018-06-26 21:24:57,120 INFO ]: Without dead ends: 7 [2018-06-26 21:24:57,121 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:24:57,137 INFO ]: Start minimizeSevpa. Operand 7 states. [2018-06-26 21:24:57,154 INFO ]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-06-26 21:24:57,155 INFO ]: Start removeUnreachable. Operand 7 states. [2018-06-26 21:24:57,156 INFO ]: Finished removeUnreachable. Reduced from 7 states to 7 states and 172 transitions. [2018-06-26 21:24:57,157 INFO ]: Start accepts. Automaton has 7 states and 172 transitions. Word has length 5 [2018-06-26 21:24:57,158 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:24:57,158 INFO ]: Abstraction has 7 states and 172 transitions. [2018-06-26 21:24:57,158 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:24:57,158 INFO ]: Start isEmpty. Operand 7 states and 172 transitions. [2018-06-26 21:24:57,159 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 21:24:57,159 INFO ]: Found error trace [2018-06-26 21:24:57,159 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 21:24:57,159 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:24:57,159 INFO ]: Analyzing trace with hash 1236124012, now seen corresponding path program 1 times [2018-06-26 21:24:57,159 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:24:57,159 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:24:57,160 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:57,160 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:24:57,160 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:57,167 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:24:57,208 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:24:57,208 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:24:57,208 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:24:57,209 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:24:57,209 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:24:57,209 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:24:57,209 INFO ]: Start difference. First operand 7 states and 172 transitions. Second operand 3 states. [2018-06-26 21:24:57,581 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:24:57,581 INFO ]: Finished difference Result 9 states and 249 transitions. [2018-06-26 21:24:57,582 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:24:57,582 INFO ]: Start accepts. Automaton has 3 states. Word has length 6 [2018-06-26 21:24:57,582 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:24:57,583 INFO ]: With dead ends: 9 [2018-06-26 21:24:57,583 INFO ]: Without dead ends: 9 [2018-06-26 21:24:57,584 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:24:57,584 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-26 21:24:57,588 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-26 21:24:57,588 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-26 21:24:57,589 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 249 transitions. [2018-06-26 21:24:57,589 INFO ]: Start accepts. Automaton has 9 states and 249 transitions. Word has length 6 [2018-06-26 21:24:57,589 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:24:57,589 INFO ]: Abstraction has 9 states and 249 transitions. [2018-06-26 21:24:57,590 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:24:57,590 INFO ]: Start isEmpty. Operand 9 states and 249 transitions. [2018-06-26 21:24:57,590 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-26 21:24:57,590 INFO ]: Found error trace [2018-06-26 21:24:57,590 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:24:57,590 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:24:57,590 INFO ]: Analyzing trace with hash -333493630, now seen corresponding path program 1 times [2018-06-26 21:24:57,590 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:24:57,590 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:24:57,591 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:57,591 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:24:57,591 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:57,604 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:24:57,621 INFO ]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:24:57,621 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:24:57,621 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:24:57,621 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:24:57,621 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:24:57,621 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:24:57,621 INFO ]: Start difference. First operand 9 states and 249 transitions. Second operand 3 states. [2018-06-26 21:24:57,866 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:24:57,867 INFO ]: Finished difference Result 13 states and 348 transitions. [2018-06-26 21:24:57,867 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:24:57,867 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-26 21:24:57,867 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:24:57,868 INFO ]: With dead ends: 13 [2018-06-26 21:24:57,868 INFO ]: Without dead ends: 13 [2018-06-26 21:24:57,868 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:24:57,868 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-26 21:24:57,873 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-26 21:24:57,873 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-26 21:24:57,874 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 348 transitions. [2018-06-26 21:24:57,874 INFO ]: Start accepts. Automaton has 13 states and 348 transitions. Word has length 7 [2018-06-26 21:24:57,875 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:24:57,875 INFO ]: Abstraction has 13 states and 348 transitions. [2018-06-26 21:24:57,875 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:24:57,875 INFO ]: Start isEmpty. Operand 13 states and 348 transitions. [2018-06-26 21:24:57,875 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-26 21:24:57,875 INFO ]: Found error trace [2018-06-26 21:24:57,875 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:24:57,875 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:24:57,876 INFO ]: Analyzing trace with hash -141248570, now seen corresponding path program 1 times [2018-06-26 21:24:57,876 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:24:57,876 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:24:57,876 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:57,876 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:24:57,876 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:57,888 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:24:57,921 INFO ]: Checked inductivity of 15 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-26 21:24:57,921 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:24:57,921 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:24:57,922 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:24:57,922 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:24:57,922 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:24:57,922 INFO ]: Start difference. First operand 13 states and 348 transitions. Second operand 3 states. [2018-06-26 21:24:58,308 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:24:58,308 INFO ]: Finished difference Result 20 states and 514 transitions. [2018-06-26 21:24:58,308 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:24:58,308 INFO ]: Start accepts. Automaton has 3 states. Word has length 10 [2018-06-26 21:24:58,309 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:24:58,309 INFO ]: With dead ends: 20 [2018-06-26 21:24:58,309 INFO ]: Without dead ends: 20 [2018-06-26 21:24:58,310 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:24:58,310 INFO ]: Start minimizeSevpa. Operand 20 states. [2018-06-26 21:24:58,314 INFO ]: Finished minimizeSevpa. Reduced states from 20 to 20. [2018-06-26 21:24:58,314 INFO ]: Start removeUnreachable. Operand 20 states. [2018-06-26 21:24:58,315 INFO ]: Finished removeUnreachable. Reduced from 20 states to 20 states and 514 transitions. [2018-06-26 21:24:58,315 INFO ]: Start accepts. Automaton has 20 states and 514 transitions. Word has length 10 [2018-06-26 21:24:58,316 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:24:58,316 INFO ]: Abstraction has 20 states and 514 transitions. [2018-06-26 21:24:58,316 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:24:58,316 INFO ]: Start isEmpty. Operand 20 states and 514 transitions. [2018-06-26 21:24:58,316 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-26 21:24:58,316 INFO ]: Found error trace [2018-06-26 21:24:58,316 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:24:58,316 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:24:58,317 INFO ]: Analyzing trace with hash -642888075, now seen corresponding path program 1 times [2018-06-26 21:24:58,317 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:24:58,317 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:24:58,317 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:58,317 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:24:58,317 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:58,326 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:24:58,385 INFO ]: Checked inductivity of 15 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-26 21:24:58,385 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:24:58,385 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:24:58,385 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:24:58,386 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:24:58,386 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:24:58,386 INFO ]: Start difference. First operand 20 states and 514 transitions. Second operand 3 states. [2018-06-26 21:24:58,591 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:24:58,591 INFO ]: Finished difference Result 26 states and 511 transitions. [2018-06-26 21:24:58,591 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:24:58,592 INFO ]: Start accepts. Automaton has 3 states. Word has length 10 [2018-06-26 21:24:58,592 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:24:58,593 INFO ]: With dead ends: 26 [2018-06-26 21:24:58,593 INFO ]: Without dead ends: 26 [2018-06-26 21:24:58,593 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:24:58,593 INFO ]: Start minimizeSevpa. Operand 26 states. [2018-06-26 21:24:58,598 INFO ]: Finished minimizeSevpa. Reduced states from 26 to 24. [2018-06-26 21:24:58,598 INFO ]: Start removeUnreachable. Operand 24 states. [2018-06-26 21:24:58,599 INFO ]: Finished removeUnreachable. Reduced from 24 states to 24 states and 499 transitions. [2018-06-26 21:24:58,599 INFO ]: Start accepts. Automaton has 24 states and 499 transitions. Word has length 10 [2018-06-26 21:24:58,599 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:24:58,599 INFO ]: Abstraction has 24 states and 499 transitions. [2018-06-26 21:24:58,600 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:24:58,600 INFO ]: Start isEmpty. Operand 24 states and 499 transitions. [2018-06-26 21:24:58,600 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-26 21:24:58,600 INFO ]: Found error trace [2018-06-26 21:24:58,600 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:24:58,600 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:24:58,601 INFO ]: Analyzing trace with hash -671543912, now seen corresponding path program 1 times [2018-06-26 21:24:58,601 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:24:58,601 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:24:58,601 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:58,601 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:24:58,601 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:58,626 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:24:58,657 INFO ]: Checked inductivity of 36 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2018-06-26 21:24:58,657 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:24:58,657 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:24:58,657 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:24:58,657 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:24:58,657 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:24:58,658 INFO ]: Start difference. First operand 24 states and 499 transitions. Second operand 3 states. [2018-06-26 21:24:58,870 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:24:58,870 INFO ]: Finished difference Result 25 states and 344 transitions. [2018-06-26 21:24:58,870 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:24:58,870 INFO ]: Start accepts. Automaton has 3 states. Word has length 13 [2018-06-26 21:24:58,870 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:24:58,871 INFO ]: With dead ends: 25 [2018-06-26 21:24:58,871 INFO ]: Without dead ends: 24 [2018-06-26 21:24:58,871 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:24:58,871 INFO ]: Start minimizeSevpa. Operand 24 states. [2018-06-26 21:24:58,875 INFO ]: Finished minimizeSevpa. Reduced states from 24 to 24. [2018-06-26 21:24:58,875 INFO ]: Start removeUnreachable. Operand 24 states. [2018-06-26 21:24:58,876 INFO ]: Finished removeUnreachable. Reduced from 24 states to 24 states and 326 transitions. [2018-06-26 21:24:58,876 INFO ]: Start accepts. Automaton has 24 states and 326 transitions. Word has length 13 [2018-06-26 21:24:58,876 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:24:58,876 INFO ]: Abstraction has 24 states and 326 transitions. [2018-06-26 21:24:58,876 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:24:58,876 INFO ]: Start isEmpty. Operand 24 states and 326 transitions. [2018-06-26 21:24:58,877 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-26 21:24:58,877 INFO ]: Found error trace [2018-06-26 21:24:58,877 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:24:58,877 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:24:58,877 INFO ]: Analyzing trace with hash -305007523, now seen corresponding path program 1 times [2018-06-26 21:24:58,877 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:24:58,877 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:24:58,878 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:58,878 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:24:58,878 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:24:58,899 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:24:58,991 INFO ]: Checked inductivity of 45 backedges. 27 proven. 8 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-26 21:24:58,991 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:24:58,991 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:24:58,999 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:24:59,057 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:24:59,069 INFO ]: Computing forward predicates... [2018-06-26 21:24:59,090 INFO ]: Checked inductivity of 45 backedges. 27 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-06-26 21:24:59,111 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 21:24:59,111 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [4] total 4 [2018-06-26 21:24:59,111 INFO ]: Interpolant automaton has 4 states [2018-06-26 21:24:59,111 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-26 21:24:59,111 INFO ]: CoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-06-26 21:24:59,111 INFO ]: Start difference. First operand 24 states and 326 transitions. Second operand 4 states. [2018-06-26 21:25:00,025 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:00,025 INFO ]: Finished difference Result 51 states and 657 transitions. [2018-06-26 21:25:00,026 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-26 21:25:00,026 INFO ]: Start accepts. Automaton has 4 states. Word has length 14 [2018-06-26 21:25:00,026 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:00,029 INFO ]: With dead ends: 51 [2018-06-26 21:25:00,029 INFO ]: Without dead ends: 51 [2018-06-26 21:25:00,030 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=6, Invalid=6, Unknown=0, NotChecked=0, Total=12 [2018-06-26 21:25:00,030 INFO ]: Start minimizeSevpa. Operand 51 states. [2018-06-26 21:25:00,043 INFO ]: Finished minimizeSevpa. Reduced states from 51 to 39. [2018-06-26 21:25:00,043 INFO ]: Start removeUnreachable. Operand 39 states. [2018-06-26 21:25:00,044 INFO ]: Finished removeUnreachable. Reduced from 39 states to 39 states and 586 transitions. [2018-06-26 21:25:00,044 INFO ]: Start accepts. Automaton has 39 states and 586 transitions. Word has length 14 [2018-06-26 21:25:00,044 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:00,044 INFO ]: Abstraction has 39 states and 586 transitions. [2018-06-26 21:25:00,044 INFO ]: Interpolant automaton has 4 states. [2018-06-26 21:25:00,044 INFO ]: Start isEmpty. Operand 39 states and 586 transitions. [2018-06-26 21:25:00,046 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-26 21:25:00,046 INFO ]: Found error trace [2018-06-26 21:25:00,046 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:00,047 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:00,047 INFO ]: Analyzing trace with hash 1835544909, now seen corresponding path program 1 times [2018-06-26 21:25:00,047 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:00,047 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:00,048 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:00,048 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:00,048 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:00,065 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:00,315 INFO ]: Checked inductivity of 45 backedges. 27 proven. 10 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-26 21:25:00,315 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:00,315 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-26 21:25:00,328 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:00,385 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:00,388 INFO ]: Computing forward predicates... [2018-06-26 21:25:00,398 INFO ]: Checked inductivity of 45 backedges. 29 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2018-06-26 21:25:00,432 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 21:25:00,432 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [5] total 5 [2018-06-26 21:25:00,432 INFO ]: Interpolant automaton has 5 states [2018-06-26 21:25:00,433 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 21:25:00,433 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-26 21:25:00,433 INFO ]: Start difference. First operand 39 states and 586 transitions. Second operand 5 states. [2018-06-26 21:25:02,489 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:02,489 INFO ]: Finished difference Result 53 states and 572 transitions. [2018-06-26 21:25:02,490 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-26 21:25:02,490 INFO ]: Start accepts. Automaton has 5 states. Word has length 14 [2018-06-26 21:25:02,490 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:02,491 INFO ]: With dead ends: 53 [2018-06-26 21:25:02,491 INFO ]: Without dead ends: 48 [2018-06-26 21:25:02,491 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-26 21:25:02,491 INFO ]: Start minimizeSevpa. Operand 48 states. [2018-06-26 21:25:02,498 INFO ]: Finished minimizeSevpa. Reduced states from 48 to 41. [2018-06-26 21:25:02,498 INFO ]: Start removeUnreachable. Operand 41 states. [2018-06-26 21:25:02,499 INFO ]: Finished removeUnreachable. Reduced from 41 states to 41 states and 488 transitions. [2018-06-26 21:25:02,499 INFO ]: Start accepts. Automaton has 41 states and 488 transitions. Word has length 14 [2018-06-26 21:25:02,500 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:02,500 INFO ]: Abstraction has 41 states and 488 transitions. [2018-06-26 21:25:02,501 INFO ]: Interpolant automaton has 5 states. [2018-06-26 21:25:02,501 INFO ]: Start isEmpty. Operand 41 states and 488 transitions. [2018-06-26 21:25:02,502 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-26 21:25:02,502 INFO ]: Found error trace [2018-06-26 21:25:02,502 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:02,502 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:02,502 INFO ]: Analyzing trace with hash -1461039160, now seen corresponding path program 1 times [2018-06-26 21:25:02,502 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:02,502 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:02,503 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:02,503 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:02,503 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:02,517 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:02,567 INFO ]: Checked inductivity of 45 backedges. 29 proven. 0 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2018-06-26 21:25:02,567 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:25:02,567 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:25:02,567 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:25:02,567 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:25:02,567 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:25:02,567 INFO ]: Start difference. First operand 41 states and 488 transitions. Second operand 3 states. [2018-06-26 21:25:02,787 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:02,787 INFO ]: Finished difference Result 41 states and 347 transitions. [2018-06-26 21:25:02,787 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:25:02,787 INFO ]: Start accepts. Automaton has 3 states. Word has length 14 [2018-06-26 21:25:02,787 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:02,788 INFO ]: With dead ends: 41 [2018-06-26 21:25:02,788 INFO ]: Without dead ends: 37 [2018-06-26 21:25:02,788 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:25:02,788 INFO ]: Start minimizeSevpa. Operand 37 states. [2018-06-26 21:25:02,794 INFO ]: Finished minimizeSevpa. Reduced states from 37 to 36. [2018-06-26 21:25:02,794 INFO ]: Start removeUnreachable. Operand 36 states. [2018-06-26 21:25:02,795 INFO ]: Finished removeUnreachable. Reduced from 36 states to 36 states and 316 transitions. [2018-06-26 21:25:02,795 INFO ]: Start accepts. Automaton has 36 states and 316 transitions. Word has length 14 [2018-06-26 21:25:02,795 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:02,795 INFO ]: Abstraction has 36 states and 316 transitions. [2018-06-26 21:25:02,795 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:25:02,795 INFO ]: Start isEmpty. Operand 36 states and 316 transitions. [2018-06-26 21:25:02,796 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-26 21:25:02,796 INFO ]: Found error trace [2018-06-26 21:25:02,796 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:02,796 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:02,796 INFO ]: Analyzing trace with hash -6811894, now seen corresponding path program 1 times [2018-06-26 21:25:02,796 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:02,796 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:02,802 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:02,802 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:02,802 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:02,814 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:02,861 INFO ]: Checked inductivity of 45 backedges. 29 proven. 10 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-26 21:25:02,861 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:02,861 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:02,867 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:02,896 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:02,898 INFO ]: Computing forward predicates... [2018-06-26 21:25:02,905 INFO ]: Checked inductivity of 45 backedges. 23 proven. 0 refuted. 0 times theorem prover too weak. 22 trivial. 0 not checked. [2018-06-26 21:25:02,925 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 21:25:02,925 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [5] total 5 [2018-06-26 21:25:02,925 INFO ]: Interpolant automaton has 5 states [2018-06-26 21:25:02,926 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 21:25:02,926 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-26 21:25:02,926 INFO ]: Start difference. First operand 36 states and 316 transitions. Second operand 5 states. [2018-06-26 21:25:03,267 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:03,267 INFO ]: Finished difference Result 55 states and 446 transitions. [2018-06-26 21:25:03,267 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-26 21:25:03,267 INFO ]: Start accepts. Automaton has 5 states. Word has length 14 [2018-06-26 21:25:03,267 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:03,268 INFO ]: With dead ends: 55 [2018-06-26 21:25:03,268 INFO ]: Without dead ends: 50 [2018-06-26 21:25:03,269 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-26 21:25:03,269 INFO ]: Start minimizeSevpa. Operand 50 states. [2018-06-26 21:25:03,274 INFO ]: Finished minimizeSevpa. Reduced states from 50 to 43. [2018-06-26 21:25:03,274 INFO ]: Start removeUnreachable. Operand 43 states. [2018-06-26 21:25:03,275 INFO ]: Finished removeUnreachable. Reduced from 43 states to 43 states and 338 transitions. [2018-06-26 21:25:03,275 INFO ]: Start accepts. Automaton has 43 states and 338 transitions. Word has length 14 [2018-06-26 21:25:03,276 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:03,276 INFO ]: Abstraction has 43 states and 338 transitions. [2018-06-26 21:25:03,276 INFO ]: Interpolant automaton has 5 states. [2018-06-26 21:25:03,276 INFO ]: Start isEmpty. Operand 43 states and 338 transitions. [2018-06-26 21:25:03,278 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-26 21:25:03,278 INFO ]: Found error trace [2018-06-26 21:25:03,278 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:03,278 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:03,278 INFO ]: Analyzing trace with hash 1921697740, now seen corresponding path program 1 times [2018-06-26 21:25:03,278 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:03,278 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:03,279 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:03,279 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:03,279 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:03,302 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:03,340 INFO ]: Checked inductivity of 55 backedges. 34 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-26 21:25:03,340 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:25:03,340 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:25:03,340 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:25:03,340 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:25:03,340 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:25:03,340 INFO ]: Start difference. First operand 43 states and 338 transitions. Second operand 3 states. [2018-06-26 21:25:04,009 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:04,009 INFO ]: Finished difference Result 32 states and 172 transitions. [2018-06-26 21:25:04,009 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:25:04,009 INFO ]: Start accepts. Automaton has 3 states. Word has length 15 [2018-06-26 21:25:04,009 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:04,009 INFO ]: With dead ends: 32 [2018-06-26 21:25:04,009 INFO ]: Without dead ends: 28 [2018-06-26 21:25:04,010 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:25:04,010 INFO ]: Start minimizeSevpa. Operand 28 states. [2018-06-26 21:25:04,012 INFO ]: Finished minimizeSevpa. Reduced states from 28 to 23. [2018-06-26 21:25:04,012 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-26 21:25:04,012 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 90 transitions. [2018-06-26 21:25:04,012 INFO ]: Start accepts. Automaton has 23 states and 90 transitions. Word has length 15 [2018-06-26 21:25:04,013 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:04,013 INFO ]: Abstraction has 23 states and 90 transitions. [2018-06-26 21:25:04,013 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:25:04,013 INFO ]: Start isEmpty. Operand 23 states and 90 transitions. [2018-06-26 21:25:04,013 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-26 21:25:04,013 INFO ]: Found error trace [2018-06-26 21:25:04,013 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:04,013 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:04,013 INFO ]: Analyzing trace with hash -839588721, now seen corresponding path program 1 times [2018-06-26 21:25:04,013 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:04,013 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:04,014 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:04,014 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:04,014 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:04,029 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:04,282 INFO ]: Checked inductivity of 91 backedges. 58 proven. 12 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-26 21:25:04,282 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:04,282 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:04,288 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:04,347 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:04,351 INFO ]: Computing forward predicates... [2018-06-26 21:25:04,519 INFO ]: Checked inductivity of 91 backedges. 58 proven. 12 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-26 21:25:04,541 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:04,541 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-26 21:25:04,541 INFO ]: Interpolant automaton has 8 states [2018-06-26 21:25:04,541 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-26 21:25:04,541 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-26 21:25:04,541 INFO ]: Start difference. First operand 23 states and 90 transitions. Second operand 8 states. [2018-06-26 21:25:06,128 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:06,129 INFO ]: Finished difference Result 47 states and 193 transitions. [2018-06-26 21:25:06,129 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-26 21:25:06,129 INFO ]: Start accepts. Automaton has 8 states. Word has length 18 [2018-06-26 21:25:06,129 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:06,129 INFO ]: With dead ends: 47 [2018-06-26 21:25:06,129 INFO ]: Without dead ends: 35 [2018-06-26 21:25:06,130 INFO ]: 0 DeclaredPredicates, 32 GetRequests, 22 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=34, Invalid=56, Unknown=0, NotChecked=0, Total=90 [2018-06-26 21:25:06,130 INFO ]: Start minimizeSevpa. Operand 35 states. [2018-06-26 21:25:06,132 INFO ]: Finished minimizeSevpa. Reduced states from 35 to 28. [2018-06-26 21:25:06,132 INFO ]: Start removeUnreachable. Operand 28 states. [2018-06-26 21:25:06,133 INFO ]: Finished removeUnreachable. Reduced from 28 states to 28 states and 112 transitions. [2018-06-26 21:25:06,133 INFO ]: Start accepts. Automaton has 28 states and 112 transitions. Word has length 18 [2018-06-26 21:25:06,133 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:06,133 INFO ]: Abstraction has 28 states and 112 transitions. [2018-06-26 21:25:06,133 INFO ]: Interpolant automaton has 8 states. [2018-06-26 21:25:06,133 INFO ]: Start isEmpty. Operand 28 states and 112 transitions. [2018-06-26 21:25:06,134 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-26 21:25:06,134 INFO ]: Found error trace [2018-06-26 21:25:06,134 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:06,134 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:06,134 INFO ]: Analyzing trace with hash 990939357, now seen corresponding path program 1 times [2018-06-26 21:25:06,134 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:06,134 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:06,135 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:06,135 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:06,135 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:06,161 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:06,930 INFO ]: Checked inductivity of 91 backedges. 25 proven. 51 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-26 21:25:06,930 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:06,930 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-26 21:25:06,945 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:07,001 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:07,005 INFO ]: Computing forward predicates... [2018-06-26 21:25:07,586 INFO ]: Checked inductivity of 91 backedges. 25 proven. 48 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2018-06-26 21:25:07,617 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:07,617 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 7] total 11 [2018-06-26 21:25:07,617 INFO ]: Interpolant automaton has 11 states [2018-06-26 21:25:07,617 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-26 21:25:07,617 INFO ]: CoverageRelationStatistics Valid=28, Invalid=82, Unknown=0, NotChecked=0, Total=110 [2018-06-26 21:25:07,617 INFO ]: Start difference. First operand 28 states and 112 transitions. Second operand 11 states. [2018-06-26 21:25:08,028 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 10 [2018-06-26 21:25:08,604 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:08,604 INFO ]: Finished difference Result 64 states and 259 transitions. [2018-06-26 21:25:08,604 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-26 21:25:08,604 INFO ]: Start accepts. Automaton has 11 states. Word has length 18 [2018-06-26 21:25:08,604 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:08,605 INFO ]: With dead ends: 64 [2018-06-26 21:25:08,605 INFO ]: Without dead ends: 62 [2018-06-26 21:25:08,605 INFO ]: 0 DeclaredPredicates, 36 GetRequests, 19 SyntacticMatches, 3 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=61, Invalid=179, Unknown=0, NotChecked=0, Total=240 [2018-06-26 21:25:08,605 INFO ]: Start minimizeSevpa. Operand 62 states. [2018-06-26 21:25:08,609 INFO ]: Finished minimizeSevpa. Reduced states from 62 to 35. [2018-06-26 21:25:08,609 INFO ]: Start removeUnreachable. Operand 35 states. [2018-06-26 21:25:08,609 INFO ]: Finished removeUnreachable. Reduced from 35 states to 35 states and 143 transitions. [2018-06-26 21:25:08,609 INFO ]: Start accepts. Automaton has 35 states and 143 transitions. Word has length 18 [2018-06-26 21:25:08,609 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:08,609 INFO ]: Abstraction has 35 states and 143 transitions. [2018-06-26 21:25:08,609 INFO ]: Interpolant automaton has 11 states. [2018-06-26 21:25:08,610 INFO ]: Start isEmpty. Operand 35 states and 143 transitions. [2018-06-26 21:25:08,610 INFO ]: Finished isEmpty. Found accepting run of length 20 [2018-06-26 21:25:08,610 INFO ]: Found error trace [2018-06-26 21:25:08,610 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:08,610 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:08,610 INFO ]: Analyzing trace with hash -175865637, now seen corresponding path program 1 times [2018-06-26 21:25:08,610 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:08,610 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:08,611 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:08,611 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:08,611 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:08,621 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:08,643 INFO ]: Checked inductivity of 105 backedges. 59 proven. 0 refuted. 0 times theorem prover too weak. 46 trivial. 0 not checked. [2018-06-26 21:25:08,644 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:25:08,644 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:25:08,644 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:25:08,644 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:25:08,644 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:25:08,644 INFO ]: Start difference. First operand 35 states and 143 transitions. Second operand 3 states. [2018-06-26 21:25:08,703 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:08,703 INFO ]: Finished difference Result 34 states and 91 transitions. [2018-06-26 21:25:08,703 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:25:08,703 INFO ]: Start accepts. Automaton has 3 states. Word has length 19 [2018-06-26 21:25:08,703 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:08,703 INFO ]: With dead ends: 34 [2018-06-26 21:25:08,703 INFO ]: Without dead ends: 34 [2018-06-26 21:25:08,703 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:25:08,704 INFO ]: Start minimizeSevpa. Operand 34 states. [2018-06-26 21:25:08,705 INFO ]: Finished minimizeSevpa. Reduced states from 34 to 33. [2018-06-26 21:25:08,705 INFO ]: Start removeUnreachable. Operand 33 states. [2018-06-26 21:25:08,706 INFO ]: Finished removeUnreachable. Reduced from 33 states to 33 states and 89 transitions. [2018-06-26 21:25:08,706 INFO ]: Start accepts. Automaton has 33 states and 89 transitions. Word has length 19 [2018-06-26 21:25:08,706 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:08,706 INFO ]: Abstraction has 33 states and 89 transitions. [2018-06-26 21:25:08,706 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:25:08,706 INFO ]: Start isEmpty. Operand 33 states and 89 transitions. [2018-06-26 21:25:08,707 INFO ]: Finished isEmpty. Found accepting run of length 23 [2018-06-26 21:25:08,707 INFO ]: Found error trace [2018-06-26 21:25:08,707 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:08,707 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:08,707 INFO ]: Analyzing trace with hash 1071905848, now seen corresponding path program 1 times [2018-06-26 21:25:08,707 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:08,707 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:08,708 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:08,708 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:08,708 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:08,721 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:08,806 INFO ]: Checked inductivity of 153 backedges. 106 proven. 24 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2018-06-26 21:25:08,806 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:08,806 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:08,815 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:08,871 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:08,875 INFO ]: Computing forward predicates... [2018-06-26 21:25:08,889 INFO ]: Checked inductivity of 153 backedges. 116 proven. 0 refuted. 0 times theorem prover too weak. 37 trivial. 0 not checked. [2018-06-26 21:25:08,920 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 21:25:08,920 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [6] total 6 [2018-06-26 21:25:08,920 INFO ]: Interpolant automaton has 6 states [2018-06-26 21:25:08,920 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-26 21:25:08,920 INFO ]: CoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-26 21:25:08,921 INFO ]: Start difference. First operand 33 states and 89 transitions. Second operand 6 states. [2018-06-26 21:25:09,171 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:09,172 INFO ]: Finished difference Result 64 states and 176 transitions. [2018-06-26 21:25:09,172 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-26 21:25:09,172 INFO ]: Start accepts. Automaton has 6 states. Word has length 22 [2018-06-26 21:25:09,172 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:09,173 INFO ]: With dead ends: 64 [2018-06-26 21:25:09,173 INFO ]: Without dead ends: 61 [2018-06-26 21:25:09,173 INFO ]: 0 DeclaredPredicates, 37 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=13, Invalid=17, Unknown=0, NotChecked=0, Total=30 [2018-06-26 21:25:09,173 INFO ]: Start minimizeSevpa. Operand 61 states. [2018-06-26 21:25:09,176 INFO ]: Finished minimizeSevpa. Reduced states from 61 to 30. [2018-06-26 21:25:09,176 INFO ]: Start removeUnreachable. Operand 30 states. [2018-06-26 21:25:09,176 INFO ]: Finished removeUnreachable. Reduced from 30 states to 30 states and 81 transitions. [2018-06-26 21:25:09,176 INFO ]: Start accepts. Automaton has 30 states and 81 transitions. Word has length 22 [2018-06-26 21:25:09,177 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:09,177 INFO ]: Abstraction has 30 states and 81 transitions. [2018-06-26 21:25:09,177 INFO ]: Interpolant automaton has 6 states. [2018-06-26 21:25:09,177 INFO ]: Start isEmpty. Operand 30 states and 81 transitions. [2018-06-26 21:25:09,177 INFO ]: Finished isEmpty. Found accepting run of length 23 [2018-06-26 21:25:09,177 INFO ]: Found error trace [2018-06-26 21:25:09,177 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:09,178 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:09,178 INFO ]: Analyzing trace with hash -1403968383, now seen corresponding path program 1 times [2018-06-26 21:25:09,178 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:09,178 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:09,178 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:09,178 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:09,178 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:09,192 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:09,260 INFO ]: Checked inductivity of 153 backedges. 79 proven. 39 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2018-06-26 21:25:09,260 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:09,260 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:09,267 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:09,331 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:09,335 INFO ]: Computing forward predicates... [2018-06-26 21:25:09,351 INFO ]: Checked inductivity of 153 backedges. 115 proven. 5 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2018-06-26 21:25:09,383 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:09,383 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4] total 5 [2018-06-26 21:25:09,383 INFO ]: Interpolant automaton has 5 states [2018-06-26 21:25:09,383 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 21:25:09,383 INFO ]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-26 21:25:09,384 INFO ]: Start difference. First operand 30 states and 81 transitions. Second operand 5 states. [2018-06-26 21:25:09,634 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:09,634 INFO ]: Finished difference Result 57 states and 148 transitions. [2018-06-26 21:25:09,634 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-26 21:25:09,635 INFO ]: Start accepts. Automaton has 5 states. Word has length 22 [2018-06-26 21:25:09,635 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:09,635 INFO ]: With dead ends: 57 [2018-06-26 21:25:09,635 INFO ]: Without dead ends: 57 [2018-06-26 21:25:09,635 INFO ]: 0 DeclaredPredicates, 37 GetRequests, 34 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2018-06-26 21:25:09,635 INFO ]: Start minimizeSevpa. Operand 57 states. [2018-06-26 21:25:09,640 INFO ]: Finished minimizeSevpa. Reduced states from 57 to 43. [2018-06-26 21:25:09,640 INFO ]: Start removeUnreachable. Operand 43 states. [2018-06-26 21:25:09,640 INFO ]: Finished removeUnreachable. Reduced from 43 states to 43 states and 112 transitions. [2018-06-26 21:25:09,640 INFO ]: Start accepts. Automaton has 43 states and 112 transitions. Word has length 22 [2018-06-26 21:25:09,640 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:09,641 INFO ]: Abstraction has 43 states and 112 transitions. [2018-06-26 21:25:09,641 INFO ]: Interpolant automaton has 5 states. [2018-06-26 21:25:09,641 INFO ]: Start isEmpty. Operand 43 states and 112 transitions. [2018-06-26 21:25:09,641 INFO ]: Finished isEmpty. Found accepting run of length 23 [2018-06-26 21:25:09,641 INFO ]: Found error trace [2018-06-26 21:25:09,641 INFO ]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:09,641 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:09,642 INFO ]: Analyzing trace with hash 657925135, now seen corresponding path program 1 times [2018-06-26 21:25:09,642 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:09,642 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:09,642 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:09,642 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:09,642 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:09,658 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:09,738 INFO ]: Checked inductivity of 153 backedges. 77 proven. 43 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2018-06-26 21:25:09,738 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:09,738 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:09,754 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:09,819 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:09,823 INFO ]: Computing forward predicates... [2018-06-26 21:25:09,877 INFO ]: Checked inductivity of 153 backedges. 117 proven. 5 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-06-26 21:25:09,907 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:09,907 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 9 [2018-06-26 21:25:09,907 INFO ]: Interpolant automaton has 9 states [2018-06-26 21:25:09,907 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-26 21:25:09,907 INFO ]: CoverageRelationStatistics Valid=31, Invalid=41, Unknown=0, NotChecked=0, Total=72 [2018-06-26 21:25:09,907 INFO ]: Start difference. First operand 43 states and 112 transitions. Second operand 9 states. [2018-06-26 21:25:10,062 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:10,062 INFO ]: Finished difference Result 60 states and 143 transitions. [2018-06-26 21:25:10,062 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-26 21:25:10,062 INFO ]: Start accepts. Automaton has 9 states. Word has length 22 [2018-06-26 21:25:10,062 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:10,063 INFO ]: With dead ends: 60 [2018-06-26 21:25:10,063 INFO ]: Without dead ends: 45 [2018-06-26 21:25:10,063 INFO ]: 0 DeclaredPredicates, 39 GetRequests, 32 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=31, Invalid=41, Unknown=0, NotChecked=0, Total=72 [2018-06-26 21:25:10,063 INFO ]: Start minimizeSevpa. Operand 45 states. [2018-06-26 21:25:10,065 INFO ]: Finished minimizeSevpa. Reduced states from 45 to 30. [2018-06-26 21:25:10,065 INFO ]: Start removeUnreachable. Operand 30 states. [2018-06-26 21:25:10,066 INFO ]: Finished removeUnreachable. Reduced from 30 states to 30 states and 81 transitions. [2018-06-26 21:25:10,066 INFO ]: Start accepts. Automaton has 30 states and 81 transitions. Word has length 22 [2018-06-26 21:25:10,066 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:10,066 INFO ]: Abstraction has 30 states and 81 transitions. [2018-06-26 21:25:10,066 INFO ]: Interpolant automaton has 9 states. [2018-06-26 21:25:10,066 INFO ]: Start isEmpty. Operand 30 states and 81 transitions. [2018-06-26 21:25:10,066 INFO ]: Finished isEmpty. Found accepting run of length 27 [2018-06-26 21:25:10,066 INFO ]: Found error trace [2018-06-26 21:25:10,066 INFO ]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:10,067 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:10,067 INFO ]: Analyzing trace with hash 1765110364, now seen corresponding path program 1 times [2018-06-26 21:25:10,067 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:10,067 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:10,067 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:10,067 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:10,067 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:10,081 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:10,245 INFO ]: Checked inductivity of 231 backedges. 134 proven. 48 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2018-06-26 21:25:10,245 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:10,245 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-26 21:25:10,275 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:10,352 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:10,356 INFO ]: Computing forward predicates... [2018-06-26 21:25:10,586 INFO ]: Checked inductivity of 231 backedges. 134 proven. 48 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2018-06-26 21:25:10,606 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:10,606 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2018-06-26 21:25:10,607 INFO ]: Interpolant automaton has 10 states [2018-06-26 21:25:10,607 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-26 21:25:10,607 INFO ]: CoverageRelationStatistics Valid=30, Invalid=60, Unknown=0, NotChecked=0, Total=90 [2018-06-26 21:25:10,607 INFO ]: Start difference. First operand 30 states and 81 transitions. Second operand 10 states. [2018-06-26 21:25:10,821 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:10,821 INFO ]: Finished difference Result 60 states and 149 transitions. [2018-06-26 21:25:10,822 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-26 21:25:10,822 INFO ]: Start accepts. Automaton has 10 states. Word has length 26 [2018-06-26 21:25:10,822 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:10,822 INFO ]: With dead ends: 60 [2018-06-26 21:25:10,822 INFO ]: Without dead ends: 42 [2018-06-26 21:25:10,822 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 36 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=49, Invalid=83, Unknown=0, NotChecked=0, Total=132 [2018-06-26 21:25:10,822 INFO ]: Start minimizeSevpa. Operand 42 states. [2018-06-26 21:25:10,824 INFO ]: Finished minimizeSevpa. Reduced states from 42 to 34. [2018-06-26 21:25:10,824 INFO ]: Start removeUnreachable. Operand 34 states. [2018-06-26 21:25:10,825 INFO ]: Finished removeUnreachable. Reduced from 34 states to 34 states and 89 transitions. [2018-06-26 21:25:10,825 INFO ]: Start accepts. Automaton has 34 states and 89 transitions. Word has length 26 [2018-06-26 21:25:10,825 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:10,825 INFO ]: Abstraction has 34 states and 89 transitions. [2018-06-26 21:25:10,825 INFO ]: Interpolant automaton has 10 states. [2018-06-26 21:25:10,825 INFO ]: Start isEmpty. Operand 34 states and 89 transitions. [2018-06-26 21:25:10,825 INFO ]: Finished isEmpty. Found accepting run of length 27 [2018-06-26 21:25:10,825 INFO ]: Found error trace [2018-06-26 21:25:10,825 INFO ]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:10,826 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:10,828 INFO ]: Analyzing trace with hash -1891178326, now seen corresponding path program 1 times [2018-06-26 21:25:10,828 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:10,828 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:10,829 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:10,829 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:10,829 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:10,847 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:11,131 INFO ]: Checked inductivity of 231 backedges. 41 proven. 147 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2018-06-26 21:25:11,131 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:11,131 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:11,137 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:11,192 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:11,196 INFO ]: Computing forward predicates... [2018-06-26 21:25:11,290 INFO ]: Checked inductivity of 231 backedges. 41 proven. 150 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2018-06-26 21:25:11,309 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:11,310 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 13 [2018-06-26 21:25:11,310 INFO ]: Interpolant automaton has 13 states [2018-06-26 21:25:11,310 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-26 21:25:11,310 INFO ]: CoverageRelationStatistics Valid=33, Invalid=123, Unknown=0, NotChecked=0, Total=156 [2018-06-26 21:25:11,310 INFO ]: Start difference. First operand 34 states and 89 transitions. Second operand 13 states. [2018-06-26 21:25:11,969 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:11,969 INFO ]: Finished difference Result 76 states and 194 transitions. [2018-06-26 21:25:11,969 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-26 21:25:11,969 INFO ]: Start accepts. Automaton has 13 states. Word has length 26 [2018-06-26 21:25:11,969 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:11,969 INFO ]: With dead ends: 76 [2018-06-26 21:25:11,969 INFO ]: Without dead ends: 74 [2018-06-26 21:25:11,970 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 33 SyntacticMatches, 3 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 78 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=109, Invalid=353, Unknown=0, NotChecked=0, Total=462 [2018-06-26 21:25:11,970 INFO ]: Start minimizeSevpa. Operand 74 states. [2018-06-26 21:25:11,972 INFO ]: Finished minimizeSevpa. Reduced states from 74 to 45. [2018-06-26 21:25:11,972 INFO ]: Start removeUnreachable. Operand 45 states. [2018-06-26 21:25:11,972 INFO ]: Finished removeUnreachable. Reduced from 45 states to 45 states and 113 transitions. [2018-06-26 21:25:11,972 INFO ]: Start accepts. Automaton has 45 states and 113 transitions. Word has length 26 [2018-06-26 21:25:11,972 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:11,973 INFO ]: Abstraction has 45 states and 113 transitions. [2018-06-26 21:25:11,973 INFO ]: Interpolant automaton has 13 states. [2018-06-26 21:25:11,973 INFO ]: Start isEmpty. Operand 45 states and 113 transitions. [2018-06-26 21:25:11,974 INFO ]: Finished isEmpty. Found accepting run of length 31 [2018-06-26 21:25:11,974 INFO ]: Found error trace [2018-06-26 21:25:11,974 INFO ]: trace histogram [3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:11,974 INFO ]: === Iteration 20 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:11,974 INFO ]: Analyzing trace with hash -2092248827, now seen corresponding path program 2 times [2018-06-26 21:25:11,974 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:11,974 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:11,975 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:11,975 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:11,975 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:11,999 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:12,461 INFO ]: Checked inductivity of 325 backedges. 214 proven. 60 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2018-06-26 21:25:12,461 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:12,461 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-26 21:25:12,475 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:12,570 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 21:25:12,570 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:12,574 INFO ]: Computing forward predicates... [2018-06-26 21:25:12,592 INFO ]: Checked inductivity of 325 backedges. 240 proven. 20 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2018-06-26 21:25:12,622 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:12,622 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 5] total 7 [2018-06-26 21:25:12,622 INFO ]: Interpolant automaton has 7 states [2018-06-26 21:25:12,622 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-26 21:25:12,622 INFO ]: CoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-06-26 21:25:12,623 INFO ]: Start difference. First operand 45 states and 113 transitions. Second operand 7 states. [2018-06-26 21:25:13,228 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:13,228 INFO ]: Finished difference Result 89 states and 226 transitions. [2018-06-26 21:25:13,228 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-26 21:25:13,228 INFO ]: Start accepts. Automaton has 7 states. Word has length 30 [2018-06-26 21:25:13,228 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:13,229 INFO ]: With dead ends: 89 [2018-06-26 21:25:13,229 INFO ]: Without dead ends: 86 [2018-06-26 21:25:13,229 INFO ]: 0 DeclaredPredicates, 53 GetRequests, 48 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-06-26 21:25:13,229 INFO ]: Start minimizeSevpa. Operand 86 states. [2018-06-26 21:25:13,231 INFO ]: Finished minimizeSevpa. Reduced states from 86 to 38. [2018-06-26 21:25:13,232 INFO ]: Start removeUnreachable. Operand 38 states. [2018-06-26 21:25:13,232 INFO ]: Finished removeUnreachable. Reduced from 38 states to 38 states and 97 transitions. [2018-06-26 21:25:13,232 INFO ]: Start accepts. Automaton has 38 states and 97 transitions. Word has length 30 [2018-06-26 21:25:13,232 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:13,232 INFO ]: Abstraction has 38 states and 97 transitions. [2018-06-26 21:25:13,232 INFO ]: Interpolant automaton has 7 states. [2018-06-26 21:25:13,232 INFO ]: Start isEmpty. Operand 38 states and 97 transitions. [2018-06-26 21:25:13,233 INFO ]: Finished isEmpty. Found accepting run of length 31 [2018-06-26 21:25:13,233 INFO ]: Found error trace [2018-06-26 21:25:13,233 INFO ]: trace histogram [3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:13,233 INFO ]: === Iteration 21 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:13,233 INFO ]: Analyzing trace with hash 998823374, now seen corresponding path program 2 times [2018-06-26 21:25:13,233 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:13,233 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:13,234 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:13,234 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:25:13,234 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:13,249 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:13,371 INFO ]: Checked inductivity of 325 backedges. 163 proven. 99 refuted. 0 times theorem prover too weak. 63 trivial. 0 not checked. [2018-06-26 21:25:13,371 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:13,371 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-26 21:25:13,384 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:13,469 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 21:25:13,469 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:13,473 INFO ]: Computing forward predicates... [2018-06-26 21:25:13,492 INFO ]: Checked inductivity of 325 backedges. 231 proven. 33 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2018-06-26 21:25:13,514 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:13,514 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 6 [2018-06-26 21:25:13,515 INFO ]: Interpolant automaton has 6 states [2018-06-26 21:25:13,515 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-26 21:25:13,515 INFO ]: CoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2018-06-26 21:25:13,515 INFO ]: Start difference. First operand 38 states and 97 transitions. Second operand 6 states. [2018-06-26 21:25:13,646 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:13,646 INFO ]: Finished difference Result 82 states and 198 transitions. [2018-06-26 21:25:13,646 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-26 21:25:13,646 INFO ]: Start accepts. Automaton has 6 states. Word has length 30 [2018-06-26 21:25:13,646 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:13,649 INFO ]: With dead ends: 82 [2018-06-26 21:25:13,649 INFO ]: Without dead ends: 82 [2018-06-26 21:25:13,649 INFO ]: 0 DeclaredPredicates, 53 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=15, Unknown=0, NotChecked=0, Total=30 [2018-06-26 21:25:13,649 INFO ]: Start minimizeSevpa. Operand 82 states. [2018-06-26 21:25:13,652 INFO ]: Finished minimizeSevpa. Reduced states from 82 to 59. [2018-06-26 21:25:13,652 INFO ]: Start removeUnreachable. Operand 59 states. [2018-06-26 21:25:13,653 INFO ]: Finished removeUnreachable. Reduced from 59 states to 59 states and 144 transitions. [2018-06-26 21:25:13,653 INFO ]: Start accepts. Automaton has 59 states and 144 transitions. Word has length 30 [2018-06-26 21:25:13,653 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:13,653 INFO ]: Abstraction has 59 states and 144 transitions. [2018-06-26 21:25:13,653 INFO ]: Interpolant automaton has 6 states. [2018-06-26 21:25:13,653 INFO ]: Start isEmpty. Operand 59 states and 144 transitions. [2018-06-26 21:25:13,654 INFO ]: Finished isEmpty. Found accepting run of length 31 [2018-06-26 21:25:13,654 INFO ]: Found error trace [2018-06-26 21:25:13,654 INFO ]: trace histogram [3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:13,654 INFO ]: === Iteration 22 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:13,654 INFO ]: Analyzing trace with hash -1234250404, now seen corresponding path program 1 times [2018-06-26 21:25:13,654 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:13,654 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:13,663 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:13,663 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:25:13,663 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:13,679 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:14,086 INFO ]: Checked inductivity of 325 backedges. 161 proven. 103 refuted. 0 times theorem prover too weak. 61 trivial. 0 not checked. [2018-06-26 21:25:14,086 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:14,086 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:14,092 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:14,155 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:14,160 INFO ]: Computing forward predicates... [2018-06-26 21:25:14,233 INFO ]: Checked inductivity of 325 backedges. 233 proven. 33 refuted. 0 times theorem prover too weak. 59 trivial. 0 not checked. [2018-06-26 21:25:14,253 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:14,253 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 11 [2018-06-26 21:25:14,253 INFO ]: Interpolant automaton has 11 states [2018-06-26 21:25:14,253 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-26 21:25:14,253 INFO ]: CoverageRelationStatistics Valid=47, Invalid=63, Unknown=0, NotChecked=0, Total=110 [2018-06-26 21:25:14,253 INFO ]: Start difference. First operand 59 states and 144 transitions. Second operand 11 states. [2018-06-26 21:25:14,806 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:14,806 INFO ]: Finished difference Result 85 states and 193 transitions. [2018-06-26 21:25:14,808 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-26 21:25:14,808 INFO ]: Start accepts. Automaton has 11 states. Word has length 30 [2018-06-26 21:25:14,808 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:14,808 INFO ]: With dead ends: 85 [2018-06-26 21:25:14,808 INFO ]: Without dead ends: 66 [2018-06-26 21:25:14,808 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 46 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=47, Invalid=63, Unknown=0, NotChecked=0, Total=110 [2018-06-26 21:25:14,808 INFO ]: Start minimizeSevpa. Operand 66 states. [2018-06-26 21:25:14,810 INFO ]: Finished minimizeSevpa. Reduced states from 66 to 38. [2018-06-26 21:25:14,810 INFO ]: Start removeUnreachable. Operand 38 states. [2018-06-26 21:25:14,810 INFO ]: Finished removeUnreachable. Reduced from 38 states to 38 states and 97 transitions. [2018-06-26 21:25:14,810 INFO ]: Start accepts. Automaton has 38 states and 97 transitions. Word has length 30 [2018-06-26 21:25:14,810 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:14,810 INFO ]: Abstraction has 38 states and 97 transitions. [2018-06-26 21:25:14,810 INFO ]: Interpolant automaton has 11 states. [2018-06-26 21:25:14,810 INFO ]: Start isEmpty. Operand 38 states and 97 transitions. [2018-06-26 21:25:14,811 INFO ]: Finished isEmpty. Found accepting run of length 35 [2018-06-26 21:25:14,811 INFO ]: Found error trace [2018-06-26 21:25:14,811 INFO ]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:14,811 INFO ]: === Iteration 23 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:14,811 INFO ]: Analyzing trace with hash 1079711913, now seen corresponding path program 3 times [2018-06-26 21:25:14,811 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:14,811 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:14,811 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:14,811 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:14,811 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:14,827 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:15,078 INFO ]: Checked inductivity of 435 backedges. 242 proven. 116 refuted. 0 times theorem prover too weak. 77 trivial. 0 not checked. [2018-06-26 21:25:15,078 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:15,078 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:15,084 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 21:25:15,177 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2018-06-26 21:25:15,177 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:15,182 INFO ]: Computing forward predicates... [2018-06-26 21:25:15,304 INFO ]: Checked inductivity of 435 backedges. 200 proven. 72 refuted. 0 times theorem prover too weak. 163 trivial. 0 not checked. [2018-06-26 21:25:15,337 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:15,337 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 11 [2018-06-26 21:25:15,337 INFO ]: Interpolant automaton has 11 states [2018-06-26 21:25:15,337 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-26 21:25:15,337 INFO ]: CoverageRelationStatistics Valid=30, Invalid=80, Unknown=0, NotChecked=0, Total=110 [2018-06-26 21:25:15,338 INFO ]: Start difference. First operand 38 states and 97 transitions. Second operand 11 states. [2018-06-26 21:25:16,009 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:16,009 INFO ]: Finished difference Result 121 states and 301 transitions. [2018-06-26 21:25:16,009 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-06-26 21:25:16,009 INFO ]: Start accepts. Automaton has 11 states. Word has length 34 [2018-06-26 21:25:16,010 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:16,010 INFO ]: With dead ends: 121 [2018-06-26 21:25:16,010 INFO ]: Without dead ends: 56 [2018-06-26 21:25:16,011 INFO ]: 0 DeclaredPredicates, 84 GetRequests, 54 SyntacticMatches, 2 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 198 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=268, Invalid=602, Unknown=0, NotChecked=0, Total=870 [2018-06-26 21:25:16,011 INFO ]: Start minimizeSevpa. Operand 56 states. [2018-06-26 21:25:16,012 INFO ]: Finished minimizeSevpa. Reduced states from 56 to 38. [2018-06-26 21:25:16,012 INFO ]: Start removeUnreachable. Operand 38 states. [2018-06-26 21:25:16,013 INFO ]: Finished removeUnreachable. Reduced from 38 states to 38 states and 89 transitions. [2018-06-26 21:25:16,013 INFO ]: Start accepts. Automaton has 38 states and 89 transitions. Word has length 34 [2018-06-26 21:25:16,013 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:16,013 INFO ]: Abstraction has 38 states and 89 transitions. [2018-06-26 21:25:16,013 INFO ]: Interpolant automaton has 11 states. [2018-06-26 21:25:16,013 INFO ]: Start isEmpty. Operand 38 states and 89 transitions. [2018-06-26 21:25:16,014 INFO ]: Finished isEmpty. Found accepting run of length 35 [2018-06-26 21:25:16,014 INFO ]: Found error trace [2018-06-26 21:25:16,014 INFO ]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:16,014 INFO ]: === Iteration 24 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:16,017 INFO ]: Analyzing trace with hash 2104516855, now seen corresponding path program 3 times [2018-06-26 21:25:16,017 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:16,017 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:16,018 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:16,018 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:25:16,018 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:16,038 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:16,569 WARN ]: Spent 100.00 ms on a formula simplification that was a NOOP. DAG size: 9 [2018-06-26 21:25:17,265 INFO ]: Checked inductivity of 435 backedges. 57 proven. 307 refuted. 0 times theorem prover too weak. 71 trivial. 0 not checked. [2018-06-26 21:25:17,265 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:17,265 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-26 21:25:17,280 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:17,386 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 16 check-sat command(s) [2018-06-26 21:25:17,386 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:17,393 INFO ]: Computing forward predicates... [2018-06-26 21:25:17,473 INFO ]: Checked inductivity of 435 backedges. 69 proven. 189 refuted. 0 times theorem prover too weak. 177 trivial. 0 not checked. [2018-06-26 21:25:17,493 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:17,493 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-26 21:25:17,493 INFO ]: Interpolant automaton has 14 states [2018-06-26 21:25:17,493 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-26 21:25:17,494 INFO ]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2018-06-26 21:25:17,494 INFO ]: Start difference. First operand 38 states and 89 transitions. Second operand 14 states. [2018-06-26 21:25:18,557 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:18,557 INFO ]: Finished difference Result 132 states and 298 transitions. [2018-06-26 21:25:18,558 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-06-26 21:25:18,558 INFO ]: Start accepts. Automaton has 14 states. Word has length 34 [2018-06-26 21:25:18,558 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:18,559 INFO ]: With dead ends: 132 [2018-06-26 21:25:18,559 INFO ]: Without dead ends: 66 [2018-06-26 21:25:18,559 INFO ]: 0 DeclaredPredicates, 82 GetRequests, 48 SyntacticMatches, 3 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 215 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=208, Invalid=848, Unknown=0, NotChecked=0, Total=1056 [2018-06-26 21:25:18,559 INFO ]: Start minimizeSevpa. Operand 66 states. [2018-06-26 21:25:18,560 INFO ]: Finished minimizeSevpa. Reduced states from 66 to 46. [2018-06-26 21:25:18,560 INFO ]: Start removeUnreachable. Operand 46 states. [2018-06-26 21:25:18,561 INFO ]: Finished removeUnreachable. Reduced from 46 states to 46 states and 103 transitions. [2018-06-26 21:25:18,561 INFO ]: Start accepts. Automaton has 46 states and 103 transitions. Word has length 34 [2018-06-26 21:25:18,561 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:18,561 INFO ]: Abstraction has 46 states and 103 transitions. [2018-06-26 21:25:18,561 INFO ]: Interpolant automaton has 14 states. [2018-06-26 21:25:18,561 INFO ]: Start isEmpty. Operand 46 states and 103 transitions. [2018-06-26 21:25:18,561 INFO ]: Finished isEmpty. Found accepting run of length 39 [2018-06-26 21:25:18,561 INFO ]: Found error trace [2018-06-26 21:25:18,561 INFO ]: trace histogram [4, 4, 4, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:18,561 INFO ]: === Iteration 25 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:18,561 INFO ]: Analyzing trace with hash -1192929719, now seen corresponding path program 1 times [2018-06-26 21:25:18,561 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:18,561 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:18,562 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:18,562 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:25:18,562 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:18,578 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:18,733 INFO ]: Checked inductivity of 561 backedges. 307 proven. 163 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2018-06-26 21:25:18,733 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:18,754 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:18,759 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:18,867 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:18,874 INFO ]: Computing forward predicates... [2018-06-26 21:25:18,903 INFO ]: Checked inductivity of 561 backedges. 379 proven. 93 refuted. 0 times theorem prover too weak. 89 trivial. 0 not checked. [2018-06-26 21:25:18,936 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:18,936 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 6] total 7 [2018-06-26 21:25:18,936 INFO ]: Interpolant automaton has 7 states [2018-06-26 21:25:18,936 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-26 21:25:18,936 INFO ]: CoverageRelationStatistics Valid=21, Invalid=21, Unknown=0, NotChecked=0, Total=42 [2018-06-26 21:25:18,936 INFO ]: Start difference. First operand 46 states and 103 transitions. Second operand 7 states. [2018-06-26 21:25:19,146 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:19,146 INFO ]: Finished difference Result 70 states and 159 transitions. [2018-06-26 21:25:19,146 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-26 21:25:19,147 INFO ]: Start accepts. Automaton has 7 states. Word has length 38 [2018-06-26 21:25:19,147 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:19,147 INFO ]: With dead ends: 70 [2018-06-26 21:25:19,147 INFO ]: Without dead ends: 70 [2018-06-26 21:25:19,147 INFO ]: 0 DeclaredPredicates, 68 GetRequests, 63 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=21, Unknown=0, NotChecked=0, Total=42 [2018-06-26 21:25:19,147 INFO ]: Start minimizeSevpa. Operand 70 states. [2018-06-26 21:25:19,149 INFO ]: Finished minimizeSevpa. Reduced states from 70 to 60. [2018-06-26 21:25:19,149 INFO ]: Start removeUnreachable. Operand 60 states. [2018-06-26 21:25:19,150 INFO ]: Finished removeUnreachable. Reduced from 60 states to 60 states and 134 transitions. [2018-06-26 21:25:19,150 INFO ]: Start accepts. Automaton has 60 states and 134 transitions. Word has length 38 [2018-06-26 21:25:19,150 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:19,150 INFO ]: Abstraction has 60 states and 134 transitions. [2018-06-26 21:25:19,150 INFO ]: Interpolant automaton has 7 states. [2018-06-26 21:25:19,150 INFO ]: Start isEmpty. Operand 60 states and 134 transitions. [2018-06-26 21:25:19,150 INFO ]: Finished isEmpty. Found accepting run of length 39 [2018-06-26 21:25:19,150 INFO ]: Found error trace [2018-06-26 21:25:19,150 INFO ]: trace histogram [4, 4, 4, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:19,150 INFO ]: === Iteration 26 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:19,151 INFO ]: Analyzing trace with hash 868963799, now seen corresponding path program 1 times [2018-06-26 21:25:19,151 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:19,151 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:19,152 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:19,152 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:19,152 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:19,168 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:19,482 INFO ]: Checked inductivity of 561 backedges. 307 proven. 165 refuted. 0 times theorem prover too weak. 89 trivial. 0 not checked. [2018-06-26 21:25:19,482 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:19,482 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:19,503 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:19,582 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:19,588 INFO ]: Computing forward predicates... [2018-06-26 21:25:19,796 INFO ]: Checked inductivity of 561 backedges. 381 proven. 93 refuted. 0 times theorem prover too weak. 87 trivial. 0 not checked. [2018-06-26 21:25:19,815 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:19,815 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 13 [2018-06-26 21:25:19,815 INFO ]: Interpolant automaton has 13 states [2018-06-26 21:25:19,815 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-26 21:25:19,816 INFO ]: CoverageRelationStatistics Valid=66, Invalid=90, Unknown=0, NotChecked=0, Total=156 [2018-06-26 21:25:19,816 INFO ]: Start difference. First operand 60 states and 134 transitions. Second operand 13 states. [2018-06-26 21:25:20,014 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:20,014 INFO ]: Finished difference Result 73 states and 154 transitions. [2018-06-26 21:25:20,014 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-26 21:25:20,014 INFO ]: Start accepts. Automaton has 13 states. Word has length 38 [2018-06-26 21:25:20,014 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:20,014 INFO ]: With dead ends: 73 [2018-06-26 21:25:20,014 INFO ]: Without dead ends: 50 [2018-06-26 21:25:20,015 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 59 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=66, Invalid=90, Unknown=0, NotChecked=0, Total=156 [2018-06-26 21:25:20,015 INFO ]: Start minimizeSevpa. Operand 50 states. [2018-06-26 21:25:20,016 INFO ]: Finished minimizeSevpa. Reduced states from 50 to 42. [2018-06-26 21:25:20,016 INFO ]: Start removeUnreachable. Operand 42 states. [2018-06-26 21:25:20,017 INFO ]: Finished removeUnreachable. Reduced from 42 states to 42 states and 93 transitions. [2018-06-26 21:25:20,017 INFO ]: Start accepts. Automaton has 42 states and 93 transitions. Word has length 38 [2018-06-26 21:25:20,017 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:20,017 INFO ]: Abstraction has 42 states and 93 transitions. [2018-06-26 21:25:20,017 INFO ]: Interpolant automaton has 13 states. [2018-06-26 21:25:20,017 INFO ]: Start isEmpty. Operand 42 states and 93 transitions. [2018-06-26 21:25:20,017 INFO ]: Finished isEmpty. Found accepting run of length 39 [2018-06-26 21:25:20,017 INFO ]: Found error trace [2018-06-26 21:25:20,017 INFO ]: trace histogram [4, 4, 4, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:20,017 INFO ]: === Iteration 27 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:20,018 INFO ]: Analyzing trace with hash 1229858382, now seen corresponding path program 2 times [2018-06-26 21:25:20,018 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:20,018 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:20,018 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:20,018 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:25:20,018 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:20,031 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:20,190 INFO ]: Checked inductivity of 561 backedges. 382 proven. 100 refuted. 0 times theorem prover too weak. 79 trivial. 0 not checked. [2018-06-26 21:25:20,190 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:20,190 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:20,196 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 21:25:20,276 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 21:25:20,276 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:20,281 INFO ]: Computing forward predicates... [2018-06-26 21:25:20,298 INFO ]: Checked inductivity of 561 backedges. 396 proven. 72 refuted. 0 times theorem prover too weak. 93 trivial. 0 not checked. [2018-06-26 21:25:20,320 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:25:20,320 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 6] total 8 [2018-06-26 21:25:20,321 INFO ]: Interpolant automaton has 8 states [2018-06-26 21:25:20,321 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-26 21:25:20,321 INFO ]: CoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2018-06-26 21:25:20,321 INFO ]: Start difference. First operand 42 states and 93 transitions. Second operand 8 states. [2018-06-26 21:25:20,493 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:25:20,493 INFO ]: Finished difference Result 68 states and 168 transitions. [2018-06-26 21:25:20,493 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-26 21:25:20,493 INFO ]: Start accepts. Automaton has 8 states. Word has length 38 [2018-06-26 21:25:20,493 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:25:20,494 INFO ]: With dead ends: 68 [2018-06-26 21:25:20,494 INFO ]: Without dead ends: 65 [2018-06-26 21:25:20,494 INFO ]: 0 DeclaredPredicates, 68 GetRequests, 62 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=24, Invalid=32, Unknown=0, NotChecked=0, Total=56 [2018-06-26 21:25:20,494 INFO ]: Start minimizeSevpa. Operand 65 states. [2018-06-26 21:25:20,495 INFO ]: Finished minimizeSevpa. Reduced states from 65 to 46. [2018-06-26 21:25:20,495 INFO ]: Start removeUnreachable. Operand 46 states. [2018-06-26 21:25:20,496 INFO ]: Finished removeUnreachable. Reduced from 46 states to 46 states and 101 transitions. [2018-06-26 21:25:20,496 INFO ]: Start accepts. Automaton has 46 states and 101 transitions. Word has length 38 [2018-06-26 21:25:20,496 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:25:20,496 INFO ]: Abstraction has 46 states and 101 transitions. [2018-06-26 21:25:20,496 INFO ]: Interpolant automaton has 8 states. [2018-06-26 21:25:20,496 INFO ]: Start isEmpty. Operand 46 states and 101 transitions. [2018-06-26 21:25:20,496 INFO ]: Finished isEmpty. Found accepting run of length 43 [2018-06-26 21:25:20,496 INFO ]: Found error trace [2018-06-26 21:25:20,496 INFO ]: trace histogram [4, 4, 4, 4, 4, 4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:25:20,497 INFO ]: === Iteration 28 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:25:20,497 INFO ]: Analyzing trace with hash -21978766, now seen corresponding path program 3 times [2018-06-26 21:25:20,497 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:25:20,497 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:25:20,497 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:20,497 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:25:20,497 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:25:20,516 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:21,057 INFO ]: Checked inductivity of 703 backedges. 74 proven. 531 refuted. 0 times theorem prover too weak. 98 trivial. 0 not checked. [2018-06-26 21:25:21,057 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:25:21,057 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:21,072 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 21:25:21,211 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 20 check-sat command(s) [2018-06-26 21:25:21,211 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:25:21,220 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-26 21:25:21,360 INFO ]: Timeout while computing interpolants [2018-06-26 21:25:21,560 WARN ]: Destroyed unattended storables created during the last iteration: 21 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:25:21,560 WARN ]: Verification canceled [2018-06-26 21:25:21,562 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-26 21:25:21,564 WARN ]: Timeout [2018-06-26 21:25:21,564 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 09:25:21 BasicIcfg [2018-06-26 21:25:21,564 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-26 21:25:21,565 INFO ]: Toolchain (without parser) took 50946.85 ms. Allocated memory was 306.2 MB in the beginning and 2.5 GB in the end (delta: 2.2 GB). Free memory was 260.5 MB in the beginning and 1.3 GB in the end (delta: -1.0 GB). Peak memory consumption was 1.1 GB. Max. memory is 3.6 GB. [2018-06-26 21:25:21,566 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 306.2 MB. Free memory is still 271.6 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-26 21:25:21,566 INFO ]: ChcToBoogie took 57.35 ms. Allocated memory is still 306.2 MB. Free memory was 260.5 MB in the beginning and 257.5 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:25:21,567 INFO ]: Boogie Preprocessor took 37.80 ms. Allocated memory is still 306.2 MB. Free memory was 257.5 MB in the beginning and 256.5 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-26 21:25:21,567 INFO ]: RCFGBuilder took 202.20 ms. Allocated memory is still 306.2 MB. Free memory was 256.5 MB in the beginning and 247.5 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:25:21,567 INFO ]: BlockEncodingV2 took 24542.19 ms. Allocated memory was 306.2 MB in the beginning and 2.5 GB in the end (delta: 2.2 GB). Free memory was 247.5 MB in the beginning and 1.0 GB in the end (delta: -797.2 MB). Peak memory consumption was 1.8 GB. Max. memory is 3.6 GB. [2018-06-26 21:25:21,568 INFO ]: TraceAbstraction took 26097.55 ms. Allocated memory was 2.5 GB in the beginning and 2.5 GB in the end (delta: -4.7 MB). Free memory was 1.0 GB in the beginning and 1.3 GB in the end (delta: -241.8 MB). There was no memory consumed. Max. memory is 3.6 GB. [2018-06-26 21:25:21,571 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.plugins.blockencoding: - StatisticsResult: Initial Icfg 10 locations, 10 edges - StatisticsResult: Encoded RCFG 6 locations, 155 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 306.2 MB. Free memory is still 271.6 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 57.35 ms. Allocated memory is still 306.2 MB. Free memory was 260.5 MB in the beginning and 257.5 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 37.80 ms. Allocated memory is still 306.2 MB. Free memory was 257.5 MB in the beginning and 256.5 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 202.20 ms. Allocated memory is still 306.2 MB. Free memory was 256.5 MB in the beginning and 247.5 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 24542.19 ms. Allocated memory was 306.2 MB in the beginning and 2.5 GB in the end (delta: 2.2 GB). Free memory was 247.5 MB in the beginning and 1.0 GB in the end (delta: -797.2 MB). Peak memory consumption was 1.8 GB. Max. memory is 3.6 GB. * TraceAbstraction took 26097.55 ms. Allocated memory was 2.5 GB in the beginning and 2.5 GB in the end (delta: -4.7 MB). Free memory was 1.0 GB in the beginning and 1.3 GB in the end (delta: -241.8 MB). There was no memory consumed. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds Cancelled while BasicCegarLoop was analyzing trace of length 43 with TraceHistMax 4, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 18 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 6 locations, 1 error locations. TIMEOUT Result, 26.0s OverallTime, 28 OverallIterations, 4 TraceHistogramMax, 14.8s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 143 SDtfs, 39 SDslu, 403 SDs, 0 SdLazy, 7672 SolverSat, 3912 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 12.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 910 GetRequests, 713 SyntacticMatches, 15 SemanticMatches, 182 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 651 ImplicationChecksByTransitivity, 6.8s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=60occurred in iteration=25, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 27 MinimizatonAttempts, 340 StatesRemovedByMinimization, 22 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.3s SatisfiabilityAnalysisTime, 7.3s InterpolantComputationTime, 1035 NumberOfCodeBlocks, 1035 NumberOfCodeBlocksAsserted, 78 NumberOfCheckSat, 990 ConstructedInterpolants, 0 QuantifiedInterpolants, 114140 SizeOfPredicates, 0 NumberOfNonLiveVariables, 10220 ConjunctsInSsa, 1416 ConjunctsInUnsatCore, 45 InterpolantComputations, 13 PerfectInterpolantSequences, 7429/9807 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig28.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-26_21-25-21-582.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig28.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-26_21-25-21-582.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig28.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-26_21-25-21-582.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig28.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-26_21-25-21-582.csv Completed graceful shutdown