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/mochi/array_init.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-62c3406-m [2018-06-26 18:16:08,438 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-26 18:16:08,440 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-26 18:16:08,453 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-26 18:16:08,453 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-26 18:16:08,454 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-26 18:16:08,457 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-26 18:16:08,463 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-26 18:16:08,465 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-26 18:16:08,468 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-26 18:16:08,469 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-26 18:16:08,469 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-26 18:16:08,470 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-26 18:16:08,470 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-26 18:16:08,473 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-26 18:16:08,473 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-26 18:16:08,474 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-26 18:16:08,476 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-26 18:16:08,478 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-26 18:16:08,479 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-26 18:16:08,480 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-26 18:16:08,481 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-26 18:16:08,483 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-26 18:16:08,484 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-26 18:16:08,484 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-26 18:16:08,485 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-26 18:16:08,486 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-26 18:16:08,486 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-26 18:16:08,487 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-26 18:16:08,488 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-26 18:16:08,488 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-26 18:16:08,489 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-26 18:16:08,489 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-06-26 18:16:08,489 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-26 18:16:08,490 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-26 18:16:08,490 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-26 18:16:08,491 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:16:08,504 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-26 18:16:08,504 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-26 18:16:08,505 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-26 18:16:08,505 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-26 18:16:08,506 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-26 18:16:08,506 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-26 18:16:08,506 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-26 18:16:08,506 INFO L133 SettingsManager]: * Use SBE=true [2018-06-26 18:16:08,507 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-26 18:16:08,507 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-26 18:16:08,507 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-26 18:16:08,507 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-26 18:16:08,507 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 18:16:08,508 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-26 18:16:08,508 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-26 18:16:08,508 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-26 18:16:08,508 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-26 18:16:08,508 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-26 18:16:08,509 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-26 18:16:08,509 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-26 18:16:08,509 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-26 18:16:08,511 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-26 18:16:08,511 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-26 18:16:08,552 INFO ]: Repository-Root is: /tmp [2018-06-26 18:16:08,571 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-26 18:16:08,577 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-26 18:16:08,578 INFO ]: Initializing SmtParser... [2018-06-26 18:16:08,579 INFO ]: SmtParser initialized [2018-06-26 18:16:08,579 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/hopv/lia/mochi/array_init.smt2 [2018-06-26 18:16:08,581 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:16:08,674 INFO ]: Executing SMT file /storage/chc-comp/hopv/lia/mochi/array_init.smt2 unknown [2018-06-26 18:16:08,951 INFO ]: Succesfully executed SMT file /storage/chc-comp/hopv/lia/mochi/array_init.smt2 [2018-06-26 18:16:08,956 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-26 18:16:08,964 INFO ]: Walking toolchain with 5 elements. [2018-06-26 18:16:08,965 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-26 18:16:08,965 INFO ]: Initializing ChcToBoogie... [2018-06-26 18:16:08,965 INFO ]: ChcToBoogie initialized [2018-06-26 18:16:08,968 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 06:16:08" (1/1) ... [2018-06-26 18:16:09,031 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:16:09 Unit [2018-06-26 18:16:09,031 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-26 18:16:09,032 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-26 18:16:09,032 INFO ]: Initializing Boogie Preprocessor... [2018-06-26 18:16:09,032 INFO ]: Boogie Preprocessor initialized [2018-06-26 18:16:09,057 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:16:09" (1/1) ... [2018-06-26 18:16:09,057 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:16:09" (1/1) ... [2018-06-26 18:16:09,066 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:16:09" (1/1) ... [2018-06-26 18:16:09,066 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:16:09" (1/1) ... [2018-06-26 18:16:09,070 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:16:09" (1/1) ... [2018-06-26 18:16:09,072 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:16:09" (1/1) ... [2018-06-26 18:16:09,073 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:16:09" (1/1) ... [2018-06-26 18:16:09,076 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-26 18:16:09,076 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-26 18:16:09,076 INFO ]: Initializing RCFGBuilder... [2018-06-26 18:16:09,076 INFO ]: RCFGBuilder initialized [2018-06-26 18:16:09,077 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:16:09" (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:16:09,097 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-26 18:16:09,097 INFO ]: Found specification of procedure gotoProc [2018-06-26 18:16:09,097 INFO ]: Found implementation of procedure gotoProc [2018-06-26 18:16:09,097 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-26 18:16:09,097 INFO ]: Found specification of procedure Ultimate.START [2018-06-26 18:16:09,097 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:16:09,451 INFO ]: Using library mode [2018-06-26 18:16:09,451 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 06:16:09 BoogieIcfgContainer [2018-06-26 18:16:09,451 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-26 18:16:09,452 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-26 18:16:09,452 INFO ]: Initializing BlockEncodingV2... [2018-06-26 18:16:09,453 INFO ]: BlockEncodingV2 initialized [2018-06-26 18:16:09,453 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 06:16:09" (1/1) ... [2018-06-26 18:16:09,465 INFO ]: Initial Icfg 14 locations, 18 edges [2018-06-26 18:16:09,466 INFO ]: Using Remove infeasible edges [2018-06-26 18:16:09,467 INFO ]: Using Maximize final states [2018-06-26 18:16:09,467 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-26 18:16:09,467 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-26 18:16:09,469 INFO ]: Using Remove sink states [2018-06-26 18:16:09,470 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-26 18:16:09,470 INFO ]: Using Use SBE [2018-06-26 18:16:09,495 INFO ]: SBE split 1 edges [2018-06-26 18:16:09,503 INFO ]: Removed 3 edges and 2 locations because of local infeasibility [2018-06-26 18:16:09,505 INFO ]: 0 new accepting states [2018-06-26 18:16:09,653 INFO ]: Removed 15 edges and 4 locations by large block encoding [2018-06-26 18:16:09,655 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 18:16:09,658 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-26 18:16:09,658 INFO ]: 0 new accepting states [2018-06-26 18:16:09,658 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-26 18:16:09,658 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 18:16:09,659 INFO ]: Encoded RCFG 8 locations, 14 edges [2018-06-26 18:16:09,659 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 06:16:09 BasicIcfg [2018-06-26 18:16:09,659 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-26 18:16:09,660 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-26 18:16:09,660 INFO ]: Initializing TraceAbstraction... [2018-06-26 18:16:09,663 INFO ]: TraceAbstraction initialized [2018-06-26 18:16:09,663 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 06:16:08" (1/4) ... [2018-06-26 18:16:09,664 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@234bf0ab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 26.06 06:16:09, skipping insertion in model container [2018-06-26 18:16:09,664 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:16:09" (2/4) ... [2018-06-26 18:16:09,664 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@234bf0ab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.06 06:16:09, skipping insertion in model container [2018-06-26 18:16:09,664 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 06:16:09" (3/4) ... [2018-06-26 18:16:09,664 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@234bf0ab and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 06:16:09, skipping insertion in model container [2018-06-26 18:16:09,665 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 06:16:09" (4/4) ... [2018-06-26 18:16:09,668 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-26 18:16:09,675 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-26 18:16:09,681 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-26 18:16:09,716 INFO ]: Using default assertion order modulation [2018-06-26 18:16:09,717 INFO ]: Interprodecural is true [2018-06-26 18:16:09,717 INFO ]: Hoare is false [2018-06-26 18:16:09,717 INFO ]: Compute interpolants for FPandBP [2018-06-26 18:16:09,717 INFO ]: Backedges is TWOTRACK [2018-06-26 18:16:09,717 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-26 18:16:09,717 INFO ]: Difference is false [2018-06-26 18:16:09,717 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-26 18:16:09,717 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-26 18:16:09,729 INFO ]: Start isEmpty. Operand 8 states. [2018-06-26 18:16:09,737 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 18:16:09,738 INFO ]: Found error trace [2018-06-26 18:16:09,738 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 18:16:09,739 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:09,742 INFO ]: Analyzing trace with hash 1022100921, now seen corresponding path program 1 times [2018-06-26 18:16:09,744 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:09,744 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:09,784 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:09,784 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:09,784 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:09,832 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:09,934 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:16:09,936 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:16:09,936 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-26 18:16:09,937 INFO ]: Interpolant automaton has 4 states [2018-06-26 18:16:09,949 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-26 18:16:09,950 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-26 18:16:09,953 INFO ]: Start difference. First operand 8 states. Second operand 4 states. [2018-06-26 18:16:10,094 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:10,094 INFO ]: Finished difference Result 9 states and 13 transitions. [2018-06-26 18:16:10,095 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-26 18:16:10,096 INFO ]: Start accepts. Automaton has 4 states. Word has length 6 [2018-06-26 18:16:10,097 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:10,111 INFO ]: With dead ends: 9 [2018-06-26 18:16:10,111 INFO ]: Without dead ends: 9 [2018-06-26 18:16:10,113 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-26 18:16:10,140 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-26 18:16:10,157 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 8. [2018-06-26 18:16:10,158 INFO ]: Start removeUnreachable. Operand 8 states. [2018-06-26 18:16:10,159 INFO ]: Finished removeUnreachable. Reduced from 8 states to 8 states and 12 transitions. [2018-06-26 18:16:10,160 INFO ]: Start accepts. Automaton has 8 states and 12 transitions. Word has length 6 [2018-06-26 18:16:10,160 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:10,160 INFO ]: Abstraction has 8 states and 12 transitions. [2018-06-26 18:16:10,160 INFO ]: Interpolant automaton has 4 states. [2018-06-26 18:16:10,160 INFO ]: Start isEmpty. Operand 8 states and 12 transitions. [2018-06-26 18:16:10,160 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 18:16:10,160 INFO ]: Found error trace [2018-06-26 18:16:10,160 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 18:16:10,161 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:10,161 INFO ]: Analyzing trace with hash 1022187411, now seen corresponding path program 1 times [2018-06-26 18:16:10,161 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:10,161 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:10,162 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:10,162 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:10,162 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:10,185 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:10,260 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:16:10,260 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:16:10,261 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-26 18:16:10,262 INFO ]: Interpolant automaton has 4 states [2018-06-26 18:16:10,262 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-26 18:16:10,262 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-26 18:16:10,262 INFO ]: Start difference. First operand 8 states and 12 transitions. Second operand 4 states. [2018-06-26 18:16:10,309 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:10,309 INFO ]: Finished difference Result 11 states and 18 transitions. [2018-06-26 18:16:10,310 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-26 18:16:10,310 INFO ]: Start accepts. Automaton has 4 states. Word has length 6 [2018-06-26 18:16:10,310 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:10,311 INFO ]: With dead ends: 11 [2018-06-26 18:16:10,311 INFO ]: Without dead ends: 11 [2018-06-26 18:16:10,311 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-26 18:16:10,312 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-26 18:16:10,314 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 9. [2018-06-26 18:16:10,314 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-26 18:16:10,314 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 14 transitions. [2018-06-26 18:16:10,314 INFO ]: Start accepts. Automaton has 9 states and 14 transitions. Word has length 6 [2018-06-26 18:16:10,314 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:10,315 INFO ]: Abstraction has 9 states and 14 transitions. [2018-06-26 18:16:10,315 INFO ]: Interpolant automaton has 4 states. [2018-06-26 18:16:10,315 INFO ]: Start isEmpty. Operand 9 states and 14 transitions. [2018-06-26 18:16:10,315 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-26 18:16:10,315 INFO ]: Found error trace [2018-06-26 18:16:10,315 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:10,315 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:10,315 INFO ]: Analyzing trace with hash 1622959974, now seen corresponding path program 1 times [2018-06-26 18:16:10,315 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:10,315 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:10,316 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:10,316 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:10,316 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:10,333 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:10,470 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:16:10,471 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:16:10,471 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-26 18:16:10,471 INFO ]: Interpolant automaton has 4 states [2018-06-26 18:16:10,471 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-26 18:16:10,471 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-26 18:16:10,471 INFO ]: Start difference. First operand 9 states and 14 transitions. Second operand 4 states. [2018-06-26 18:16:10,538 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:10,538 INFO ]: Finished difference Result 14 states and 24 transitions. [2018-06-26 18:16:10,538 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-26 18:16:10,538 INFO ]: Start accepts. Automaton has 4 states. Word has length 7 [2018-06-26 18:16:10,539 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:10,539 INFO ]: With dead ends: 14 [2018-06-26 18:16:10,539 INFO ]: Without dead ends: 14 [2018-06-26 18:16:10,539 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-26 18:16:10,539 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-26 18:16:10,541 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 11. [2018-06-26 18:16:10,541 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-26 18:16:10,541 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 17 transitions. [2018-06-26 18:16:10,542 INFO ]: Start accepts. Automaton has 11 states and 17 transitions. Word has length 7 [2018-06-26 18:16:10,542 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:10,542 INFO ]: Abstraction has 11 states and 17 transitions. [2018-06-26 18:16:10,542 INFO ]: Interpolant automaton has 4 states. [2018-06-26 18:16:10,542 INFO ]: Start isEmpty. Operand 11 states and 17 transitions. [2018-06-26 18:16:10,542 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-26 18:16:10,542 INFO ]: Found error trace [2018-06-26 18:16:10,542 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:10,542 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:10,542 INFO ]: Analyzing trace with hash 1622990726, now seen corresponding path program 1 times [2018-06-26 18:16:10,542 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:10,542 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:10,543 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:10,543 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:10,543 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:10,559 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:10,641 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:10,641 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:10,641 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:16:10,648 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:10,692 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:10,700 INFO ]: Computing forward predicates... [2018-06-26 18:16:10,755 INFO ]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:16:10,777 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 18:16:10,777 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [5] total 6 [2018-06-26 18:16:10,778 INFO ]: Interpolant automaton has 6 states [2018-06-26 18:16:10,778 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-26 18:16:10,778 INFO ]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-06-26 18:16:10,778 INFO ]: Start difference. First operand 11 states and 17 transitions. Second operand 6 states. [2018-06-26 18:16:10,944 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:10,944 INFO ]: Finished difference Result 10 states and 14 transitions. [2018-06-26 18:16:10,944 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-26 18:16:10,945 INFO ]: Start accepts. Automaton has 6 states. Word has length 7 [2018-06-26 18:16:10,945 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:10,945 INFO ]: With dead ends: 10 [2018-06-26 18:16:10,945 INFO ]: Without dead ends: 10 [2018-06-26 18:16:10,945 INFO ]: 0 DeclaredPredicates, 13 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-06-26 18:16:10,945 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-26 18:16:10,946 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 9. [2018-06-26 18:16:10,946 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-26 18:16:10,947 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 12 transitions. [2018-06-26 18:16:10,947 INFO ]: Start accepts. Automaton has 9 states and 12 transitions. Word has length 7 [2018-06-26 18:16:10,947 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:10,947 INFO ]: Abstraction has 9 states and 12 transitions. [2018-06-26 18:16:10,947 INFO ]: Interpolant automaton has 6 states. [2018-06-26 18:16:10,947 INFO ]: Start isEmpty. Operand 9 states and 12 transitions. [2018-06-26 18:16:10,947 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-26 18:16:10,947 INFO ]: Found error trace [2018-06-26 18:16:10,947 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:10,947 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:10,947 INFO ]: Analyzing trace with hash -1944549558, now seen corresponding path program 1 times [2018-06-26 18:16:10,947 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:10,947 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:10,948 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:10,948 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:10,948 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:10,965 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:11,075 INFO ]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:16:11,075 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:16:11,075 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-06-26 18:16:11,075 INFO ]: Interpolant automaton has 5 states [2018-06-26 18:16:11,075 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 18:16:11,075 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-26 18:16:11,075 INFO ]: Start difference. First operand 9 states and 12 transitions. Second operand 5 states. [2018-06-26 18:16:11,249 WARN ]: Spent 112.00 ms on a formula simplification that was a NOOP. DAG size: 8 [2018-06-26 18:16:11,325 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:11,325 INFO ]: Finished difference Result 9 states and 11 transitions. [2018-06-26 18:16:11,326 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-26 18:16:11,326 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-26 18:16:11,326 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:11,326 INFO ]: With dead ends: 9 [2018-06-26 18:16:11,326 INFO ]: Without dead ends: 9 [2018-06-26 18:16:11,326 INFO ]: 0 DeclaredPredicates, 8 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-06-26 18:16:11,326 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-26 18:16:11,327 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-26 18:16:11,327 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-26 18:16:11,328 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 11 transitions. [2018-06-26 18:16:11,328 INFO ]: Start accepts. Automaton has 9 states and 11 transitions. Word has length 8 [2018-06-26 18:16:11,328 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:11,328 INFO ]: Abstraction has 9 states and 11 transitions. [2018-06-26 18:16:11,328 INFO ]: Interpolant automaton has 5 states. [2018-06-26 18:16:11,328 INFO ]: Start isEmpty. Operand 9 states and 11 transitions. [2018-06-26 18:16:11,328 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-26 18:16:11,328 INFO ]: Found error trace [2018-06-26 18:16:11,328 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:11,328 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:11,328 INFO ]: Analyzing trace with hash -1944547636, now seen corresponding path program 1 times [2018-06-26 18:16:11,328 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:11,328 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:11,329 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:11,329 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:11,329 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:11,352 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:11,419 INFO ]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:16:11,419 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:16:11,420 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-06-26 18:16:11,420 INFO ]: Interpolant automaton has 5 states [2018-06-26 18:16:11,420 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 18:16:11,420 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-26 18:16:11,420 INFO ]: Start difference. First operand 9 states and 11 transitions. Second operand 5 states. [2018-06-26 18:16:11,529 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:11,529 INFO ]: Finished difference Result 9 states and 10 transitions. [2018-06-26 18:16:11,529 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-26 18:16:11,529 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-26 18:16:11,529 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:11,530 INFO ]: With dead ends: 9 [2018-06-26 18:16:11,530 INFO ]: Without dead ends: 9 [2018-06-26 18:16:11,530 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:16:11,530 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-26 18:16:11,531 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-26 18:16:11,531 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-26 18:16:11,531 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 10 transitions. [2018-06-26 18:16:11,532 INFO ]: Start accepts. Automaton has 9 states and 10 transitions. Word has length 8 [2018-06-26 18:16:11,532 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:11,532 INFO ]: Abstraction has 9 states and 10 transitions. [2018-06-26 18:16:11,532 INFO ]: Interpolant automaton has 5 states. [2018-06-26 18:16:11,532 INFO ]: Start isEmpty. Operand 9 states and 10 transitions. [2018-06-26 18:16:11,532 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-26 18:16:11,532 INFO ]: Found error trace [2018-06-26 18:16:11,532 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:11,532 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:11,532 INFO ]: Analyzing trace with hash -1944546675, now seen corresponding path program 1 times [2018-06-26 18:16:11,532 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:11,532 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:11,533 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:11,533 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:11,533 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:11,549 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:11,791 INFO ]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:16:11,791 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:16:11,791 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-06-26 18:16:11,791 INFO ]: Interpolant automaton has 5 states [2018-06-26 18:16:11,791 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 18:16:11,791 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-26 18:16:11,791 INFO ]: Start difference. First operand 9 states and 10 transitions. Second operand 5 states. [2018-06-26 18:16:11,993 WARN ]: Spent 184.00 ms on a formula simplification that was a NOOP. DAG size: 22 [2018-06-26 18:16:12,153 WARN ]: Spent 103.00 ms on a formula simplification that was a NOOP. DAG size: 29 [2018-06-26 18:16:12,184 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:12,184 INFO ]: Finished difference Result 11 states and 12 transitions. [2018-06-26 18:16:12,185 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-26 18:16:12,185 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-26 18:16:12,185 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:12,186 INFO ]: With dead ends: 11 [2018-06-26 18:16:12,186 INFO ]: Without dead ends: 10 [2018-06-26 18:16:12,186 INFO ]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-06-26 18:16:12,186 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-26 18:16:12,187 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-26 18:16:12,187 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-26 18:16:12,187 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 11 transitions. [2018-06-26 18:16:12,187 INFO ]: Start accepts. Automaton has 10 states and 11 transitions. Word has length 8 [2018-06-26 18:16:12,187 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:12,187 INFO ]: Abstraction has 10 states and 11 transitions. [2018-06-26 18:16:12,187 INFO ]: Interpolant automaton has 5 states. [2018-06-26 18:16:12,187 INFO ]: Start isEmpty. Operand 10 states and 11 transitions. [2018-06-26 18:16:12,188 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-26 18:16:12,188 INFO ]: Found error trace [2018-06-26 18:16:12,188 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:12,188 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:12,188 INFO ]: Analyzing trace with hash -150616654, now seen corresponding path program 1 times [2018-06-26 18:16:12,188 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:12,188 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:12,188 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:12,188 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:12,188 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:12,210 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:12,371 INFO ]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:12,371 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:12,371 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:16:12,377 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:12,416 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:12,419 INFO ]: Computing forward predicates... [2018-06-26 18:16:12,492 INFO ]: Checked inductivity of 2 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:12,511 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:12,511 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-26 18:16:12,512 INFO ]: Interpolant automaton has 7 states [2018-06-26 18:16:12,512 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-26 18:16:12,512 INFO ]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-06-26 18:16:12,512 INFO ]: Start difference. First operand 10 states and 11 transitions. Second operand 7 states. [2018-06-26 18:16:12,560 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:12,560 INFO ]: Finished difference Result 13 states and 15 transitions. [2018-06-26 18:16:12,561 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-26 18:16:12,561 INFO ]: Start accepts. Automaton has 7 states. Word has length 9 [2018-06-26 18:16:12,561 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:12,561 INFO ]: With dead ends: 13 [2018-06-26 18:16:12,561 INFO ]: Without dead ends: 11 [2018-06-26 18:16:12,561 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2018-06-26 18:16:12,561 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-26 18:16:12,563 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 11. [2018-06-26 18:16:12,563 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-26 18:16:12,564 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 12 transitions. [2018-06-26 18:16:12,564 INFO ]: Start accepts. Automaton has 11 states and 12 transitions. Word has length 9 [2018-06-26 18:16:12,564 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:12,564 INFO ]: Abstraction has 11 states and 12 transitions. [2018-06-26 18:16:12,564 INFO ]: Interpolant automaton has 7 states. [2018-06-26 18:16:12,564 INFO ]: Start isEmpty. Operand 11 states and 12 transitions. [2018-06-26 18:16:12,564 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-26 18:16:12,564 INFO ]: Found error trace [2018-06-26 18:16:12,564 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:12,564 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:12,565 INFO ]: Analyzing trace with hash -1143374698, now seen corresponding path program 2 times [2018-06-26 18:16:12,565 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:12,565 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:12,565 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:12,565 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:12,565 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:12,586 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:12,781 INFO ]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:12,781 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:12,781 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:16:12,787 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 18:16:12,822 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 18:16:12,822 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:12,825 INFO ]: Computing forward predicates... [2018-06-26 18:16:13,189 INFO ]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:13,214 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:13,214 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 13 [2018-06-26 18:16:13,214 INFO ]: Interpolant automaton has 13 states [2018-06-26 18:16:13,214 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-26 18:16:13,215 INFO ]: CoverageRelationStatistics Valid=38, Invalid=118, Unknown=0, NotChecked=0, Total=156 [2018-06-26 18:16:13,215 INFO ]: Start difference. First operand 11 states and 12 transitions. Second operand 13 states. [2018-06-26 18:16:13,328 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:13,328 INFO ]: Finished difference Result 14 states and 16 transitions. [2018-06-26 18:16:13,328 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-26 18:16:13,328 INFO ]: Start accepts. Automaton has 13 states. Word has length 10 [2018-06-26 18:16:13,328 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:13,328 INFO ]: With dead ends: 14 [2018-06-26 18:16:13,328 INFO ]: Without dead ends: 12 [2018-06-26 18:16:13,329 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=62, Invalid=178, Unknown=0, NotChecked=0, Total=240 [2018-06-26 18:16:13,329 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-26 18:16:13,330 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-26 18:16:13,330 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-26 18:16:13,330 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 13 transitions. [2018-06-26 18:16:13,330 INFO ]: Start accepts. Automaton has 12 states and 13 transitions. Word has length 10 [2018-06-26 18:16:13,330 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:13,330 INFO ]: Abstraction has 12 states and 13 transitions. [2018-06-26 18:16:13,330 INFO ]: Interpolant automaton has 13 states. [2018-06-26 18:16:13,330 INFO ]: Start isEmpty. Operand 12 states and 13 transitions. [2018-06-26 18:16:13,330 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-26 18:16:13,330 INFO ]: Found error trace [2018-06-26 18:16:13,331 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:13,331 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:13,331 INFO ]: Analyzing trace with hash -1854102990, now seen corresponding path program 3 times [2018-06-26 18:16:13,331 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:13,331 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:13,331 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:13,332 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:13,332 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:13,346 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:13,700 INFO ]: Checked inductivity of 7 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:13,700 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:13,700 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:16:13,719 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 18:16:13,743 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-26 18:16:13,743 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:13,745 INFO ]: Computing forward predicates... [2018-06-26 18:16:13,768 INFO ]: Checked inductivity of 7 backedges. 6 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:13,789 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:13,789 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2018-06-26 18:16:13,790 INFO ]: Interpolant automaton has 9 states [2018-06-26 18:16:13,790 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-26 18:16:13,790 INFO ]: CoverageRelationStatistics Valid=24, Invalid=48, Unknown=0, NotChecked=0, Total=72 [2018-06-26 18:16:13,790 INFO ]: Start difference. First operand 12 states and 13 transitions. Second operand 9 states. [2018-06-26 18:16:13,823 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:13,823 INFO ]: Finished difference Result 13 states and 14 transitions. [2018-06-26 18:16:13,823 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-26 18:16:13,823 INFO ]: Start accepts. Automaton has 9 states. Word has length 11 [2018-06-26 18:16:13,823 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:13,823 INFO ]: With dead ends: 13 [2018-06-26 18:16:13,823 INFO ]: Without dead ends: 13 [2018-06-26 18:16:13,823 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 11 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=42, Invalid=68, Unknown=0, NotChecked=0, Total=110 [2018-06-26 18:16:13,823 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-26 18:16:13,824 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-26 18:16:13,824 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-26 18:16:13,825 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 14 transitions. [2018-06-26 18:16:13,825 INFO ]: Start accepts. Automaton has 13 states and 14 transitions. Word has length 11 [2018-06-26 18:16:13,825 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:13,825 INFO ]: Abstraction has 13 states and 14 transitions. [2018-06-26 18:16:13,825 INFO ]: Interpolant automaton has 9 states. [2018-06-26 18:16:13,825 INFO ]: Start isEmpty. Operand 13 states and 14 transitions. [2018-06-26 18:16:13,825 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-26 18:16:13,825 INFO ]: Found error trace [2018-06-26 18:16:13,825 INFO ]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:13,825 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:13,825 INFO ]: Analyzing trace with hash -1641829715, now seen corresponding path program 4 times [2018-06-26 18:16:13,826 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:13,826 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:13,826 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:13,826 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:13,826 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:13,850 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:14,216 INFO ]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:14,216 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:14,216 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:14,223 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 18:16:14,249 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 18:16:14,249 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:14,252 INFO ]: Computing forward predicates... [2018-06-26 18:16:14,451 INFO ]: Checked inductivity of 9 backedges. 3 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:14,472 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:14,521 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 9] total 17 [2018-06-26 18:16:14,521 INFO ]: Interpolant automaton has 17 states [2018-06-26 18:16:14,521 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-26 18:16:14,521 INFO ]: CoverageRelationStatistics Valid=61, Invalid=211, Unknown=0, NotChecked=0, Total=272 [2018-06-26 18:16:14,522 INFO ]: Start difference. First operand 13 states and 14 transitions. Second operand 17 states. [2018-06-26 18:16:14,728 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:14,728 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-26 18:16:14,729 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-26 18:16:14,729 INFO ]: Start accepts. Automaton has 17 states. Word has length 12 [2018-06-26 18:16:14,729 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:14,729 INFO ]: With dead ends: 17 [2018-06-26 18:16:14,729 INFO ]: Without dead ends: 14 [2018-06-26 18:16:14,729 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 89 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=118, Invalid=388, Unknown=0, NotChecked=0, Total=506 [2018-06-26 18:16:14,729 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-26 18:16:14,731 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-26 18:16:14,731 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-26 18:16:14,731 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 15 transitions. [2018-06-26 18:16:14,731 INFO ]: Start accepts. Automaton has 14 states and 15 transitions. Word has length 12 [2018-06-26 18:16:14,731 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:14,731 INFO ]: Abstraction has 14 states and 15 transitions. [2018-06-26 18:16:14,731 INFO ]: Interpolant automaton has 17 states. [2018-06-26 18:16:14,731 INFO ]: Start isEmpty. Operand 14 states and 15 transitions. [2018-06-26 18:16:14,732 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-26 18:16:14,732 INFO ]: Found error trace [2018-06-26 18:16:14,732 INFO ]: trace histogram [4, 2, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:14,732 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:14,732 INFO ]: Analyzing trace with hash -1751918263, now seen corresponding path program 5 times [2018-06-26 18:16:14,732 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:14,732 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:14,732 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:14,732 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:14,732 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:14,746 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:14,850 INFO ]: Checked inductivity of 13 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:14,850 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:14,850 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:16:14,867 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-26 18:16:14,906 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2018-06-26 18:16:14,906 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:14,908 INFO ]: Computing forward predicates... [2018-06-26 18:16:14,936 INFO ]: Checked inductivity of 13 backedges. 10 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:14,957 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:14,957 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 11 [2018-06-26 18:16:14,957 INFO ]: Interpolant automaton has 11 states [2018-06-26 18:16:14,957 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-26 18:16:14,958 INFO ]: CoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2018-06-26 18:16:14,958 INFO ]: Start difference. First operand 14 states and 15 transitions. Second operand 11 states. [2018-06-26 18:16:15,031 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:15,031 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-26 18:16:15,032 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-26 18:16:15,032 INFO ]: Start accepts. Automaton has 11 states. Word has length 13 [2018-06-26 18:16:15,032 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:15,032 INFO ]: With dead ends: 15 [2018-06-26 18:16:15,032 INFO ]: Without dead ends: 15 [2018-06-26 18:16:15,033 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 13 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=68, Invalid=114, Unknown=0, NotChecked=0, Total=182 [2018-06-26 18:16:15,033 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-26 18:16:15,034 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-26 18:16:15,034 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-26 18:16:15,034 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 16 transitions. [2018-06-26 18:16:15,034 INFO ]: Start accepts. Automaton has 15 states and 16 transitions. Word has length 13 [2018-06-26 18:16:15,034 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:15,034 INFO ]: Abstraction has 15 states and 16 transitions. [2018-06-26 18:16:15,034 INFO ]: Interpolant automaton has 11 states. [2018-06-26 18:16:15,034 INFO ]: Start isEmpty. Operand 15 states and 16 transitions. [2018-06-26 18:16:15,035 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-26 18:16:15,035 INFO ]: Found error trace [2018-06-26 18:16:15,035 INFO ]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:15,035 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:15,035 INFO ]: Analyzing trace with hash 1525896822, now seen corresponding path program 6 times [2018-06-26 18:16:15,035 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:15,035 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:15,036 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:15,036 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:15,036 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:15,074 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:15,521 WARN ]: Spent 160.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 14 [2018-06-26 18:16:15,794 INFO ]: Checked inductivity of 16 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:15,794 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:15,794 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:16:15,807 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-26 18:16:15,864 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2018-06-26 18:16:15,864 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:15,867 INFO ]: Computing forward predicates... [2018-06-26 18:16:16,202 INFO ]: Checked inductivity of 16 backedges. 3 proven. 13 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:16,221 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:16,221 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 22 [2018-06-26 18:16:16,221 INFO ]: Interpolant automaton has 22 states [2018-06-26 18:16:16,221 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-26 18:16:16,222 INFO ]: CoverageRelationStatistics Valid=92, Invalid=370, Unknown=0, NotChecked=0, Total=462 [2018-06-26 18:16:16,222 INFO ]: Start difference. First operand 15 states and 16 transitions. Second operand 22 states. [2018-06-26 18:16:16,600 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:16,600 INFO ]: Finished difference Result 21 states and 23 transitions. [2018-06-26 18:16:16,601 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-26 18:16:16,601 INFO ]: Start accepts. Automaton has 22 states. Word has length 14 [2018-06-26 18:16:16,601 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:16,601 INFO ]: With dead ends: 21 [2018-06-26 18:16:16,601 INFO ]: Without dead ends: 16 [2018-06-26 18:16:16,602 INFO ]: 0 DeclaredPredicates, 33 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 164 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=188, Invalid=682, Unknown=0, NotChecked=0, Total=870 [2018-06-26 18:16:16,602 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-26 18:16:16,603 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-06-26 18:16:16,603 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-26 18:16:16,603 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 17 transitions. [2018-06-26 18:16:16,603 INFO ]: Start accepts. Automaton has 16 states and 17 transitions. Word has length 14 [2018-06-26 18:16:16,603 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:16,603 INFO ]: Abstraction has 16 states and 17 transitions. [2018-06-26 18:16:16,603 INFO ]: Interpolant automaton has 22 states. [2018-06-26 18:16:16,604 INFO ]: Start isEmpty. Operand 16 states and 17 transitions. [2018-06-26 18:16:16,604 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-26 18:16:16,604 INFO ]: Found error trace [2018-06-26 18:16:16,604 INFO ]: trace histogram [5, 3, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:16,604 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:16,604 INFO ]: Analyzing trace with hash -1189982702, now seen corresponding path program 7 times [2018-06-26 18:16:16,604 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:16,604 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:16,605 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:16,605 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:16,605 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:16,620 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:16,833 INFO ]: Checked inductivity of 21 backedges. 15 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:16,833 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:16,833 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:16:16,841 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:16,907 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:16,910 INFO ]: Computing forward predicates... [2018-06-26 18:16:17,000 INFO ]: Checked inductivity of 21 backedges. 15 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:17,020 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:17,020 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 13 [2018-06-26 18:16:17,020 INFO ]: Interpolant automaton has 13 states [2018-06-26 18:16:17,020 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-26 18:16:17,020 INFO ]: CoverageRelationStatistics Valid=48, Invalid=108, Unknown=0, NotChecked=0, Total=156 [2018-06-26 18:16:17,020 INFO ]: Start difference. First operand 16 states and 17 transitions. Second operand 13 states. [2018-06-26 18:16:17,071 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:17,071 INFO ]: Finished difference Result 17 states and 18 transitions. [2018-06-26 18:16:17,071 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-26 18:16:17,071 INFO ]: Start accepts. Automaton has 13 states. Word has length 15 [2018-06-26 18:16:17,071 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:17,071 INFO ]: With dead ends: 17 [2018-06-26 18:16:17,071 INFO ]: Without dead ends: 17 [2018-06-26 18:16:17,072 INFO ]: 0 DeclaredPredicates, 30 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=100, Invalid=172, Unknown=0, NotChecked=0, Total=272 [2018-06-26 18:16:17,072 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-26 18:16:17,073 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-26 18:16:17,073 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-26 18:16:17,073 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 18 transitions. [2018-06-26 18:16:17,073 INFO ]: Start accepts. Automaton has 17 states and 18 transitions. Word has length 15 [2018-06-26 18:16:17,074 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:17,074 INFO ]: Abstraction has 17 states and 18 transitions. [2018-06-26 18:16:17,074 INFO ]: Interpolant automaton has 13 states. [2018-06-26 18:16:17,074 INFO ]: Start isEmpty. Operand 17 states and 18 transitions. [2018-06-26 18:16:17,074 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-26 18:16:17,074 INFO ]: Found error trace [2018-06-26 18:16:17,074 INFO ]: trace histogram [5, 4, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:17,074 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:17,074 INFO ]: Analyzing trace with hash 1766030029, now seen corresponding path program 8 times [2018-06-26 18:16:17,074 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:17,074 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:17,075 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:17,075 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:17,075 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:17,118 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:17,491 WARN ]: Spent 238.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 10 [2018-06-26 18:16:17,981 INFO ]: Checked inductivity of 25 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:17,981 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:17,981 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-26 18:16:17,996 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:18,033 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 18:16:18,033 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:18,037 INFO ]: Computing forward predicates... [2018-06-26 18:16:18,439 INFO ]: Checked inductivity of 25 backedges. 6 proven. 19 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:18,458 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:18,458 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 25 [2018-06-26 18:16:18,458 INFO ]: Interpolant automaton has 25 states [2018-06-26 18:16:18,458 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-26 18:16:18,458 INFO ]: CoverageRelationStatistics Valid=113, Invalid=487, Unknown=0, NotChecked=0, Total=600 [2018-06-26 18:16:18,459 INFO ]: Start difference. First operand 17 states and 18 transitions. Second operand 25 states. [2018-06-26 18:16:18,746 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:18,746 INFO ]: Finished difference Result 23 states and 25 transitions. [2018-06-26 18:16:18,747 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-26 18:16:18,747 INFO ]: Start accepts. Automaton has 25 states. Word has length 16 [2018-06-26 18:16:18,747 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:18,747 INFO ]: With dead ends: 23 [2018-06-26 18:16:18,747 INFO ]: Without dead ends: 18 [2018-06-26 18:16:18,748 INFO ]: 0 DeclaredPredicates, 39 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 204 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=236, Invalid=954, Unknown=0, NotChecked=0, Total=1190 [2018-06-26 18:16:18,748 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-26 18:16:18,749 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 18. [2018-06-26 18:16:18,749 INFO ]: Start removeUnreachable. Operand 18 states. [2018-06-26 18:16:18,749 INFO ]: Finished removeUnreachable. Reduced from 18 states to 18 states and 19 transitions. [2018-06-26 18:16:18,749 INFO ]: Start accepts. Automaton has 18 states and 19 transitions. Word has length 16 [2018-06-26 18:16:18,750 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:18,750 INFO ]: Abstraction has 18 states and 19 transitions. [2018-06-26 18:16:18,750 INFO ]: Interpolant automaton has 25 states. [2018-06-26 18:16:18,750 INFO ]: Start isEmpty. Operand 18 states and 19 transitions. [2018-06-26 18:16:18,750 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-26 18:16:18,750 INFO ]: Found error trace [2018-06-26 18:16:18,750 INFO ]: trace histogram [6, 4, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:18,750 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:18,750 INFO ]: Analyzing trace with hash -1149043863, now seen corresponding path program 9 times [2018-06-26 18:16:18,750 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:18,750 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:18,751 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:18,751 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:18,751 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:18,766 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:18,941 INFO ]: Checked inductivity of 31 backedges. 21 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:18,941 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:18,941 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:16:18,947 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 18:16:18,986 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-26 18:16:18,986 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:18,989 INFO ]: Computing forward predicates... [2018-06-26 18:16:19,035 INFO ]: Checked inductivity of 31 backedges. 21 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:19,054 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:19,054 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 15 [2018-06-26 18:16:19,055 INFO ]: Interpolant automaton has 15 states [2018-06-26 18:16:19,055 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-26 18:16:19,055 INFO ]: CoverageRelationStatistics Valid=63, Invalid=147, Unknown=0, NotChecked=0, Total=210 [2018-06-26 18:16:19,055 INFO ]: Start difference. First operand 18 states and 19 transitions. Second operand 15 states. [2018-06-26 18:16:19,112 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:19,112 INFO ]: Finished difference Result 19 states and 20 transitions. [2018-06-26 18:16:19,112 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-26 18:16:19,112 INFO ]: Start accepts. Automaton has 15 states. Word has length 17 [2018-06-26 18:16:19,112 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:19,112 INFO ]: With dead ends: 19 [2018-06-26 18:16:19,112 INFO ]: Without dead ends: 19 [2018-06-26 18:16:19,113 INFO ]: 0 DeclaredPredicates, 35 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=138, Invalid=242, Unknown=0, NotChecked=0, Total=380 [2018-06-26 18:16:19,113 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-26 18:16:19,114 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-26 18:16:19,114 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-26 18:16:19,115 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 20 transitions. [2018-06-26 18:16:19,115 INFO ]: Start accepts. Automaton has 19 states and 20 transitions. Word has length 17 [2018-06-26 18:16:19,115 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:19,115 INFO ]: Abstraction has 19 states and 20 transitions. [2018-06-26 18:16:19,115 INFO ]: Interpolant automaton has 15 states. [2018-06-26 18:16:19,115 INFO ]: Start isEmpty. Operand 19 states and 20 transitions. [2018-06-26 18:16:19,115 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-26 18:16:19,115 INFO ]: Found error trace [2018-06-26 18:16:19,115 INFO ]: trace histogram [6, 5, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:19,115 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:19,115 INFO ]: Analyzing trace with hash -1259833258, now seen corresponding path program 10 times [2018-06-26 18:16:19,115 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:19,115 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:19,116 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:19,116 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:19,116 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:19,143 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:19,487 WARN ]: Spent 232.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 10 [2018-06-26 18:16:19,844 WARN ]: Spent 307.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 13 [2018-06-26 18:16:20,268 WARN ]: Spent 353.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 14 [2018-06-26 18:16:20,583 WARN ]: Spent 215.00 ms on a formula simplification. DAG size of input: 39 DAG size of output: 14 [2018-06-26 18:16:21,010 WARN ]: Spent 141.00 ms on a formula simplification. DAG size of input: 47 DAG size of output: 19 [2018-06-26 18:16:21,828 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:21,828 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:21,828 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:16:21,835 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 18:16:21,875 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 18:16:21,875 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:21,880 INFO ]: Computing forward predicates... [2018-06-26 18:16:22,269 INFO ]: Checked inductivity of 36 backedges. 15 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:22,288 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:22,288 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 15] total 29 [2018-06-26 18:16:22,288 INFO ]: Interpolant automaton has 29 states [2018-06-26 18:16:22,289 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-26 18:16:22,289 INFO ]: CoverageRelationStatistics Valid=151, Invalid=661, Unknown=0, NotChecked=0, Total=812 [2018-06-26 18:16:22,289 INFO ]: Start difference. First operand 19 states and 20 transitions. Second operand 29 states. [2018-06-26 18:16:22,657 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:22,657 INFO ]: Finished difference Result 26 states and 27 transitions. [2018-06-26 18:16:22,658 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-26 18:16:22,658 INFO ]: Start accepts. Automaton has 29 states. Word has length 18 [2018-06-26 18:16:22,658 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:22,658 INFO ]: With dead ends: 26 [2018-06-26 18:16:22,658 INFO ]: Without dead ends: 20 [2018-06-26 18:16:22,659 INFO ]: 0 DeclaredPredicates, 45 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 281 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=315, Invalid=1325, Unknown=0, NotChecked=0, Total=1640 [2018-06-26 18:16:22,659 INFO ]: Start minimizeSevpa. Operand 20 states. [2018-06-26 18:16:22,660 INFO ]: Finished minimizeSevpa. Reduced states from 20 to 20. [2018-06-26 18:16:22,660 INFO ]: Start removeUnreachable. Operand 20 states. [2018-06-26 18:16:22,661 INFO ]: Finished removeUnreachable. Reduced from 20 states to 20 states and 21 transitions. [2018-06-26 18:16:22,661 INFO ]: Start accepts. Automaton has 20 states and 21 transitions. Word has length 18 [2018-06-26 18:16:22,661 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:22,661 INFO ]: Abstraction has 20 states and 21 transitions. [2018-06-26 18:16:22,661 INFO ]: Interpolant automaton has 29 states. [2018-06-26 18:16:22,661 INFO ]: Start isEmpty. Operand 20 states and 21 transitions. [2018-06-26 18:16:22,661 INFO ]: Finished isEmpty. Found accepting run of length 20 [2018-06-26 18:16:22,661 INFO ]: Found error trace [2018-06-26 18:16:22,661 INFO ]: trace histogram [7, 5, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:22,661 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:22,661 INFO ]: Analyzing trace with hash 1967800818, now seen corresponding path program 11 times [2018-06-26 18:16:22,661 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:22,661 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:22,662 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:22,662 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:22,662 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:22,690 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:23,473 INFO ]: Checked inductivity of 43 backedges. 28 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:23,473 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:23,473 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:16:23,479 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-26 18:16:23,528 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2018-06-26 18:16:23,528 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:23,531 INFO ]: Computing forward predicates... [2018-06-26 18:16:23,591 INFO ]: Checked inductivity of 43 backedges. 28 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:23,610 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:23,610 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 17 [2018-06-26 18:16:23,610 INFO ]: Interpolant automaton has 17 states [2018-06-26 18:16:23,611 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-26 18:16:23,611 INFO ]: CoverageRelationStatistics Valid=80, Invalid=192, Unknown=0, NotChecked=0, Total=272 [2018-06-26 18:16:23,611 INFO ]: Start difference. First operand 20 states and 21 transitions. Second operand 17 states. [2018-06-26 18:16:23,691 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:23,691 INFO ]: Finished difference Result 21 states and 22 transitions. [2018-06-26 18:16:23,691 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-06-26 18:16:23,691 INFO ]: Start accepts. Automaton has 17 states. Word has length 19 [2018-06-26 18:16:23,691 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:23,691 INFO ]: With dead ends: 21 [2018-06-26 18:16:23,691 INFO ]: Without dead ends: 21 [2018-06-26 18:16:23,692 INFO ]: 0 DeclaredPredicates, 40 GetRequests, 19 SyntacticMatches, 0 SemanticMatches, 21 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 64 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=182, Invalid=324, Unknown=0, NotChecked=0, Total=506 [2018-06-26 18:16:23,692 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-26 18:16:23,693 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-26 18:16:23,693 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-26 18:16:23,694 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 22 transitions. [2018-06-26 18:16:23,694 INFO ]: Start accepts. Automaton has 21 states and 22 transitions. Word has length 19 [2018-06-26 18:16:23,694 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:23,694 INFO ]: Abstraction has 21 states and 22 transitions. [2018-06-26 18:16:23,694 INFO ]: Interpolant automaton has 17 states. [2018-06-26 18:16:23,694 INFO ]: Start isEmpty. Operand 21 states and 22 transitions. [2018-06-26 18:16:23,694 INFO ]: Finished isEmpty. Found accepting run of length 21 [2018-06-26 18:16:23,694 INFO ]: Found error trace [2018-06-26 18:16:23,694 INFO ]: trace histogram [7, 6, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:23,695 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:23,695 INFO ]: Analyzing trace with hash 873071341, now seen corresponding path program 12 times [2018-06-26 18:16:23,695 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:23,695 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:23,695 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:23,695 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:23,695 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:23,724 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:24,125 WARN ]: Spent 221.00 ms on a formula simplification. DAG size of input: 19 DAG size of output: 10 [2018-06-26 18:16:25,637 WARN ]: Spent 301.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 15 [2018-06-26 18:16:25,882 INFO ]: Checked inductivity of 49 backedges. 1 proven. 48 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:25,883 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:25,883 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:25,888 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-26 18:16:25,937 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2018-06-26 18:16:25,937 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:25,941 INFO ]: Computing forward predicates... [2018-06-26 18:16:26,238 INFO ]: Checked inductivity of 49 backedges. 11 proven. 38 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:26,257 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:26,257 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 34 [2018-06-26 18:16:26,258 INFO ]: Interpolant automaton has 34 states [2018-06-26 18:16:26,258 INFO ]: Constructing interpolant automaton starting with 34 interpolants. [2018-06-26 18:16:26,258 INFO ]: CoverageRelationStatistics Valid=211, Invalid=911, Unknown=0, NotChecked=0, Total=1122 [2018-06-26 18:16:26,258 INFO ]: Start difference. First operand 21 states and 22 transitions. Second operand 34 states. [2018-06-26 18:16:26,721 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:26,721 INFO ]: Finished difference Result 30 states and 32 transitions. [2018-06-26 18:16:26,721 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-06-26 18:16:26,721 INFO ]: Start accepts. Automaton has 34 states. Word has length 20 [2018-06-26 18:16:26,721 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:26,722 INFO ]: With dead ends: 30 [2018-06-26 18:16:26,722 INFO ]: Without dead ends: 22 [2018-06-26 18:16:26,722 INFO ]: 0 DeclaredPredicates, 48 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 478 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=398, Invalid=1582, Unknown=0, NotChecked=0, Total=1980 [2018-06-26 18:16:26,722 INFO ]: Start minimizeSevpa. Operand 22 states. [2018-06-26 18:16:26,724 INFO ]: Finished minimizeSevpa. Reduced states from 22 to 22. [2018-06-26 18:16:26,724 INFO ]: Start removeUnreachable. Operand 22 states. [2018-06-26 18:16:26,724 INFO ]: Finished removeUnreachable. Reduced from 22 states to 22 states and 23 transitions. [2018-06-26 18:16:26,724 INFO ]: Start accepts. Automaton has 22 states and 23 transitions. Word has length 20 [2018-06-26 18:16:26,724 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:26,724 INFO ]: Abstraction has 22 states and 23 transitions. [2018-06-26 18:16:26,724 INFO ]: Interpolant automaton has 34 states. [2018-06-26 18:16:26,725 INFO ]: Start isEmpty. Operand 22 states and 23 transitions. [2018-06-26 18:16:26,725 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-26 18:16:26,725 INFO ]: Found error trace [2018-06-26 18:16:26,725 INFO ]: trace histogram [8, 6, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:26,725 INFO ]: === Iteration 20 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:26,725 INFO ]: Analyzing trace with hash 1663030665, now seen corresponding path program 13 times [2018-06-26 18:16:26,725 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:26,725 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:26,726 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:26,726 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:26,726 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:26,742 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:27,002 INFO ]: Checked inductivity of 57 backedges. 36 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:27,002 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:27,002 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 16 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:27,008 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:27,056 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:27,059 INFO ]: Computing forward predicates... [2018-06-26 18:16:27,090 INFO ]: Checked inductivity of 57 backedges. 36 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:27,121 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:27,121 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 18] total 19 [2018-06-26 18:16:27,121 INFO ]: Interpolant automaton has 19 states [2018-06-26 18:16:27,121 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-26 18:16:27,121 INFO ]: CoverageRelationStatistics Valid=99, Invalid=243, Unknown=0, NotChecked=0, Total=342 [2018-06-26 18:16:27,122 INFO ]: Start difference. First operand 22 states and 23 transitions. Second operand 19 states. [2018-06-26 18:16:27,231 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:27,231 INFO ]: Finished difference Result 23 states and 24 transitions. [2018-06-26 18:16:27,232 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-06-26 18:16:27,232 INFO ]: Start accepts. Automaton has 19 states. Word has length 21 [2018-06-26 18:16:27,232 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:27,233 INFO ]: With dead ends: 23 [2018-06-26 18:16:27,233 INFO ]: Without dead ends: 23 [2018-06-26 18:16:27,233 INFO ]: 0 DeclaredPredicates, 45 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 85 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=232, Invalid=418, Unknown=0, NotChecked=0, Total=650 [2018-06-26 18:16:27,233 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-26 18:16:27,235 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-26 18:16:27,235 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-26 18:16:27,235 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 24 transitions. [2018-06-26 18:16:27,235 INFO ]: Start accepts. Automaton has 23 states and 24 transitions. Word has length 21 [2018-06-26 18:16:27,235 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:27,235 INFO ]: Abstraction has 23 states and 24 transitions. [2018-06-26 18:16:27,235 INFO ]: Interpolant automaton has 19 states. [2018-06-26 18:16:27,235 INFO ]: Start isEmpty. Operand 23 states and 24 transitions. [2018-06-26 18:16:27,236 INFO ]: Finished isEmpty. Found accepting run of length 23 [2018-06-26 18:16:27,236 INFO ]: Found error trace [2018-06-26 18:16:27,236 INFO ]: trace histogram [8, 7, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:27,236 INFO ]: === Iteration 21 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:27,236 INFO ]: Analyzing trace with hash 15131190, now seen corresponding path program 14 times [2018-06-26 18:16:27,236 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:27,236 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:27,236 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:27,236 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:27,236 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:27,372 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:28,677 INFO ]: Checked inductivity of 64 backedges. 0 proven. 64 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:28,677 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:28,677 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 17 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:28,683 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 18:16:28,734 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 18:16:28,734 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:28,738 INFO ]: Computing forward predicates... [2018-06-26 18:16:29,497 WARN ]: Spent 111.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-26 18:16:30,376 INFO ]: Checked inductivity of 64 backedges. 21 proven. 43 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:30,395 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:30,395 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 19] total 37 [2018-06-26 18:16:30,395 INFO ]: Interpolant automaton has 37 states [2018-06-26 18:16:30,396 INFO ]: Constructing interpolant automaton starting with 37 interpolants. [2018-06-26 18:16:30,396 INFO ]: CoverageRelationStatistics Valid=224, Invalid=1108, Unknown=0, NotChecked=0, Total=1332 [2018-06-26 18:16:30,396 INFO ]: Start difference. First operand 23 states and 24 transitions. Second operand 37 states. [2018-06-26 18:16:31,009 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:31,009 INFO ]: Finished difference Result 32 states and 34 transitions. [2018-06-26 18:16:31,010 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-06-26 18:16:31,011 INFO ]: Start accepts. Automaton has 37 states. Word has length 22 [2018-06-26 18:16:31,011 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:31,011 INFO ]: With dead ends: 32 [2018-06-26 18:16:31,011 INFO ]: Without dead ends: 24 [2018-06-26 18:16:31,011 INFO ]: 0 DeclaredPredicates, 57 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 468 ImplicationChecksByTransitivity, 3.0s TimeCoverageRelationStatistics Valid=485, Invalid=2271, Unknown=0, NotChecked=0, Total=2756 [2018-06-26 18:16:31,012 INFO ]: Start minimizeSevpa. Operand 24 states. [2018-06-26 18:16:31,013 INFO ]: Finished minimizeSevpa. Reduced states from 24 to 24. [2018-06-26 18:16:31,013 INFO ]: Start removeUnreachable. Operand 24 states. [2018-06-26 18:16:31,014 INFO ]: Finished removeUnreachable. Reduced from 24 states to 24 states and 25 transitions. [2018-06-26 18:16:31,014 INFO ]: Start accepts. Automaton has 24 states and 25 transitions. Word has length 22 [2018-06-26 18:16:31,014 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:31,014 INFO ]: Abstraction has 24 states and 25 transitions. [2018-06-26 18:16:31,014 INFO ]: Interpolant automaton has 37 states. [2018-06-26 18:16:31,014 INFO ]: Start isEmpty. Operand 24 states and 25 transitions. [2018-06-26 18:16:31,015 INFO ]: Finished isEmpty. Found accepting run of length 24 [2018-06-26 18:16:31,015 INFO ]: Found error trace [2018-06-26 18:16:31,015 INFO ]: trace histogram [9, 7, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:31,015 INFO ]: === Iteration 22 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:31,015 INFO ]: Analyzing trace with hash -1043169838, now seen corresponding path program 15 times [2018-06-26 18:16:31,015 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:31,015 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:31,015 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:31,015 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:31,015 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:31,034 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:31,487 INFO ]: Checked inductivity of 73 backedges. 45 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:31,487 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:31,487 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 18 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:31,493 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 18:16:31,555 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-06-26 18:16:31,555 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:31,558 INFO ]: Computing forward predicates... [2018-06-26 18:16:31,582 INFO ]: Checked inductivity of 73 backedges. 45 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:31,607 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:31,607 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [20, 20] total 21 [2018-06-26 18:16:31,607 INFO ]: Interpolant automaton has 21 states [2018-06-26 18:16:31,607 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-26 18:16:31,607 INFO ]: CoverageRelationStatistics Valid=120, Invalid=300, Unknown=0, NotChecked=0, Total=420 [2018-06-26 18:16:31,607 INFO ]: Start difference. First operand 24 states and 25 transitions. Second operand 21 states. [2018-06-26 18:16:31,720 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:31,720 INFO ]: Finished difference Result 25 states and 26 transitions. [2018-06-26 18:16:31,723 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-06-26 18:16:31,723 INFO ]: Start accepts. Automaton has 21 states. Word has length 23 [2018-06-26 18:16:31,723 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:31,723 INFO ]: With dead ends: 25 [2018-06-26 18:16:31,723 INFO ]: Without dead ends: 25 [2018-06-26 18:16:31,724 INFO ]: 0 DeclaredPredicates, 50 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 27 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 109 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=288, Invalid=524, Unknown=0, NotChecked=0, Total=812 [2018-06-26 18:16:31,724 INFO ]: Start minimizeSevpa. Operand 25 states. [2018-06-26 18:16:31,725 INFO ]: Finished minimizeSevpa. Reduced states from 25 to 25. [2018-06-26 18:16:31,726 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-26 18:16:31,726 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 26 transitions. [2018-06-26 18:16:31,726 INFO ]: Start accepts. Automaton has 25 states and 26 transitions. Word has length 23 [2018-06-26 18:16:31,726 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:31,726 INFO ]: Abstraction has 25 states and 26 transitions. [2018-06-26 18:16:31,726 INFO ]: Interpolant automaton has 21 states. [2018-06-26 18:16:31,726 INFO ]: Start isEmpty. Operand 25 states and 26 transitions. [2018-06-26 18:16:31,727 INFO ]: Finished isEmpty. Found accepting run of length 25 [2018-06-26 18:16:31,727 INFO ]: Found error trace [2018-06-26 18:16:31,727 INFO ]: trace histogram [9, 8, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:31,732 INFO ]: === Iteration 23 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:31,732 INFO ]: Analyzing trace with hash 2022261517, now seen corresponding path program 16 times [2018-06-26 18:16:31,732 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:31,732 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:31,733 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:31,733 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:31,733 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:31,777 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:33,334 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 89 DAG size of output: 14 [2018-06-26 18:16:33,497 INFO ]: Checked inductivity of 81 backedges. 0 proven. 81 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:33,497 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:33,497 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 19 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:33,524 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 18:16:33,585 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 18:16:33,585 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:33,591 INFO ]: Computing forward predicates... [2018-06-26 18:16:34,280 INFO ]: Checked inductivity of 81 backedges. 36 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:34,312 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:34,312 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 21] total 41 [2018-06-26 18:16:34,312 INFO ]: Interpolant automaton has 41 states [2018-06-26 18:16:34,312 INFO ]: Constructing interpolant automaton starting with 41 interpolants. [2018-06-26 18:16:34,313 INFO ]: CoverageRelationStatistics Valid=277, Invalid=1363, Unknown=0, NotChecked=0, Total=1640 [2018-06-26 18:16:34,313 INFO ]: Start difference. First operand 25 states and 26 transitions. Second operand 41 states. [2018-06-26 18:16:35,285 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:35,285 INFO ]: Finished difference Result 35 states and 36 transitions. [2018-06-26 18:16:35,286 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-06-26 18:16:35,286 INFO ]: Start accepts. Automaton has 41 states. Word has length 24 [2018-06-26 18:16:35,286 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:35,286 INFO ]: With dead ends: 35 [2018-06-26 18:16:35,286 INFO ]: Without dead ends: 26 [2018-06-26 18:16:35,287 INFO ]: 0 DeclaredPredicates, 63 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 57 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 581 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=594, Invalid=2828, Unknown=0, NotChecked=0, Total=3422 [2018-06-26 18:16:35,287 INFO ]: Start minimizeSevpa. Operand 26 states. [2018-06-26 18:16:35,289 INFO ]: Finished minimizeSevpa. Reduced states from 26 to 26. [2018-06-26 18:16:35,289 INFO ]: Start removeUnreachable. Operand 26 states. [2018-06-26 18:16:35,289 INFO ]: Finished removeUnreachable. Reduced from 26 states to 26 states and 27 transitions. [2018-06-26 18:16:35,289 INFO ]: Start accepts. Automaton has 26 states and 27 transitions. Word has length 24 [2018-06-26 18:16:35,289 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:35,289 INFO ]: Abstraction has 26 states and 27 transitions. [2018-06-26 18:16:35,289 INFO ]: Interpolant automaton has 41 states. [2018-06-26 18:16:35,289 INFO ]: Start isEmpty. Operand 26 states and 27 transitions. [2018-06-26 18:16:35,290 INFO ]: Finished isEmpty. Found accepting run of length 26 [2018-06-26 18:16:35,290 INFO ]: Found error trace [2018-06-26 18:16:35,290 INFO ]: trace histogram [10, 8, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:35,290 INFO ]: === Iteration 24 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:35,290 INFO ]: Analyzing trace with hash -1392744535, now seen corresponding path program 17 times [2018-06-26 18:16:35,290 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:35,290 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:35,290 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:35,290 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:35,290 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:35,307 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:35,662 INFO ]: Checked inductivity of 91 backedges. 55 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:35,662 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:35,662 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 20 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:35,667 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-26 18:16:35,742 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 6 check-sat command(s) [2018-06-26 18:16:35,742 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:35,747 INFO ]: Computing forward predicates... [2018-06-26 18:16:35,842 INFO ]: Checked inductivity of 91 backedges. 55 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:35,861 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:35,861 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 23 [2018-06-26 18:16:35,862 INFO ]: Interpolant automaton has 23 states [2018-06-26 18:16:35,862 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-26 18:16:35,862 INFO ]: CoverageRelationStatistics Valid=143, Invalid=363, Unknown=0, NotChecked=0, Total=506 [2018-06-26 18:16:35,862 INFO ]: Start difference. First operand 26 states and 27 transitions. Second operand 23 states. [2018-06-26 18:16:35,998 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:35,998 INFO ]: Finished difference Result 27 states and 28 transitions. [2018-06-26 18:16:35,998 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-06-26 18:16:35,998 INFO ]: Start accepts. Automaton has 23 states. Word has length 25 [2018-06-26 18:16:35,999 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:35,999 INFO ]: With dead ends: 27 [2018-06-26 18:16:35,999 INFO ]: Without dead ends: 27 [2018-06-26 18:16:35,999 INFO ]: 0 DeclaredPredicates, 55 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 136 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=350, Invalid=642, Unknown=0, NotChecked=0, Total=992 [2018-06-26 18:16:35,999 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-26 18:16:36,001 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 27. [2018-06-26 18:16:36,001 INFO ]: Start removeUnreachable. Operand 27 states. [2018-06-26 18:16:36,001 INFO ]: Finished removeUnreachable. Reduced from 27 states to 27 states and 28 transitions. [2018-06-26 18:16:36,001 INFO ]: Start accepts. Automaton has 27 states and 28 transitions. Word has length 25 [2018-06-26 18:16:36,001 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:36,001 INFO ]: Abstraction has 27 states and 28 transitions. [2018-06-26 18:16:36,001 INFO ]: Interpolant automaton has 23 states. [2018-06-26 18:16:36,001 INFO ]: Start isEmpty. Operand 27 states and 28 transitions. [2018-06-26 18:16:36,002 INFO ]: Finished isEmpty. Found accepting run of length 27 [2018-06-26 18:16:36,002 INFO ]: Found error trace [2018-06-26 18:16:36,002 INFO ]: trace histogram [10, 9, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:36,002 INFO ]: === Iteration 25 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:36,002 INFO ]: Analyzing trace with hash -224619498, now seen corresponding path program 18 times [2018-06-26 18:16:36,002 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:36,002 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:36,007 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:36,007 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:36,007 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:36,044 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:37,039 WARN ]: Spent 259.00 ms on a formula simplification. DAG size of input: 18 DAG size of output: 10 [2018-06-26 18:16:37,351 WARN ]: Spent 263.00 ms on a formula simplification. DAG size of input: 29 DAG size of output: 18 [2018-06-26 18:16:37,612 WARN ]: Spent 197.00 ms on a formula simplification. DAG size of input: 37 DAG size of output: 19 [2018-06-26 18:16:39,032 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 84 DAG size of output: 15 [2018-06-26 18:16:39,211 WARN ]: Spent 105.00 ms on a formula simplification. DAG size of input: 93 DAG size of output: 15 [2018-06-26 18:16:39,420 WARN ]: Spent 131.00 ms on a formula simplification. DAG size of input: 100 DAG size of output: 19 [2018-06-26 18:16:39,625 WARN ]: Spent 124.00 ms on a formula simplification. DAG size of input: 105 DAG size of output: 23 [2018-06-26 18:16:39,823 WARN ]: Spent 115.00 ms on a formula simplification. DAG size of input: 108 DAG size of output: 14 [2018-06-26 18:16:40,019 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 106 DAG size of output: 14 [2018-06-26 18:16:40,041 INFO ]: Checked inductivity of 100 backedges. 1 proven. 99 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:40,041 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:40,041 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 21 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:40,047 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-26 18:16:40,115 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 6 check-sat command(s) [2018-06-26 18:16:40,115 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:40,121 INFO ]: Computing forward predicates... [2018-06-26 18:16:40,994 INFO ]: Checked inductivity of 100 backedges. 24 proven. 76 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:41,027 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:41,027 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 46 [2018-06-26 18:16:41,027 INFO ]: Interpolant automaton has 46 states [2018-06-26 18:16:41,027 INFO ]: Constructing interpolant automaton starting with 46 interpolants. [2018-06-26 18:16:41,028 INFO ]: CoverageRelationStatistics Valid=307, Invalid=1763, Unknown=0, NotChecked=0, Total=2070 [2018-06-26 18:16:41,028 INFO ]: Start difference. First operand 27 states and 28 transitions. Second operand 46 states. [2018-06-26 18:16:41,464 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:41,464 INFO ]: Finished difference Result 39 states and 41 transitions. [2018-06-26 18:16:41,465 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-26 18:16:41,465 INFO ]: Start accepts. Automaton has 46 states. Word has length 26 [2018-06-26 18:16:41,465 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:41,465 INFO ]: With dead ends: 39 [2018-06-26 18:16:41,465 INFO ]: Without dead ends: 28 [2018-06-26 18:16:41,466 INFO ]: 0 DeclaredPredicates, 61 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 727 ImplicationChecksByTransitivity, 3.9s TimeCoverageRelationStatistics Valid=520, Invalid=2786, Unknown=0, NotChecked=0, Total=3306 [2018-06-26 18:16:41,466 INFO ]: Start minimizeSevpa. Operand 28 states. [2018-06-26 18:16:41,467 INFO ]: Finished minimizeSevpa. Reduced states from 28 to 28. [2018-06-26 18:16:41,467 INFO ]: Start removeUnreachable. Operand 28 states. [2018-06-26 18:16:41,468 INFO ]: Finished removeUnreachable. Reduced from 28 states to 28 states and 29 transitions. [2018-06-26 18:16:41,468 INFO ]: Start accepts. Automaton has 28 states and 29 transitions. Word has length 26 [2018-06-26 18:16:41,468 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:41,468 INFO ]: Abstraction has 28 states and 29 transitions. [2018-06-26 18:16:41,468 INFO ]: Interpolant automaton has 46 states. [2018-06-26 18:16:41,468 INFO ]: Start isEmpty. Operand 28 states and 29 transitions. [2018-06-26 18:16:41,468 INFO ]: Finished isEmpty. Found accepting run of length 28 [2018-06-26 18:16:41,468 INFO ]: Found error trace [2018-06-26 18:16:41,468 INFO ]: trace histogram [11, 9, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:41,468 INFO ]: === Iteration 26 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:41,468 INFO ]: Analyzing trace with hash -690421326, now seen corresponding path program 19 times [2018-06-26 18:16:41,468 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:41,468 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:41,469 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:41,469 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:41,469 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:41,486 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:41,973 INFO ]: Checked inductivity of 111 backedges. 66 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:41,973 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:41,973 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 22 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:41,981 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:42,064 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:42,067 INFO ]: Computing forward predicates... [2018-06-26 18:16:42,094 INFO ]: Checked inductivity of 111 backedges. 66 proven. 45 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:42,114 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:42,114 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 24] total 25 [2018-06-26 18:16:42,114 INFO ]: Interpolant automaton has 25 states [2018-06-26 18:16:42,114 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-26 18:16:42,114 INFO ]: CoverageRelationStatistics Valid=168, Invalid=432, Unknown=0, NotChecked=0, Total=600 [2018-06-26 18:16:42,114 INFO ]: Start difference. First operand 28 states and 29 transitions. Second operand 25 states. [2018-06-26 18:16:42,275 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:42,275 INFO ]: Finished difference Result 29 states and 30 transitions. [2018-06-26 18:16:42,279 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-06-26 18:16:42,279 INFO ]: Start accepts. Automaton has 25 states. Word has length 27 [2018-06-26 18:16:42,279 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:42,279 INFO ]: With dead ends: 29 [2018-06-26 18:16:42,279 INFO ]: Without dead ends: 29 [2018-06-26 18:16:42,279 INFO ]: 0 DeclaredPredicates, 60 GetRequests, 27 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 166 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=418, Invalid=772, Unknown=0, NotChecked=0, Total=1190 [2018-06-26 18:16:42,279 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-26 18:16:42,281 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 29. [2018-06-26 18:16:42,281 INFO ]: Start removeUnreachable. Operand 29 states. [2018-06-26 18:16:42,281 INFO ]: Finished removeUnreachable. Reduced from 29 states to 29 states and 30 transitions. [2018-06-26 18:16:42,281 INFO ]: Start accepts. Automaton has 29 states and 30 transitions. Word has length 27 [2018-06-26 18:16:42,281 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:42,281 INFO ]: Abstraction has 29 states and 30 transitions. [2018-06-26 18:16:42,281 INFO ]: Interpolant automaton has 25 states. [2018-06-26 18:16:42,281 INFO ]: Start isEmpty. Operand 29 states and 30 transitions. [2018-06-26 18:16:42,281 INFO ]: Finished isEmpty. Found accepting run of length 29 [2018-06-26 18:16:42,281 INFO ]: Found error trace [2018-06-26 18:16:42,281 INFO ]: trace histogram [11, 10, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:42,281 INFO ]: === Iteration 27 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:42,281 INFO ]: Analyzing trace with hash 72563501, now seen corresponding path program 20 times [2018-06-26 18:16:42,281 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:42,281 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:42,282 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:42,282 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:16:42,282 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:42,324 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:46,038 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 103 DAG size of output: 13 [2018-06-26 18:16:46,288 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 15 [2018-06-26 18:16:46,542 WARN ]: Spent 128.00 ms on a formula simplification. DAG size of input: 115 DAG size of output: 13 [2018-06-26 18:16:46,795 WARN ]: Spent 124.00 ms on a formula simplification. DAG size of input: 118 DAG size of output: 14 [2018-06-26 18:16:47,027 WARN ]: Spent 102.00 ms on a formula simplification. DAG size of input: 116 DAG size of output: 18 [2018-06-26 18:16:47,050 INFO ]: Checked inductivity of 121 backedges. 1 proven. 120 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:47,050 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:47,050 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:47,060 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 18:16:47,129 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 18:16:47,129 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:47,136 INFO ]: Computing forward predicates... [2018-06-26 18:16:48,796 INFO ]: Checked inductivity of 121 backedges. 45 proven. 76 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:48,816 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:48,816 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 25] total 49 [2018-06-26 18:16:48,817 INFO ]: Interpolant automaton has 49 states [2018-06-26 18:16:48,817 INFO ]: Constructing interpolant automaton starting with 49 interpolants. [2018-06-26 18:16:48,817 INFO ]: CoverageRelationStatistics Valid=379, Invalid=1973, Unknown=0, NotChecked=0, Total=2352 [2018-06-26 18:16:48,817 INFO ]: Start difference. First operand 29 states and 30 transitions. Second operand 49 states. [2018-06-26 18:16:49,705 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:49,705 INFO ]: Finished difference Result 41 states and 43 transitions. [2018-06-26 18:16:49,706 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-06-26 18:16:49,706 INFO ]: Start accepts. Automaton has 49 states. Word has length 28 [2018-06-26 18:16:49,706 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:49,706 INFO ]: With dead ends: 41 [2018-06-26 18:16:49,706 INFO ]: Without dead ends: 30 [2018-06-26 18:16:49,707 INFO ]: 0 DeclaredPredicates, 73 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 932 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=820, Invalid=3872, Unknown=0, NotChecked=0, Total=4692 [2018-06-26 18:16:49,707 INFO ]: Start minimizeSevpa. Operand 30 states. [2018-06-26 18:16:49,708 INFO ]: Finished minimizeSevpa. Reduced states from 30 to 30. [2018-06-26 18:16:49,708 INFO ]: Start removeUnreachable. Operand 30 states. [2018-06-26 18:16:49,709 INFO ]: Finished removeUnreachable. Reduced from 30 states to 30 states and 31 transitions. [2018-06-26 18:16:49,709 INFO ]: Start accepts. Automaton has 30 states and 31 transitions. Word has length 28 [2018-06-26 18:16:49,709 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:49,709 INFO ]: Abstraction has 30 states and 31 transitions. [2018-06-26 18:16:49,709 INFO ]: Interpolant automaton has 49 states. [2018-06-26 18:16:49,709 INFO ]: Start isEmpty. Operand 30 states and 31 transitions. [2018-06-26 18:16:49,711 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-26 18:16:49,711 INFO ]: Found error trace [2018-06-26 18:16:49,711 INFO ]: trace histogram [12, 10, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:49,711 INFO ]: === Iteration 28 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:49,711 INFO ]: Analyzing trace with hash -886394423, now seen corresponding path program 21 times [2018-06-26 18:16:49,711 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:49,711 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:49,711 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:49,711 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:49,711 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:49,732 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:50,532 INFO ]: Checked inductivity of 133 backedges. 78 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:50,532 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:50,532 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 24 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:50,539 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 18:16:50,618 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 7 check-sat command(s) [2018-06-26 18:16:50,618 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:50,623 INFO ]: Computing forward predicates... [2018-06-26 18:16:50,664 INFO ]: Checked inductivity of 133 backedges. 78 proven. 55 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:50,686 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:16:50,686 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [26, 26] total 27 [2018-06-26 18:16:50,686 INFO ]: Interpolant automaton has 27 states [2018-06-26 18:16:50,686 INFO ]: Constructing interpolant automaton starting with 27 interpolants. [2018-06-26 18:16:50,687 INFO ]: CoverageRelationStatistics Valid=195, Invalid=507, Unknown=0, NotChecked=0, Total=702 [2018-06-26 18:16:50,687 INFO ]: Start difference. First operand 30 states and 31 transitions. Second operand 27 states. [2018-06-26 18:16:50,840 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:16:50,840 INFO ]: Finished difference Result 31 states and 32 transitions. [2018-06-26 18:16:50,840 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-06-26 18:16:50,840 INFO ]: Start accepts. Automaton has 27 states. Word has length 29 [2018-06-26 18:16:50,840 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:16:50,840 INFO ]: With dead ends: 31 [2018-06-26 18:16:50,840 INFO ]: Without dead ends: 31 [2018-06-26 18:16:50,840 INFO ]: 0 DeclaredPredicates, 65 GetRequests, 29 SyntacticMatches, 0 SemanticMatches, 36 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 199 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=492, Invalid=914, Unknown=0, NotChecked=0, Total=1406 [2018-06-26 18:16:50,841 INFO ]: Start minimizeSevpa. Operand 31 states. [2018-06-26 18:16:50,842 INFO ]: Finished minimizeSevpa. Reduced states from 31 to 31. [2018-06-26 18:16:50,842 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-26 18:16:50,843 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 32 transitions. [2018-06-26 18:16:50,843 INFO ]: Start accepts. Automaton has 31 states and 32 transitions. Word has length 29 [2018-06-26 18:16:50,843 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:16:50,843 INFO ]: Abstraction has 31 states and 32 transitions. [2018-06-26 18:16:50,843 INFO ]: Interpolant automaton has 27 states. [2018-06-26 18:16:50,843 INFO ]: Start isEmpty. Operand 31 states and 32 transitions. [2018-06-26 18:16:50,843 INFO ]: Finished isEmpty. Found accepting run of length 31 [2018-06-26 18:16:50,843 INFO ]: Found error trace [2018-06-26 18:16:50,843 INFO ]: trace histogram [12, 11, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:16:50,843 INFO ]: === Iteration 29 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:16:50,844 INFO ]: Analyzing trace with hash -1707635210, now seen corresponding path program 22 times [2018-06-26 18:16:50,844 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:16:50,844 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:16:50,844 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:50,844 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:16:50,844 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:16:50,883 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:56,328 WARN ]: Spent 117.00 ms on a formula simplification. DAG size of input: 96 DAG size of output: 22 [2018-06-26 18:16:56,698 WARN ]: Spent 156.00 ms on a formula simplification. DAG size of input: 110 DAG size of output: 26 [2018-06-26 18:16:57,075 WARN ]: Spent 162.00 ms on a formula simplification. DAG size of input: 122 DAG size of output: 15 [2018-06-26 18:16:57,466 WARN ]: Spent 171.00 ms on a formula simplification. DAG size of input: 132 DAG size of output: 30 [2018-06-26 18:16:58,033 WARN ]: Spent 211.00 ms on a formula simplification. DAG size of input: 140 DAG size of output: 23 [2018-06-26 18:16:58,478 WARN ]: Spent 217.00 ms on a formula simplification. DAG size of input: 152 DAG size of output: 14 [2018-06-26 18:16:58,909 WARN ]: Spent 203.00 ms on a formula simplification. DAG size of input: 150 DAG size of output: 14 [2018-06-26 18:16:58,934 INFO ]: Checked inductivity of 144 backedges. 0 proven. 144 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:16:58,934 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:16:58,935 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 25 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:16:58,940 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 18:16:59,014 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 18:16:59,014 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:16:59,027 INFO ]: Computing forward predicates... [2018-06-26 18:17:01,211 INFO ]: Checked inductivity of 144 backedges. 66 proven. 78 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:17:01,230 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:17:01,230 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 27] total 53 [2018-06-26 18:17:01,231 INFO ]: Interpolant automaton has 53 states [2018-06-26 18:17:01,231 INFO ]: Constructing interpolant automaton starting with 53 interpolants. [2018-06-26 18:17:01,231 INFO ]: CoverageRelationStatistics Valid=439, Invalid=2317, Unknown=0, NotChecked=0, Total=2756 [2018-06-26 18:17:01,231 INFO ]: Start difference. First operand 31 states and 32 transitions. Second operand 53 states. [2018-06-26 18:17:02,342 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:17:02,342 INFO ]: Finished difference Result 44 states and 45 transitions. [2018-06-26 18:17:02,343 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-06-26 18:17:02,343 INFO ]: Start accepts. Automaton has 53 states. Word has length 30 [2018-06-26 18:17:02,343 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:17:02,343 INFO ]: With dead ends: 44 [2018-06-26 18:17:02,343 INFO ]: Without dead ends: 32 [2018-06-26 18:17:02,345 INFO ]: 0 DeclaredPredicates, 81 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 75 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 989 ImplicationChecksByTransitivity, 5.9s TimeCoverageRelationStatistics Valid=954, Invalid=4898, Unknown=0, NotChecked=0, Total=5852 [2018-06-26 18:17:02,345 INFO ]: Start minimizeSevpa. Operand 32 states. [2018-06-26 18:17:02,349 INFO ]: Finished minimizeSevpa. Reduced states from 32 to 32. [2018-06-26 18:17:02,349 INFO ]: Start removeUnreachable. Operand 32 states. [2018-06-26 18:17:02,349 INFO ]: Finished removeUnreachable. Reduced from 32 states to 32 states and 33 transitions. [2018-06-26 18:17:02,349 INFO ]: Start accepts. Automaton has 32 states and 33 transitions. Word has length 30 [2018-06-26 18:17:02,349 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:17:02,349 INFO ]: Abstraction has 32 states and 33 transitions. [2018-06-26 18:17:02,349 INFO ]: Interpolant automaton has 53 states. [2018-06-26 18:17:02,349 INFO ]: Start isEmpty. Operand 32 states and 33 transitions. [2018-06-26 18:17:02,350 INFO ]: Finished isEmpty. Found accepting run of length 32 [2018-06-26 18:17:02,350 INFO ]: Found error trace [2018-06-26 18:17:02,350 INFO ]: trace histogram [13, 11, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:17:02,350 INFO ]: === Iteration 30 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:17:02,350 INFO ]: Analyzing trace with hash 151768466, now seen corresponding path program 23 times [2018-06-26 18:17:02,350 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:17:02,350 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:17:02,350 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:17:02,350 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:17:02,350 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:17:02,373 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:17:02,806 INFO ]: Checked inductivity of 157 backedges. 91 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:17:02,806 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:17:02,806 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 26 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:17:02,817 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-26 18:17:02,902 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 8 check-sat command(s) [2018-06-26 18:17:02,902 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:17:02,906 INFO ]: Computing forward predicates... [2018-06-26 18:17:02,933 INFO ]: Checked inductivity of 157 backedges. 91 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:17:02,953 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:17:02,953 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 28] total 29 [2018-06-26 18:17:02,953 INFO ]: Interpolant automaton has 29 states [2018-06-26 18:17:02,953 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-26 18:17:02,954 INFO ]: CoverageRelationStatistics Valid=224, Invalid=588, Unknown=0, NotChecked=0, Total=812 [2018-06-26 18:17:02,954 INFO ]: Start difference. First operand 32 states and 33 transitions. Second operand 29 states. [2018-06-26 18:17:03,192 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:17:03,192 INFO ]: Finished difference Result 33 states and 34 transitions. [2018-06-26 18:17:03,192 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2018-06-26 18:17:03,192 INFO ]: Start accepts. Automaton has 29 states. Word has length 31 [2018-06-26 18:17:03,192 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:17:03,193 INFO ]: With dead ends: 33 [2018-06-26 18:17:03,193 INFO ]: Without dead ends: 33 [2018-06-26 18:17:03,193 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 235 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=572, Invalid=1068, Unknown=0, NotChecked=0, Total=1640 [2018-06-26 18:17:03,193 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-26 18:17:03,194 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-06-26 18:17:03,194 INFO ]: Start removeUnreachable. Operand 33 states. [2018-06-26 18:17:03,195 INFO ]: Finished removeUnreachable. Reduced from 33 states to 33 states and 34 transitions. [2018-06-26 18:17:03,195 INFO ]: Start accepts. Automaton has 33 states and 34 transitions. Word has length 31 [2018-06-26 18:17:03,195 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:17:03,195 INFO ]: Abstraction has 33 states and 34 transitions. [2018-06-26 18:17:03,195 INFO ]: Interpolant automaton has 29 states. [2018-06-26 18:17:03,195 INFO ]: Start isEmpty. Operand 33 states and 34 transitions. [2018-06-26 18:17:03,195 INFO ]: Finished isEmpty. Found accepting run of length 33 [2018-06-26 18:17:03,195 INFO ]: Found error trace [2018-06-26 18:17:03,195 INFO ]: trace histogram [13, 12, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:17:03,195 INFO ]: === Iteration 31 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:17:03,195 INFO ]: Analyzing trace with hash 410643277, now seen corresponding path program 24 times [2018-06-26 18:17:03,195 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:17:03,195 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:17:03,196 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:17:03,196 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 18:17:03,196 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:17:03,240 INFO ]: Conjunction of SSA is unsat Received shutdown request... [2018-06-26 18:17:06,902 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-26 18:17:06,946 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-26 18:17:06,990 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-26 18:17:07,034 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-26 18:17:07,096 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-26 18:17:07,139 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-26 18:17:07,183 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-26 18:17:07,226 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-26 18:17:07,249 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-26 18:17:07,249 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-26 18:17:07,249 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-26 18:17:07,249 WARN ]: Unable to check validity of interpolant: cancelled [2018-06-26 18:17:07,254 WARN ]: Verification canceled [2018-06-26 18:17:07,261 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-26 18:17:07,262 WARN ]: Timeout [2018-06-26 18:17:07,262 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 06:17:07 BasicIcfg [2018-06-26 18:17:07,262 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-26 18:17:07,263 INFO ]: Toolchain (without parser) took 58306.66 ms. Allocated memory was 304.6 MB in the beginning and 1.5 GB in the end (delta: 1.1 GB). Free memory was 258.9 MB in the beginning and 526.0 MB in the end (delta: -267.0 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-26 18:17:07,264 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 304.6 MB. Free memory is still 270.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-26 18:17:07,264 INFO ]: ChcToBoogie took 67.19 ms. Allocated memory is still 304.6 MB. Free memory was 257.9 MB in the beginning and 255.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-26 18:17:07,264 INFO ]: Boogie Preprocessor took 43.40 ms. Allocated memory is still 304.6 MB. Free memory was 255.9 MB in the beginning and 254.9 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-26 18:17:07,264 INFO ]: RCFGBuilder took 374.80 ms. Allocated memory is still 304.6 MB. Free memory was 254.9 MB in the beginning and 244.8 MB in the end (delta: 10.1 MB). Peak memory consumption was 10.1 MB. Max. memory is 3.6 GB. [2018-06-26 18:17:07,265 INFO ]: BlockEncodingV2 took 207.43 ms. Allocated memory is still 304.6 MB. Free memory was 244.8 MB in the beginning and 236.8 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-26 18:17:07,265 INFO ]: TraceAbstraction took 57601.95 ms. Allocated memory was 304.6 MB in the beginning and 1.5 GB in the end (delta: 1.1 GB). Free memory was 235.8 MB in the beginning and 526.0 MB in the end (delta: -290.1 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. [2018-06-26 18:17:07,268 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.plugins.blockencoding: - StatisticsResult: Initial Icfg 14 locations, 18 edges - StatisticsResult: Encoded RCFG 8 locations, 14 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 304.6 MB. Free memory is still 270.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 67.19 ms. Allocated memory is still 304.6 MB. Free memory was 257.9 MB in the beginning and 255.9 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 43.40 ms. Allocated memory is still 304.6 MB. Free memory was 255.9 MB in the beginning and 254.9 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 374.80 ms. Allocated memory is still 304.6 MB. Free memory was 254.9 MB in the beginning and 244.8 MB in the end (delta: 10.1 MB). Peak memory consumption was 10.1 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 207.43 ms. Allocated memory is still 304.6 MB. Free memory was 244.8 MB in the beginning and 236.8 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 57601.95 ms. Allocated memory was 304.6 MB in the beginning and 1.5 GB in the end (delta: 1.1 GB). Free memory was 235.8 MB in the beginning and 526.0 MB in the end (delta: -290.1 MB). Peak memory consumption was 1.4 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds Cancelled while BasicCegarLoop was analyzing trace of length 33 with TraceHistMax 13, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while NestedInterpolantsBuilder was constructing predicates for 31 interpolants. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 8 locations, 1 error locations. TIMEOUT Result, 57.5s OverallTime, 31 OverallIterations, 13 TraceHistogramMax, 8.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 184 SDtfs, 534 SDslu, 1606 SDs, 0 SdLazy, 4017 SolverSat, 1029 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 2.8s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1110 GetRequests, 324 SyntacticMatches, 1 SemanticMatches, 785 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6056 ImplicationChecksByTransitivity, 35.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=33occurred in iteration=30, 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.0s AutomataMinimizationTime, 30 MinimizatonAttempts, 7 StatesRemovedByMinimization, 4 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.8s SatisfiabilityAnalysisTime, 41.9s InterpolantComputationTime, 977 NumberOfCodeBlocks, 977 NumberOfCodeBlocksAsserted, 103 NumberOfCheckSat, 923 ConstructedInterpolants, 0 QuantifiedInterpolants, 161827 SizeOfPredicates, 555 NumberOfNonLiveVariables, 10034 ConjunctsInSsa, 2239 ConjunctsInUnsatCore, 54 InterpolantComputations, 7 PerfectInterpolantSequences, 1140/2781 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/array_init.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-26_18-17-07-283.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/array_init.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-26_18-17-07-283.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/array_init.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-26_18-17-07-283.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/array_init.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-26_18-17-07-283.csv Completed graceful shutdown