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/hopv/lia/termination/McCarthy9103.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-62c3406-m [2018-06-26 18:31:35,475 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-26 18:31:35,476 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-26 18:31:35,491 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-26 18:31:35,491 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-26 18:31:35,492 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-26 18:31:35,493 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-26 18:31:35,496 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-26 18:31:35,497 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-26 18:31:35,499 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-26 18:31:35,500 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-26 18:31:35,501 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-26 18:31:35,501 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-26 18:31:35,502 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-26 18:31:35,507 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-26 18:31:35,508 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-26 18:31:35,509 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-26 18:31:35,512 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-26 18:31:35,514 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-26 18:31:35,516 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-26 18:31:35,517 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-26 18:31:35,518 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-26 18:31:35,521 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-26 18:31:35,521 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-26 18:31:35,521 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-26 18:31:35,522 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-26 18:31:35,523 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-26 18:31:35,524 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-26 18:31:35,524 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-26 18:31:35,525 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-26 18:31:35,526 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-26 18:31:35,526 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-26 18:31:35,526 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-06-26 18:31:35,527 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-26 18:31:35,527 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-26 18:31:35,528 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-26 18:31:35,528 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:31:35,541 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-26 18:31:35,542 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-26 18:31:35,542 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-26 18:31:35,542 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-26 18:31:35,543 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-26 18:31:35,544 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-26 18:31:35,544 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-26 18:31:35,544 INFO L133 SettingsManager]: * Use SBE=true [2018-06-26 18:31:35,544 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-26 18:31:35,544 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-26 18:31:35,545 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-26 18:31:35,545 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-26 18:31:35,545 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 18:31:35,545 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-26 18:31:35,546 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-26 18:31:35,546 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-26 18:31:35,546 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-26 18:31:35,546 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-26 18:31:35,546 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-26 18:31:35,546 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-26 18:31:35,547 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-26 18:31:35,549 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-26 18:31:35,549 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-26 18:31:35,592 INFO ]: Repository-Root is: /tmp [2018-06-26 18:31:35,605 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-26 18:31:35,611 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-26 18:31:35,613 INFO ]: Initializing SmtParser... [2018-06-26 18:31:35,613 INFO ]: SmtParser initialized [2018-06-26 18:31:35,614 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/hopv/lia/termination/McCarthy9103.smt2 [2018-06-26 18:31:35,615 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:31:35,706 INFO ]: Executing SMT file /storage/chc-comp/hopv/lia/termination/McCarthy9103.smt2 unknown [2018-06-26 18:31:36,040 INFO ]: Succesfully executed SMT file /storage/chc-comp/hopv/lia/termination/McCarthy9103.smt2 [2018-06-26 18:31:36,046 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-26 18:31:36,051 INFO ]: Walking toolchain with 5 elements. [2018-06-26 18:31:36,052 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-26 18:31:36,052 INFO ]: Initializing ChcToBoogie... [2018-06-26 18:31:36,052 INFO ]: ChcToBoogie initialized [2018-06-26 18:31:36,056 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 06:31:36" (1/1) ... [2018-06-26 18:31:36,126 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:31:36 Unit [2018-06-26 18:31:36,126 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-26 18:31:36,129 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-26 18:31:36,129 INFO ]: Initializing Boogie Preprocessor... [2018-06-26 18:31:36,129 INFO ]: Boogie Preprocessor initialized [2018-06-26 18:31:36,149 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:31:36" (1/1) ... [2018-06-26 18:31:36,149 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:31:36" (1/1) ... [2018-06-26 18:31:36,156 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:31:36" (1/1) ... [2018-06-26 18:31:36,156 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:31:36" (1/1) ... [2018-06-26 18:31:36,177 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:31:36" (1/1) ... [2018-06-26 18:31:36,180 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:31:36" (1/1) ... [2018-06-26 18:31:36,182 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:31:36" (1/1) ... [2018-06-26 18:31:36,193 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-26 18:31:36,194 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-26 18:31:36,194 INFO ]: Initializing RCFGBuilder... [2018-06-26 18:31:36,194 INFO ]: RCFGBuilder initialized [2018-06-26 18:31:36,194 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:31:36" (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:31:36,210 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-26 18:31:36,210 INFO ]: Found specification of procedure gotoProc [2018-06-26 18:31:36,210 INFO ]: Found implementation of procedure gotoProc [2018-06-26 18:31:36,210 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-26 18:31:36,210 INFO ]: Found specification of procedure Ultimate.START [2018-06-26 18:31:36,211 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:31:36,675 INFO ]: Using library mode [2018-06-26 18:31:36,675 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 06:31:36 BoogieIcfgContainer [2018-06-26 18:31:36,675 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-26 18:31:36,676 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-26 18:31:36,676 INFO ]: Initializing BlockEncodingV2... [2018-06-26 18:31:36,677 INFO ]: BlockEncodingV2 initialized [2018-06-26 18:31:36,677 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 06:31:36" (1/1) ... [2018-06-26 18:31:36,702 INFO ]: Initial Icfg 47 locations, 75 edges [2018-06-26 18:31:36,704 INFO ]: Using Remove infeasible edges [2018-06-26 18:31:36,704 INFO ]: Using Maximize final states [2018-06-26 18:31:36,705 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-26 18:31:36,707 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-26 18:31:36,709 INFO ]: Using Remove sink states [2018-06-26 18:31:36,710 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-26 18:31:36,710 INFO ]: Using Use SBE [2018-06-26 18:31:36,758 INFO ]: SBE split 3 edges [2018-06-26 18:31:36,765 INFO ]: Removed 4 edges and 2 locations because of local infeasibility [2018-06-26 18:31:36,766 INFO ]: 0 new accepting states [2018-06-26 18:31:37,180 INFO ]: Removed 46 edges and 12 locations by large block encoding [2018-06-26 18:31:37,182 INFO ]: Removed 1 edges and 1 locations by removing sink states [2018-06-26 18:31:37,183 INFO ]: Removed 2 edges and 0 locations because of local infeasibility [2018-06-26 18:31:37,183 INFO ]: 0 new accepting states [2018-06-26 18:31:37,184 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-26 18:31:37,185 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 18:31:37,185 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-26 18:31:37,185 INFO ]: 0 new accepting states [2018-06-26 18:31:37,186 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-26 18:31:37,186 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 18:31:37,186 INFO ]: Encoded RCFG 32 locations, 62 edges [2018-06-26 18:31:37,187 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 06:31:37 BasicIcfg [2018-06-26 18:31:37,187 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-26 18:31:37,188 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-26 18:31:37,188 INFO ]: Initializing TraceAbstraction... [2018-06-26 18:31:37,193 INFO ]: TraceAbstraction initialized [2018-06-26 18:31:37,193 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 06:31:36" (1/4) ... [2018-06-26 18:31:37,194 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@49b13bc7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 26.06 06:31:37, skipping insertion in model container [2018-06-26 18:31:37,194 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:31:36" (2/4) ... [2018-06-26 18:31:37,194 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@49b13bc7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.06 06:31:37, skipping insertion in model container [2018-06-26 18:31:37,194 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 06:31:36" (3/4) ... [2018-06-26 18:31:37,195 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@49b13bc7 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 06:31:37, skipping insertion in model container [2018-06-26 18:31:37,195 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 06:31:37" (4/4) ... [2018-06-26 18:31:37,196 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-26 18:31:37,205 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-26 18:31:37,213 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-26 18:31:37,254 INFO ]: Using default assertion order modulation [2018-06-26 18:31:37,255 INFO ]: Interprodecural is true [2018-06-26 18:31:37,255 INFO ]: Hoare is false [2018-06-26 18:31:37,255 INFO ]: Compute interpolants for FPandBP [2018-06-26 18:31:37,255 INFO ]: Backedges is TWOTRACK [2018-06-26 18:31:37,255 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-26 18:31:37,255 INFO ]: Difference is false [2018-06-26 18:31:37,255 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-26 18:31:37,255 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-26 18:31:37,267 INFO ]: Start isEmpty. Operand 32 states. [2018-06-26 18:31:37,279 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-26 18:31:37,279 INFO ]: Found error trace [2018-06-26 18:31:37,282 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-26 18:31:37,282 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:37,287 INFO ]: Analyzing trace with hash 46918026, now seen corresponding path program 1 times [2018-06-26 18:31:37,289 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:37,290 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:37,323 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:37,323 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:37,323 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:37,360 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:37,414 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:31:37,416 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:31:37,416 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 18:31:37,418 INFO ]: Interpolant automaton has 3 states [2018-06-26 18:31:37,430 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 18:31:37,431 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:31:37,434 INFO ]: Start difference. First operand 32 states. Second operand 3 states. [2018-06-26 18:31:38,209 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:38,209 INFO ]: Finished difference Result 57 states and 110 transitions. [2018-06-26 18:31:38,210 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 18:31:38,211 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-26 18:31:38,211 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:38,223 INFO ]: With dead ends: 57 [2018-06-26 18:31:38,223 INFO ]: Without dead ends: 41 [2018-06-26 18:31:38,225 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:31:38,241 INFO ]: Start minimizeSevpa. Operand 41 states. [2018-06-26 18:31:38,275 INFO ]: Finished minimizeSevpa. Reduced states from 41 to 41. [2018-06-26 18:31:38,276 INFO ]: Start removeUnreachable. Operand 41 states. [2018-06-26 18:31:38,281 INFO ]: Finished removeUnreachable. Reduced from 41 states to 41 states and 72 transitions. [2018-06-26 18:31:38,282 INFO ]: Start accepts. Automaton has 41 states and 72 transitions. Word has length 5 [2018-06-26 18:31:38,283 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:38,283 INFO ]: Abstraction has 41 states and 72 transitions. [2018-06-26 18:31:38,283 INFO ]: Interpolant automaton has 3 states. [2018-06-26 18:31:38,283 INFO ]: Start isEmpty. Operand 41 states and 72 transitions. [2018-06-26 18:31:38,285 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 18:31:38,285 INFO ]: Found error trace [2018-06-26 18:31:38,285 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 18:31:38,286 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:38,286 INFO ]: Analyzing trace with hash 1479448052, now seen corresponding path program 1 times [2018-06-26 18:31:38,286 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:38,286 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:38,286 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:38,287 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:38,287 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:38,297 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:38,369 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:31:38,370 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:31:38,370 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 18:31:38,371 INFO ]: Interpolant automaton has 3 states [2018-06-26 18:31:38,371 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 18:31:38,371 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:31:38,371 INFO ]: Start difference. First operand 41 states and 72 transitions. Second operand 3 states. [2018-06-26 18:31:38,912 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:38,912 INFO ]: Finished difference Result 58 states and 104 transitions. [2018-06-26 18:31:38,912 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 18:31:38,912 INFO ]: Start accepts. Automaton has 3 states. Word has length 6 [2018-06-26 18:31:38,912 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:38,917 INFO ]: With dead ends: 58 [2018-06-26 18:31:38,917 INFO ]: Without dead ends: 58 [2018-06-26 18:31:38,917 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:31:38,917 INFO ]: Start minimizeSevpa. Operand 58 states. [2018-06-26 18:31:38,928 INFO ]: Finished minimizeSevpa. Reduced states from 58 to 58. [2018-06-26 18:31:38,928 INFO ]: Start removeUnreachable. Operand 58 states. [2018-06-26 18:31:38,930 INFO ]: Finished removeUnreachable. Reduced from 58 states to 58 states and 104 transitions. [2018-06-26 18:31:38,930 INFO ]: Start accepts. Automaton has 58 states and 104 transitions. Word has length 6 [2018-06-26 18:31:38,931 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:38,931 INFO ]: Abstraction has 58 states and 104 transitions. [2018-06-26 18:31:38,931 INFO ]: Interpolant automaton has 3 states. [2018-06-26 18:31:38,931 INFO ]: Start isEmpty. Operand 58 states and 104 transitions. [2018-06-26 18:31:38,934 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-26 18:31:38,934 INFO ]: Found error trace [2018-06-26 18:31:38,934 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:38,934 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:38,935 INFO ]: Analyzing trace with hash 43260942, now seen corresponding path program 1 times [2018-06-26 18:31:38,935 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:38,935 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:38,935 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:38,936 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:38,936 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:38,960 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:38,990 INFO ]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:31:38,990 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:31:38,990 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 18:31:38,990 INFO ]: Interpolant automaton has 3 states [2018-06-26 18:31:38,991 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 18:31:38,991 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:31:38,991 INFO ]: Start difference. First operand 58 states and 104 transitions. Second operand 3 states. [2018-06-26 18:31:39,051 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:39,051 INFO ]: Finished difference Result 74 states and 130 transitions. [2018-06-26 18:31:39,051 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 18:31:39,051 INFO ]: Start accepts. Automaton has 3 states. Word has length 11 [2018-06-26 18:31:39,051 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:39,054 INFO ]: With dead ends: 74 [2018-06-26 18:31:39,054 INFO ]: Without dead ends: 58 [2018-06-26 18:31:39,055 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:31:39,055 INFO ]: Start minimizeSevpa. Operand 58 states. [2018-06-26 18:31:39,068 INFO ]: Finished minimizeSevpa. Reduced states from 58 to 58. [2018-06-26 18:31:39,069 INFO ]: Start removeUnreachable. Operand 58 states. [2018-06-26 18:31:39,071 INFO ]: Finished removeUnreachable. Reduced from 58 states to 58 states and 103 transitions. [2018-06-26 18:31:39,071 INFO ]: Start accepts. Automaton has 58 states and 103 transitions. Word has length 11 [2018-06-26 18:31:39,071 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:39,071 INFO ]: Abstraction has 58 states and 103 transitions. [2018-06-26 18:31:39,071 INFO ]: Interpolant automaton has 3 states. [2018-06-26 18:31:39,071 INFO ]: Start isEmpty. Operand 58 states and 103 transitions. [2018-06-26 18:31:39,073 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-26 18:31:39,073 INFO ]: Found error trace [2018-06-26 18:31:39,073 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:39,073 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:39,073 INFO ]: Analyzing trace with hash -349766068, now seen corresponding path program 1 times [2018-06-26 18:31:39,073 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:39,073 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:39,074 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:39,074 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:39,074 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:39,110 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:39,173 INFO ]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:31:39,174 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:31:39,174 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-06-26 18:31:39,174 INFO ]: Interpolant automaton has 5 states [2018-06-26 18:31:39,174 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 18:31:39,174 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-26 18:31:39,174 INFO ]: Start difference. First operand 58 states and 103 transitions. Second operand 5 states. [2018-06-26 18:31:39,722 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:39,722 INFO ]: Finished difference Result 129 states and 275 transitions. [2018-06-26 18:31:39,723 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-26 18:31:39,723 INFO ]: Start accepts. Automaton has 5 states. Word has length 11 [2018-06-26 18:31:39,723 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:39,735 INFO ]: With dead ends: 129 [2018-06-26 18:31:39,735 INFO ]: Without dead ends: 129 [2018-06-26 18:31:39,736 INFO ]: 0 DeclaredPredicates, 8 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-06-26 18:31:39,736 INFO ]: Start minimizeSevpa. Operand 129 states. [2018-06-26 18:31:39,760 INFO ]: Finished minimizeSevpa. Reduced states from 129 to 62. [2018-06-26 18:31:39,760 INFO ]: Start removeUnreachable. Operand 62 states. [2018-06-26 18:31:39,762 INFO ]: Finished removeUnreachable. Reduced from 62 states to 62 states and 111 transitions. [2018-06-26 18:31:39,762 INFO ]: Start accepts. Automaton has 62 states and 111 transitions. Word has length 11 [2018-06-26 18:31:39,762 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:39,762 INFO ]: Abstraction has 62 states and 111 transitions. [2018-06-26 18:31:39,762 INFO ]: Interpolant automaton has 5 states. [2018-06-26 18:31:39,762 INFO ]: Start isEmpty. Operand 62 states and 111 transitions. [2018-06-26 18:31:39,764 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-26 18:31:39,764 INFO ]: Found error trace [2018-06-26 18:31:39,764 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:39,764 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:39,764 INFO ]: Analyzing trace with hash 2040807782, now seen corresponding path program 1 times [2018-06-26 18:31:39,764 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:39,765 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:39,765 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:39,765 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:39,765 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:39,782 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:39,863 INFO ]: Checked inductivity of 5 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-26 18:31:39,863 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:31:39,863 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-26 18:31:39,864 INFO ]: Interpolant automaton has 4 states [2018-06-26 18:31:39,864 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-26 18:31:39,864 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-26 18:31:39,864 INFO ]: Start difference. First operand 62 states and 111 transitions. Second operand 4 states. [2018-06-26 18:31:39,942 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:39,942 INFO ]: Finished difference Result 98 states and 168 transitions. [2018-06-26 18:31:39,944 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-26 18:31:39,944 INFO ]: Start accepts. Automaton has 4 states. Word has length 12 [2018-06-26 18:31:39,944 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:39,947 INFO ]: With dead ends: 98 [2018-06-26 18:31:39,947 INFO ]: Without dead ends: 98 [2018-06-26 18:31:39,947 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-26 18:31:39,947 INFO ]: Start minimizeSevpa. Operand 98 states. [2018-06-26 18:31:39,957 INFO ]: Finished minimizeSevpa. Reduced states from 98 to 71. [2018-06-26 18:31:39,957 INFO ]: Start removeUnreachable. Operand 71 states. [2018-06-26 18:31:39,959 INFO ]: Finished removeUnreachable. Reduced from 71 states to 71 states and 123 transitions. [2018-06-26 18:31:39,959 INFO ]: Start accepts. Automaton has 71 states and 123 transitions. Word has length 12 [2018-06-26 18:31:39,959 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:39,959 INFO ]: Abstraction has 71 states and 123 transitions. [2018-06-26 18:31:39,959 INFO ]: Interpolant automaton has 4 states. [2018-06-26 18:31:39,960 INFO ]: Start isEmpty. Operand 71 states and 123 transitions. [2018-06-26 18:31:39,962 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-26 18:31:39,962 INFO ]: Found error trace [2018-06-26 18:31:39,962 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:39,962 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:39,962 INFO ]: Analyzing trace with hash 243856423, now seen corresponding path program 1 times [2018-06-26 18:31:39,963 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:39,963 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:39,963 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:39,963 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:39,963 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:39,979 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:40,075 INFO ]: Checked inductivity of 5 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:31:40,075 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:31:40,075 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-06-26 18:31:40,076 INFO ]: Interpolant automaton has 5 states [2018-06-26 18:31:40,076 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 18:31:40,076 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-26 18:31:40,076 INFO ]: Start difference. First operand 71 states and 123 transitions. Second operand 5 states. [2018-06-26 18:31:40,390 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:40,390 INFO ]: Finished difference Result 158 states and 264 transitions. [2018-06-26 18:31:40,390 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-26 18:31:40,390 INFO ]: Start accepts. Automaton has 5 states. Word has length 12 [2018-06-26 18:31:40,390 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:40,395 INFO ]: With dead ends: 158 [2018-06-26 18:31:40,395 INFO ]: Without dead ends: 158 [2018-06-26 18:31:40,395 INFO ]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=34, Unknown=0, NotChecked=0, Total=56 [2018-06-26 18:31:40,395 INFO ]: Start minimizeSevpa. Operand 158 states. [2018-06-26 18:31:40,411 INFO ]: Finished minimizeSevpa. Reduced states from 158 to 83. [2018-06-26 18:31:40,411 INFO ]: Start removeUnreachable. Operand 83 states. [2018-06-26 18:31:40,412 INFO ]: Finished removeUnreachable. Reduced from 83 states to 83 states and 141 transitions. [2018-06-26 18:31:40,413 INFO ]: Start accepts. Automaton has 83 states and 141 transitions. Word has length 12 [2018-06-26 18:31:40,413 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:40,413 INFO ]: Abstraction has 83 states and 141 transitions. [2018-06-26 18:31:40,413 INFO ]: Interpolant automaton has 5 states. [2018-06-26 18:31:40,413 INFO ]: Start isEmpty. Operand 83 states and 141 transitions. [2018-06-26 18:31:40,418 INFO ]: Finished isEmpty. Found accepting run of length 31 [2018-06-26 18:31:40,418 INFO ]: Found error trace [2018-06-26 18:31:40,418 INFO ]: trace histogram [5, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:40,418 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:40,418 INFO ]: Analyzing trace with hash 1677085476, now seen corresponding path program 1 times [2018-06-26 18:31:40,418 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:40,418 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:40,419 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:40,419 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:40,419 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:40,451 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:40,868 INFO ]: Checked inductivity of 46 backedges. 24 proven. 2 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2018-06-26 18:31:40,868 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:31:40,868 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:31:40,887 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:40,959 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:40,971 INFO ]: Computing forward predicates... [2018-06-26 18:31:41,124 INFO ]: Checked inductivity of 46 backedges. 20 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2018-06-26 18:31:41,158 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 18:31:41,158 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [6] total 8 [2018-06-26 18:31:41,158 INFO ]: Interpolant automaton has 8 states [2018-06-26 18:31:41,159 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-26 18:31:41,159 INFO ]: CoverageRelationStatistics Valid=13, Invalid=43, Unknown=0, NotChecked=0, Total=56 [2018-06-26 18:31:41,159 INFO ]: Start difference. First operand 83 states and 141 transitions. Second operand 8 states. [2018-06-26 18:31:43,320 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:43,320 INFO ]: Finished difference Result 223 states and 466 transitions. [2018-06-26 18:31:43,321 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-06-26 18:31:43,321 INFO ]: Start accepts. Automaton has 8 states. Word has length 30 [2018-06-26 18:31:43,321 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:43,331 INFO ]: With dead ends: 223 [2018-06-26 18:31:43,331 INFO ]: Without dead ends: 206 [2018-06-26 18:31:43,331 INFO ]: 0 DeclaredPredicates, 51 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=69, Invalid=237, Unknown=0, NotChecked=0, Total=306 [2018-06-26 18:31:43,332 INFO ]: Start minimizeSevpa. Operand 206 states. [2018-06-26 18:31:43,373 INFO ]: Finished minimizeSevpa. Reduced states from 206 to 102. [2018-06-26 18:31:43,374 INFO ]: Start removeUnreachable. Operand 102 states. [2018-06-26 18:31:43,380 INFO ]: Finished removeUnreachable. Reduced from 102 states to 102 states and 194 transitions. [2018-06-26 18:31:43,380 INFO ]: Start accepts. Automaton has 102 states and 194 transitions. Word has length 30 [2018-06-26 18:31:43,380 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:43,380 INFO ]: Abstraction has 102 states and 194 transitions. [2018-06-26 18:31:43,380 INFO ]: Interpolant automaton has 8 states. [2018-06-26 18:31:43,380 INFO ]: Start isEmpty. Operand 102 states and 194 transitions. [2018-06-26 18:31:43,388 INFO ]: Finished isEmpty. Found accepting run of length 35 [2018-06-26 18:31:43,388 INFO ]: Found error trace [2018-06-26 18:31:43,388 INFO ]: trace histogram [6, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:43,389 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:43,389 INFO ]: Analyzing trace with hash -1298477567, now seen corresponding path program 1 times [2018-06-26 18:31:43,389 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:43,389 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:43,389 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:43,389 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:43,389 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:43,410 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:43,508 INFO ]: Checked inductivity of 59 backedges. 22 proven. 8 refuted. 0 times theorem prover too weak. 29 trivial. 0 not checked. [2018-06-26 18:31:43,508 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:31:43,508 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:31:43,516 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:43,576 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:43,579 INFO ]: Computing forward predicates... [2018-06-26 18:31:43,761 INFO ]: Checked inductivity of 59 backedges. 34 proven. 0 refuted. 0 times theorem prover too weak. 25 trivial. 0 not checked. [2018-06-26 18:31:43,787 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 18:31:43,787 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2018-06-26 18:31:43,787 INFO ]: Interpolant automaton has 10 states [2018-06-26 18:31:43,787 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-26 18:31:43,787 INFO ]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2018-06-26 18:31:43,788 INFO ]: Start difference. First operand 102 states and 194 transitions. Second operand 10 states. [2018-06-26 18:31:44,541 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:44,542 INFO ]: Finished difference Result 274 states and 663 transitions. [2018-06-26 18:31:44,542 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-26 18:31:44,542 INFO ]: Start accepts. Automaton has 10 states. Word has length 34 [2018-06-26 18:31:44,542 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:44,548 INFO ]: With dead ends: 274 [2018-06-26 18:31:44,548 INFO ]: Without dead ends: 172 [2018-06-26 18:31:44,549 INFO ]: 0 DeclaredPredicates, 52 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=106, Invalid=236, Unknown=0, NotChecked=0, Total=342 [2018-06-26 18:31:44,549 INFO ]: Start minimizeSevpa. Operand 172 states. [2018-06-26 18:31:44,581 INFO ]: Finished minimizeSevpa. Reduced states from 172 to 106. [2018-06-26 18:31:44,581 INFO ]: Start removeUnreachable. Operand 106 states. [2018-06-26 18:31:44,585 INFO ]: Finished removeUnreachable. Reduced from 106 states to 106 states and 213 transitions. [2018-06-26 18:31:44,585 INFO ]: Start accepts. Automaton has 106 states and 213 transitions. Word has length 34 [2018-06-26 18:31:44,585 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:44,585 INFO ]: Abstraction has 106 states and 213 transitions. [2018-06-26 18:31:44,585 INFO ]: Interpolant automaton has 10 states. [2018-06-26 18:31:44,585 INFO ]: Start isEmpty. Operand 106 states and 213 transitions. [2018-06-26 18:31:44,590 INFO ]: Finished isEmpty. Found accepting run of length 36 [2018-06-26 18:31:44,590 INFO ]: Found error trace [2018-06-26 18:31:44,590 INFO ]: trace histogram [6, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:44,590 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:44,590 INFO ]: Analyzing trace with hash -117475901, now seen corresponding path program 2 times [2018-06-26 18:31:44,590 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:44,590 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:44,591 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:44,591 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:44,591 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:44,620 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:44,819 INFO ]: Checked inductivity of 66 backedges. 28 proven. 5 refuted. 0 times theorem prover too weak. 33 trivial. 0 not checked. [2018-06-26 18:31:44,819 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:31:44,819 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:31:44,831 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 18:31:44,905 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 18:31:44,905 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:44,908 INFO ]: Computing forward predicates... [2018-06-26 18:31:44,991 INFO ]: Checked inductivity of 66 backedges. 45 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-26 18:31:45,021 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 18:31:45,021 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2018-06-26 18:31:45,021 INFO ]: Interpolant automaton has 10 states [2018-06-26 18:31:45,021 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-26 18:31:45,021 INFO ]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2018-06-26 18:31:45,021 INFO ]: Start difference. First operand 106 states and 213 transitions. Second operand 10 states. [2018-06-26 18:31:45,681 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:45,681 INFO ]: Finished difference Result 146 states and 304 transitions. [2018-06-26 18:31:45,681 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-26 18:31:45,681 INFO ]: Start accepts. Automaton has 10 states. Word has length 35 [2018-06-26 18:31:45,681 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:45,683 INFO ]: With dead ends: 146 [2018-06-26 18:31:45,683 INFO ]: Without dead ends: 146 [2018-06-26 18:31:45,683 INFO ]: 0 DeclaredPredicates, 54 GetRequests, 37 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=90, Invalid=252, Unknown=0, NotChecked=0, Total=342 [2018-06-26 18:31:45,683 INFO ]: Start minimizeSevpa. Operand 146 states. [2018-06-26 18:31:45,701 INFO ]: Finished minimizeSevpa. Reduced states from 146 to 98. [2018-06-26 18:31:45,701 INFO ]: Start removeUnreachable. Operand 98 states. [2018-06-26 18:31:45,703 INFO ]: Finished removeUnreachable. Reduced from 98 states to 98 states and 189 transitions. [2018-06-26 18:31:45,703 INFO ]: Start accepts. Automaton has 98 states and 189 transitions. Word has length 35 [2018-06-26 18:31:45,703 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:45,703 INFO ]: Abstraction has 98 states and 189 transitions. [2018-06-26 18:31:45,703 INFO ]: Interpolant automaton has 10 states. [2018-06-26 18:31:45,703 INFO ]: Start isEmpty. Operand 98 states and 189 transitions. [2018-06-26 18:31:45,710 INFO ]: Finished isEmpty. Found accepting run of length 37 [2018-06-26 18:31:45,710 INFO ]: Found error trace [2018-06-26 18:31:45,710 INFO ]: trace histogram [6, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:45,710 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:45,710 INFO ]: Analyzing trace with hash 2021633429, now seen corresponding path program 3 times [2018-06-26 18:31:45,710 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:45,710 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:45,711 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:45,711 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:31:45,711 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:45,728 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:45,788 INFO ]: Checked inductivity of 74 backedges. 34 proven. 2 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2018-06-26 18:31:45,788 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:31:45,788 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:31:45,795 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 18:31:45,871 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-26 18:31:45,871 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:45,874 INFO ]: Computing forward predicates... [2018-06-26 18:31:45,879 INFO ]: Checked inductivity of 74 backedges. 46 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-26 18:31:45,909 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 18:31:45,910 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [3] total 3 [2018-06-26 18:31:45,910 INFO ]: Interpolant automaton has 3 states [2018-06-26 18:31:45,910 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 18:31:45,910 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:31:45,910 INFO ]: Start difference. First operand 98 states and 189 transitions. Second operand 3 states. [2018-06-26 18:31:45,943 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:45,943 INFO ]: Finished difference Result 134 states and 249 transitions. [2018-06-26 18:31:45,943 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 18:31:45,943 INFO ]: Start accepts. Automaton has 3 states. Word has length 36 [2018-06-26 18:31:45,944 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:45,945 INFO ]: With dead ends: 134 [2018-06-26 18:31:45,945 INFO ]: Without dead ends: 116 [2018-06-26 18:31:45,946 INFO ]: 0 DeclaredPredicates, 38 GetRequests, 37 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:31:45,946 INFO ]: Start minimizeSevpa. Operand 116 states. [2018-06-26 18:31:45,953 INFO ]: Finished minimizeSevpa. Reduced states from 116 to 116. [2018-06-26 18:31:45,953 INFO ]: Start removeUnreachable. Operand 116 states. [2018-06-26 18:31:45,955 INFO ]: Finished removeUnreachable. Reduced from 116 states to 116 states and 215 transitions. [2018-06-26 18:31:45,956 INFO ]: Start accepts. Automaton has 116 states and 215 transitions. Word has length 36 [2018-06-26 18:31:45,956 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:45,956 INFO ]: Abstraction has 116 states and 215 transitions. [2018-06-26 18:31:45,956 INFO ]: Interpolant automaton has 3 states. [2018-06-26 18:31:45,956 INFO ]: Start isEmpty. Operand 116 states and 215 transitions. [2018-06-26 18:31:45,959 INFO ]: Finished isEmpty. Found accepting run of length 44 [2018-06-26 18:31:45,959 INFO ]: Found error trace [2018-06-26 18:31:45,959 INFO ]: trace histogram [7, 4, 4, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:45,959 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:45,960 INFO ]: Analyzing trace with hash 1484234489, now seen corresponding path program 1 times [2018-06-26 18:31:45,960 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:45,960 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:45,960 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:45,960 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:31:45,960 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:45,978 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:46,064 INFO ]: Checked inductivity of 109 backedges. 51 proven. 3 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-26 18:31:46,065 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:31:46,065 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-26 18:31:46,080 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:31:46,159 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:46,163 INFO ]: Computing forward predicates... [2018-06-26 18:31:46,171 INFO ]: Checked inductivity of 109 backedges. 67 proven. 0 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2018-06-26 18:31:46,208 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 18:31:46,208 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [3] total 3 [2018-06-26 18:31:46,209 INFO ]: Interpolant automaton has 3 states [2018-06-26 18:31:46,209 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 18:31:46,209 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:31:46,209 INFO ]: Start difference. First operand 116 states and 215 transitions. Second operand 3 states. [2018-06-26 18:31:46,328 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:46,329 INFO ]: Finished difference Result 125 states and 226 transitions. [2018-06-26 18:31:46,329 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 18:31:46,329 INFO ]: Start accepts. Automaton has 3 states. Word has length 43 [2018-06-26 18:31:46,329 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:46,330 INFO ]: With dead ends: 125 [2018-06-26 18:31:46,330 INFO ]: Without dead ends: 110 [2018-06-26 18:31:46,331 INFO ]: 0 DeclaredPredicates, 45 GetRequests, 44 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:31:46,331 INFO ]: Start minimizeSevpa. Operand 110 states. [2018-06-26 18:31:46,340 INFO ]: Finished minimizeSevpa. Reduced states from 110 to 110. [2018-06-26 18:31:46,340 INFO ]: Start removeUnreachable. Operand 110 states. [2018-06-26 18:31:46,342 INFO ]: Finished removeUnreachable. Reduced from 110 states to 110 states and 199 transitions. [2018-06-26 18:31:46,342 INFO ]: Start accepts. Automaton has 110 states and 199 transitions. Word has length 43 [2018-06-26 18:31:46,342 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:46,342 INFO ]: Abstraction has 110 states and 199 transitions. [2018-06-26 18:31:46,342 INFO ]: Interpolant automaton has 3 states. [2018-06-26 18:31:46,342 INFO ]: Start isEmpty. Operand 110 states and 199 transitions. [2018-06-26 18:31:46,351 INFO ]: Finished isEmpty. Found accepting run of length 59 [2018-06-26 18:31:46,351 INFO ]: Found error trace [2018-06-26 18:31:46,351 INFO ]: trace histogram [10, 5, 5, 4, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:46,352 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:46,353 INFO ]: Analyzing trace with hash -1027889551, now seen corresponding path program 1 times [2018-06-26 18:31:46,353 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:46,353 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:46,354 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:46,354 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:46,354 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:46,374 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:46,451 INFO ]: Checked inductivity of 202 backedges. 77 proven. 4 refuted. 0 times theorem prover too weak. 121 trivial. 0 not checked. [2018-06-26 18:31:46,451 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:31:46,451 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:31:46,460 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:46,529 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:46,533 INFO ]: Computing forward predicates... [2018-06-26 18:31:46,592 INFO ]: Checked inductivity of 202 backedges. 100 proven. 0 refuted. 0 times theorem prover too weak. 102 trivial. 0 not checked. [2018-06-26 18:31:46,612 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 18:31:46,612 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 10 [2018-06-26 18:31:46,613 INFO ]: Interpolant automaton has 10 states [2018-06-26 18:31:46,613 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-26 18:31:46,613 INFO ]: CoverageRelationStatistics Valid=21, Invalid=69, Unknown=0, NotChecked=0, Total=90 [2018-06-26 18:31:46,613 INFO ]: Start difference. First operand 110 states and 199 transitions. Second operand 10 states. [2018-06-26 18:31:46,750 WARN ]: Spent 115.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-26 18:31:47,051 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:47,051 INFO ]: Finished difference Result 136 states and 258 transitions. [2018-06-26 18:31:47,052 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-26 18:31:47,052 INFO ]: Start accepts. Automaton has 10 states. Word has length 58 [2018-06-26 18:31:47,052 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:47,054 INFO ]: With dead ends: 136 [2018-06-26 18:31:47,054 INFO ]: Without dead ends: 135 [2018-06-26 18:31:47,055 INFO ]: 0 DeclaredPredicates, 69 GetRequests, 58 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=43, Invalid=113, Unknown=0, NotChecked=0, Total=156 [2018-06-26 18:31:47,055 INFO ]: Start minimizeSevpa. Operand 135 states. [2018-06-26 18:31:47,062 INFO ]: Finished minimizeSevpa. Reduced states from 135 to 108. [2018-06-26 18:31:47,062 INFO ]: Start removeUnreachable. Operand 108 states. [2018-06-26 18:31:47,064 INFO ]: Finished removeUnreachable. Reduced from 108 states to 108 states and 195 transitions. [2018-06-26 18:31:47,064 INFO ]: Start accepts. Automaton has 108 states and 195 transitions. Word has length 58 [2018-06-26 18:31:47,064 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:47,064 INFO ]: Abstraction has 108 states and 195 transitions. [2018-06-26 18:31:47,064 INFO ]: Interpolant automaton has 10 states. [2018-06-26 18:31:47,064 INFO ]: Start isEmpty. Operand 108 states and 195 transitions. [2018-06-26 18:31:47,068 INFO ]: Finished isEmpty. Found accepting run of length 60 [2018-06-26 18:31:47,068 INFO ]: Found error trace [2018-06-26 18:31:47,068 INFO ]: trace histogram [10, 5, 5, 5, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:47,068 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:47,068 INFO ]: Analyzing trace with hash 442786971, now seen corresponding path program 2 times [2018-06-26 18:31:47,068 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:47,068 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:47,069 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:47,069 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:47,069 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:47,088 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:47,192 INFO ]: Checked inductivity of 216 backedges. 66 proven. 2 refuted. 0 times theorem prover too weak. 148 trivial. 0 not checked. [2018-06-26 18:31:47,193 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:31:47,193 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:31:47,199 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 18:31:47,290 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 18:31:47,290 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:47,294 INFO ]: Computing forward predicates... [2018-06-26 18:31:47,692 INFO ]: Checked inductivity of 216 backedges. 92 proven. 0 refuted. 0 times theorem prover too weak. 124 trivial. 0 not checked. [2018-06-26 18:31:47,721 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 18:31:47,721 INFO ]: Number of different interpolants: perfect sequences [8] imperfect sequences [8] total 14 [2018-06-26 18:31:47,722 INFO ]: Interpolant automaton has 14 states [2018-06-26 18:31:47,722 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-26 18:31:47,722 INFO ]: CoverageRelationStatistics Valid=31, Invalid=151, Unknown=0, NotChecked=0, Total=182 [2018-06-26 18:31:47,722 INFO ]: Start difference. First operand 108 states and 195 transitions. Second operand 14 states. [2018-06-26 18:31:49,094 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:49,094 INFO ]: Finished difference Result 248 states and 593 transitions. [2018-06-26 18:31:49,094 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-06-26 18:31:49,094 INFO ]: Start accepts. Automaton has 14 states. Word has length 59 [2018-06-26 18:31:49,094 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:49,099 INFO ]: With dead ends: 248 [2018-06-26 18:31:49,099 INFO ]: Without dead ends: 247 [2018-06-26 18:31:49,100 INFO ]: 0 DeclaredPredicates, 100 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 282 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=243, Invalid=1163, Unknown=0, NotChecked=0, Total=1406 [2018-06-26 18:31:49,100 INFO ]: Start minimizeSevpa. Operand 247 states. [2018-06-26 18:31:49,116 INFO ]: Finished minimizeSevpa. Reduced states from 247 to 108. [2018-06-26 18:31:49,116 INFO ]: Start removeUnreachable. Operand 108 states. [2018-06-26 18:31:49,118 INFO ]: Finished removeUnreachable. Reduced from 108 states to 108 states and 195 transitions. [2018-06-26 18:31:49,118 INFO ]: Start accepts. Automaton has 108 states and 195 transitions. Word has length 59 [2018-06-26 18:31:49,118 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:49,118 INFO ]: Abstraction has 108 states and 195 transitions. [2018-06-26 18:31:49,118 INFO ]: Interpolant automaton has 14 states. [2018-06-26 18:31:49,118 INFO ]: Start isEmpty. Operand 108 states and 195 transitions. [2018-06-26 18:31:49,121 INFO ]: Finished isEmpty. Found accepting run of length 61 [2018-06-26 18:31:49,121 INFO ]: Found error trace [2018-06-26 18:31:49,121 INFO ]: trace histogram [10, 6, 5, 5, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:49,121 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:49,121 INFO ]: Analyzing trace with hash -361030443, now seen corresponding path program 3 times [2018-06-26 18:31:49,121 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:49,121 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:49,122 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:49,122 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:31:49,122 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:49,144 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:49,392 INFO ]: Checked inductivity of 231 backedges. 82 proven. 31 refuted. 0 times theorem prover too weak. 118 trivial. 0 not checked. [2018-06-26 18:31:49,392 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:31:49,392 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:31:49,400 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 18:31:49,482 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2018-06-26 18:31:49,482 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:49,486 INFO ]: Computing forward predicates... [2018-06-26 18:31:49,608 INFO ]: Checked inductivity of 231 backedges. 122 proven. 10 refuted. 0 times theorem prover too weak. 99 trivial. 0 not checked. [2018-06-26 18:31:49,628 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:31:49,628 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 19 [2018-06-26 18:31:49,628 INFO ]: Interpolant automaton has 19 states [2018-06-26 18:31:49,629 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-26 18:31:49,629 INFO ]: CoverageRelationStatistics Valid=36, Invalid=306, Unknown=0, NotChecked=0, Total=342 [2018-06-26 18:31:49,629 INFO ]: Start difference. First operand 108 states and 195 transitions. Second operand 19 states. [2018-06-26 18:31:58,558 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:58,559 INFO ]: Finished difference Result 665 states and 2040 transitions. [2018-06-26 18:31:58,559 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 112 states. [2018-06-26 18:31:58,559 INFO ]: Start accepts. Automaton has 19 states. Word has length 60 [2018-06-26 18:31:58,559 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:58,579 INFO ]: With dead ends: 665 [2018-06-26 18:31:58,580 INFO ]: Without dead ends: 665 [2018-06-26 18:31:58,583 INFO ]: 0 DeclaredPredicates, 214 GetRequests, 93 SyntacticMatches, 0 SemanticMatches, 121 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5141 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=1109, Invalid=13897, Unknown=0, NotChecked=0, Total=15006 [2018-06-26 18:31:58,584 INFO ]: Start minimizeSevpa. Operand 665 states. [2018-06-26 18:31:58,734 INFO ]: Finished minimizeSevpa. Reduced states from 665 to 205. [2018-06-26 18:31:58,734 INFO ]: Start removeUnreachable. Operand 205 states. [2018-06-26 18:31:58,738 INFO ]: Finished removeUnreachable. Reduced from 205 states to 205 states and 392 transitions. [2018-06-26 18:31:58,738 INFO ]: Start accepts. Automaton has 205 states and 392 transitions. Word has length 60 [2018-06-26 18:31:58,738 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:58,738 INFO ]: Abstraction has 205 states and 392 transitions. [2018-06-26 18:31:58,738 INFO ]: Interpolant automaton has 19 states. [2018-06-26 18:31:58,738 INFO ]: Start isEmpty. Operand 205 states and 392 transitions. [2018-06-26 18:31:58,743 INFO ]: Finished isEmpty. Found accepting run of length 80 [2018-06-26 18:31:58,743 INFO ]: Found error trace [2018-06-26 18:31:58,744 INFO ]: trace histogram [13, 7, 7, 7, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:58,744 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:58,744 INFO ]: Analyzing trace with hash 1646766968, now seen corresponding path program 1 times [2018-06-26 18:31:58,744 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:58,744 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:58,744 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:58,744 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:31:58,744 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:58,776 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:59,028 INFO ]: Checked inductivity of 407 backedges. 124 proven. 54 refuted. 0 times theorem prover too weak. 229 trivial. 0 not checked. [2018-06-26 18:31:59,028 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:31:59,028 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:31:59,037 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:59,112 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:31:59,117 INFO ]: Computing forward predicates... [2018-06-26 18:31:59,238 INFO ]: Checked inductivity of 407 backedges. 161 proven. 47 refuted. 0 times theorem prover too weak. 199 trivial. 0 not checked. [2018-06-26 18:31:59,258 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:31:59,258 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 13 [2018-06-26 18:31:59,258 INFO ]: Interpolant automaton has 13 states [2018-06-26 18:31:59,258 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-26 18:31:59,258 INFO ]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-06-26 18:31:59,258 INFO ]: Start difference. First operand 205 states and 392 transitions. Second operand 13 states. [2018-06-26 18:31:59,809 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:31:59,809 INFO ]: Finished difference Result 356 states and 793 transitions. [2018-06-26 18:31:59,809 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-26 18:31:59,809 INFO ]: Start accepts. Automaton has 13 states. Word has length 79 [2018-06-26 18:31:59,809 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:31:59,816 INFO ]: With dead ends: 356 [2018-06-26 18:31:59,816 INFO ]: Without dead ends: 356 [2018-06-26 18:31:59,817 INFO ]: 0 DeclaredPredicates, 108 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 23 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 72 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=102, Invalid=498, Unknown=0, NotChecked=0, Total=600 [2018-06-26 18:31:59,817 INFO ]: Start minimizeSevpa. Operand 356 states. [2018-06-26 18:31:59,846 INFO ]: Finished minimizeSevpa. Reduced states from 356 to 264. [2018-06-26 18:31:59,846 INFO ]: Start removeUnreachable. Operand 264 states. [2018-06-26 18:31:59,856 INFO ]: Finished removeUnreachable. Reduced from 264 states to 264 states and 522 transitions. [2018-06-26 18:31:59,857 INFO ]: Start accepts. Automaton has 264 states and 522 transitions. Word has length 79 [2018-06-26 18:31:59,857 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:31:59,857 INFO ]: Abstraction has 264 states and 522 transitions. [2018-06-26 18:31:59,857 INFO ]: Interpolant automaton has 13 states. [2018-06-26 18:31:59,857 INFO ]: Start isEmpty. Operand 264 states and 522 transitions. [2018-06-26 18:31:59,867 INFO ]: Finished isEmpty. Found accepting run of length 80 [2018-06-26 18:31:59,867 INFO ]: Found error trace [2018-06-26 18:31:59,867 INFO ]: trace histogram [13, 7, 7, 7, 4, 4, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:31:59,867 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:31:59,867 INFO ]: Analyzing trace with hash 2066283799, now seen corresponding path program 1 times [2018-06-26 18:31:59,867 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:31:59,867 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:31:59,868 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:59,868 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:31:59,868 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:31:59,904 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:32:00,597 INFO ]: Checked inductivity of 407 backedges. 123 proven. 55 refuted. 0 times theorem prover too weak. 229 trivial. 0 not checked. [2018-06-26 18:32:00,597 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:32:00,597 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:32:00,605 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:32:00,711 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:32:00,717 INFO ]: Computing forward predicates... [2018-06-26 18:32:00,883 INFO ]: Checked inductivity of 407 backedges. 161 proven. 47 refuted. 0 times theorem prover too weak. 199 trivial. 0 not checked. [2018-06-26 18:32:00,902 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:32:00,903 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 10] total 18 [2018-06-26 18:32:00,903 INFO ]: Interpolant automaton has 18 states [2018-06-26 18:32:00,903 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-26 18:32:00,903 INFO ]: CoverageRelationStatistics Valid=38, Invalid=268, Unknown=0, NotChecked=0, Total=306 [2018-06-26 18:32:00,903 INFO ]: Start difference. First operand 264 states and 522 transitions. Second operand 18 states. [2018-06-26 18:32:01,663 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:32:01,663 INFO ]: Finished difference Result 380 states and 835 transitions. [2018-06-26 18:32:01,663 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-26 18:32:01,663 INFO ]: Start accepts. Automaton has 18 states. Word has length 79 [2018-06-26 18:32:01,663 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:32:01,669 INFO ]: With dead ends: 380 [2018-06-26 18:32:01,669 INFO ]: Without dead ends: 380 [2018-06-26 18:32:01,670 INFO ]: 0 DeclaredPredicates, 105 GetRequests, 79 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 62 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=110, Invalid=646, Unknown=0, NotChecked=0, Total=756 [2018-06-26 18:32:01,670 INFO ]: Start minimizeSevpa. Operand 380 states. [2018-06-26 18:32:01,701 INFO ]: Finished minimizeSevpa. Reduced states from 380 to 276. [2018-06-26 18:32:01,701 INFO ]: Start removeUnreachable. Operand 276 states. [2018-06-26 18:32:01,707 INFO ]: Finished removeUnreachable. Reduced from 276 states to 276 states and 552 transitions. [2018-06-26 18:32:01,707 INFO ]: Start accepts. Automaton has 276 states and 552 transitions. Word has length 79 [2018-06-26 18:32:01,707 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:32:01,707 INFO ]: Abstraction has 276 states and 552 transitions. [2018-06-26 18:32:01,707 INFO ]: Interpolant automaton has 18 states. [2018-06-26 18:32:01,707 INFO ]: Start isEmpty. Operand 276 states and 552 transitions. [2018-06-26 18:32:01,723 INFO ]: Finished isEmpty. Found accepting run of length 127 [2018-06-26 18:32:01,723 INFO ]: Found error trace [2018-06-26 18:32:01,723 INFO ]: trace histogram [21, 11, 11, 11, 6, 6, 6, 5, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:32:01,723 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:32:01,723 INFO ]: Analyzing trace with hash 774562341, now seen corresponding path program 2 times [2018-06-26 18:32:01,723 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:32:01,723 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:32:01,724 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:32:01,724 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:32:01,724 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:32:01,752 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:32:02,553 INFO ]: Checked inductivity of 1068 backedges. 216 proven. 49 refuted. 0 times theorem prover too weak. 803 trivial. 0 not checked. [2018-06-26 18:32:02,553 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:32:02,553 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:32:02,567 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 18:32:02,746 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 18:32:02,746 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:32:02,754 INFO ]: Computing forward predicates... [2018-06-26 18:32:02,938 INFO ]: Checked inductivity of 1068 backedges. 281 proven. 120 refuted. 0 times theorem prover too weak. 667 trivial. 0 not checked. [2018-06-26 18:32:02,957 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:32:02,957 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 12] total 19 [2018-06-26 18:32:02,957 INFO ]: Interpolant automaton has 19 states [2018-06-26 18:32:02,957 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-26 18:32:02,958 INFO ]: CoverageRelationStatistics Valid=36, Invalid=306, Unknown=0, NotChecked=0, Total=342 [2018-06-26 18:32:02,958 INFO ]: Start difference. First operand 276 states and 552 transitions. Second operand 19 states. [2018-06-26 18:32:05,131 WARN ]: Spent 121.00 ms on a formula simplification that was a NOOP. DAG size: 13 [2018-06-26 18:32:08,277 WARN ]: Spent 195.00 ms on a formula simplification that was a NOOP. DAG size: 21 [2018-06-26 18:32:12,898 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:32:12,898 INFO ]: Finished difference Result 790 states and 2778 transitions. [2018-06-26 18:32:12,898 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 110 states. [2018-06-26 18:32:12,898 INFO ]: Start accepts. Automaton has 19 states. Word has length 126 [2018-06-26 18:32:12,898 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:32:12,928 INFO ]: With dead ends: 790 [2018-06-26 18:32:12,928 INFO ]: Without dead ends: 744 [2018-06-26 18:32:12,932 INFO ]: 0 DeclaredPredicates, 264 GetRequests, 142 SyntacticMatches, 0 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5132 ImplicationChecksByTransitivity, 4.1s TimeCoverageRelationStatistics Valid=1652, Invalid=13600, Unknown=0, NotChecked=0, Total=15252 [2018-06-26 18:32:12,932 INFO ]: Start minimizeSevpa. Operand 744 states. [2018-06-26 18:32:13,076 INFO ]: Finished minimizeSevpa. Reduced states from 744 to 292. [2018-06-26 18:32:13,076 INFO ]: Start removeUnreachable. Operand 292 states. [2018-06-26 18:32:13,087 INFO ]: Finished removeUnreachable. Reduced from 292 states to 292 states and 596 transitions. [2018-06-26 18:32:13,088 INFO ]: Start accepts. Automaton has 292 states and 596 transitions. Word has length 126 [2018-06-26 18:32:13,088 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:32:13,088 INFO ]: Abstraction has 292 states and 596 transitions. [2018-06-26 18:32:13,088 INFO ]: Interpolant automaton has 19 states. [2018-06-26 18:32:13,088 INFO ]: Start isEmpty. Operand 292 states and 596 transitions. [2018-06-26 18:32:13,106 INFO ]: Finished isEmpty. Found accepting run of length 195 [2018-06-26 18:32:13,106 INFO ]: Found error trace [2018-06-26 18:32:13,106 INFO ]: trace histogram [32, 18, 17, 17, 9, 9, 9, 8, 5, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1] [2018-06-26 18:32:13,106 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:32:13,108 INFO ]: Analyzing trace with hash 1812401005, now seen corresponding path program 3 times [2018-06-26 18:32:13,108 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:32:13,108 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:32:13,109 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:32:13,109 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:32:13,109 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:32:13,185 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:32:13,593 INFO ]: Checked inductivity of 2620 backedges. 423 proven. 400 refuted. 0 times theorem prover too weak. 1797 trivial. 0 not checked. [2018-06-26 18:32:13,593 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:32:13,593 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:32:13,600 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 18:32:13,829 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-26 18:32:13,829 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:32:13,834 INFO ]: Computing forward predicates... [2018-06-26 18:32:14,065 INFO ]: Checked inductivity of 2620 backedges. 639 proven. 81 refuted. 0 times theorem prover too weak. 1900 trivial. 0 not checked. [2018-06-26 18:32:14,084 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:32:14,085 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 12] total 26 [2018-06-26 18:32:14,085 INFO ]: Interpolant automaton has 26 states [2018-06-26 18:32:14,085 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-26 18:32:14,085 INFO ]: CoverageRelationStatistics Valid=55, Invalid=595, Unknown=0, NotChecked=0, Total=650 [2018-06-26 18:32:14,085 INFO ]: Start difference. First operand 292 states and 596 transitions. Second operand 26 states. Received shutdown request... [2018-06-26 18:32:35,852 WARN ]: Removed 2 from assertion stack [2018-06-26 18:32:35,852 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 198 states. [2018-06-26 18:32:35,853 WARN ]: Verification canceled [2018-06-26 18:32:35,854 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-26 18:32:35,855 WARN ]: Timeout [2018-06-26 18:32:35,856 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 06:32:35 BasicIcfg [2018-06-26 18:32:35,856 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-26 18:32:35,856 INFO ]: Toolchain (without parser) took 59809.96 ms. Allocated memory was 305.1 MB in the beginning and 1.1 GB in the end (delta: 768.6 MB). Free memory was 252.5 MB in the beginning and 416.7 MB in the end (delta: -164.2 MB). Peak memory consumption was 604.4 MB. Max. memory is 3.6 GB. [2018-06-26 18:32:35,857 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 305.1 MB. Free memory is still 268.6 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-26 18:32:35,857 INFO ]: ChcToBoogie took 74.39 ms. Allocated memory is still 305.1 MB. Free memory was 251.5 MB in the beginning and 249.5 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:32:35,858 INFO ]: Boogie Preprocessor took 64.54 ms. Allocated memory is still 305.1 MB. Free memory was 249.5 MB in the beginning and 247.5 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:32:35,858 INFO ]: RCFGBuilder took 481.74 ms. Allocated memory is still 305.1 MB. Free memory was 247.5 MB in the beginning and 226.5 MB in the end (delta: 21.0 MB). Peak memory consumption was 21.0 MB. Max. memory is 3.6 GB. [2018-06-26 18:32:35,858 INFO ]: BlockEncodingV2 took 511.04 ms. Allocated memory is still 305.1 MB. Free memory was 226.5 MB in the beginning and 208.5 MB in the end (delta: 18.0 MB). Peak memory consumption was 18.0 MB. Max. memory is 3.6 GB. [2018-06-26 18:32:35,859 INFO ]: TraceAbstraction took 58667.88 ms. Allocated memory was 305.1 MB in the beginning and 1.1 GB in the end (delta: 768.6 MB). Free memory was 208.5 MB in the beginning and 416.7 MB in the end (delta: -208.2 MB). Peak memory consumption was 560.4 MB. Max. memory is 3.6 GB. [2018-06-26 18:32:35,870 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.plugins.blockencoding: - StatisticsResult: Initial Icfg 47 locations, 75 edges - StatisticsResult: Encoded RCFG 32 locations, 62 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 305.1 MB. Free memory is still 268.6 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 74.39 ms. Allocated memory is still 305.1 MB. Free memory was 251.5 MB in the beginning and 249.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 64.54 ms. Allocated memory is still 305.1 MB. Free memory was 249.5 MB in the beginning and 247.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 481.74 ms. Allocated memory is still 305.1 MB. Free memory was 247.5 MB in the beginning and 226.5 MB in the end (delta: 21.0 MB). Peak memory consumption was 21.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 511.04 ms. Allocated memory is still 305.1 MB. Free memory was 226.5 MB in the beginning and 208.5 MB in the end (delta: 18.0 MB). Peak memory consumption was 18.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 58667.88 ms. Allocated memory was 305.1 MB in the beginning and 1.1 GB in the end (delta: 768.6 MB). Free memory was 208.5 MB in the beginning and 416.7 MB in the end (delta: -208.2 MB). Peak memory consumption was 560.4 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 (292states) and interpolant automaton (currently 198 states, 26 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 17. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 32 locations, 1 error locations. TIMEOUT Result, 58.6s OverallTime, 18 OverallIterations, 32 TraceHistogramMax, 49.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 2489 SDtfs, 1573 SDslu, 11308 SDs, 0 SdLazy, 59261 SolverSat, 6705 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 34.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1526 GetRequests, 909 SyntacticMatches, 0 SemanticMatches, 616 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 28122 ImplicationChecksByTransitivity, 13.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=292occurred in iteration=17, 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.6s AutomataMinimizationTime, 17 MinimizatonAttempts, 1661 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.3s SatisfiabilityAnalysisTime, 5.5s InterpolantComputationTime, 1723 NumberOfCodeBlocks, 1591 NumberOfCodeBlocksAsserted, 52 NumberOfCheckSat, 1693 ConstructedInterpolants, 0 QuantifiedInterpolants, 271578 SizeOfPredicates, 75 NumberOfNonLiveVariables, 6963 ConjunctsInSsa, 144 ConjunctsInUnsatCore, 30 InterpolantComputations, 13 PerfectInterpolantSequences, 10106/11026 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/McCarthy9103.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-26_18-32-35-882.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/McCarthy9103.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-26_18-32-35-882.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/McCarthy9103.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-26_18-32-35-882.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/McCarthy9103.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-26_18-32-35-882.csv Completed graceful shutdown