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/eldarica-misc/LIA/reve/020b-horn.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-62c3406-m [2018-06-26 18:08:35,212 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-26 18:08:35,214 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-26 18:08:35,225 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-26 18:08:35,225 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-26 18:08:35,226 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-26 18:08:35,227 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-26 18:08:35,229 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-26 18:08:35,231 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-26 18:08:35,231 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-26 18:08:35,232 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-26 18:08:35,232 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-26 18:08:35,233 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-26 18:08:35,234 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-26 18:08:35,235 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-26 18:08:35,236 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-26 18:08:35,236 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-26 18:08:35,240 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-26 18:08:35,251 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-26 18:08:35,253 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-26 18:08:35,254 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-26 18:08:35,255 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-26 18:08:35,257 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-26 18:08:35,257 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-26 18:08:35,258 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-26 18:08:35,258 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-26 18:08:35,259 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-26 18:08:35,260 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-26 18:08:35,261 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-26 18:08:35,262 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-26 18:08:35,262 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-26 18:08:35,263 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-26 18:08:35,263 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-06-26 18:08:35,263 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-26 18:08:35,264 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-26 18:08:35,264 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-26 18:08:35,265 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-26 18:08:35,287 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-26 18:08:35,287 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-26 18:08:35,287 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-26 18:08:35,288 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-26 18:08:35,288 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-26 18:08:35,289 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-26 18:08:35,292 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-26 18:08:35,292 INFO L133 SettingsManager]: * Use SBE=true [2018-06-26 18:08:35,292 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-26 18:08:35,293 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-26 18:08:35,293 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-26 18:08:35,293 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-26 18:08:35,293 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 18:08:35,293 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-26 18:08:35,293 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-26 18:08:35,294 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-26 18:08:35,294 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-26 18:08:35,294 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-26 18:08:35,294 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-26 18:08:35,294 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-26 18:08:35,294 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-26 18:08:35,297 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-26 18:08:35,297 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-26 18:08:35,343 INFO ]: Repository-Root is: /tmp [2018-06-26 18:08:35,357 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-26 18:08:35,362 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-26 18:08:35,364 INFO ]: Initializing SmtParser... [2018-06-26 18:08:35,364 INFO ]: SmtParser initialized [2018-06-26 18:08:35,364 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/eldarica-misc/LIA/reve/020b-horn.smt2 [2018-06-26 18:08:35,366 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 18:08:35,455 INFO ]: Executing SMT file /storage/chc-comp/eldarica-misc/LIA/reve/020b-horn.smt2 unknown [2018-06-26 18:08:35,632 INFO ]: Succesfully executed SMT file /storage/chc-comp/eldarica-misc/LIA/reve/020b-horn.smt2 [2018-06-26 18:08:35,636 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-26 18:08:35,641 INFO ]: Walking toolchain with 5 elements. [2018-06-26 18:08:35,641 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-26 18:08:35,641 INFO ]: Initializing ChcToBoogie... [2018-06-26 18:08:35,641 INFO ]: ChcToBoogie initialized [2018-06-26 18:08:35,644 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 06:08:35" (1/1) ... [2018-06-26 18:08:35,702 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:08:35 Unit [2018-06-26 18:08:35,702 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-26 18:08:35,703 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-26 18:08:35,703 INFO ]: Initializing Boogie Preprocessor... [2018-06-26 18:08:35,703 INFO ]: Boogie Preprocessor initialized [2018-06-26 18:08:35,725 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:08:35" (1/1) ... [2018-06-26 18:08:35,726 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:08:35" (1/1) ... [2018-06-26 18:08:35,731 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:08:35" (1/1) ... [2018-06-26 18:08:35,731 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:08:35" (1/1) ... [2018-06-26 18:08:35,733 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:08:35" (1/1) ... [2018-06-26 18:08:35,736 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:08:35" (1/1) ... [2018-06-26 18:08:35,737 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:08:35" (1/1) ... [2018-06-26 18:08:35,738 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-26 18:08:35,740 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-26 18:08:35,740 INFO ]: Initializing RCFGBuilder... [2018-06-26 18:08:35,741 INFO ]: RCFGBuilder initialized [2018-06-26 18:08:35,741 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:08:35" (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) [2018-06-26 18:08:35,755 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-26 18:08:35,755 INFO ]: Found specification of procedure gotoProc [2018-06-26 18:08:35,755 INFO ]: Found implementation of procedure gotoProc [2018-06-26 18:08:35,755 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-26 18:08:35,755 INFO ]: Found specification of procedure Ultimate.START [2018-06-26 18:08:35,755 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 18:08:35,985 INFO ]: Using library mode [2018-06-26 18:08:35,986 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 06:08:35 BoogieIcfgContainer [2018-06-26 18:08:35,986 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-26 18:08:35,986 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-26 18:08:35,986 INFO ]: Initializing BlockEncodingV2... [2018-06-26 18:08:35,995 INFO ]: BlockEncodingV2 initialized [2018-06-26 18:08:35,996 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 06:08:35" (1/1) ... [2018-06-26 18:08:36,031 INFO ]: Initial Icfg 10 locations, 12 edges [2018-06-26 18:08:36,032 INFO ]: Using Remove infeasible edges [2018-06-26 18:08:36,033 INFO ]: Using Maximize final states [2018-06-26 18:08:36,033 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-26 18:08:36,033 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-26 18:08:36,035 INFO ]: Using Remove sink states [2018-06-26 18:08:36,036 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-26 18:08:36,036 INFO ]: Using Use SBE [2018-06-26 18:08:36,041 INFO ]: SBE split 0 edges [2018-06-26 18:08:36,046 INFO ]: Removed 2 edges and 2 locations because of local infeasibility [2018-06-26 18:08:36,048 INFO ]: 0 new accepting states [2018-06-26 18:08:36,090 INFO ]: Removed 4 edges and 2 locations by large block encoding [2018-06-26 18:08:36,092 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 18:08:36,105 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-26 18:08:36,105 INFO ]: 0 new accepting states [2018-06-26 18:08:36,105 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-26 18:08:36,105 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 18:08:36,106 INFO ]: Encoded RCFG 6 locations, 8 edges [2018-06-26 18:08:36,106 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 06:08:36 BasicIcfg [2018-06-26 18:08:36,106 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-26 18:08:36,107 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-26 18:08:36,107 INFO ]: Initializing TraceAbstraction... [2018-06-26 18:08:36,113 INFO ]: TraceAbstraction initialized [2018-06-26 18:08:36,113 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 06:08:35" (1/4) ... [2018-06-26 18:08:36,114 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1024e1b9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 26.06 06:08:36, skipping insertion in model container [2018-06-26 18:08:36,114 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:08:35" (2/4) ... [2018-06-26 18:08:36,114 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1024e1b9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.06 06:08:36, skipping insertion in model container [2018-06-26 18:08:36,114 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 06:08:35" (3/4) ... [2018-06-26 18:08:36,114 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1024e1b9 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 06:08:36, skipping insertion in model container [2018-06-26 18:08:36,115 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 06:08:36" (4/4) ... [2018-06-26 18:08:36,116 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-26 18:08:36,125 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-26 18:08:36,131 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-26 18:08:36,165 INFO ]: Using default assertion order modulation [2018-06-26 18:08:36,166 INFO ]: Interprodecural is true [2018-06-26 18:08:36,166 INFO ]: Hoare is false [2018-06-26 18:08:36,166 INFO ]: Compute interpolants for FPandBP [2018-06-26 18:08:36,166 INFO ]: Backedges is TWOTRACK [2018-06-26 18:08:36,166 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-26 18:08:36,166 INFO ]: Difference is false [2018-06-26 18:08:36,166 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-26 18:08:36,166 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-26 18:08:36,176 INFO ]: Start isEmpty. Operand 6 states. [2018-06-26 18:08:36,186 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-26 18:08:36,186 INFO ]: Found error trace [2018-06-26 18:08:36,186 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-26 18:08:36,187 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:36,192 INFO ]: Analyzing trace with hash 37311172, now seen corresponding path program 1 times [2018-06-26 18:08:36,194 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:36,194 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:36,225 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:36,225 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:08:36,225 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:36,279 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:36,393 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:36,395 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:08:36,395 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 18:08:36,396 INFO ]: Interpolant automaton has 3 states [2018-06-26 18:08:36,409 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 18:08:36,410 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:08:36,412 INFO ]: Start difference. First operand 6 states. Second operand 3 states. [2018-06-26 18:08:36,509 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:36,509 INFO ]: Finished difference Result 7 states and 11 transitions. [2018-06-26 18:08:36,509 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 18:08:36,511 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-26 18:08:36,511 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:36,518 INFO ]: With dead ends: 7 [2018-06-26 18:08:36,518 INFO ]: Without dead ends: 7 [2018-06-26 18:08:36,520 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 18:08:36,532 INFO ]: Start minimizeSevpa. Operand 7 states. [2018-06-26 18:08:36,546 INFO ]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-06-26 18:08:36,547 INFO ]: Start removeUnreachable. Operand 7 states. [2018-06-26 18:08:36,547 INFO ]: Finished removeUnreachable. Reduced from 7 states to 7 states and 11 transitions. [2018-06-26 18:08:36,548 INFO ]: Start accepts. Automaton has 7 states and 11 transitions. Word has length 5 [2018-06-26 18:08:36,549 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:36,549 INFO ]: Abstraction has 7 states and 11 transitions. [2018-06-26 18:08:36,549 INFO ]: Interpolant automaton has 3 states. [2018-06-26 18:08:36,549 INFO ]: Start isEmpty. Operand 7 states and 11 transitions. [2018-06-26 18:08:36,549 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 18:08:36,549 INFO ]: Found error trace [2018-06-26 18:08:36,549 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 18:08:36,549 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:36,549 INFO ]: Analyzing trace with hash 1156261132, now seen corresponding path program 1 times [2018-06-26 18:08:36,549 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:36,549 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:36,550 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:36,550 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:08:36,550 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:36,564 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:36,681 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:36,681 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:36,681 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 18:08:36,692 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:08:36,729 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:36,737 INFO ]: Computing forward predicates... [2018-06-26 18:08:36,880 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:36,900 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:36,900 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 6 [2018-06-26 18:08:36,901 INFO ]: Interpolant automaton has 6 states [2018-06-26 18:08:36,901 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-26 18:08:36,901 INFO ]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-06-26 18:08:36,901 INFO ]: Start difference. First operand 7 states and 11 transitions. Second operand 6 states. [2018-06-26 18:08:37,137 WARN ]: Spent 200.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 19 [2018-06-26 18:08:37,278 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:37,278 INFO ]: Finished difference Result 10 states and 18 transitions. [2018-06-26 18:08:37,278 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-26 18:08:37,278 INFO ]: Start accepts. Automaton has 6 states. Word has length 6 [2018-06-26 18:08:37,278 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:37,279 INFO ]: With dead ends: 10 [2018-06-26 18:08:37,279 INFO ]: Without dead ends: 10 [2018-06-26 18:08:37,279 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=21, Invalid=35, Unknown=0, NotChecked=0, Total=56 [2018-06-26 18:08:37,280 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-26 18:08:37,281 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-26 18:08:37,281 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-26 18:08:37,281 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 18 transitions. [2018-06-26 18:08:37,281 INFO ]: Start accepts. Automaton has 10 states and 18 transitions. Word has length 6 [2018-06-26 18:08:37,281 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:37,281 INFO ]: Abstraction has 10 states and 18 transitions. [2018-06-26 18:08:37,282 INFO ]: Interpolant automaton has 6 states. [2018-06-26 18:08:37,282 INFO ]: Start isEmpty. Operand 10 states and 18 transitions. [2018-06-26 18:08:37,282 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 18:08:37,282 INFO ]: Found error trace [2018-06-26 18:08:37,282 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 18:08:37,282 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:37,282 INFO ]: Analyzing trace with hash 1156290923, now seen corresponding path program 1 times [2018-06-26 18:08:37,282 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:37,282 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:37,283 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:37,283 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:08:37,283 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:37,294 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:37,416 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:37,416 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:37,416 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) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:08:37,423 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:08:37,460 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:37,461 INFO ]: Computing forward predicates... [2018-06-26 18:08:37,534 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:37,553 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 18:08:37,553 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [4] total 5 [2018-06-26 18:08:37,554 INFO ]: Interpolant automaton has 5 states [2018-06-26 18:08:37,554 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 18:08:37,554 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-26 18:08:37,554 INFO ]: Start difference. First operand 10 states and 18 transitions. Second operand 5 states. [2018-06-26 18:08:37,710 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:37,710 INFO ]: Finished difference Result 12 states and 22 transitions. [2018-06-26 18:08:37,711 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-26 18:08:37,711 INFO ]: Start accepts. Automaton has 5 states. Word has length 6 [2018-06-26 18:08:37,711 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:37,711 INFO ]: With dead ends: 12 [2018-06-26 18:08:37,711 INFO ]: Without dead ends: 12 [2018-06-26 18:08:37,712 INFO ]: 0 DeclaredPredicates, 10 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-26 18:08:37,712 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-26 18:08:37,715 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 11. [2018-06-26 18:08:37,715 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-26 18:08:37,716 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 20 transitions. [2018-06-26 18:08:37,716 INFO ]: Start accepts. Automaton has 11 states and 20 transitions. Word has length 6 [2018-06-26 18:08:37,716 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:37,716 INFO ]: Abstraction has 11 states and 20 transitions. [2018-06-26 18:08:37,716 INFO ]: Interpolant automaton has 5 states. [2018-06-26 18:08:37,716 INFO ]: Start isEmpty. Operand 11 states and 20 transitions. [2018-06-26 18:08:37,716 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-26 18:08:37,716 INFO ]: Found error trace [2018-06-26 18:08:37,716 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:08:37,716 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:37,717 INFO ]: Analyzing trace with hash 1484895045, now seen corresponding path program 1 times [2018-06-26 18:08:37,717 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:37,717 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:37,717 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:37,717 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:08:37,717 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:37,740 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:37,930 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:37,930 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:37,930 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 18:08:37,936 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:08:37,959 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:37,961 INFO ]: Computing forward predicates... [2018-06-26 18:08:37,982 INFO ]: Checked inductivity of 3 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:08:38,001 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:38,001 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 4] total 6 [2018-06-26 18:08:38,002 INFO ]: Interpolant automaton has 6 states [2018-06-26 18:08:38,002 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-26 18:08:38,002 INFO ]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-06-26 18:08:38,002 INFO ]: Start difference. First operand 11 states and 20 transitions. Second operand 6 states. [2018-06-26 18:08:38,333 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:38,333 INFO ]: Finished difference Result 13 states and 25 transitions. [2018-06-26 18:08:38,334 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-26 18:08:38,334 INFO ]: Start accepts. Automaton has 6 states. Word has length 7 [2018-06-26 18:08:38,334 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:38,334 INFO ]: With dead ends: 13 [2018-06-26 18:08:38,334 INFO ]: Without dead ends: 13 [2018-06-26 18:08:38,335 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-06-26 18:08:38,335 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-26 18:08:38,336 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-26 18:08:38,336 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-26 18:08:38,337 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 25 transitions. [2018-06-26 18:08:38,337 INFO ]: Start accepts. Automaton has 13 states and 25 transitions. Word has length 7 [2018-06-26 18:08:38,337 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:38,337 INFO ]: Abstraction has 13 states and 25 transitions. [2018-06-26 18:08:38,337 INFO ]: Interpolant automaton has 6 states. [2018-06-26 18:08:38,337 INFO ]: Start isEmpty. Operand 13 states and 25 transitions. [2018-06-26 18:08:38,337 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-26 18:08:38,337 INFO ]: Found error trace [2018-06-26 18:08:38,337 INFO ]: trace histogram [3, 1, 1, 1, 1, 1] [2018-06-26 18:08:38,337 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:38,338 INFO ]: Analyzing trace with hash -1241908212, now seen corresponding path program 2 times [2018-06-26 18:08:38,338 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:38,338 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:38,338 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:38,338 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:08:38,338 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:38,354 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:38,587 WARN ]: Spent 113.00 ms on a formula simplification that was a NOOP. DAG size: 12 [2018-06-26 18:08:38,588 INFO ]: Checked inductivity of 6 backedges. 1 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:38,588 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:38,588 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) [2018-06-26 18:08:38,606 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:08:38,659 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 18:08:38,659 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:38,661 INFO ]: Computing forward predicates... [2018-06-26 18:08:38,777 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:38,797 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:38,797 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2018-06-26 18:08:38,797 INFO ]: Interpolant automaton has 10 states [2018-06-26 18:08:38,798 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-26 18:08:38,798 INFO ]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2018-06-26 18:08:38,799 INFO ]: Start difference. First operand 13 states and 25 transitions. Second operand 10 states. [2018-06-26 18:08:39,353 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:39,353 INFO ]: Finished difference Result 21 states and 40 transitions. [2018-06-26 18:08:39,353 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-26 18:08:39,353 INFO ]: Start accepts. Automaton has 10 states. Word has length 8 [2018-06-26 18:08:39,353 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:39,353 INFO ]: With dead ends: 21 [2018-06-26 18:08:39,353 INFO ]: Without dead ends: 10 [2018-06-26 18:08:39,354 INFO ]: 0 DeclaredPredicates, 24 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 47 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=128, Invalid=292, Unknown=0, NotChecked=0, Total=420 [2018-06-26 18:08:39,354 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-26 18:08:39,355 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-26 18:08:39,355 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-26 18:08:39,355 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 14 transitions. [2018-06-26 18:08:39,356 INFO ]: Start accepts. Automaton has 10 states and 14 transitions. Word has length 8 [2018-06-26 18:08:39,356 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:39,356 INFO ]: Abstraction has 10 states and 14 transitions. [2018-06-26 18:08:39,356 INFO ]: Interpolant automaton has 10 states. [2018-06-26 18:08:39,356 INFO ]: Start isEmpty. Operand 10 states and 14 transitions. [2018-06-26 18:08:39,356 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-26 18:08:39,356 INFO ]: Found error trace [2018-06-26 18:08:39,356 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1] [2018-06-26 18:08:39,356 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:39,356 INFO ]: Analyzing trace with hash -1213279061, now seen corresponding path program 2 times [2018-06-26 18:08:39,356 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:39,356 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:39,357 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:39,357 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:08:39,357 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:39,370 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:39,419 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:39,419 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:39,419 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) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:08:39,430 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 18:08:39,461 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 18:08:39,461 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:39,463 INFO ]: Computing forward predicates... [2018-06-26 18:08:39,663 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:39,682 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:39,682 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2018-06-26 18:08:39,682 INFO ]: Interpolant automaton has 10 states [2018-06-26 18:08:39,682 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-26 18:08:39,682 INFO ]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2018-06-26 18:08:39,682 INFO ]: Start difference. First operand 10 states and 14 transitions. Second operand 10 states. [2018-06-26 18:08:39,841 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:39,841 INFO ]: Finished difference Result 16 states and 23 transitions. [2018-06-26 18:08:39,842 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-26 18:08:39,842 INFO ]: Start accepts. Automaton has 10 states. Word has length 8 [2018-06-26 18:08:39,842 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:39,844 INFO ]: With dead ends: 16 [2018-06-26 18:08:39,844 INFO ]: Without dead ends: 16 [2018-06-26 18:08:39,844 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=41, Invalid=141, Unknown=0, NotChecked=0, Total=182 [2018-06-26 18:08:39,844 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-26 18:08:39,846 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 14. [2018-06-26 18:08:39,846 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-26 18:08:39,846 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 20 transitions. [2018-06-26 18:08:39,846 INFO ]: Start accepts. Automaton has 14 states and 20 transitions. Word has length 8 [2018-06-26 18:08:39,846 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:39,846 INFO ]: Abstraction has 14 states and 20 transitions. [2018-06-26 18:08:39,846 INFO ]: Interpolant automaton has 10 states. [2018-06-26 18:08:39,847 INFO ]: Start isEmpty. Operand 14 states and 20 transitions. [2018-06-26 18:08:39,847 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-26 18:08:39,847 INFO ]: Found error trace [2018-06-26 18:08:39,847 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1] [2018-06-26 18:08:39,847 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:39,848 INFO ]: Analyzing trace with hash -1212355540, now seen corresponding path program 3 times [2018-06-26 18:08:39,848 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:39,848 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:39,848 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:39,848 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:08:39,848 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:39,860 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:39,919 INFO ]: Checked inductivity of 6 backedges. 1 proven. 5 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:39,920 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:39,920 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 18:08:39,928 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 18:08:39,950 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-26 18:08:39,950 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:39,951 INFO ]: Computing forward predicates... [2018-06-26 18:08:40,071 INFO ]: Checked inductivity of 6 backedges. 5 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:40,092 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:40,092 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 9 [2018-06-26 18:08:40,092 INFO ]: Interpolant automaton has 9 states [2018-06-26 18:08:40,092 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-26 18:08:40,092 INFO ]: CoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2018-06-26 18:08:40,092 INFO ]: Start difference. First operand 14 states and 20 transitions. Second operand 9 states. [2018-06-26 18:08:40,314 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:40,314 INFO ]: Finished difference Result 18 states and 27 transitions. [2018-06-26 18:08:40,314 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-26 18:08:40,314 INFO ]: Start accepts. Automaton has 9 states. Word has length 8 [2018-06-26 18:08:40,315 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:40,315 INFO ]: With dead ends: 18 [2018-06-26 18:08:40,315 INFO ]: Without dead ends: 18 [2018-06-26 18:08:40,315 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 21 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=72, Invalid=138, Unknown=0, NotChecked=0, Total=210 [2018-06-26 18:08:40,315 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-26 18:08:40,317 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 17. [2018-06-26 18:08:40,317 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-26 18:08:40,318 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 26 transitions. [2018-06-26 18:08:40,318 INFO ]: Start accepts. Automaton has 17 states and 26 transitions. Word has length 8 [2018-06-26 18:08:40,318 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:40,318 INFO ]: Abstraction has 17 states and 26 transitions. [2018-06-26 18:08:40,318 INFO ]: Interpolant automaton has 9 states. [2018-06-26 18:08:40,318 INFO ]: Start isEmpty. Operand 17 states and 26 transitions. [2018-06-26 18:08:40,318 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-26 18:08:40,318 INFO ]: Found error trace [2018-06-26 18:08:40,318 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1] [2018-06-26 18:08:40,318 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:40,318 INFO ]: Analyzing trace with hash 1071298724, now seen corresponding path program 4 times [2018-06-26 18:08:40,318 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:40,318 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:40,319 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:40,319 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:08:40,319 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:40,337 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:40,439 INFO ]: Checked inductivity of 10 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:08:40,439 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:40,439 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 18:08:40,446 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 18:08:40,484 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 18:08:40,484 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:40,486 INFO ]: Computing forward predicates... [2018-06-26 18:08:40,745 INFO ]: Checked inductivity of 10 backedges. 0 proven. 8 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-26 18:08:40,764 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:40,764 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 8 [2018-06-26 18:08:40,764 INFO ]: Interpolant automaton has 8 states [2018-06-26 18:08:40,764 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-26 18:08:40,765 INFO ]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2018-06-26 18:08:40,765 INFO ]: Start difference. First operand 17 states and 26 transitions. Second operand 8 states. [2018-06-26 18:08:40,794 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:40,794 INFO ]: Finished difference Result 28 states and 47 transitions. [2018-06-26 18:08:40,794 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-26 18:08:40,794 INFO ]: Start accepts. Automaton has 8 states. Word has length 9 [2018-06-26 18:08:40,794 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:40,794 INFO ]: With dead ends: 28 [2018-06-26 18:08:40,794 INFO ]: Without dead ends: 28 [2018-06-26 18:08:40,795 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-06-26 18:08:40,795 INFO ]: Start minimizeSevpa. Operand 28 states. [2018-06-26 18:08:40,797 INFO ]: Finished minimizeSevpa. Reduced states from 28 to 16. [2018-06-26 18:08:40,797 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-26 18:08:40,797 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 24 transitions. [2018-06-26 18:08:40,797 INFO ]: Start accepts. Automaton has 16 states and 24 transitions. Word has length 9 [2018-06-26 18:08:40,797 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:40,797 INFO ]: Abstraction has 16 states and 24 transitions. [2018-06-26 18:08:40,797 INFO ]: Interpolant automaton has 8 states. [2018-06-26 18:08:40,797 INFO ]: Start isEmpty. Operand 16 states and 24 transitions. [2018-06-26 18:08:40,798 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-26 18:08:40,798 INFO ]: Found error trace [2018-06-26 18:08:40,798 INFO ]: trace histogram [3, 2, 1, 1, 1, 1, 1] [2018-06-26 18:08:40,798 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:40,798 INFO ]: Analyzing trace with hash -1149863124, now seen corresponding path program 5 times [2018-06-26 18:08:40,798 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:40,798 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:40,799 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:40,799 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:08:40,799 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:40,811 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:40,914 INFO ]: Checked inductivity of 15 backedges. 1 proven. 14 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:40,914 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:40,914 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 18:08:40,920 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-26 18:08:40,942 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-26 18:08:40,942 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:40,944 INFO ]: Computing forward predicates... [2018-06-26 18:08:41,081 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:41,100 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:41,100 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2018-06-26 18:08:41,100 INFO ]: Interpolant automaton has 14 states [2018-06-26 18:08:41,100 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-26 18:08:41,100 INFO ]: CoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2018-06-26 18:08:41,101 INFO ]: Start difference. First operand 16 states and 24 transitions. Second operand 14 states. [2018-06-26 18:08:41,493 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:41,493 INFO ]: Finished difference Result 30 states and 44 transitions. [2018-06-26 18:08:41,494 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-26 18:08:41,494 INFO ]: Start accepts. Automaton has 14 states. Word has length 10 [2018-06-26 18:08:41,494 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:41,495 INFO ]: With dead ends: 30 [2018-06-26 18:08:41,495 INFO ]: Without dead ends: 30 [2018-06-26 18:08:41,495 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 66 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=101, Invalid=405, Unknown=0, NotChecked=0, Total=506 [2018-06-26 18:08:41,495 INFO ]: Start minimizeSevpa. Operand 30 states. [2018-06-26 18:08:41,498 INFO ]: Finished minimizeSevpa. Reduced states from 30 to 19. [2018-06-26 18:08:41,498 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-26 18:08:41,498 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 28 transitions. [2018-06-26 18:08:41,498 INFO ]: Start accepts. Automaton has 19 states and 28 transitions. Word has length 10 [2018-06-26 18:08:41,499 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:41,499 INFO ]: Abstraction has 19 states and 28 transitions. [2018-06-26 18:08:41,499 INFO ]: Interpolant automaton has 14 states. [2018-06-26 18:08:41,499 INFO ]: Start isEmpty. Operand 19 states and 28 transitions. [2018-06-26 18:08:41,499 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-26 18:08:41,499 INFO ]: Found error trace [2018-06-26 18:08:41,499 INFO ]: trace histogram [3, 3, 1, 1, 1, 1, 1] [2018-06-26 18:08:41,500 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:41,500 INFO ]: Analyzing trace with hash -398899995, now seen corresponding path program 6 times [2018-06-26 18:08:41,500 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:41,500 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:41,500 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:41,500 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:08:41,500 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:41,522 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:41,833 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:41,834 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:41,834 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) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:08:41,849 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-26 18:08:41,902 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-26 18:08:41,902 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:41,904 INFO ]: Computing forward predicates... [2018-06-26 18:08:41,937 INFO ]: Checked inductivity of 21 backedges. 0 proven. 18 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-26 18:08:41,967 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:41,967 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 6] total 13 [2018-06-26 18:08:41,967 INFO ]: Interpolant automaton has 13 states [2018-06-26 18:08:41,967 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-26 18:08:41,967 INFO ]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-06-26 18:08:41,968 INFO ]: Start difference. First operand 19 states and 28 transitions. Second operand 13 states. [2018-06-26 18:08:42,760 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:42,761 INFO ]: Finished difference Result 41 states and 66 transitions. [2018-06-26 18:08:42,761 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-26 18:08:42,761 INFO ]: Start accepts. Automaton has 13 states. Word has length 11 [2018-06-26 18:08:42,761 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:42,761 INFO ]: With dead ends: 41 [2018-06-26 18:08:42,761 INFO ]: Without dead ends: 41 [2018-06-26 18:08:42,762 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 72 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=94, Invalid=412, Unknown=0, NotChecked=0, Total=506 [2018-06-26 18:08:42,762 INFO ]: Start minimizeSevpa. Operand 41 states. [2018-06-26 18:08:42,764 INFO ]: Finished minimizeSevpa. Reduced states from 41 to 29. [2018-06-26 18:08:42,764 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-26 18:08:42,764 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 48 transitions. [2018-06-26 18:08:42,764 INFO ]: Start accepts. Automaton has 29 states and 48 transitions. Word has length 11 [2018-06-26 18:08:42,765 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:42,765 INFO ]: Abstraction has 29 states and 48 transitions. [2018-06-26 18:08:42,765 INFO ]: Interpolant automaton has 13 states. [2018-06-26 18:08:42,765 INFO ]: Start isEmpty. Operand 29 states and 48 transitions. [2018-06-26 18:08:42,770 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-26 18:08:42,770 INFO ]: Found error trace [2018-06-26 18:08:42,770 INFO ]: trace histogram [4, 3, 1, 1, 1, 1, 1] [2018-06-26 18:08:42,770 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:42,770 INFO ]: Analyzing trace with hash 518616843, now seen corresponding path program 7 times [2018-06-26 18:08:42,770 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:42,770 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:42,773 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:42,773 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:08:42,773 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:42,787 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:42,929 INFO ]: Checked inductivity of 28 backedges. 3 proven. 25 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:42,929 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:42,929 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 18:08:42,935 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:08:42,961 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:42,963 INFO ]: Computing forward predicates... [2018-06-26 18:08:43,178 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:43,197 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:43,197 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2018-06-26 18:08:43,197 INFO ]: Interpolant automaton has 18 states [2018-06-26 18:08:43,198 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-26 18:08:43,198 INFO ]: CoverageRelationStatistics Valid=58, Invalid=248, Unknown=0, NotChecked=0, Total=306 [2018-06-26 18:08:43,198 INFO ]: Start difference. First operand 29 states and 48 transitions. Second operand 18 states. [2018-06-26 18:08:43,871 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 17 [2018-06-26 18:08:44,212 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:44,212 INFO ]: Finished difference Result 48 states and 66 transitions. [2018-06-26 18:08:44,212 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-06-26 18:08:44,212 INFO ]: Start accepts. Automaton has 18 states. Word has length 12 [2018-06-26 18:08:44,212 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:44,213 INFO ]: With dead ends: 48 [2018-06-26 18:08:44,213 INFO ]: Without dead ends: 48 [2018-06-26 18:08:44,213 INFO ]: 0 DeclaredPredicates, 37 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 185 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=211, Invalid=911, Unknown=0, NotChecked=0, Total=1122 [2018-06-26 18:08:44,213 INFO ]: Start minimizeSevpa. Operand 48 states. [2018-06-26 18:08:44,216 INFO ]: Finished minimizeSevpa. Reduced states from 48 to 28. [2018-06-26 18:08:44,216 INFO ]: Start removeUnreachable. Operand 28 states. [2018-06-26 18:08:44,217 INFO ]: Finished removeUnreachable. Reduced from 28 states to 28 states and 42 transitions. [2018-06-26 18:08:44,217 INFO ]: Start accepts. Automaton has 28 states and 42 transitions. Word has length 12 [2018-06-26 18:08:44,217 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:44,217 INFO ]: Abstraction has 28 states and 42 transitions. [2018-06-26 18:08:44,217 INFO ]: Interpolant automaton has 18 states. [2018-06-26 18:08:44,217 INFO ]: Start isEmpty. Operand 28 states and 42 transitions. [2018-06-26 18:08:44,218 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-26 18:08:44,218 INFO ]: Found error trace [2018-06-26 18:08:44,218 INFO ]: trace histogram [4, 3, 1, 1, 1, 1, 1] [2018-06-26 18:08:44,218 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:44,218 INFO ]: Analyzing trace with hash 1406120524, now seen corresponding path program 8 times [2018-06-26 18:08:44,218 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:44,218 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:44,219 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:44,219 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:08:44,219 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:44,233 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:44,321 INFO ]: Checked inductivity of 28 backedges. 9 proven. 17 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-26 18:08:44,321 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:44,321 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) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:08:44,326 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 18:08:44,351 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 18:08:44,351 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:44,353 INFO ]: Computing forward predicates... [2018-06-26 18:08:44,489 INFO ]: Checked inductivity of 28 backedges. 22 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:44,509 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:44,509 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9] total 15 [2018-06-26 18:08:44,509 INFO ]: Interpolant automaton has 15 states [2018-06-26 18:08:44,509 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-26 18:08:44,509 INFO ]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2018-06-26 18:08:44,509 INFO ]: Start difference. First operand 28 states and 42 transitions. Second operand 15 states. [2018-06-26 18:08:44,951 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:44,951 INFO ]: Finished difference Result 56 states and 86 transitions. [2018-06-26 18:08:44,952 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2018-06-26 18:08:44,952 INFO ]: Start accepts. Automaton has 15 states. Word has length 12 [2018-06-26 18:08:44,953 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:44,953 INFO ]: With dead ends: 56 [2018-06-26 18:08:44,953 INFO ]: Without dead ends: 56 [2018-06-26 18:08:44,954 INFO ]: 0 DeclaredPredicates, 39 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 144 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=323, Invalid=733, Unknown=0, NotChecked=0, Total=1056 [2018-06-26 18:08:44,954 INFO ]: Start minimizeSevpa. Operand 56 states. [2018-06-26 18:08:44,957 INFO ]: Finished minimizeSevpa. Reduced states from 56 to 34. [2018-06-26 18:08:44,957 INFO ]: Start removeUnreachable. Operand 34 states. [2018-06-26 18:08:44,958 INFO ]: Finished removeUnreachable. Reduced from 34 states to 34 states and 56 transitions. [2018-06-26 18:08:44,958 INFO ]: Start accepts. Automaton has 34 states and 56 transitions. Word has length 12 [2018-06-26 18:08:44,958 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:44,958 INFO ]: Abstraction has 34 states and 56 transitions. [2018-06-26 18:08:44,958 INFO ]: Interpolant automaton has 15 states. [2018-06-26 18:08:44,958 INFO ]: Start isEmpty. Operand 34 states and 56 transitions. [2018-06-26 18:08:44,959 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-26 18:08:44,959 INFO ]: Found error trace [2018-06-26 18:08:44,959 INFO ]: trace histogram [4, 4, 1, 1, 1, 1, 1] [2018-06-26 18:08:44,959 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:44,959 INFO ]: Analyzing trace with hash 639678084, now seen corresponding path program 9 times [2018-06-26 18:08:44,959 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:44,959 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:44,960 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:44,960 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:08:44,960 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:44,979 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:45,390 WARN ]: Spent 334.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 23 [2018-06-26 18:08:45,596 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:45,596 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:45,596 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) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:08:45,602 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 18:08:45,633 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-26 18:08:45,633 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:45,636 INFO ]: Computing forward predicates... [2018-06-26 18:08:45,730 INFO ]: Checked inductivity of 36 backedges. 0 proven. 32 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-26 18:08:45,750 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:45,750 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 7] total 16 [2018-06-26 18:08:45,750 INFO ]: Interpolant automaton has 16 states [2018-06-26 18:08:45,750 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-26 18:08:45,750 INFO ]: CoverageRelationStatistics Valid=30, Invalid=210, Unknown=0, NotChecked=0, Total=240 [2018-06-26 18:08:45,750 INFO ]: Start difference. First operand 34 states and 56 transitions. Second operand 16 states. [2018-06-26 18:08:46,128 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:46,128 INFO ]: Finished difference Result 64 states and 110 transitions. [2018-06-26 18:08:46,128 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-26 18:08:46,128 INFO ]: Start accepts. Automaton has 16 states. Word has length 13 [2018-06-26 18:08:46,128 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:46,129 INFO ]: With dead ends: 64 [2018-06-26 18:08:46,129 INFO ]: Without dead ends: 64 [2018-06-26 18:08:46,130 INFO ]: 0 DeclaredPredicates, 32 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=89, Invalid=511, Unknown=0, NotChecked=0, Total=600 [2018-06-26 18:08:46,130 INFO ]: Start minimizeSevpa. Operand 64 states. [2018-06-26 18:08:46,137 INFO ]: Finished minimizeSevpa. Reduced states from 64 to 35. [2018-06-26 18:08:46,137 INFO ]: Start removeUnreachable. Operand 35 states. [2018-06-26 18:08:46,138 INFO ]: Finished removeUnreachable. Reduced from 35 states to 35 states and 58 transitions. [2018-06-26 18:08:46,138 INFO ]: Start accepts. Automaton has 35 states and 58 transitions. Word has length 13 [2018-06-26 18:08:46,138 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:46,138 INFO ]: Abstraction has 35 states and 58 transitions. [2018-06-26 18:08:46,138 INFO ]: Interpolant automaton has 16 states. [2018-06-26 18:08:46,138 INFO ]: Start isEmpty. Operand 35 states and 58 transitions. [2018-06-26 18:08:46,142 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-26 18:08:46,142 INFO ]: Found error trace [2018-06-26 18:08:46,142 INFO ]: trace histogram [5, 4, 1, 1, 1, 1, 1] [2018-06-26 18:08:46,143 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:46,143 INFO ]: Analyzing trace with hash -1645201076, now seen corresponding path program 10 times [2018-06-26 18:08:46,143 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:46,143 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:46,143 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:46,143 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:08:46,143 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:46,155 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:46,358 INFO ]: Checked inductivity of 45 backedges. 6 proven. 39 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:46,358 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:46,358 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 18:08:46,365 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 18:08:46,397 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 18:08:46,398 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:46,400 INFO ]: Computing forward predicates... [2018-06-26 18:08:46,601 INFO ]: Checked inductivity of 45 backedges. 0 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:46,619 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:46,619 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 22 [2018-06-26 18:08:46,619 INFO ]: Interpolant automaton has 22 states [2018-06-26 18:08:46,620 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-26 18:08:46,620 INFO ]: CoverageRelationStatistics Valid=82, Invalid=380, Unknown=0, NotChecked=0, Total=462 [2018-06-26 18:08:46,620 INFO ]: Start difference. First operand 35 states and 58 transitions. Second operand 22 states. [2018-06-26 18:08:47,635 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:47,635 INFO ]: Finished difference Result 77 states and 106 transitions. [2018-06-26 18:08:47,636 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2018-06-26 18:08:47,636 INFO ]: Start accepts. Automaton has 22 states. Word has length 14 [2018-06-26 18:08:47,636 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:47,636 INFO ]: With dead ends: 77 [2018-06-26 18:08:47,636 INFO ]: Without dead ends: 77 [2018-06-26 18:08:47,637 INFO ]: 0 DeclaredPredicates, 50 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 45 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 414 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=391, Invalid=1771, Unknown=0, NotChecked=0, Total=2162 [2018-06-26 18:08:47,637 INFO ]: Start minimizeSevpa. Operand 77 states. [2018-06-26 18:08:47,640 INFO ]: Finished minimizeSevpa. Reduced states from 77 to 38. [2018-06-26 18:08:47,641 INFO ]: Start removeUnreachable. Operand 38 states. [2018-06-26 18:08:47,643 INFO ]: Finished removeUnreachable. Reduced from 38 states to 38 states and 62 transitions. [2018-06-26 18:08:47,643 INFO ]: Start accepts. Automaton has 38 states and 62 transitions. Word has length 14 [2018-06-26 18:08:47,643 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:47,643 INFO ]: Abstraction has 38 states and 62 transitions. [2018-06-26 18:08:47,643 INFO ]: Interpolant automaton has 22 states. [2018-06-26 18:08:47,643 INFO ]: Start isEmpty. Operand 38 states and 62 transitions. [2018-06-26 18:08:47,644 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-26 18:08:47,644 INFO ]: Found error trace [2018-06-26 18:08:47,644 INFO ]: trace histogram [5, 5, 1, 1, 1, 1, 1] [2018-06-26 18:08:47,644 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:47,644 INFO ]: Analyzing trace with hash -1269465467, now seen corresponding path program 11 times [2018-06-26 18:08:47,644 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:47,644 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:47,644 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:47,644 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:08:47,644 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:47,678 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:47,906 INFO ]: Checked inductivity of 55 backedges. 0 proven. 51 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-26 18:08:47,906 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:47,906 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 18:08:47,911 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-26 18:08:47,947 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-26 18:08:47,947 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:47,950 INFO ]: Computing forward predicates... [2018-06-26 18:08:48,056 INFO ]: Checked inductivity of 55 backedges. 0 proven. 50 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-26 18:08:48,075 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:48,075 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 14 [2018-06-26 18:08:48,075 INFO ]: Interpolant automaton has 14 states [2018-06-26 18:08:48,075 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-26 18:08:48,075 INFO ]: CoverageRelationStatistics Valid=31, Invalid=151, Unknown=0, NotChecked=0, Total=182 [2018-06-26 18:08:48,075 INFO ]: Start difference. First operand 38 states and 62 transitions. Second operand 14 states. [2018-06-26 18:08:48,169 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:48,169 INFO ]: Finished difference Result 86 states and 148 transitions. [2018-06-26 18:08:48,169 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-26 18:08:48,169 INFO ]: Start accepts. Automaton has 14 states. Word has length 15 [2018-06-26 18:08:48,170 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:48,170 INFO ]: With dead ends: 86 [2018-06-26 18:08:48,170 INFO ]: Without dead ends: 86 [2018-06-26 18:08:48,170 INFO ]: 0 DeclaredPredicates, 28 GetRequests, 10 SyntacticMatches, 5 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=43, Invalid=167, Unknown=0, NotChecked=0, Total=210 [2018-06-26 18:08:48,170 INFO ]: Start minimizeSevpa. Operand 86 states. [2018-06-26 18:08:48,173 INFO ]: Finished minimizeSevpa. Reduced states from 86 to 34. [2018-06-26 18:08:48,173 INFO ]: Start removeUnreachable. Operand 34 states. [2018-06-26 18:08:48,174 INFO ]: Finished removeUnreachable. Reduced from 34 states to 34 states and 54 transitions. [2018-06-26 18:08:48,174 INFO ]: Start accepts. Automaton has 34 states and 54 transitions. Word has length 15 [2018-06-26 18:08:48,174 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:48,174 INFO ]: Abstraction has 34 states and 54 transitions. [2018-06-26 18:08:48,174 INFO ]: Interpolant automaton has 14 states. [2018-06-26 18:08:48,174 INFO ]: Start isEmpty. Operand 34 states and 54 transitions. [2018-06-26 18:08:48,174 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-26 18:08:48,174 INFO ]: Found error trace [2018-06-26 18:08:48,174 INFO ]: trace histogram [6, 5, 1, 1, 1, 1, 1] [2018-06-26 18:08:48,175 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:48,175 INFO ]: Analyzing trace with hash -699109013, now seen corresponding path program 12 times [2018-06-26 18:08:48,175 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:48,175 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:48,175 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:48,175 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:08:48,175 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:48,196 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:48,634 INFO ]: Checked inductivity of 66 backedges. 10 proven. 56 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:48,634 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:48,634 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) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:08:48,640 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-26 18:08:48,681 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 7 check-sat command(s) [2018-06-26 18:08:48,681 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:48,684 INFO ]: Computing forward predicates... [2018-06-26 18:08:49,029 INFO ]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:49,048 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:49,048 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 26 [2018-06-26 18:08:49,049 INFO ]: Interpolant automaton has 26 states [2018-06-26 18:08:49,049 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-26 18:08:49,049 INFO ]: CoverageRelationStatistics Valid=110, Invalid=540, Unknown=0, NotChecked=0, Total=650 [2018-06-26 18:08:49,049 INFO ]: Start difference. First operand 34 states and 54 transitions. Second operand 26 states. [2018-06-26 18:08:50,693 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:50,693 INFO ]: Finished difference Result 93 states and 125 transitions. [2018-06-26 18:08:50,693 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2018-06-26 18:08:50,693 INFO ]: Start accepts. Automaton has 26 states. Word has length 16 [2018-06-26 18:08:50,693 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:50,694 INFO ]: With dead ends: 93 [2018-06-26 18:08:50,694 INFO ]: Without dead ends: 93 [2018-06-26 18:08:50,694 INFO ]: 0 DeclaredPredicates, 65 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 808 ImplicationChecksByTransitivity, 1.9s TimeCoverageRelationStatistics Valid=665, Invalid=3117, Unknown=0, NotChecked=0, Total=3782 [2018-06-26 18:08:50,694 INFO ]: Start minimizeSevpa. Operand 93 states. [2018-06-26 18:08:50,697 INFO ]: Finished minimizeSevpa. Reduced states from 93 to 37. [2018-06-26 18:08:50,697 INFO ]: Start removeUnreachable. Operand 37 states. [2018-06-26 18:08:50,698 INFO ]: Finished removeUnreachable. Reduced from 37 states to 37 states and 58 transitions. [2018-06-26 18:08:50,698 INFO ]: Start accepts. Automaton has 37 states and 58 transitions. Word has length 16 [2018-06-26 18:08:50,698 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:50,698 INFO ]: Abstraction has 37 states and 58 transitions. [2018-06-26 18:08:50,698 INFO ]: Interpolant automaton has 26 states. [2018-06-26 18:08:50,698 INFO ]: Start isEmpty. Operand 37 states and 58 transitions. [2018-06-26 18:08:50,698 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-26 18:08:50,698 INFO ]: Found error trace [2018-06-26 18:08:50,698 INFO ]: trace histogram [6, 6, 1, 1, 1, 1, 1] [2018-06-26 18:08:50,698 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:50,699 INFO ]: Analyzing trace with hash -394441628, now seen corresponding path program 13 times [2018-06-26 18:08:50,699 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:50,699 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:50,699 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:50,699 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:08:50,699 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:50,733 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:51,905 INFO ]: Checked inductivity of 78 backedges. 0 proven. 73 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-26 18:08:51,905 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:51,905 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 18:08:51,911 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:08:51,947 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:51,950 INFO ]: Computing forward predicates... [2018-06-26 18:08:52,031 INFO ]: Checked inductivity of 78 backedges. 0 proven. 72 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-26 18:08:52,050 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:52,050 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 16 [2018-06-26 18:08:52,050 INFO ]: Interpolant automaton has 16 states [2018-06-26 18:08:52,051 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-26 18:08:52,051 INFO ]: CoverageRelationStatistics Valid=36, Invalid=204, Unknown=0, NotChecked=0, Total=240 [2018-06-26 18:08:52,051 INFO ]: Start difference. First operand 37 states and 58 transitions. Second operand 16 states. [2018-06-26 18:08:52,275 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:08:52,275 INFO ]: Finished difference Result 104 states and 177 transitions. [2018-06-26 18:08:52,275 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-26 18:08:52,275 INFO ]: Start accepts. Automaton has 16 states. Word has length 17 [2018-06-26 18:08:52,275 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:08:52,275 INFO ]: With dead ends: 104 [2018-06-26 18:08:52,275 INFO ]: Without dead ends: 104 [2018-06-26 18:08:52,276 INFO ]: 0 DeclaredPredicates, 32 GetRequests, 10 SyntacticMatches, 7 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 33 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=50, Invalid=222, Unknown=0, NotChecked=0, Total=272 [2018-06-26 18:08:52,276 INFO ]: Start minimizeSevpa. Operand 104 states. [2018-06-26 18:08:52,280 INFO ]: Finished minimizeSevpa. Reduced states from 104 to 87. [2018-06-26 18:08:52,280 INFO ]: Start removeUnreachable. Operand 87 states. [2018-06-26 18:08:52,281 INFO ]: Finished removeUnreachable. Reduced from 87 states to 87 states and 158 transitions. [2018-06-26 18:08:52,281 INFO ]: Start accepts. Automaton has 87 states and 158 transitions. Word has length 17 [2018-06-26 18:08:52,281 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:08:52,281 INFO ]: Abstraction has 87 states and 158 transitions. [2018-06-26 18:08:52,281 INFO ]: Interpolant automaton has 16 states. [2018-06-26 18:08:52,281 INFO ]: Start isEmpty. Operand 87 states and 158 transitions. [2018-06-26 18:08:52,282 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-26 18:08:52,282 INFO ]: Found error trace [2018-06-26 18:08:52,282 INFO ]: trace histogram [7, 6, 1, 1, 1, 1, 1] [2018-06-26 18:08:52,282 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:08:52,282 INFO ]: Analyzing trace with hash 656826220, now seen corresponding path program 14 times [2018-06-26 18:08:52,282 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:08:52,282 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:08:52,283 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:52,283 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:08:52,283 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:08:52,306 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:52,489 INFO ]: Checked inductivity of 91 backedges. 15 proven. 76 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:52,489 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:08:52,489 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 18:08:52,494 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 18:08:52,546 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 18:08:52,546 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:08:52,550 INFO ]: Computing forward predicates... [2018-06-26 18:08:52,967 INFO ]: Checked inductivity of 91 backedges. 0 proven. 91 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:08:52,986 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:08:52,986 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 30 [2018-06-26 18:08:52,987 INFO ]: Interpolant automaton has 30 states [2018-06-26 18:08:52,987 INFO ]: Constructing interpolant automaton starting with 30 interpolants. [2018-06-26 18:08:52,987 INFO ]: CoverageRelationStatistics Valid=142, Invalid=728, Unknown=0, NotChecked=0, Total=870 [2018-06-26 18:08:52,987 INFO ]: Start difference. First operand 87 states and 158 transitions. Second operand 30 states. [2018-06-26 18:08:53,297 WARN ]: Spent 210.00 ms on a formula simplification. DAG size of input: 25 DAG size of output: 14 [2018-06-26 18:08:54,381 WARN ]: Spent 190.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 14 [2018-06-26 18:08:54,530 WARN ]: Spent 126.00 ms on a formula simplification. DAG size of input: 50 DAG size of output: 14 [2018-06-26 18:08:55,655 WARN ]: Spent 172.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 18 [2018-06-26 18:08:56,294 WARN ]: Spent 328.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 18 [2018-06-26 18:08:56,936 WARN ]: Spent 257.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 18 [2018-06-26 18:08:57,656 WARN ]: Spent 238.00 ms on a formula simplification. DAG size of input: 28 DAG size of output: 18 [2018-06-26 18:08:58,427 WARN ]: Spent 205.00 ms on a formula simplification. DAG size of input: 22 DAG size of output: 17 [2018-06-26 18:08:59,138 WARN ]: Spent 339.00 ms on a formula simplification. DAG size of input: 56 DAG size of output: 18 [2018-06-26 18:08:59,770 WARN ]: Spent 319.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 18 [2018-06-26 18:09:00,913 WARN ]: Spent 103.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 20 [2018-06-26 18:09:01,005 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:09:01,005 INFO ]: Finished difference Result 126 states and 162 transitions. [2018-06-26 18:09:01,005 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-06-26 18:09:01,006 INFO ]: Start accepts. Automaton has 30 states. Word has length 18 [2018-06-26 18:09:01,006 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:09:01,007 INFO ]: With dead ends: 126 [2018-06-26 18:09:01,007 INFO ]: Without dead ends: 126 [2018-06-26 18:09:01,009 INFO ]: 0 DeclaredPredicates, 82 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 77 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1434 ImplicationChecksByTransitivity, 7.7s TimeCoverageRelationStatistics Valid=1059, Invalid=5103, Unknown=0, NotChecked=0, Total=6162 [2018-06-26 18:09:01,009 INFO ]: Start minimizeSevpa. Operand 126 states. [2018-06-26 18:09:01,013 INFO ]: Finished minimizeSevpa. Reduced states from 126 to 52. [2018-06-26 18:09:01,013 INFO ]: Start removeUnreachable. Operand 52 states. [2018-06-26 18:09:01,014 INFO ]: Finished removeUnreachable. Reduced from 52 states to 52 states and 81 transitions. [2018-06-26 18:09:01,014 INFO ]: Start accepts. Automaton has 52 states and 81 transitions. Word has length 18 [2018-06-26 18:09:01,014 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:09:01,014 INFO ]: Abstraction has 52 states and 81 transitions. [2018-06-26 18:09:01,014 INFO ]: Interpolant automaton has 30 states. [2018-06-26 18:09:01,014 INFO ]: Start isEmpty. Operand 52 states and 81 transitions. [2018-06-26 18:09:01,015 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-26 18:09:01,015 INFO ]: Found error trace [2018-06-26 18:09:01,015 INFO ]: trace histogram [7, 6, 1, 1, 1, 1, 1] [2018-06-26 18:09:01,015 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:09:01,016 INFO ]: Analyzing trace with hash 460312715, now seen corresponding path program 15 times [2018-06-26 18:09:01,016 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:09:01,016 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:09:01,016 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:01,016 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:09:01,016 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:01,033 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:01,187 INFO ]: Checked inductivity of 91 backedges. 36 proven. 50 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-26 18:09:01,187 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:09:01,187 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 18:09:01,193 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 18:09:01,237 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2018-06-26 18:09:01,237 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:01,240 INFO ]: Computing forward predicates... [2018-06-26 18:09:01,485 INFO ]: Checked inductivity of 91 backedges. 70 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:09:01,504 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:09:01,504 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 15] total 24 [2018-06-26 18:09:01,504 INFO ]: Interpolant automaton has 24 states [2018-06-26 18:09:01,504 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-26 18:09:01,504 INFO ]: CoverageRelationStatistics Valid=130, Invalid=422, Unknown=0, NotChecked=0, Total=552 [2018-06-26 18:09:01,505 INFO ]: Start difference. First operand 52 states and 81 transitions. Second operand 24 states. [2018-06-26 18:09:02,565 WARN ]: Spent 231.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 18 [2018-06-26 18:09:03,710 WARN ]: Spent 115.00 ms on a formula simplification that was a NOOP. DAG size: 23 [2018-06-26 18:09:03,740 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:09:03,740 INFO ]: Finished difference Result 152 states and 229 transitions. [2018-06-26 18:09:03,740 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-06-26 18:09:03,740 INFO ]: Start accepts. Automaton has 24 states. Word has length 18 [2018-06-26 18:09:03,740 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:09:03,741 INFO ]: With dead ends: 152 [2018-06-26 18:09:03,741 INFO ]: Without dead ends: 152 [2018-06-26 18:09:03,743 INFO ]: 0 DeclaredPredicates, 82 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1008 ImplicationChecksByTransitivity, 2.1s TimeCoverageRelationStatistics Valid=1515, Invalid=3741, Unknown=0, NotChecked=0, Total=5256 [2018-06-26 18:09:03,743 INFO ]: Start minimizeSevpa. Operand 152 states. [2018-06-26 18:09:03,752 INFO ]: Finished minimizeSevpa. Reduced states from 152 to 63. [2018-06-26 18:09:03,752 INFO ]: Start removeUnreachable. Operand 63 states. [2018-06-26 18:09:03,755 INFO ]: Finished removeUnreachable. Reduced from 63 states to 63 states and 108 transitions. [2018-06-26 18:09:03,755 INFO ]: Start accepts. Automaton has 63 states and 108 transitions. Word has length 18 [2018-06-26 18:09:03,755 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:09:03,755 INFO ]: Abstraction has 63 states and 108 transitions. [2018-06-26 18:09:03,755 INFO ]: Interpolant automaton has 24 states. [2018-06-26 18:09:03,755 INFO ]: Start isEmpty. Operand 63 states and 108 transitions. [2018-06-26 18:09:03,756 INFO ]: Finished isEmpty. Found accepting run of length 20 [2018-06-26 18:09:03,756 INFO ]: Found error trace [2018-06-26 18:09:03,756 INFO ]: trace histogram [7, 7, 1, 1, 1, 1, 1] [2018-06-26 18:09:03,756 INFO ]: === Iteration 20 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:09:03,756 INFO ]: Analyzing trace with hash 1384407077, now seen corresponding path program 16 times [2018-06-26 18:09:03,756 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:09:03,756 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:09:03,757 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:03,757 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:09:03,757 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:03,790 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:04,295 INFO ]: Checked inductivity of 105 backedges. 0 proven. 105 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:09:04,295 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:09:04,295 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 18:09:04,301 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 18:09:04,340 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 18:09:04,340 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:04,344 INFO ]: Computing forward predicates... [2018-06-26 18:09:04,516 INFO ]: Checked inductivity of 105 backedges. 0 proven. 98 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-26 18:09:04,536 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:09:04,536 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 10] total 25 [2018-06-26 18:09:04,536 INFO ]: Interpolant automaton has 25 states [2018-06-26 18:09:04,536 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-26 18:09:04,536 INFO ]: CoverageRelationStatistics Valid=54, Invalid=546, Unknown=0, NotChecked=0, Total=600 [2018-06-26 18:09:04,536 INFO ]: Start difference. First operand 63 states and 108 transitions. Second operand 25 states. [2018-06-26 18:09:04,712 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 78 DAG size of output: 77 [2018-06-26 18:09:04,874 WARN ]: Spent 100.00 ms on a formula simplification. DAG size of input: 69 DAG size of output: 68 [2018-06-26 18:09:07,106 WARN ]: Spent 285.00 ms on a formula simplification. DAG size of input: 151 DAG size of output: 136 [2018-06-26 18:09:07,108 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:09:07,108 INFO ]: Finished difference Result 167 states and 274 transitions. [2018-06-26 18:09:07,108 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 53 states. [2018-06-26 18:09:07,108 INFO ]: Start accepts. Automaton has 25 states. Word has length 19 [2018-06-26 18:09:07,109 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:09:07,109 INFO ]: With dead ends: 167 [2018-06-26 18:09:07,109 INFO ]: Without dead ends: 167 [2018-06-26 18:09:07,111 INFO ]: 0 DeclaredPredicates, 72 GetRequests, 9 SyntacticMatches, 3 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 764 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=276, Invalid=3506, Unknown=0, NotChecked=0, Total=3782 [2018-06-26 18:09:07,111 INFO ]: Start minimizeSevpa. Operand 167 states. [2018-06-26 18:09:07,115 INFO ]: Finished minimizeSevpa. Reduced states from 167 to 65. [2018-06-26 18:09:07,115 INFO ]: Start removeUnreachable. Operand 65 states. [2018-06-26 18:09:07,116 INFO ]: Finished removeUnreachable. Reduced from 65 states to 65 states and 112 transitions. [2018-06-26 18:09:07,116 INFO ]: Start accepts. Automaton has 65 states and 112 transitions. Word has length 19 [2018-06-26 18:09:07,116 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:09:07,116 INFO ]: Abstraction has 65 states and 112 transitions. [2018-06-26 18:09:07,116 INFO ]: Interpolant automaton has 25 states. [2018-06-26 18:09:07,116 INFO ]: Start isEmpty. Operand 65 states and 112 transitions. [2018-06-26 18:09:07,117 INFO ]: Finished isEmpty. Found accepting run of length 21 [2018-06-26 18:09:07,117 INFO ]: Found error trace [2018-06-26 18:09:07,117 INFO ]: trace histogram [8, 7, 1, 1, 1, 1, 1] [2018-06-26 18:09:07,117 INFO ]: === Iteration 21 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:09:07,117 INFO ]: Analyzing trace with hash -33438773, now seen corresponding path program 17 times [2018-06-26 18:09:07,118 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:09:07,118 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:09:07,118 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:07,118 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:09:07,118 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:07,143 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:07,412 INFO ]: Checked inductivity of 120 backedges. 21 proven. 99 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:09:07,412 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:09:07,412 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:09:07,426 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-26 18:09:07,481 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 9 check-sat command(s) [2018-06-26 18:09:07,481 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:07,484 INFO ]: Computing forward predicates... [2018-06-26 18:09:08,512 INFO ]: Checked inductivity of 120 backedges. 0 proven. 120 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:09:08,531 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:09:08,531 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 34 [2018-06-26 18:09:08,531 INFO ]: Interpolant automaton has 34 states [2018-06-26 18:09:08,531 INFO ]: Constructing interpolant automaton starting with 34 interpolants. [2018-06-26 18:09:08,531 INFO ]: CoverageRelationStatistics Valid=178, Invalid=944, Unknown=0, NotChecked=0, Total=1122 [2018-06-26 18:09:08,532 INFO ]: Start difference. First operand 65 states and 112 transitions. Second operand 34 states. [2018-06-26 18:09:11,410 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:09:11,410 INFO ]: Finished difference Result 182 states and 238 transitions. [2018-06-26 18:09:11,410 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 76 states. [2018-06-26 18:09:11,410 INFO ]: Start accepts. Automaton has 34 states. Word has length 20 [2018-06-26 18:09:11,410 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:09:11,411 INFO ]: With dead ends: 182 [2018-06-26 18:09:11,411 INFO ]: Without dead ends: 182 [2018-06-26 18:09:11,413 INFO ]: 0 DeclaredPredicates, 101 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 96 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2371 ImplicationChecksByTransitivity, 3.8s TimeCoverageRelationStatistics Valid=1603, Invalid=7903, Unknown=0, NotChecked=0, Total=9506 [2018-06-26 18:09:11,414 INFO ]: Start minimizeSevpa. Operand 182 states. [2018-06-26 18:09:11,417 INFO ]: Finished minimizeSevpa. Reduced states from 182 to 67. [2018-06-26 18:09:11,417 INFO ]: Start removeUnreachable. Operand 67 states. [2018-06-26 18:09:11,423 INFO ]: Finished removeUnreachable. Reduced from 67 states to 67 states and 114 transitions. [2018-06-26 18:09:11,423 INFO ]: Start accepts. Automaton has 67 states and 114 transitions. Word has length 20 [2018-06-26 18:09:11,423 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:09:11,423 INFO ]: Abstraction has 67 states and 114 transitions. [2018-06-26 18:09:11,423 INFO ]: Interpolant automaton has 34 states. [2018-06-26 18:09:11,423 INFO ]: Start isEmpty. Operand 67 states and 114 transitions. [2018-06-26 18:09:11,424 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-26 18:09:11,424 INFO ]: Found error trace [2018-06-26 18:09:11,424 INFO ]: trace histogram [8, 8, 1, 1, 1, 1, 1] [2018-06-26 18:09:11,424 INFO ]: === Iteration 22 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:09:11,424 INFO ]: Analyzing trace with hash -907904444, now seen corresponding path program 18 times [2018-06-26 18:09:11,424 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:09:11,424 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:09:11,425 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:11,425 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:09:11,425 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:11,456 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:11,864 WARN ]: Spent 294.00 ms on a formula simplification. DAG size of input: 30 DAG size of output: 23 [2018-06-26 18:09:12,374 INFO ]: Checked inductivity of 136 backedges. 0 proven. 136 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:09:12,375 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:09:12,375 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:09:12,380 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-26 18:09:12,440 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 9 check-sat command(s) [2018-06-26 18:09:12,440 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:12,444 INFO ]: Computing forward predicates... [2018-06-26 18:09:12,669 INFO ]: Checked inductivity of 136 backedges. 0 proven. 128 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-26 18:09:12,690 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:09:12,690 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 11] total 28 [2018-06-26 18:09:12,690 INFO ]: Interpolant automaton has 28 states [2018-06-26 18:09:12,690 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-26 18:09:12,691 INFO ]: CoverageRelationStatistics Valid=54, Invalid=702, Unknown=0, NotChecked=0, Total=756 [2018-06-26 18:09:12,691 INFO ]: Start difference. First operand 67 states and 114 transitions. Second operand 28 states. [2018-06-26 18:09:13,668 WARN ]: Spent 158.00 ms on a formula simplification. DAG size of input: 134 DAG size of output: 82 [2018-06-26 18:09:13,670 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:09:13,670 INFO ]: Finished difference Result 174 states and 300 transitions. [2018-06-26 18:09:13,670 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-06-26 18:09:13,670 INFO ]: Start accepts. Automaton has 28 states. Word has length 21 [2018-06-26 18:09:13,670 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:09:13,671 INFO ]: With dead ends: 174 [2018-06-26 18:09:13,671 INFO ]: Without dead ends: 174 [2018-06-26 18:09:13,671 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 11 SyntacticMatches, 2 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 153 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=173, Invalid=1807, Unknown=0, NotChecked=0, Total=1980 [2018-06-26 18:09:13,672 INFO ]: Start minimizeSevpa. Operand 174 states. [2018-06-26 18:09:13,675 INFO ]: Finished minimizeSevpa. Reduced states from 174 to 68. [2018-06-26 18:09:13,675 INFO ]: Start removeUnreachable. Operand 68 states. [2018-06-26 18:09:13,675 INFO ]: Finished removeUnreachable. Reduced from 68 states to 68 states and 116 transitions. [2018-06-26 18:09:13,676 INFO ]: Start accepts. Automaton has 68 states and 116 transitions. Word has length 21 [2018-06-26 18:09:13,676 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:09:13,676 INFO ]: Abstraction has 68 states and 116 transitions. [2018-06-26 18:09:13,676 INFO ]: Interpolant automaton has 28 states. [2018-06-26 18:09:13,676 INFO ]: Start isEmpty. Operand 68 states and 116 transitions. [2018-06-26 18:09:13,676 INFO ]: Finished isEmpty. Found accepting run of length 23 [2018-06-26 18:09:13,676 INFO ]: Found error trace [2018-06-26 18:09:13,676 INFO ]: trace histogram [9, 8, 1, 1, 1, 1, 1] [2018-06-26 18:09:13,676 INFO ]: === Iteration 23 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:09:13,676 INFO ]: Analyzing trace with hash 1919348108, now seen corresponding path program 19 times [2018-06-26 18:09:13,676 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:09:13,676 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:09:13,677 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:13,677 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:09:13,677 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:13,693 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:14,288 INFO ]: Checked inductivity of 153 backedges. 28 proven. 125 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:09:14,288 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:09:14,288 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:09:14,294 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:09:14,367 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:14,372 INFO ]: Computing forward predicates... [2018-06-26 18:09:15,213 INFO ]: Checked inductivity of 153 backedges. 0 proven. 153 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:09:15,234 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:09:15,234 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 38 [2018-06-26 18:09:15,234 INFO ]: Interpolant automaton has 38 states [2018-06-26 18:09:15,234 INFO ]: Constructing interpolant automaton starting with 38 interpolants. [2018-06-26 18:09:15,234 INFO ]: CoverageRelationStatistics Valid=218, Invalid=1188, Unknown=0, NotChecked=0, Total=1406 [2018-06-26 18:09:15,235 INFO ]: Start difference. First operand 68 states and 116 transitions. Second operand 38 states. [2018-06-26 18:09:19,399 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:09:19,399 INFO ]: Finished difference Result 213 states and 271 transitions. [2018-06-26 18:09:19,399 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 94 states. [2018-06-26 18:09:19,399 INFO ]: Start accepts. Automaton has 38 states. Word has length 22 [2018-06-26 18:09:19,399 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:09:19,400 INFO ]: With dead ends: 213 [2018-06-26 18:09:19,400 INFO ]: Without dead ends: 213 [2018-06-26 18:09:19,403 INFO ]: 0 DeclaredPredicates, 122 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 117 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3710 ImplicationChecksByTransitivity, 5.1s TimeCoverageRelationStatistics Valid=2329, Invalid=11713, Unknown=0, NotChecked=0, Total=14042 [2018-06-26 18:09:19,403 INFO ]: Start minimizeSevpa. Operand 213 states. [2018-06-26 18:09:19,406 INFO ]: Finished minimizeSevpa. Reduced states from 213 to 71. [2018-06-26 18:09:19,407 INFO ]: Start removeUnreachable. Operand 71 states. [2018-06-26 18:09:19,407 INFO ]: Finished removeUnreachable. Reduced from 71 states to 71 states and 120 transitions. [2018-06-26 18:09:19,407 INFO ]: Start accepts. Automaton has 71 states and 120 transitions. Word has length 22 [2018-06-26 18:09:19,407 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:09:19,407 INFO ]: Abstraction has 71 states and 120 transitions. [2018-06-26 18:09:19,407 INFO ]: Interpolant automaton has 38 states. [2018-06-26 18:09:19,407 INFO ]: Start isEmpty. Operand 71 states and 120 transitions. [2018-06-26 18:09:19,408 INFO ]: Finished isEmpty. Found accepting run of length 24 [2018-06-26 18:09:19,408 INFO ]: Found error trace [2018-06-26 18:09:19,408 INFO ]: trace histogram [9, 9, 1, 1, 1, 1, 1] [2018-06-26 18:09:19,408 INFO ]: === Iteration 24 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:09:19,408 INFO ]: Analyzing trace with hash -923539003, now seen corresponding path program 20 times [2018-06-26 18:09:19,408 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:09:19,408 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:09:19,409 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:19,409 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:09:19,409 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:19,433 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:19,706 INFO ]: Checked inductivity of 171 backedges. 0 proven. 163 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-26 18:09:19,706 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:09:19,706 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:09:19,721 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 18:09:19,771 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 18:09:19,771 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:19,775 INFO ]: Computing forward predicates... [2018-06-26 18:09:19,982 INFO ]: Checked inductivity of 171 backedges. 0 proven. 162 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-06-26 18:09:20,001 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:09:20,001 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 12] total 22 [2018-06-26 18:09:20,001 INFO ]: Interpolant automaton has 22 states [2018-06-26 18:09:20,001 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-26 18:09:20,001 INFO ]: CoverageRelationStatistics Valid=51, Invalid=411, Unknown=0, NotChecked=0, Total=462 [2018-06-26 18:09:20,001 INFO ]: Start difference. First operand 71 states and 120 transitions. Second operand 22 states. [2018-06-26 18:09:20,201 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:09:20,209 INFO ]: Finished difference Result 212 states and 366 transitions. [2018-06-26 18:09:20,209 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-26 18:09:20,209 INFO ]: Start accepts. Automaton has 22 states. Word has length 23 [2018-06-26 18:09:20,209 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:09:20,210 INFO ]: With dead ends: 212 [2018-06-26 18:09:20,210 INFO ]: Without dead ends: 212 [2018-06-26 18:09:20,210 INFO ]: 0 DeclaredPredicates, 44 GetRequests, 11 SyntacticMatches, 12 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 81 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=71, Invalid=435, Unknown=0, NotChecked=0, Total=506 [2018-06-26 18:09:20,210 INFO ]: Start minimizeSevpa. Operand 212 states. [2018-06-26 18:09:20,214 INFO ]: Finished minimizeSevpa. Reduced states from 212 to 63. [2018-06-26 18:09:20,214 INFO ]: Start removeUnreachable. Operand 63 states. [2018-06-26 18:09:20,214 INFO ]: Finished removeUnreachable. Reduced from 63 states to 63 states and 104 transitions. [2018-06-26 18:09:20,214 INFO ]: Start accepts. Automaton has 63 states and 104 transitions. Word has length 23 [2018-06-26 18:09:20,214 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:09:20,214 INFO ]: Abstraction has 63 states and 104 transitions. [2018-06-26 18:09:20,214 INFO ]: Interpolant automaton has 22 states. [2018-06-26 18:09:20,214 INFO ]: Start isEmpty. Operand 63 states and 104 transitions. [2018-06-26 18:09:20,215 INFO ]: Finished isEmpty. Found accepting run of length 25 [2018-06-26 18:09:20,215 INFO ]: Found error trace [2018-06-26 18:09:20,215 INFO ]: trace histogram [10, 9, 1, 1, 1, 1, 1] [2018-06-26 18:09:20,215 INFO ]: === Iteration 25 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:09:20,215 INFO ]: Analyzing trace with hash 1434676779, now seen corresponding path program 21 times [2018-06-26 18:09:20,215 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:09:20,215 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:09:20,216 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:20,216 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:09:20,216 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:20,232 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:20,959 INFO ]: Checked inductivity of 190 backedges. 36 proven. 154 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:09:20,959 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:09:20,959 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:09:20,965 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 18:09:21,050 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 11 check-sat command(s) [2018-06-26 18:09:21,050 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:21,053 INFO ]: Computing forward predicates... [2018-06-26 18:09:21,671 INFO ]: Checked inductivity of 190 backedges. 0 proven. 190 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:09:21,690 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:09:21,690 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 42 [2018-06-26 18:09:21,691 INFO ]: Interpolant automaton has 42 states [2018-06-26 18:09:21,691 INFO ]: Constructing interpolant automaton starting with 42 interpolants. [2018-06-26 18:09:21,691 INFO ]: CoverageRelationStatistics Valid=262, Invalid=1460, Unknown=0, NotChecked=0, Total=1722 [2018-06-26 18:09:21,691 INFO ]: Start difference. First operand 63 states and 104 transitions. Second operand 42 states. [2018-06-26 18:09:27,165 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:09:27,165 INFO ]: Finished difference Result 238 states and 299 transitions. [2018-06-26 18:09:27,165 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 114 states. [2018-06-26 18:09:27,165 INFO ]: Start accepts. Automaton has 42 states. Word has length 24 [2018-06-26 18:09:27,165 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:09:27,166 INFO ]: With dead ends: 238 [2018-06-26 18:09:27,166 INFO ]: Without dead ends: 238 [2018-06-26 18:09:27,167 INFO ]: 0 DeclaredPredicates, 145 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 140 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5554 ImplicationChecksByTransitivity, 6.2s TimeCoverageRelationStatistics Valid=3273, Invalid=16749, Unknown=0, NotChecked=0, Total=20022 [2018-06-26 18:09:27,168 INFO ]: Start minimizeSevpa. Operand 238 states. [2018-06-26 18:09:27,171 INFO ]: Finished minimizeSevpa. Reduced states from 238 to 66. [2018-06-26 18:09:27,172 INFO ]: Start removeUnreachable. Operand 66 states. [2018-06-26 18:09:27,172 INFO ]: Finished removeUnreachable. Reduced from 66 states to 66 states and 108 transitions. [2018-06-26 18:09:27,172 INFO ]: Start accepts. Automaton has 66 states and 108 transitions. Word has length 24 [2018-06-26 18:09:27,172 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:09:27,172 INFO ]: Abstraction has 66 states and 108 transitions. [2018-06-26 18:09:27,172 INFO ]: Interpolant automaton has 42 states. [2018-06-26 18:09:27,172 INFO ]: Start isEmpty. Operand 66 states and 108 transitions. [2018-06-26 18:09:27,174 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-26 18:09:27,174 INFO ]: Found error trace [2018-06-26 18:09:27,174 INFO ]: trace histogram [10, 10, 1, 1, 1, 1, 1] [2018-06-26 18:09:27,175 INFO ]: === Iteration 26 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:09:27,175 INFO ]: Analyzing trace with hash 1019363364, now seen corresponding path program 22 times [2018-06-26 18:09:27,175 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:09:27,175 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:09:27,175 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:27,175 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:09:27,175 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:27,202 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:28,088 INFO ]: Checked inductivity of 210 backedges. 0 proven. 210 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:09:28,088 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:09:28,088 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:09:28,094 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 18:09:28,149 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 18:09:28,149 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:28,154 INFO ]: Computing forward predicates... [2018-06-26 18:09:28,558 INFO ]: Checked inductivity of 210 backedges. 0 proven. 200 refuted. 0 times theorem prover too weak. 10 trivial. 0 not checked. [2018-06-26 18:09:28,577 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:09:28,577 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 13] total 34 [2018-06-26 18:09:28,577 INFO ]: Interpolant automaton has 34 states [2018-06-26 18:09:28,577 INFO ]: Constructing interpolant automaton starting with 34 interpolants. [2018-06-26 18:09:28,577 INFO ]: CoverageRelationStatistics Valid=66, Invalid=1056, Unknown=0, NotChecked=0, Total=1122 [2018-06-26 18:09:28,577 INFO ]: Start difference. First operand 66 states and 108 transitions. Second operand 34 states. [2018-06-26 18:09:29,806 WARN ]: Spent 203.00 ms on a formula simplification. DAG size of input: 163 DAG size of output: 98 [2018-06-26 18:09:29,808 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:09:29,808 INFO ]: Finished difference Result 244 states and 419 transitions. [2018-06-26 18:09:29,808 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-06-26 18:09:29,808 INFO ]: Start accepts. Automaton has 34 states. Word has length 25 [2018-06-26 18:09:29,808 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:09:29,809 INFO ]: With dead ends: 244 [2018-06-26 18:09:29,809 INFO ]: Without dead ends: 244 [2018-06-26 18:09:29,810 INFO ]: 0 DeclaredPredicates, 68 GetRequests, 12 SyntacticMatches, 3 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 232 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=215, Invalid=2755, Unknown=0, NotChecked=0, Total=2970 [2018-06-26 18:09:29,810 INFO ]: Start minimizeSevpa. Operand 244 states. [2018-06-26 18:09:29,816 INFO ]: Finished minimizeSevpa. Reduced states from 244 to 196. [2018-06-26 18:09:29,816 INFO ]: Start removeUnreachable. Operand 196 states. [2018-06-26 18:09:29,818 INFO ]: Finished removeUnreachable. Reduced from 196 states to 196 states and 368 transitions. [2018-06-26 18:09:29,818 INFO ]: Start accepts. Automaton has 196 states and 368 transitions. Word has length 25 [2018-06-26 18:09:29,818 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:09:29,818 INFO ]: Abstraction has 196 states and 368 transitions. [2018-06-26 18:09:29,818 INFO ]: Interpolant automaton has 34 states. [2018-06-26 18:09:29,818 INFO ]: Start isEmpty. Operand 196 states and 368 transitions. [2018-06-26 18:09:29,819 INFO ]: Finished isEmpty. Found accepting run of length 27 [2018-06-26 18:09:29,819 INFO ]: Found error trace [2018-06-26 18:09:29,820 INFO ]: trace histogram [11, 10, 1, 1, 1, 1, 1] [2018-06-26 18:09:29,820 INFO ]: === Iteration 27 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:09:29,820 INFO ]: Analyzing trace with hash 1535108012, now seen corresponding path program 23 times [2018-06-26 18:09:29,820 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:09:29,821 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:09:29,821 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:29,821 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:09:29,821 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:09:29,839 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:30,287 INFO ]: Checked inductivity of 231 backedges. 45 proven. 186 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:09:30,287 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:09:30,287 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:09:30,295 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-26 18:09:30,368 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 12 check-sat command(s) [2018-06-26 18:09:30,368 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:09:30,374 INFO ]: Computing forward predicates... [2018-06-26 18:09:31,137 INFO ]: Checked inductivity of 231 backedges. 0 proven. 231 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:09:31,157 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:09:31,157 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 46 [2018-06-26 18:09:31,157 INFO ]: Interpolant automaton has 46 states [2018-06-26 18:09:31,157 INFO ]: Constructing interpolant automaton starting with 46 interpolants. [2018-06-26 18:09:31,157 INFO ]: CoverageRelationStatistics Valid=310, Invalid=1760, Unknown=0, NotChecked=0, Total=2070 [2018-06-26 18:09:31,157 INFO ]: Start difference. First operand 196 states and 368 transitions. Second operand 46 states. Received shutdown request... [2018-06-26 18:09:35,427 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 83 states. [2018-06-26 18:09:35,427 WARN ]: Verification canceled [2018-06-26 18:09:35,428 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-26 18:09:35,429 WARN ]: Timeout [2018-06-26 18:09:35,429 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 06:09:35 BasicIcfg [2018-06-26 18:09:35,429 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-26 18:09:35,430 INFO ]: Toolchain (without parser) took 59793.48 ms. Allocated memory was 304.6 MB in the beginning and 794.3 MB in the end (delta: 489.7 MB). Free memory was 258.9 MB in the beginning and 711.1 MB in the end (delta: -452.2 MB). Peak memory consumption was 37.5 MB. Max. memory is 3.6 GB. [2018-06-26 18:09:35,430 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 304.6 MB. Free memory is still 268.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-26 18:09:35,431 INFO ]: ChcToBoogie took 61.63 ms. Allocated memory is still 304.6 MB. Free memory was 258.9 MB in the beginning and 256.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-26 18:09:35,431 INFO ]: Boogie Preprocessor took 35.09 ms. Allocated memory is still 304.6 MB. Free memory was 256.9 MB in the beginning and 254.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-26 18:09:35,431 INFO ]: RCFGBuilder took 245.65 ms. Allocated memory is still 304.6 MB. Free memory was 254.9 MB in the beginning and 246.9 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-26 18:09:35,432 INFO ]: BlockEncodingV2 took 119.64 ms. Allocated memory is still 304.6 MB. Free memory was 246.9 MB in the beginning and 244.0 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-26 18:09:35,432 INFO ]: TraceAbstraction took 59322.32 ms. Allocated memory was 304.6 MB in the beginning and 794.3 MB in the end (delta: 489.7 MB). Free memory was 244.0 MB in the beginning and 711.1 MB in the end (delta: -467.2 MB). Peak memory consumption was 22.5 MB. Max. memory is 3.6 GB. [2018-06-26 18:09:35,435 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.plugins.blockencoding: - StatisticsResult: Initial Icfg 10 locations, 12 edges - StatisticsResult: Encoded RCFG 6 locations, 8 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 304.6 MB. Free memory is still 268.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 61.63 ms. Allocated memory is still 304.6 MB. Free memory was 258.9 MB in the beginning and 256.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 35.09 ms. Allocated memory is still 304.6 MB. Free memory was 256.9 MB in the beginning and 254.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 245.65 ms. Allocated memory is still 304.6 MB. Free memory was 254.9 MB in the beginning and 246.9 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 119.64 ms. Allocated memory is still 304.6 MB. Free memory was 246.9 MB in the beginning and 244.0 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 59322.32 ms. Allocated memory was 304.6 MB in the beginning and 794.3 MB in the end (delta: 489.7 MB). Free memory was 244.0 MB in the beginning and 711.1 MB in the end (delta: -467.2 MB). Peak memory consumption was 22.5 MB. 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 constructing difference of abstraction (196states) and interpolant automaton (currently 83 states, 46 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 116 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 6 locations, 1 error locations. TIMEOUT Result, 59.2s OverallTime, 27 OverallIterations, 11 TraceHistogramMax, 40.0s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 132 SDtfs, 11 SDslu, 910 SDs, 0 SdLazy, 5742 SolverSat, 1429 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 5.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1341 GetRequests, 186 SyntacticMatches, 35 SemanticMatches, 1119 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 20333 ImplicationChecksByTransitivity, 47.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=196occurred in iteration=26, 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, 26 MinimizatonAttempts, 1271 StatesRemovedByMinimization, 22 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 1.4s SatisfiabilityAnalysisTime, 16.5s InterpolantComputationTime, 781 NumberOfCodeBlocks, 781 NumberOfCodeBlocksAsserted, 125 NumberOfCheckSat, 728 ConstructedInterpolants, 160 QuantifiedInterpolants, 140722 SizeOfPredicates, 84 NumberOfNonLiveVariables, 8314 ConjunctsInSsa, 1554 ConjunctsInUnsatCore, 53 InterpolantComputations, 2 PerfectInterpolantSequences, 390/3806 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/020b-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-26_18-09-35-445.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/020b-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-26_18-09-35-445.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/020b-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-26_18-09-35-445.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/020b-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-26_18-09-35-445.csv Completed graceful shutdown