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/enc-rev_append.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-24 21:15:55,597 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-24 21:15:55,599 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-24 21:15:55,610 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-24 21:15:55,610 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-24 21:15:55,611 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-24 21:15:55,612 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-24 21:15:55,614 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-24 21:15:55,616 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-24 21:15:55,616 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-24 21:15:55,617 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-24 21:15:55,617 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-24 21:15:55,618 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-24 21:15:55,619 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-24 21:15:55,620 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-24 21:15:55,621 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-24 21:15:55,622 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-24 21:15:55,624 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-24 21:15:55,626 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-24 21:15:55,627 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-24 21:15:55,628 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-24 21:15:55,631 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-24 21:15:55,631 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-24 21:15:55,631 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-24 21:15:55,632 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-24 21:15:55,633 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-24 21:15:55,634 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-24 21:15:55,634 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-24 21:15:55,636 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-24 21:15:55,636 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-24 21:15:55,637 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-24 21:15:55,637 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-24 21:15:55,638 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-24 21:15:55,638 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-24 21:15:55,639 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-24 21:15:55,639 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-24 21:15:55,654 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-24 21:15:55,654 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-24 21:15:55,654 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-24 21:15:55,655 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-24 21:15:55,656 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-24 21:15:55,656 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-24 21:15:55,656 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-24 21:15:55,656 INFO L133 SettingsManager]: * Use SBE=true [2018-06-24 21:15:55,657 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-24 21:15:55,657 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-24 21:15:55,657 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-24 21:15:55,657 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-24 21:15:55,658 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-24 21:15:55,658 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-24 21:15:55,658 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-24 21:15:55,658 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-24 21:15:55,659 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-24 21:15:55,659 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-24 21:15:55,659 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-24 21:15:55,659 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-24 21:15:55,660 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-24 21:15:55,661 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-24 21:15:55,661 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-24 21:15:55,698 INFO ]: Repository-Root is: /tmp [2018-06-24 21:15:55,709 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-24 21:15:55,712 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-24 21:15:55,714 INFO ]: Initializing SmtParser... [2018-06-24 21:15:55,714 INFO ]: SmtParser initialized [2018-06-24 21:15:55,714 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/hopv/lia/mochi/enc-rev_append.smt2 [2018-06-24 21:15:55,716 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-24 21:15:55,806 INFO ]: Executing SMT file /storage/chc-comp/hopv/lia/mochi/enc-rev_append.smt2 unknown [2018-06-24 21:15:56,024 INFO ]: Succesfully executed SMT file /storage/chc-comp/hopv/lia/mochi/enc-rev_append.smt2 [2018-06-24 21:15:56,032 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-24 21:15:56,039 INFO ]: Walking toolchain with 5 elements. [2018-06-24 21:15:56,042 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-24 21:15:56,042 INFO ]: Initializing ChcToBoogie... [2018-06-24 21:15:56,043 INFO ]: ChcToBoogie initialized [2018-06-24 21:15:56,046 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 24.06 09:15:56" (1/1) ... [2018-06-24 21:15:56,100 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:15:56 Unit [2018-06-24 21:15:56,100 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-24 21:15:56,100 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-24 21:15:56,100 INFO ]: Initializing Boogie Preprocessor... [2018-06-24 21:15:56,100 INFO ]: Boogie Preprocessor initialized [2018-06-24 21:15:56,121 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:15:56" (1/1) ... [2018-06-24 21:15:56,121 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:15:56" (1/1) ... [2018-06-24 21:15:56,126 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:15:56" (1/1) ... [2018-06-24 21:15:56,127 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:15:56" (1/1) ... [2018-06-24 21:15:56,130 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:15:56" (1/1) ... [2018-06-24 21:15:56,132 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:15:56" (1/1) ... [2018-06-24 21:15:56,133 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:15:56" (1/1) ... [2018-06-24 21:15:56,134 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-24 21:15:56,139 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-24 21:15:56,139 INFO ]: Initializing RCFGBuilder... [2018-06-24 21:15:56,139 INFO ]: RCFGBuilder initialized [2018-06-24 21:15:56,140 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:15:56" (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-24 21:15:56,156 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-24 21:15:56,156 INFO ]: Found specification of procedure gotoProc [2018-06-24 21:15:56,156 INFO ]: Found implementation of procedure gotoProc [2018-06-24 21:15:56,156 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-24 21:15:56,156 INFO ]: Found specification of procedure Ultimate.START [2018-06-24 21:15:56,156 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-24 21:15:56,439 INFO ]: Using library mode [2018-06-24 21:15:56,440 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:15:56 BoogieIcfgContainer [2018-06-24 21:15:56,440 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-24 21:15:56,440 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-24 21:15:56,440 INFO ]: Initializing BlockEncodingV2... [2018-06-24 21:15:56,441 INFO ]: BlockEncodingV2 initialized [2018-06-24 21:15:56,442 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:15:56" (1/1) ... [2018-06-24 21:15:56,458 INFO ]: Initial Icfg 16 locations, 22 edges [2018-06-24 21:15:56,459 INFO ]: Using Remove infeasible edges [2018-06-24 21:15:56,461 INFO ]: Using Maximize final states [2018-06-24 21:15:56,461 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-24 21:15:56,461 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-24 21:15:56,463 INFO ]: Using Remove sink states [2018-06-24 21:15:56,463 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-24 21:15:56,463 INFO ]: Using Use SBE [2018-06-24 21:15:56,471 INFO ]: SBE split 0 edges [2018-06-24 21:15:56,476 INFO ]: Removed 3 edges and 2 locations because of local infeasibility [2018-06-24 21:15:56,477 INFO ]: 0 new accepting states [2018-06-24 21:15:56,569 INFO ]: Removed 14 edges and 4 locations by large block encoding [2018-06-24 21:15:56,571 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 21:15:56,572 INFO ]: Removed 1 edges and 0 locations because of local infeasibility [2018-06-24 21:15:56,572 INFO ]: 0 new accepting states [2018-06-24 21:15:56,573 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-24 21:15:56,573 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 21:15:56,573 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-24 21:15:56,573 INFO ]: 0 new accepting states [2018-06-24 21:15:56,573 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-24 21:15:56,574 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 21:15:56,574 INFO ]: Encoded RCFG 10 locations, 15 edges [2018-06-24 21:15:56,574 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 24.06 09:15:56 BasicIcfg [2018-06-24 21:15:56,574 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-24 21:15:56,575 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-24 21:15:56,575 INFO ]: Initializing TraceAbstraction... [2018-06-24 21:15:56,578 INFO ]: TraceAbstraction initialized [2018-06-24 21:15:56,579 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 24.06 09:15:56" (1/4) ... [2018-06-24 21:15:56,579 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@34f98a39 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 24.06 09:15:56, skipping insertion in model container [2018-06-24 21:15:56,580 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:15:56" (2/4) ... [2018-06-24 21:15:56,580 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@34f98a39 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.06 09:15:56, skipping insertion in model container [2018-06-24 21:15:56,580 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:15:56" (3/4) ... [2018-06-24 21:15:56,580 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@34f98a39 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.06 09:15:56, skipping insertion in model container [2018-06-24 21:15:56,580 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 24.06 09:15:56" (4/4) ... [2018-06-24 21:15:56,583 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-24 21:15:56,596 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-24 21:15:56,603 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-24 21:15:56,646 INFO ]: Using default assertion order modulation [2018-06-24 21:15:56,647 INFO ]: Interprodecural is true [2018-06-24 21:15:56,647 INFO ]: Hoare is false [2018-06-24 21:15:56,647 INFO ]: Compute interpolants for FPandBP [2018-06-24 21:15:56,647 INFO ]: Backedges is TWOTRACK [2018-06-24 21:15:56,647 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-24 21:15:56,647 INFO ]: Difference is false [2018-06-24 21:15:56,647 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-24 21:15:56,647 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-24 21:15:56,656 INFO ]: Start isEmpty. Operand 10 states. [2018-06-24 21:15:56,665 INFO ]: Finished isEmpty. Found accepting run of length 5 [2018-06-24 21:15:56,665 INFO ]: Found error trace [2018-06-24 21:15:56,666 INFO ]: trace histogram [1, 1, 1, 1] [2018-06-24 21:15:56,666 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:15:56,671 INFO ]: Analyzing trace with hash 1132694, now seen corresponding path program 1 times [2018-06-24 21:15:56,672 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:15:56,672 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:15:56,702 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:15:56,703 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:15:56,703 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:15:56,740 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:15:56,787 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:15:56,789 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:15:56,789 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:15:56,790 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:15:56,801 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:15:56,801 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:15:56,804 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-24 21:15:56,992 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:15:56,992 INFO ]: Finished difference Result 17 states and 27 transitions. [2018-06-24 21:15:56,993 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:15:56,994 INFO ]: Start accepts. Automaton has 3 states. Word has length 4 [2018-06-24 21:15:56,994 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:15:57,001 INFO ]: With dead ends: 17 [2018-06-24 21:15:57,001 INFO ]: Without dead ends: 17 [2018-06-24 21:15:57,003 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:15:57,016 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-24 21:15:57,047 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 17. [2018-06-24 21:15:57,049 INFO ]: Start removeUnreachable. Operand 17 states. [2018-06-24 21:15:57,049 INFO ]: Finished removeUnreachable. Reduced from 17 states to 17 states and 27 transitions. [2018-06-24 21:15:57,051 INFO ]: Start accepts. Automaton has 17 states and 27 transitions. Word has length 4 [2018-06-24 21:15:57,053 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:15:57,054 INFO ]: Abstraction has 17 states and 27 transitions. [2018-06-24 21:15:57,054 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:15:57,054 INFO ]: Start isEmpty. Operand 17 states and 27 transitions. [2018-06-24 21:15:57,055 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-24 21:15:57,055 INFO ]: Found error trace [2018-06-24 21:15:57,055 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:15:57,055 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:15:57,058 INFO ]: Analyzing trace with hash -607951780, now seen corresponding path program 1 times [2018-06-24 21:15:57,058 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:15:57,058 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:15:57,059 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:15:57,059 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:15:57,059 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:15:57,084 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:15:57,346 WARN ]: Spent 100.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-24 21:15:57,347 INFO ]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 21:15:57,347 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:15:57,347 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-24 21:15:57,350 INFO ]: Interpolant automaton has 4 states [2018-06-24 21:15:57,350 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-24 21:15:57,351 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-24 21:15:57,351 INFO ]: Start difference. First operand 17 states and 27 transitions. Second operand 4 states. [2018-06-24 21:15:57,439 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:15:57,439 INFO ]: Finished difference Result 19 states and 29 transitions. [2018-06-24 21:15:57,439 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-24 21:15:57,439 INFO ]: Start accepts. Automaton has 4 states. Word has length 9 [2018-06-24 21:15:57,439 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:15:57,440 INFO ]: With dead ends: 19 [2018-06-24 21:15:57,440 INFO ]: Without dead ends: 19 [2018-06-24 21:15:57,441 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-24 21:15:57,441 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-24 21:15:57,443 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-24 21:15:57,443 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-24 21:15:57,444 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 29 transitions. [2018-06-24 21:15:57,444 INFO ]: Start accepts. Automaton has 19 states and 29 transitions. Word has length 9 [2018-06-24 21:15:57,445 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:15:57,445 INFO ]: Abstraction has 19 states and 29 transitions. [2018-06-24 21:15:57,445 INFO ]: Interpolant automaton has 4 states. [2018-06-24 21:15:57,445 INFO ]: Start isEmpty. Operand 19 states and 29 transitions. [2018-06-24 21:15:57,446 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-24 21:15:57,446 INFO ]: Found error trace [2018-06-24 21:15:57,446 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:15:57,446 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:15:57,446 INFO ]: Analyzing trace with hash 1293079289, now seen corresponding path program 1 times [2018-06-24 21:15:57,446 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:15:57,446 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:15:57,447 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:15:57,447 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:15:57,447 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:15:57,458 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:15:57,736 INFO ]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 21:15:57,736 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:15:57,736 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-06-24 21:15:57,736 INFO ]: Interpolant automaton has 6 states [2018-06-24 21:15:57,736 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-24 21:15:57,736 INFO ]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-06-24 21:15:57,737 INFO ]: Start difference. First operand 19 states and 29 transitions. Second operand 6 states. [2018-06-24 21:15:57,924 WARN ]: Spent 101.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-24 21:15:58,293 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:15:58,294 INFO ]: Finished difference Result 26 states and 40 transitions. [2018-06-24 21:15:58,294 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-24 21:15:58,294 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-24 21:15:58,294 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:15:58,297 INFO ]: With dead ends: 26 [2018-06-24 21:15:58,297 INFO ]: Without dead ends: 26 [2018-06-24 21:15:58,298 INFO ]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2018-06-24 21:15:58,298 INFO ]: Start minimizeSevpa. Operand 26 states. [2018-06-24 21:15:58,303 INFO ]: Finished minimizeSevpa. Reduced states from 26 to 23. [2018-06-24 21:15:58,303 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-24 21:15:58,304 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 37 transitions. [2018-06-24 21:15:58,304 INFO ]: Start accepts. Automaton has 23 states and 37 transitions. Word has length 9 [2018-06-24 21:15:58,305 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:15:58,305 INFO ]: Abstraction has 23 states and 37 transitions. [2018-06-24 21:15:58,305 INFO ]: Interpolant automaton has 6 states. [2018-06-24 21:15:58,305 INFO ]: Start isEmpty. Operand 23 states and 37 transitions. [2018-06-24 21:15:58,306 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-24 21:15:58,306 INFO ]: Found error trace [2018-06-24 21:15:58,306 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:15:58,306 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:15:58,306 INFO ]: Analyzing trace with hash -1667547845, now seen corresponding path program 1 times [2018-06-24 21:15:58,306 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:15:58,306 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:15:58,307 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:15:58,307 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:15:58,307 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:15:58,327 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:15:58,382 INFO ]: Checked inductivity of 3 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 21:15:58,382 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:15:58,382 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-24 21:15:58,407 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:15:58,432 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:15:58,438 INFO ]: Computing forward predicates... [2018-06-24 21:15:58,504 INFO ]: Checked inductivity of 3 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 21:15:58,531 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:15:58,531 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2018-06-24 21:15:58,531 INFO ]: Interpolant automaton has 10 states [2018-06-24 21:15:58,531 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-24 21:15:58,531 INFO ]: CoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2018-06-24 21:15:58,531 INFO ]: Start difference. First operand 23 states and 37 transitions. Second operand 10 states. [2018-06-24 21:15:59,005 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:15:59,005 INFO ]: Finished difference Result 27 states and 39 transitions. [2018-06-24 21:15:59,007 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-24 21:15:59,007 INFO ]: Start accepts. Automaton has 10 states. Word has length 10 [2018-06-24 21:15:59,007 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:15:59,008 INFO ]: With dead ends: 27 [2018-06-24 21:15:59,008 INFO ]: Without dead ends: 23 [2018-06-24 21:15:59,008 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2018-06-24 21:15:59,009 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-24 21:15:59,012 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-24 21:15:59,012 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-24 21:15:59,014 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 35 transitions. [2018-06-24 21:15:59,014 INFO ]: Start accepts. Automaton has 23 states and 35 transitions. Word has length 10 [2018-06-24 21:15:59,014 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:15:59,014 INFO ]: Abstraction has 23 states and 35 transitions. [2018-06-24 21:15:59,014 INFO ]: Interpolant automaton has 10 states. [2018-06-24 21:15:59,014 INFO ]: Start isEmpty. Operand 23 states and 35 transitions. [2018-06-24 21:15:59,015 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-24 21:15:59,015 INFO ]: Found error trace [2018-06-24 21:15:59,015 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:15:59,015 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:15:59,015 INFO ]: Analyzing trace with hash 1429840446, now seen corresponding path program 1 times [2018-06-24 21:15:59,015 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:15:59,015 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:15:59,016 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:15:59,016 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:15:59,016 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:15:59,026 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:15:59,235 INFO ]: Checked inductivity of 3 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 21:15:59,236 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:15:59,236 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-24 21:15:59,242 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:15:59,272 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:15:59,274 INFO ]: Computing forward predicates... [2018-06-24 21:15:59,326 INFO ]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 21:15:59,346 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-24 21:15:59,346 INFO ]: Number of different interpolants: perfect sequences [6] imperfect sequences [6] total 8 [2018-06-24 21:15:59,346 INFO ]: Interpolant automaton has 8 states [2018-06-24 21:15:59,346 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-24 21:15:59,346 INFO ]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-06-24 21:15:59,347 INFO ]: Start difference. First operand 23 states and 35 transitions. Second operand 8 states. [2018-06-24 21:15:59,427 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:15:59,427 INFO ]: Finished difference Result 29 states and 42 transitions. [2018-06-24 21:15:59,427 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-24 21:15:59,427 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-24 21:15:59,427 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:15:59,428 INFO ]: With dead ends: 29 [2018-06-24 21:15:59,428 INFO ]: Without dead ends: 23 [2018-06-24 21:15:59,429 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=34, Invalid=76, Unknown=0, NotChecked=0, Total=110 [2018-06-24 21:15:59,429 INFO ]: Start minimizeSevpa. Operand 23 states. [2018-06-24 21:15:59,432 INFO ]: Finished minimizeSevpa. Reduced states from 23 to 23. [2018-06-24 21:15:59,432 INFO ]: Start removeUnreachable. Operand 23 states. [2018-06-24 21:15:59,433 INFO ]: Finished removeUnreachable. Reduced from 23 states to 23 states and 33 transitions. [2018-06-24 21:15:59,433 INFO ]: Start accepts. Automaton has 23 states and 33 transitions. Word has length 10 [2018-06-24 21:15:59,433 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:15:59,433 INFO ]: Abstraction has 23 states and 33 transitions. [2018-06-24 21:15:59,433 INFO ]: Interpolant automaton has 8 states. [2018-06-24 21:15:59,433 INFO ]: Start isEmpty. Operand 23 states and 33 transitions. [2018-06-24 21:15:59,434 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-24 21:15:59,434 INFO ]: Found error trace [2018-06-24 21:15:59,434 INFO ]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2018-06-24 21:15:59,434 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:15:59,435 INFO ]: Analyzing trace with hash 1541744881, now seen corresponding path program 1 times [2018-06-24 21:15:59,435 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:15:59,435 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:15:59,435 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:15:59,435 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:15:59,435 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:15:59,448 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:15:59,525 INFO ]: Checked inductivity of 9 backedges. 3 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-24 21:15:59,525 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:15:59,525 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-24 21:15:59,531 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:15:59,560 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:15:59,562 INFO ]: Computing forward predicates... [2018-06-24 21:15:59,754 INFO ]: Checked inductivity of 9 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-24 21:15:59,773 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:15:59,773 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 7] total 14 [2018-06-24 21:15:59,773 INFO ]: Interpolant automaton has 14 states [2018-06-24 21:15:59,774 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-24 21:15:59,774 INFO ]: CoverageRelationStatistics Valid=29, Invalid=153, Unknown=0, NotChecked=0, Total=182 [2018-06-24 21:15:59,774 INFO ]: Start difference. First operand 23 states and 33 transitions. Second operand 14 states. [2018-06-24 21:16:00,085 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:00,085 INFO ]: Finished difference Result 33 states and 52 transitions. [2018-06-24 21:16:00,086 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2018-06-24 21:16:00,086 INFO ]: Start accepts. Automaton has 14 states. Word has length 14 [2018-06-24 21:16:00,086 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:00,087 INFO ]: With dead ends: 33 [2018-06-24 21:16:00,087 INFO ]: Without dead ends: 33 [2018-06-24 21:16:00,087 INFO ]: 0 DeclaredPredicates, 30 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 52 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=72, Invalid=390, Unknown=0, NotChecked=0, Total=462 [2018-06-24 21:16:00,087 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-24 21:16:00,094 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 30. [2018-06-24 21:16:00,094 INFO ]: Start removeUnreachable. Operand 30 states. [2018-06-24 21:16:00,095 INFO ]: Finished removeUnreachable. Reduced from 30 states to 30 states and 45 transitions. [2018-06-24 21:16:00,095 INFO ]: Start accepts. Automaton has 30 states and 45 transitions. Word has length 14 [2018-06-24 21:16:00,095 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:00,095 INFO ]: Abstraction has 30 states and 45 transitions. [2018-06-24 21:16:00,095 INFO ]: Interpolant automaton has 14 states. [2018-06-24 21:16:00,095 INFO ]: Start isEmpty. Operand 30 states and 45 transitions. [2018-06-24 21:16:00,096 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-24 21:16:00,096 INFO ]: Found error trace [2018-06-24 21:16:00,096 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:16:00,096 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:00,096 INFO ]: Analyzing trace with hash -690934295, now seen corresponding path program 1 times [2018-06-24 21:16:00,097 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:00,097 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:00,097 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:00,097 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:00,097 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:00,113 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:00,265 INFO ]: Checked inductivity of 9 backedges. 2 proven. 4 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-24 21:16:00,265 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:00,265 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-24 21:16:00,272 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:00,291 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:00,293 INFO ]: Computing forward predicates... [2018-06-24 21:16:00,419 INFO ]: Checked inductivity of 9 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-24 21:16:00,439 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-24 21:16:00,439 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [8] total 9 [2018-06-24 21:16:00,439 INFO ]: Interpolant automaton has 9 states [2018-06-24 21:16:00,439 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-24 21:16:00,439 INFO ]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-06-24 21:16:00,439 INFO ]: Start difference. First operand 30 states and 45 transitions. Second operand 9 states. [2018-06-24 21:16:00,542 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:00,543 INFO ]: Finished difference Result 34 states and 49 transitions. [2018-06-24 21:16:00,543 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-24 21:16:00,543 INFO ]: Start accepts. Automaton has 9 states. Word has length 15 [2018-06-24 21:16:00,543 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:00,544 INFO ]: With dead ends: 34 [2018-06-24 21:16:00,544 INFO ]: Without dead ends: 26 [2018-06-24 21:16:00,544 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=33, Invalid=99, Unknown=0, NotChecked=0, Total=132 [2018-06-24 21:16:00,544 INFO ]: Start minimizeSevpa. Operand 26 states. [2018-06-24 21:16:00,547 INFO ]: Finished minimizeSevpa. Reduced states from 26 to 26. [2018-06-24 21:16:00,547 INFO ]: Start removeUnreachable. Operand 26 states. [2018-06-24 21:16:00,548 INFO ]: Finished removeUnreachable. Reduced from 26 states to 26 states and 35 transitions. [2018-06-24 21:16:00,548 INFO ]: Start accepts. Automaton has 26 states and 35 transitions. Word has length 15 [2018-06-24 21:16:00,549 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:00,549 INFO ]: Abstraction has 26 states and 35 transitions. [2018-06-24 21:16:00,549 INFO ]: Interpolant automaton has 9 states. [2018-06-24 21:16:00,549 INFO ]: Start isEmpty. Operand 26 states and 35 transitions. [2018-06-24 21:16:00,549 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-24 21:16:00,549 INFO ]: Found error trace [2018-06-24 21:16:00,549 INFO ]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:16:00,550 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:00,550 INFO ]: Analyzing trace with hash 548539206, now seen corresponding path program 1 times [2018-06-24 21:16:00,550 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:00,550 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:00,550 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:00,550 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:00,550 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:00,567 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:00,660 INFO ]: Checked inductivity of 11 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-24 21:16:00,660 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:00,660 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-24 21:16:00,669 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:00,684 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:00,686 INFO ]: Computing forward predicates... [2018-06-24 21:16:00,757 INFO ]: Checked inductivity of 11 backedges. 2 proven. 6 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-24 21:16:00,785 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:00,785 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 13 [2018-06-24 21:16:00,785 INFO ]: Interpolant automaton has 13 states [2018-06-24 21:16:00,785 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-24 21:16:00,785 INFO ]: CoverageRelationStatistics Valid=27, Invalid=129, Unknown=0, NotChecked=0, Total=156 [2018-06-24 21:16:00,785 INFO ]: Start difference. First operand 26 states and 35 transitions. Second operand 13 states. [2018-06-24 21:16:01,105 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:01,105 INFO ]: Finished difference Result 33 states and 44 transitions. [2018-06-24 21:16:01,105 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2018-06-24 21:16:01,105 INFO ]: Start accepts. Automaton has 13 states. Word has length 15 [2018-06-24 21:16:01,105 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:01,106 INFO ]: With dead ends: 33 [2018-06-24 21:16:01,106 INFO ]: Without dead ends: 33 [2018-06-24 21:16:01,106 INFO ]: 0 DeclaredPredicates, 31 GetRequests, 10 SyntacticMatches, 2 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 57 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=70, Invalid=350, Unknown=0, NotChecked=0, Total=420 [2018-06-24 21:16:01,106 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-24 21:16:01,110 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 31. [2018-06-24 21:16:01,110 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-24 21:16:01,111 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 42 transitions. [2018-06-24 21:16:01,111 INFO ]: Start accepts. Automaton has 31 states and 42 transitions. Word has length 15 [2018-06-24 21:16:01,112 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:01,112 INFO ]: Abstraction has 31 states and 42 transitions. [2018-06-24 21:16:01,112 INFO ]: Interpolant automaton has 13 states. [2018-06-24 21:16:01,112 INFO ]: Start isEmpty. Operand 31 states and 42 transitions. [2018-06-24 21:16:01,112 INFO ]: Finished isEmpty. Found accepting run of length 17 [2018-06-24 21:16:01,112 INFO ]: Found error trace [2018-06-24 21:16:01,112 INFO ]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1] [2018-06-24 21:16:01,113 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:01,113 INFO ]: Analyzing trace with hash -176065647, now seen corresponding path program 2 times [2018-06-24 21:16:01,113 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:01,113 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:01,113 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:01,113 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:01,113 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:01,129 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:01,220 INFO ]: Checked inductivity of 14 backedges. 3 proven. 8 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-24 21:16:01,220 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:01,220 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-24 21:16:01,233 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:16:01,252 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:16:01,252 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:01,253 INFO ]: Computing forward predicates... [2018-06-24 21:16:01,312 INFO ]: Checked inductivity of 14 backedges. 7 proven. 4 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-24 21:16:01,331 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:01,331 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 15 [2018-06-24 21:16:01,331 INFO ]: Interpolant automaton has 15 states [2018-06-24 21:16:01,332 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-24 21:16:01,332 INFO ]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2018-06-24 21:16:01,332 INFO ]: Start difference. First operand 31 states and 42 transitions. Second operand 15 states. [2018-06-24 21:16:01,899 WARN ]: Spent 102.00 ms on a formula simplification that was a NOOP. DAG size: 11 [2018-06-24 21:16:01,903 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:01,903 INFO ]: Finished difference Result 47 states and 64 transitions. [2018-06-24 21:16:01,903 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 19 states. [2018-06-24 21:16:01,903 INFO ]: Start accepts. Automaton has 15 states. Word has length 16 [2018-06-24 21:16:01,903 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:01,904 INFO ]: With dead ends: 47 [2018-06-24 21:16:01,904 INFO ]: Without dead ends: 38 [2018-06-24 21:16:01,904 INFO ]: 0 DeclaredPredicates, 38 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=112, Invalid=538, Unknown=0, NotChecked=0, Total=650 [2018-06-24 21:16:01,904 INFO ]: Start minimizeSevpa. Operand 38 states. [2018-06-24 21:16:01,909 INFO ]: Finished minimizeSevpa. Reduced states from 38 to 38. [2018-06-24 21:16:01,909 INFO ]: Start removeUnreachable. Operand 38 states. [2018-06-24 21:16:01,910 INFO ]: Finished removeUnreachable. Reduced from 38 states to 38 states and 50 transitions. [2018-06-24 21:16:01,910 INFO ]: Start accepts. Automaton has 38 states and 50 transitions. Word has length 16 [2018-06-24 21:16:01,910 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:01,910 INFO ]: Abstraction has 38 states and 50 transitions. [2018-06-24 21:16:01,910 INFO ]: Interpolant automaton has 15 states. [2018-06-24 21:16:01,910 INFO ]: Start isEmpty. Operand 38 states and 50 transitions. [2018-06-24 21:16:01,911 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-24 21:16:01,911 INFO ]: Found error trace [2018-06-24 21:16:01,911 INFO ]: trace histogram [3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1] [2018-06-24 21:16:01,911 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:01,911 INFO ]: Analyzing trace with hash 1604517395, now seen corresponding path program 3 times [2018-06-24 21:16:01,911 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:01,911 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:01,913 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:01,913 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:01,913 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:01,932 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:02,266 INFO ]: Checked inductivity of 28 backedges. 5 proven. 16 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-24 21:16:02,266 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:02,266 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-24 21:16:02,272 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:16:02,292 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-24 21:16:02,292 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:02,294 INFO ]: Computing forward predicates... [2018-06-24 21:16:02,421 INFO ]: Checked inductivity of 28 backedges. 8 proven. 12 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-24 21:16:02,439 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:02,439 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 11] total 21 [2018-06-24 21:16:02,440 INFO ]: Interpolant automaton has 21 states [2018-06-24 21:16:02,440 INFO ]: Constructing interpolant automaton starting with 21 interpolants. [2018-06-24 21:16:02,440 INFO ]: CoverageRelationStatistics Valid=52, Invalid=368, Unknown=0, NotChecked=0, Total=420 [2018-06-24 21:16:02,440 INFO ]: Start difference. First operand 38 states and 50 transitions. Second operand 21 states. [2018-06-24 21:16:03,007 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:03,007 INFO ]: Finished difference Result 66 states and 87 transitions. [2018-06-24 21:16:03,008 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2018-06-24 21:16:03,008 INFO ]: Start accepts. Automaton has 21 states. Word has length 21 [2018-06-24 21:16:03,008 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:03,009 INFO ]: With dead ends: 66 [2018-06-24 21:16:03,009 INFO ]: Without dead ends: 63 [2018-06-24 21:16:03,010 INFO ]: 0 DeclaredPredicates, 61 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 490 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=210, Invalid=1770, Unknown=0, NotChecked=0, Total=1980 [2018-06-24 21:16:03,010 INFO ]: Start minimizeSevpa. Operand 63 states. [2018-06-24 21:16:03,016 INFO ]: Finished minimizeSevpa. Reduced states from 63 to 57. [2018-06-24 21:16:03,016 INFO ]: Start removeUnreachable. Operand 57 states. [2018-06-24 21:16:03,017 INFO ]: Finished removeUnreachable. Reduced from 57 states to 57 states and 75 transitions. [2018-06-24 21:16:03,017 INFO ]: Start accepts. Automaton has 57 states and 75 transitions. Word has length 21 [2018-06-24 21:16:03,017 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:03,017 INFO ]: Abstraction has 57 states and 75 transitions. [2018-06-24 21:16:03,017 INFO ]: Interpolant automaton has 21 states. [2018-06-24 21:16:03,018 INFO ]: Start isEmpty. Operand 57 states and 75 transitions. [2018-06-24 21:16:03,018 INFO ]: Finished isEmpty. Found accepting run of length 23 [2018-06-24 21:16:03,018 INFO ]: Found error trace [2018-06-24 21:16:03,019 INFO ]: trace histogram [3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1] [2018-06-24 21:16:03,019 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:03,019 INFO ]: Analyzing trace with hash -1800480156, now seen corresponding path program 4 times [2018-06-24 21:16:03,019 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:03,019 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:03,020 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:03,020 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:03,020 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:03,033 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:03,170 INFO ]: Checked inductivity of 33 backedges. 3 proven. 22 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-24 21:16:03,170 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:03,170 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-24 21:16:03,176 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-24 21:16:03,197 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-24 21:16:03,197 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:03,200 INFO ]: Computing forward predicates... [2018-06-24 21:16:03,329 INFO ]: Checked inductivity of 33 backedges. 3 proven. 22 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2018-06-24 21:16:03,348 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:03,348 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 16 [2018-06-24 21:16:03,349 INFO ]: Interpolant automaton has 16 states [2018-06-24 21:16:03,349 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-24 21:16:03,349 INFO ]: CoverageRelationStatistics Valid=34, Invalid=206, Unknown=0, NotChecked=0, Total=240 [2018-06-24 21:16:03,349 INFO ]: Start difference. First operand 57 states and 75 transitions. Second operand 16 states. [2018-06-24 21:16:03,676 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:03,676 INFO ]: Finished difference Result 69 states and 87 transitions. [2018-06-24 21:16:03,679 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-06-24 21:16:03,679 INFO ]: Start accepts. Automaton has 16 states. Word has length 22 [2018-06-24 21:16:03,679 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:03,680 INFO ]: With dead ends: 69 [2018-06-24 21:16:03,680 INFO ]: Without dead ends: 61 [2018-06-24 21:16:03,680 INFO ]: 0 DeclaredPredicates, 45 GetRequests, 16 SyntacticMatches, 3 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 120 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=99, Invalid=657, Unknown=0, NotChecked=0, Total=756 [2018-06-24 21:16:03,680 INFO ]: Start minimizeSevpa. Operand 61 states. [2018-06-24 21:16:03,686 INFO ]: Finished minimizeSevpa. Reduced states from 61 to 61. [2018-06-24 21:16:03,686 INFO ]: Start removeUnreachable. Operand 61 states. [2018-06-24 21:16:03,687 INFO ]: Finished removeUnreachable. Reduced from 61 states to 61 states and 79 transitions. [2018-06-24 21:16:03,687 INFO ]: Start accepts. Automaton has 61 states and 79 transitions. Word has length 22 [2018-06-24 21:16:03,687 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:03,687 INFO ]: Abstraction has 61 states and 79 transitions. [2018-06-24 21:16:03,687 INFO ]: Interpolant automaton has 16 states. [2018-06-24 21:16:03,687 INFO ]: Start isEmpty. Operand 61 states and 79 transitions. [2018-06-24 21:16:03,688 INFO ]: Finished isEmpty. Found accepting run of length 30 [2018-06-24 21:16:03,688 INFO ]: Found error trace [2018-06-24 21:16:03,689 INFO ]: trace histogram [5, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1] [2018-06-24 21:16:03,689 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:03,689 INFO ]: Analyzing trace with hash 450088686, now seen corresponding path program 5 times [2018-06-24 21:16:03,689 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:03,689 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:03,689 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:03,689 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:03,689 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:03,704 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:03,880 INFO ]: Checked inductivity of 68 backedges. 21 proven. 32 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-24 21:16:03,880 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:03,880 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:16:03,886 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-24 21:16:03,948 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2018-06-24 21:16:03,948 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:03,951 INFO ]: Computing forward predicates... [2018-06-24 21:16:04,045 INFO ]: Checked inductivity of 68 backedges. 33 proven. 15 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2018-06-24 21:16:04,064 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:04,064 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 11] total 20 [2018-06-24 21:16:04,065 INFO ]: Interpolant automaton has 20 states [2018-06-24 21:16:04,065 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-24 21:16:04,065 INFO ]: CoverageRelationStatistics Valid=55, Invalid=325, Unknown=0, NotChecked=0, Total=380 [2018-06-24 21:16:04,065 INFO ]: Start difference. First operand 61 states and 79 transitions. Second operand 20 states. [2018-06-24 21:16:04,368 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:04,368 INFO ]: Finished difference Result 69 states and 87 transitions. [2018-06-24 21:16:04,368 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 25 states. [2018-06-24 21:16:04,368 INFO ]: Start accepts. Automaton has 20 states. Word has length 29 [2018-06-24 21:16:04,368 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:04,369 INFO ]: With dead ends: 69 [2018-06-24 21:16:04,369 INFO ]: Without dead ends: 69 [2018-06-24 21:16:04,369 INFO ]: 0 DeclaredPredicates, 56 GetRequests, 25 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 158 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=148, Invalid=908, Unknown=0, NotChecked=0, Total=1056 [2018-06-24 21:16:04,369 INFO ]: Start minimizeSevpa. Operand 69 states. [2018-06-24 21:16:04,375 INFO ]: Finished minimizeSevpa. Reduced states from 69 to 58. [2018-06-24 21:16:04,375 INFO ]: Start removeUnreachable. Operand 58 states. [2018-06-24 21:16:04,376 INFO ]: Finished removeUnreachable. Reduced from 58 states to 58 states and 73 transitions. [2018-06-24 21:16:04,376 INFO ]: Start accepts. Automaton has 58 states and 73 transitions. Word has length 29 [2018-06-24 21:16:04,376 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:04,376 INFO ]: Abstraction has 58 states and 73 transitions. [2018-06-24 21:16:04,376 INFO ]: Interpolant automaton has 20 states. [2018-06-24 21:16:04,376 INFO ]: Start isEmpty. Operand 58 states and 73 transitions. [2018-06-24 21:16:04,377 INFO ]: Finished isEmpty. Found accepting run of length 31 [2018-06-24 21:16:04,377 INFO ]: Found error trace [2018-06-24 21:16:04,377 INFO ]: trace histogram [6, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1] [2018-06-24 21:16:04,377 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:04,377 INFO ]: Analyzing trace with hash 1066935529, now seen corresponding path program 6 times [2018-06-24 21:16:04,377 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:04,377 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:04,378 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:04,378 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:04,378 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:04,394 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:04,543 INFO ]: Checked inductivity of 77 backedges. 4 proven. 56 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-06-24 21:16:04,543 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:04,543 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-24 21:16:04,561 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-24 21:16:04,598 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 6 check-sat command(s) [2018-06-24 21:16:04,599 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:04,602 INFO ]: Computing forward predicates... [2018-06-24 21:16:05,067 INFO ]: Checked inductivity of 77 backedges. 4 proven. 56 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2018-06-24 21:16:05,086 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:05,086 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 19 [2018-06-24 21:16:05,086 INFO ]: Interpolant automaton has 19 states [2018-06-24 21:16:05,087 INFO ]: Constructing interpolant automaton starting with 19 interpolants. [2018-06-24 21:16:05,087 INFO ]: CoverageRelationStatistics Valid=41, Invalid=301, Unknown=0, NotChecked=0, Total=342 [2018-06-24 21:16:05,087 INFO ]: Start difference. First operand 58 states and 73 transitions. Second operand 19 states. [2018-06-24 21:16:05,556 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:05,556 INFO ]: Finished difference Result 73 states and 90 transitions. [2018-06-24 21:16:05,557 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-06-24 21:16:05,557 INFO ]: Start accepts. Automaton has 19 states. Word has length 30 [2018-06-24 21:16:05,557 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:05,558 INFO ]: With dead ends: 73 [2018-06-24 21:16:05,558 INFO ]: Without dead ends: 73 [2018-06-24 21:16:05,558 INFO ]: 0 DeclaredPredicates, 59 GetRequests, 23 SyntacticMatches, 4 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 188 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=126, Invalid=996, Unknown=0, NotChecked=0, Total=1122 [2018-06-24 21:16:05,559 INFO ]: Start minimizeSevpa. Operand 73 states. [2018-06-24 21:16:05,564 INFO ]: Finished minimizeSevpa. Reduced states from 73 to 67. [2018-06-24 21:16:05,564 INFO ]: Start removeUnreachable. Operand 67 states. [2018-06-24 21:16:05,565 INFO ]: Finished removeUnreachable. Reduced from 67 states to 67 states and 84 transitions. [2018-06-24 21:16:05,565 INFO ]: Start accepts. Automaton has 67 states and 84 transitions. Word has length 30 [2018-06-24 21:16:05,565 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:05,565 INFO ]: Abstraction has 67 states and 84 transitions. [2018-06-24 21:16:05,565 INFO ]: Interpolant automaton has 19 states. [2018-06-24 21:16:05,565 INFO ]: Start isEmpty. Operand 67 states and 84 transitions. [2018-06-24 21:16:05,566 INFO ]: Finished isEmpty. Found accepting run of length 32 [2018-06-24 21:16:05,566 INFO ]: Found error trace [2018-06-24 21:16:05,566 INFO ]: trace histogram [7, 4, 4, 4, 4, 3, 1, 1, 1, 1, 1] [2018-06-24 21:16:05,566 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:05,566 INFO ]: Analyzing trace with hash -1285648818, now seen corresponding path program 7 times [2018-06-24 21:16:05,566 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:05,566 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:05,567 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:05,567 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:05,567 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:05,582 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:05,863 INFO ]: Checked inductivity of 87 backedges. 28 proven. 44 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-24 21:16:05,863 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:05,863 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-24 21:16:05,870 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:05,899 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:05,902 INFO ]: Computing forward predicates... [2018-06-24 21:16:06,053 INFO ]: Checked inductivity of 87 backedges. 46 proven. 21 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2018-06-24 21:16:06,073 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:06,073 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 22 [2018-06-24 21:16:06,073 INFO ]: Interpolant automaton has 22 states [2018-06-24 21:16:06,073 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-24 21:16:06,074 INFO ]: CoverageRelationStatistics Valid=70, Invalid=392, Unknown=0, NotChecked=0, Total=462 [2018-06-24 21:16:06,074 INFO ]: Start difference. First operand 67 states and 84 transitions. Second operand 22 states. [2018-06-24 21:16:06,446 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:06,447 INFO ]: Finished difference Result 97 states and 120 transitions. [2018-06-24 21:16:06,447 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-06-24 21:16:06,447 INFO ]: Start accepts. Automaton has 22 states. Word has length 31 [2018-06-24 21:16:06,447 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:06,448 INFO ]: With dead ends: 97 [2018-06-24 21:16:06,448 INFO ]: Without dead ends: 84 [2018-06-24 21:16:06,448 INFO ]: 0 DeclaredPredicates, 66 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 265 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=264, Invalid=1296, Unknown=0, NotChecked=0, Total=1560 [2018-06-24 21:16:06,449 INFO ]: Start minimizeSevpa. Operand 84 states. [2018-06-24 21:16:06,456 INFO ]: Finished minimizeSevpa. Reduced states from 84 to 74. [2018-06-24 21:16:06,456 INFO ]: Start removeUnreachable. Operand 74 states. [2018-06-24 21:16:06,457 INFO ]: Finished removeUnreachable. Reduced from 74 states to 74 states and 92 transitions. [2018-06-24 21:16:06,457 INFO ]: Start accepts. Automaton has 74 states and 92 transitions. Word has length 31 [2018-06-24 21:16:06,458 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:06,458 INFO ]: Abstraction has 74 states and 92 transitions. [2018-06-24 21:16:06,458 INFO ]: Interpolant automaton has 22 states. [2018-06-24 21:16:06,458 INFO ]: Start isEmpty. Operand 74 states and 92 transitions. [2018-06-24 21:16:06,459 INFO ]: Finished isEmpty. Found accepting run of length 39 [2018-06-24 21:16:06,459 INFO ]: Found error trace [2018-06-24 21:16:06,459 INFO ]: trace histogram [9, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1] [2018-06-24 21:16:06,459 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:06,459 INFO ]: Analyzing trace with hash -1930220626, now seen corresponding path program 8 times [2018-06-24 21:16:06,459 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:06,459 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:06,459 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:06,459 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:06,459 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:06,481 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:06,935 INFO ]: Checked inductivity of 141 backedges. 54 proven. 52 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2018-06-24 21:16:06,935 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:06,935 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-24 21:16:06,941 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:16:06,990 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:16:06,990 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:06,994 INFO ]: Computing forward predicates... [2018-06-24 21:16:07,248 INFO ]: Checked inductivity of 141 backedges. 70 proven. 26 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-24 21:16:07,267 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:07,268 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 13] total 23 [2018-06-24 21:16:07,268 INFO ]: Interpolant automaton has 23 states [2018-06-24 21:16:07,268 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-24 21:16:07,268 INFO ]: CoverageRelationStatistics Valid=73, Invalid=433, Unknown=0, NotChecked=0, Total=506 [2018-06-24 21:16:07,268 INFO ]: Start difference. First operand 74 states and 92 transitions. Second operand 23 states. [2018-06-24 21:16:08,183 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:08,183 INFO ]: Finished difference Result 77 states and 95 transitions. [2018-06-24 21:16:08,183 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-06-24 21:16:08,183 INFO ]: Start accepts. Automaton has 23 states. Word has length 38 [2018-06-24 21:16:08,183 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:08,184 INFO ]: With dead ends: 77 [2018-06-24 21:16:08,184 INFO ]: Without dead ends: 77 [2018-06-24 21:16:08,185 INFO ]: 0 DeclaredPredicates, 70 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 253 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=206, Invalid=1276, Unknown=0, NotChecked=0, Total=1482 [2018-06-24 21:16:08,185 INFO ]: Start minimizeSevpa. Operand 77 states. [2018-06-24 21:16:08,190 INFO ]: Finished minimizeSevpa. Reduced states from 77 to 77. [2018-06-24 21:16:08,190 INFO ]: Start removeUnreachable. Operand 77 states. [2018-06-24 21:16:08,191 INFO ]: Finished removeUnreachable. Reduced from 77 states to 77 states and 95 transitions. [2018-06-24 21:16:08,191 INFO ]: Start accepts. Automaton has 77 states and 95 transitions. Word has length 38 [2018-06-24 21:16:08,191 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:08,191 INFO ]: Abstraction has 77 states and 95 transitions. [2018-06-24 21:16:08,191 INFO ]: Interpolant automaton has 23 states. [2018-06-24 21:16:08,191 INFO ]: Start isEmpty. Operand 77 states and 95 transitions. [2018-06-24 21:16:08,194 INFO ]: Finished isEmpty. Found accepting run of length 40 [2018-06-24 21:16:08,194 INFO ]: Found error trace [2018-06-24 21:16:08,194 INFO ]: trace histogram [10, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1] [2018-06-24 21:16:08,195 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:08,195 INFO ]: Analyzing trace with hash 291790889, now seen corresponding path program 9 times [2018-06-24 21:16:08,195 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:08,195 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:08,195 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:08,195 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:08,195 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:08,221 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:09,020 INFO ]: Checked inductivity of 155 backedges. 5 proven. 119 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-06-24 21:16:09,020 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:09,020 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-24 21:16:09,025 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:16:09,062 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 6 check-sat command(s) [2018-06-24 21:16:09,063 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:09,066 INFO ]: Computing forward predicates... [2018-06-24 21:16:09,243 INFO ]: Checked inductivity of 155 backedges. 5 proven. 119 refuted. 0 times theorem prover too weak. 31 trivial. 0 not checked. [2018-06-24 21:16:09,262 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:09,262 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 22 [2018-06-24 21:16:09,262 INFO ]: Interpolant automaton has 22 states [2018-06-24 21:16:09,262 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-24 21:16:09,262 INFO ]: CoverageRelationStatistics Valid=48, Invalid=414, Unknown=0, NotChecked=0, Total=462 [2018-06-24 21:16:09,263 INFO ]: Start difference. First operand 77 states and 95 transitions. Second operand 22 states. [2018-06-24 21:16:09,790 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:09,790 INFO ]: Finished difference Result 95 states and 115 transitions. [2018-06-24 21:16:09,790 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 32 states. [2018-06-24 21:16:09,790 INFO ]: Start accepts. Automaton has 22 states. Word has length 39 [2018-06-24 21:16:09,790 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:09,791 INFO ]: With dead ends: 95 [2018-06-24 21:16:09,791 INFO ]: Without dead ends: 95 [2018-06-24 21:16:09,792 INFO ]: 0 DeclaredPredicates, 74 GetRequests, 31 SyntacticMatches, 5 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 268 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=155, Invalid=1405, Unknown=0, NotChecked=0, Total=1560 [2018-06-24 21:16:09,792 INFO ]: Start minimizeSevpa. Operand 95 states. [2018-06-24 21:16:09,800 INFO ]: Finished minimizeSevpa. Reduced states from 95 to 87. [2018-06-24 21:16:09,800 INFO ]: Start removeUnreachable. Operand 87 states. [2018-06-24 21:16:09,801 INFO ]: Finished removeUnreachable. Reduced from 87 states to 87 states and 107 transitions. [2018-06-24 21:16:09,801 INFO ]: Start accepts. Automaton has 87 states and 107 transitions. Word has length 39 [2018-06-24 21:16:09,801 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:09,801 INFO ]: Abstraction has 87 states and 107 transitions. [2018-06-24 21:16:09,801 INFO ]: Interpolant automaton has 22 states. [2018-06-24 21:16:09,801 INFO ]: Start isEmpty. Operand 87 states and 107 transitions. [2018-06-24 21:16:09,802 INFO ]: Finished isEmpty. Found accepting run of length 41 [2018-06-24 21:16:09,802 INFO ]: Found error trace [2018-06-24 21:16:09,802 INFO ]: trace histogram [11, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1] [2018-06-24 21:16:09,802 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:09,802 INFO ]: Analyzing trace with hash 454671118, now seen corresponding path program 10 times [2018-06-24 21:16:09,802 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:09,802 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:09,803 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:09,803 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:09,803 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:09,827 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:10,143 INFO ]: Checked inductivity of 170 backedges. 69 proven. 66 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2018-06-24 21:16:10,144 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:10,144 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-24 21:16:10,149 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-24 21:16:10,186 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-24 21:16:10,186 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:10,189 INFO ]: Computing forward predicates... [2018-06-24 21:16:10,398 INFO ]: Checked inductivity of 170 backedges. 91 proven. 34 refuted. 0 times theorem prover too weak. 45 trivial. 0 not checked. [2018-06-24 21:16:10,420 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:10,420 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 15] total 25 [2018-06-24 21:16:10,420 INFO ]: Interpolant automaton has 25 states [2018-06-24 21:16:10,420 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-24 21:16:10,420 INFO ]: CoverageRelationStatistics Valid=92, Invalid=508, Unknown=0, NotChecked=0, Total=600 [2018-06-24 21:16:10,420 INFO ]: Start difference. First operand 87 states and 107 transitions. Second operand 25 states. [2018-06-24 21:16:10,844 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:10,844 INFO ]: Finished difference Result 128 states and 154 transitions. [2018-06-24 21:16:10,844 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-06-24 21:16:10,844 INFO ]: Start accepts. Automaton has 25 states. Word has length 40 [2018-06-24 21:16:10,844 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:10,845 INFO ]: With dead ends: 128 [2018-06-24 21:16:10,845 INFO ]: Without dead ends: 113 [2018-06-24 21:16:10,846 INFO ]: 0 DeclaredPredicates, 80 GetRequests, 36 SyntacticMatches, 0 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 387 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=351, Invalid=1719, Unknown=0, NotChecked=0, Total=2070 [2018-06-24 21:16:10,846 INFO ]: Start minimizeSevpa. Operand 113 states. [2018-06-24 21:16:10,852 INFO ]: Finished minimizeSevpa. Reduced states from 113 to 95. [2018-06-24 21:16:10,852 INFO ]: Start removeUnreachable. Operand 95 states. [2018-06-24 21:16:10,853 INFO ]: Finished removeUnreachable. Reduced from 95 states to 95 states and 116 transitions. [2018-06-24 21:16:10,853 INFO ]: Start accepts. Automaton has 95 states and 116 transitions. Word has length 40 [2018-06-24 21:16:10,853 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:10,853 INFO ]: Abstraction has 95 states and 116 transitions. [2018-06-24 21:16:10,853 INFO ]: Interpolant automaton has 25 states. [2018-06-24 21:16:10,853 INFO ]: Start isEmpty. Operand 95 states and 116 transitions. [2018-06-24 21:16:10,854 INFO ]: Finished isEmpty. Found accepting run of length 49 [2018-06-24 21:16:10,854 INFO ]: Found error trace [2018-06-24 21:16:10,854 INFO ]: trace histogram [14, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1] [2018-06-24 21:16:10,854 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:10,854 INFO ]: Analyzing trace with hash -57874943, now seen corresponding path program 11 times [2018-06-24 21:16:10,854 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:10,854 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:10,855 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:10,855 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:10,855 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:10,872 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:11,114 INFO ]: Checked inductivity of 262 backedges. 123 proven. 47 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2018-06-24 21:16:11,114 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:11,114 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-24 21:16:11,120 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-24 21:16:11,175 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 7 check-sat command(s) [2018-06-24 21:16:11,175 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:11,178 INFO ]: Computing forward predicates... [2018-06-24 21:16:11,336 INFO ]: Checked inductivity of 262 backedges. 130 proven. 40 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2018-06-24 21:16:11,355 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:11,355 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 23 [2018-06-24 21:16:11,355 INFO ]: Interpolant automaton has 23 states [2018-06-24 21:16:11,356 INFO ]: Constructing interpolant automaton starting with 23 interpolants. [2018-06-24 21:16:11,356 INFO ]: CoverageRelationStatistics Valid=88, Invalid=418, Unknown=0, NotChecked=0, Total=506 [2018-06-24 21:16:11,357 INFO ]: Start difference. First operand 95 states and 116 transitions. Second operand 23 states. [2018-06-24 21:16:11,577 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:11,577 INFO ]: Finished difference Result 98 states and 119 transitions. [2018-06-24 21:16:11,577 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-06-24 21:16:11,577 INFO ]: Start accepts. Automaton has 23 states. Word has length 48 [2018-06-24 21:16:11,577 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:11,578 INFO ]: With dead ends: 98 [2018-06-24 21:16:11,578 INFO ]: Without dead ends: 98 [2018-06-24 21:16:11,578 INFO ]: 0 DeclaredPredicates, 73 GetRequests, 41 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 180 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=208, Invalid=914, Unknown=0, NotChecked=0, Total=1122 [2018-06-24 21:16:11,578 INFO ]: Start minimizeSevpa. Operand 98 states. [2018-06-24 21:16:11,584 INFO ]: Finished minimizeSevpa. Reduced states from 98 to 98. [2018-06-24 21:16:11,584 INFO ]: Start removeUnreachable. Operand 98 states. [2018-06-24 21:16:11,584 INFO ]: Finished removeUnreachable. Reduced from 98 states to 98 states and 119 transitions. [2018-06-24 21:16:11,584 INFO ]: Start accepts. Automaton has 98 states and 119 transitions. Word has length 48 [2018-06-24 21:16:11,584 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:11,584 INFO ]: Abstraction has 98 states and 119 transitions. [2018-06-24 21:16:11,584 INFO ]: Interpolant automaton has 23 states. [2018-06-24 21:16:11,585 INFO ]: Start isEmpty. Operand 98 states and 119 transitions. [2018-06-24 21:16:11,585 INFO ]: Finished isEmpty. Found accepting run of length 50 [2018-06-24 21:16:11,585 INFO ]: Found error trace [2018-06-24 21:16:11,585 INFO ]: trace histogram [15, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1] [2018-06-24 21:16:11,585 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:11,585 INFO ]: Analyzing trace with hash -1795035082, now seen corresponding path program 12 times [2018-06-24 21:16:11,586 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:11,586 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:11,586 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:11,586 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:11,586 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:11,608 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:11,843 INFO ]: Checked inductivity of 282 backedges. 6 proven. 225 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2018-06-24 21:16:11,843 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:11,843 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-24 21:16:11,848 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-24 21:16:11,899 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 8 check-sat command(s) [2018-06-24 21:16:11,899 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:11,903 INFO ]: Computing forward predicates... [2018-06-24 21:16:12,115 INFO ]: Checked inductivity of 282 backedges. 6 proven. 225 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2018-06-24 21:16:12,139 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:12,139 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 25 [2018-06-24 21:16:12,139 INFO ]: Interpolant automaton has 25 states [2018-06-24 21:16:12,140 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-24 21:16:12,140 INFO ]: CoverageRelationStatistics Valid=55, Invalid=545, Unknown=0, NotChecked=0, Total=600 [2018-06-24 21:16:12,140 INFO ]: Start difference. First operand 98 states and 119 transitions. Second operand 25 states. [2018-06-24 21:16:13,019 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:13,019 INFO ]: Finished difference Result 119 states and 142 transitions. [2018-06-24 21:16:13,020 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-06-24 21:16:13,020 INFO ]: Start accepts. Automaton has 25 states. Word has length 49 [2018-06-24 21:16:13,020 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:13,021 INFO ]: With dead ends: 119 [2018-06-24 21:16:13,021 INFO ]: Without dead ends: 119 [2018-06-24 21:16:13,022 INFO ]: 0 DeclaredPredicates, 90 GetRequests, 40 SyntacticMatches, 6 SemanticMatches, 44 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 363 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=186, Invalid=1884, Unknown=0, NotChecked=0, Total=2070 [2018-06-24 21:16:13,022 INFO ]: Start minimizeSevpa. Operand 119 states. [2018-06-24 21:16:13,028 INFO ]: Finished minimizeSevpa. Reduced states from 119 to 109. [2018-06-24 21:16:13,028 INFO ]: Start removeUnreachable. Operand 109 states. [2018-06-24 21:16:13,031 INFO ]: Finished removeUnreachable. Reduced from 109 states to 109 states and 132 transitions. [2018-06-24 21:16:13,031 INFO ]: Start accepts. Automaton has 109 states and 132 transitions. Word has length 49 [2018-06-24 21:16:13,031 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:13,031 INFO ]: Abstraction has 109 states and 132 transitions. [2018-06-24 21:16:13,031 INFO ]: Interpolant automaton has 25 states. [2018-06-24 21:16:13,031 INFO ]: Start isEmpty. Operand 109 states and 132 transitions. [2018-06-24 21:16:13,032 INFO ]: Finished isEmpty. Found accepting run of length 51 [2018-06-24 21:16:13,032 INFO ]: Found error trace [2018-06-24 21:16:13,032 INFO ]: trace histogram [16, 6, 6, 6, 6, 5, 1, 1, 1, 1, 1] [2018-06-24 21:16:13,032 INFO ]: === Iteration 20 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:13,032 INFO ]: Analyzing trace with hash 187575457, now seen corresponding path program 13 times [2018-06-24 21:16:13,032 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:13,032 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:13,033 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:13,033 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:13,033 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:13,053 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:13,979 INFO ]: Checked inductivity of 303 backedges. 150 proven. 61 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2018-06-24 21:16:13,979 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:13,979 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-24 21:16:13,986 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:14,034 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:14,037 INFO ]: Computing forward predicates... [2018-06-24 21:16:14,189 INFO ]: Checked inductivity of 303 backedges. 161 proven. 50 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2018-06-24 21:16:14,208 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:14,208 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 25 [2018-06-24 21:16:14,208 INFO ]: Interpolant automaton has 25 states [2018-06-24 21:16:14,208 INFO ]: Constructing interpolant automaton starting with 25 interpolants. [2018-06-24 21:16:14,209 INFO ]: CoverageRelationStatistics Valid=112, Invalid=488, Unknown=0, NotChecked=0, Total=600 [2018-06-24 21:16:14,209 INFO ]: Start difference. First operand 109 states and 132 transitions. Second operand 25 states. [2018-06-24 21:16:14,946 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:14,946 INFO ]: Finished difference Result 163 states and 192 transitions. [2018-06-24 21:16:14,946 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-06-24 21:16:14,946 INFO ]: Start accepts. Automaton has 25 states. Word has length 50 [2018-06-24 21:16:14,947 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:14,948 INFO ]: With dead ends: 163 [2018-06-24 21:16:14,948 INFO ]: Without dead ends: 146 [2018-06-24 21:16:14,948 INFO ]: 0 DeclaredPredicates, 85 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 402 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=392, Invalid=1500, Unknown=0, NotChecked=0, Total=1892 [2018-06-24 21:16:14,949 INFO ]: Start minimizeSevpa. Operand 146 states. [2018-06-24 21:16:14,957 INFO ]: Finished minimizeSevpa. Reduced states from 146 to 118. [2018-06-24 21:16:14,957 INFO ]: Start removeUnreachable. Operand 118 states. [2018-06-24 21:16:14,958 INFO ]: Finished removeUnreachable. Reduced from 118 states to 118 states and 142 transitions. [2018-06-24 21:16:14,958 INFO ]: Start accepts. Automaton has 118 states and 142 transitions. Word has length 50 [2018-06-24 21:16:14,959 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:14,959 INFO ]: Abstraction has 118 states and 142 transitions. [2018-06-24 21:16:14,959 INFO ]: Interpolant automaton has 25 states. [2018-06-24 21:16:14,959 INFO ]: Start isEmpty. Operand 118 states and 142 transitions. [2018-06-24 21:16:14,962 INFO ]: Finished isEmpty. Found accepting run of length 60 [2018-06-24 21:16:14,962 INFO ]: Found error trace [2018-06-24 21:16:14,962 INFO ]: trace histogram [20, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1] [2018-06-24 21:16:14,962 INFO ]: === Iteration 21 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:14,963 INFO ]: Analyzing trace with hash 1849954883, now seen corresponding path program 14 times [2018-06-24 21:16:14,963 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:14,963 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:14,963 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:14,963 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:14,963 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:14,985 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:15,176 INFO ]: Checked inductivity of 449 backedges. 210 proven. 66 refuted. 0 times theorem prover too weak. 173 trivial. 0 not checked. [2018-06-24 21:16:15,176 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:15,176 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-24 21:16:15,183 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:16:15,239 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:16:15,239 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:15,241 INFO ]: Computing forward predicates... [2018-06-24 21:16:15,381 INFO ]: Checked inductivity of 449 backedges. 219 proven. 57 refuted. 0 times theorem prover too weak. 173 trivial. 0 not checked. [2018-06-24 21:16:15,402 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:15,402 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 17] total 26 [2018-06-24 21:16:15,402 INFO ]: Interpolant automaton has 26 states [2018-06-24 21:16:15,403 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-24 21:16:15,403 INFO ]: CoverageRelationStatistics Valid=114, Invalid=536, Unknown=0, NotChecked=0, Total=650 [2018-06-24 21:16:15,403 INFO ]: Start difference. First operand 118 states and 142 transitions. Second operand 26 states. [2018-06-24 21:16:15,650 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:15,650 INFO ]: Finished difference Result 121 states and 145 transitions. [2018-06-24 21:16:15,650 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-06-24 21:16:15,650 INFO ]: Start accepts. Automaton has 26 states. Word has length 59 [2018-06-24 21:16:15,650 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:15,651 INFO ]: With dead ends: 121 [2018-06-24 21:16:15,651 INFO ]: Without dead ends: 121 [2018-06-24 21:16:15,651 INFO ]: 0 DeclaredPredicates, 88 GetRequests, 51 SyntacticMatches, 0 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 251 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=277, Invalid=1205, Unknown=0, NotChecked=0, Total=1482 [2018-06-24 21:16:15,652 INFO ]: Start minimizeSevpa. Operand 121 states. [2018-06-24 21:16:15,657 INFO ]: Finished minimizeSevpa. Reduced states from 121 to 121. [2018-06-24 21:16:15,657 INFO ]: Start removeUnreachable. Operand 121 states. [2018-06-24 21:16:15,658 INFO ]: Finished removeUnreachable. Reduced from 121 states to 121 states and 145 transitions. [2018-06-24 21:16:15,658 INFO ]: Start accepts. Automaton has 121 states and 145 transitions. Word has length 59 [2018-06-24 21:16:15,658 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:15,658 INFO ]: Abstraction has 121 states and 145 transitions. [2018-06-24 21:16:15,658 INFO ]: Interpolant automaton has 26 states. [2018-06-24 21:16:15,658 INFO ]: Start isEmpty. Operand 121 states and 145 transitions. [2018-06-24 21:16:15,659 INFO ]: Finished isEmpty. Found accepting run of length 61 [2018-06-24 21:16:15,659 INFO ]: Found error trace [2018-06-24 21:16:15,659 INFO ]: trace histogram [21, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1] [2018-06-24 21:16:15,659 INFO ]: === Iteration 22 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:15,659 INFO ]: Analyzing trace with hash 1513114676, now seen corresponding path program 15 times [2018-06-24 21:16:15,659 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:15,659 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:15,660 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:15,660 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:15,660 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:15,686 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:15,969 INFO ]: Checked inductivity of 476 backedges. 7 proven. 391 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2018-06-24 21:16:15,969 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:15,969 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-24 21:16:15,975 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:16:16,142 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 8 check-sat command(s) [2018-06-24 21:16:16,142 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:16,147 INFO ]: Computing forward predicates... [2018-06-24 21:16:16,543 INFO ]: Checked inductivity of 476 backedges. 7 proven. 391 refuted. 0 times theorem prover too weak. 78 trivial. 0 not checked. [2018-06-24 21:16:16,562 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:16,562 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 28 [2018-06-24 21:16:16,562 INFO ]: Interpolant automaton has 28 states [2018-06-24 21:16:16,562 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-24 21:16:16,562 INFO ]: CoverageRelationStatistics Valid=62, Invalid=694, Unknown=0, NotChecked=0, Total=756 [2018-06-24 21:16:16,563 INFO ]: Start difference. First operand 121 states and 145 transitions. Second operand 28 states. [2018-06-24 21:16:17,100 WARN ]: Spent 125.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-24 21:16:17,795 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:17,795 INFO ]: Finished difference Result 145 states and 171 transitions. [2018-06-24 21:16:17,796 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2018-06-24 21:16:17,796 INFO ]: Start accepts. Automaton has 28 states. Word has length 60 [2018-06-24 21:16:17,796 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:17,797 INFO ]: With dead ends: 145 [2018-06-24 21:16:17,797 INFO ]: Without dead ends: 145 [2018-06-24 21:16:17,798 INFO ]: 0 DeclaredPredicates, 107 GetRequests, 50 SyntacticMatches, 7 SemanticMatches, 50 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 472 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=219, Invalid=2433, Unknown=0, NotChecked=0, Total=2652 [2018-06-24 21:16:17,798 INFO ]: Start minimizeSevpa. Operand 145 states. [2018-06-24 21:16:17,804 INFO ]: Finished minimizeSevpa. Reduced states from 145 to 133. [2018-06-24 21:16:17,804 INFO ]: Start removeUnreachable. Operand 133 states. [2018-06-24 21:16:17,805 INFO ]: Finished removeUnreachable. Reduced from 133 states to 133 states and 159 transitions. [2018-06-24 21:16:17,805 INFO ]: Start accepts. Automaton has 133 states and 159 transitions. Word has length 60 [2018-06-24 21:16:17,805 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:17,805 INFO ]: Abstraction has 133 states and 159 transitions. [2018-06-24 21:16:17,805 INFO ]: Interpolant automaton has 28 states. [2018-06-24 21:16:17,805 INFO ]: Start isEmpty. Operand 133 states and 159 transitions. [2018-06-24 21:16:17,806 INFO ]: Finished isEmpty. Found accepting run of length 62 [2018-06-24 21:16:17,806 INFO ]: Found error trace [2018-06-24 21:16:17,806 INFO ]: trace histogram [22, 7, 7, 7, 7, 6, 1, 1, 1, 1, 1] [2018-06-24 21:16:17,806 INFO ]: === Iteration 23 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:17,806 INFO ]: Analyzing trace with hash -338997149, now seen corresponding path program 16 times [2018-06-24 21:16:17,806 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:17,806 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:17,807 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:17,807 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:17,807 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:17,827 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:18,202 INFO ]: Checked inductivity of 504 backedges. 249 proven. 82 refuted. 0 times theorem prover too weak. 173 trivial. 0 not checked. [2018-06-24 21:16:18,202 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:18,202 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-24 21:16:18,208 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-24 21:16:18,266 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-24 21:16:18,266 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:18,269 INFO ]: Computing forward predicates... [2018-06-24 21:16:18,407 INFO ]: Checked inductivity of 504 backedges. 262 proven. 69 refuted. 0 times theorem prover too weak. 173 trivial. 0 not checked. [2018-06-24 21:16:18,427 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:18,427 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 28 [2018-06-24 21:16:18,427 INFO ]: Interpolant automaton has 28 states [2018-06-24 21:16:18,428 INFO ]: Constructing interpolant automaton starting with 28 interpolants. [2018-06-24 21:16:18,428 INFO ]: CoverageRelationStatistics Valid=142, Invalid=614, Unknown=0, NotChecked=0, Total=756 [2018-06-24 21:16:18,428 INFO ]: Start difference. First operand 133 states and 159 transitions. Second operand 28 states. [2018-06-24 21:16:18,860 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:18,860 INFO ]: Finished difference Result 202 states and 234 transitions. [2018-06-24 21:16:18,860 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 41 states. [2018-06-24 21:16:18,860 INFO ]: Start accepts. Automaton has 28 states. Word has length 61 [2018-06-24 21:16:18,860 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:18,861 INFO ]: With dead ends: 202 [2018-06-24 21:16:18,861 INFO ]: Without dead ends: 183 [2018-06-24 21:16:18,862 INFO ]: 0 DeclaredPredicates, 101 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 548 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=512, Invalid=1938, Unknown=0, NotChecked=0, Total=2450 [2018-06-24 21:16:18,862 INFO ]: Start minimizeSevpa. Operand 183 states. [2018-06-24 21:16:18,874 INFO ]: Finished minimizeSevpa. Reduced states from 183 to 143. [2018-06-24 21:16:18,874 INFO ]: Start removeUnreachable. Operand 143 states. [2018-06-24 21:16:18,875 INFO ]: Finished removeUnreachable. Reduced from 143 states to 143 states and 170 transitions. [2018-06-24 21:16:18,875 INFO ]: Start accepts. Automaton has 143 states and 170 transitions. Word has length 61 [2018-06-24 21:16:18,876 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:18,876 INFO ]: Abstraction has 143 states and 170 transitions. [2018-06-24 21:16:18,876 INFO ]: Interpolant automaton has 28 states. [2018-06-24 21:16:18,876 INFO ]: Start isEmpty. Operand 143 states and 170 transitions. [2018-06-24 21:16:18,877 INFO ]: Finished isEmpty. Found accepting run of length 72 [2018-06-24 21:16:18,877 INFO ]: Found error trace [2018-06-24 21:16:18,877 INFO ]: trace histogram [27, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1] [2018-06-24 21:16:18,878 INFO ]: === Iteration 24 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:18,878 INFO ]: Analyzing trace with hash 517547742, now seen corresponding path program 17 times [2018-06-24 21:16:18,878 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:18,878 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:18,878 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:18,878 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:18,878 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:18,900 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:19,458 INFO ]: Checked inductivity of 723 backedges. 332 proven. 88 refuted. 0 times theorem prover too weak. 303 trivial. 0 not checked. [2018-06-24 21:16:19,458 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:19,458 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) [2018-06-24 21:16:19,472 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 23 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:16:19,560 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2018-06-24 21:16:19,560 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:19,564 INFO ]: Computing forward predicates... [2018-06-24 21:16:19,725 INFO ]: Checked inductivity of 723 backedges. 343 proven. 77 refuted. 0 times theorem prover too weak. 303 trivial. 0 not checked. [2018-06-24 21:16:19,744 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:19,744 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 19] total 29 [2018-06-24 21:16:19,744 INFO ]: Interpolant automaton has 29 states [2018-06-24 21:16:19,744 INFO ]: Constructing interpolant automaton starting with 29 interpolants. [2018-06-24 21:16:19,744 INFO ]: CoverageRelationStatistics Valid=144, Invalid=668, Unknown=0, NotChecked=0, Total=812 [2018-06-24 21:16:19,744 INFO ]: Start difference. First operand 143 states and 170 transitions. Second operand 29 states. [2018-06-24 21:16:20,095 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:20,095 INFO ]: Finished difference Result 146 states and 173 transitions. [2018-06-24 21:16:20,095 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 34 states. [2018-06-24 21:16:20,095 INFO ]: Start accepts. Automaton has 29 states. Word has length 71 [2018-06-24 21:16:20,095 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:20,096 INFO ]: With dead ends: 146 [2018-06-24 21:16:20,096 INFO ]: Without dead ends: 146 [2018-06-24 21:16:20,096 INFO ]: 0 DeclaredPredicates, 104 GetRequests, 62 SyntacticMatches, 0 SemanticMatches, 42 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 333 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=357, Invalid=1535, Unknown=0, NotChecked=0, Total=1892 [2018-06-24 21:16:20,097 INFO ]: Start minimizeSevpa. Operand 146 states. [2018-06-24 21:16:20,103 INFO ]: Finished minimizeSevpa. Reduced states from 146 to 146. [2018-06-24 21:16:20,103 INFO ]: Start removeUnreachable. Operand 146 states. [2018-06-24 21:16:20,108 INFO ]: Finished removeUnreachable. Reduced from 146 states to 146 states and 173 transitions. [2018-06-24 21:16:20,108 INFO ]: Start accepts. Automaton has 146 states and 173 transitions. Word has length 71 [2018-06-24 21:16:20,108 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:20,108 INFO ]: Abstraction has 146 states and 173 transitions. [2018-06-24 21:16:20,108 INFO ]: Interpolant automaton has 29 states. [2018-06-24 21:16:20,108 INFO ]: Start isEmpty. Operand 146 states and 173 transitions. [2018-06-24 21:16:20,109 INFO ]: Finished isEmpty. Found accepting run of length 73 [2018-06-24 21:16:20,109 INFO ]: Found error trace [2018-06-24 21:16:20,109 INFO ]: trace histogram [28, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1] [2018-06-24 21:16:20,109 INFO ]: === Iteration 25 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:20,110 INFO ]: Analyzing trace with hash -1136801031, now seen corresponding path program 18 times [2018-06-24 21:16:20,110 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:20,110 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:20,110 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:20,110 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:20,110 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:20,138 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:20,586 INFO ]: Checked inductivity of 758 backedges. 8 proven. 637 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2018-06-24 21:16:20,586 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:20,586 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-24 21:16:20,592 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-24 21:16:20,672 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 11 check-sat command(s) [2018-06-24 21:16:20,672 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:20,677 INFO ]: Computing forward predicates... [2018-06-24 21:16:21,432 INFO ]: Checked inductivity of 758 backedges. 8 proven. 637 refuted. 0 times theorem prover too weak. 113 trivial. 0 not checked. [2018-06-24 21:16:21,451 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:21,451 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 31 [2018-06-24 21:16:21,451 INFO ]: Interpolant automaton has 31 states [2018-06-24 21:16:21,451 INFO ]: Constructing interpolant automaton starting with 31 interpolants. [2018-06-24 21:16:21,451 INFO ]: CoverageRelationStatistics Valid=69, Invalid=861, Unknown=0, NotChecked=0, Total=930 [2018-06-24 21:16:21,451 INFO ]: Start difference. First operand 146 states and 173 transitions. Second operand 31 states. [2018-06-24 21:16:21,989 WARN ]: Spent 261.00 ms on a formula simplification that was a NOOP. DAG size: 43 [2018-06-24 21:16:23,137 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:23,137 INFO ]: Finished difference Result 173 states and 202 transitions. [2018-06-24 21:16:23,137 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-06-24 21:16:23,138 INFO ]: Start accepts. Automaton has 31 states. Word has length 72 [2018-06-24 21:16:23,138 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:23,139 INFO ]: With dead ends: 173 [2018-06-24 21:16:23,139 INFO ]: Without dead ends: 173 [2018-06-24 21:16:23,140 INFO ]: 0 DeclaredPredicates, 125 GetRequests, 61 SyntacticMatches, 8 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 595 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=254, Invalid=3052, Unknown=0, NotChecked=0, Total=3306 [2018-06-24 21:16:23,140 INFO ]: Start minimizeSevpa. Operand 173 states. [2018-06-24 21:16:23,147 INFO ]: Finished minimizeSevpa. Reduced states from 173 to 159. [2018-06-24 21:16:23,147 INFO ]: Start removeUnreachable. Operand 159 states. [2018-06-24 21:16:23,148 INFO ]: Finished removeUnreachable. Reduced from 159 states to 159 states and 188 transitions. [2018-06-24 21:16:23,148 INFO ]: Start accepts. Automaton has 159 states and 188 transitions. Word has length 72 [2018-06-24 21:16:23,148 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:23,148 INFO ]: Abstraction has 159 states and 188 transitions. [2018-06-24 21:16:23,148 INFO ]: Interpolant automaton has 31 states. [2018-06-24 21:16:23,148 INFO ]: Start isEmpty. Operand 159 states and 188 transitions. [2018-06-24 21:16:23,149 INFO ]: Finished isEmpty. Found accepting run of length 74 [2018-06-24 21:16:23,149 INFO ]: Found error trace [2018-06-24 21:16:23,149 INFO ]: trace histogram [29, 8, 8, 8, 8, 7, 1, 1, 1, 1, 1] [2018-06-24 21:16:23,149 INFO ]: === Iteration 26 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:23,150 INFO ]: Analyzing trace with hash -882005442, now seen corresponding path program 19 times [2018-06-24 21:16:23,150 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:23,150 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:23,150 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:23,150 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:23,150 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:23,173 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:23,409 INFO ]: Checked inductivity of 794 backedges. 385 proven. 106 refuted. 0 times theorem prover too weak. 303 trivial. 0 not checked. [2018-06-24 21:16:23,410 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:23,410 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-24 21:16:23,417 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:23,487 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:23,490 INFO ]: Computing forward predicates... [2018-06-24 21:16:23,706 INFO ]: Checked inductivity of 794 backedges. 400 proven. 91 refuted. 0 times theorem prover too weak. 303 trivial. 0 not checked. [2018-06-24 21:16:23,725 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:23,725 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 31 [2018-06-24 21:16:23,725 INFO ]: Interpolant automaton has 31 states [2018-06-24 21:16:23,725 INFO ]: Constructing interpolant automaton starting with 31 interpolants. [2018-06-24 21:16:23,725 INFO ]: CoverageRelationStatistics Valid=176, Invalid=754, Unknown=0, NotChecked=0, Total=930 [2018-06-24 21:16:23,726 INFO ]: Start difference. First operand 159 states and 188 transitions. Second operand 31 states. [2018-06-24 21:16:24,210 WARN ]: Spent 118.00 ms on a formula simplification that was a NOOP. DAG size: 14 [2018-06-24 21:16:25,329 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:25,329 INFO ]: Finished difference Result 245 states and 280 transitions. [2018-06-24 21:16:25,329 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 46 states. [2018-06-24 21:16:25,329 INFO ]: Start accepts. Automaton has 31 states. Word has length 73 [2018-06-24 21:16:25,330 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:25,331 INFO ]: With dead ends: 245 [2018-06-24 21:16:25,331 INFO ]: Without dead ends: 224 [2018-06-24 21:16:25,332 INFO ]: 0 DeclaredPredicates, 118 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 716 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=649, Invalid=2431, Unknown=0, NotChecked=0, Total=3080 [2018-06-24 21:16:25,332 INFO ]: Start minimizeSevpa. Operand 224 states. [2018-06-24 21:16:25,341 INFO ]: Finished minimizeSevpa. Reduced states from 224 to 170. [2018-06-24 21:16:25,341 INFO ]: Start removeUnreachable. Operand 170 states. [2018-06-24 21:16:25,342 INFO ]: Finished removeUnreachable. Reduced from 170 states to 170 states and 200 transitions. [2018-06-24 21:16:25,342 INFO ]: Start accepts. Automaton has 170 states and 200 transitions. Word has length 73 [2018-06-24 21:16:25,342 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:25,342 INFO ]: Abstraction has 170 states and 200 transitions. [2018-06-24 21:16:25,342 INFO ]: Interpolant automaton has 31 states. [2018-06-24 21:16:25,342 INFO ]: Start isEmpty. Operand 170 states and 200 transitions. [2018-06-24 21:16:25,343 INFO ]: Finished isEmpty. Found accepting run of length 85 [2018-06-24 21:16:25,343 INFO ]: Found error trace [2018-06-24 21:16:25,343 INFO ]: trace histogram [35, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1] [2018-06-24 21:16:25,343 INFO ]: === Iteration 27 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:25,343 INFO ]: Analyzing trace with hash -1024129666, now seen corresponding path program 20 times [2018-06-24 21:16:25,343 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:25,343 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:25,344 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:25,344 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:25,344 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:25,370 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:26,226 INFO ]: Checked inductivity of 1108 backedges. 495 proven. 113 refuted. 0 times theorem prover too weak. 500 trivial. 0 not checked. [2018-06-24 21:16:26,226 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:26,226 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-24 21:16:26,231 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:16:26,310 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:16:26,310 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:26,314 INFO ]: Computing forward predicates... [2018-06-24 21:16:26,499 INFO ]: Checked inductivity of 1108 backedges. 508 proven. 100 refuted. 0 times theorem prover too weak. 500 trivial. 0 not checked. [2018-06-24 21:16:26,518 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:26,519 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 21] total 32 [2018-06-24 21:16:26,519 INFO ]: Interpolant automaton has 32 states [2018-06-24 21:16:26,519 INFO ]: Constructing interpolant automaton starting with 32 interpolants. [2018-06-24 21:16:26,519 INFO ]: CoverageRelationStatistics Valid=178, Invalid=814, Unknown=0, NotChecked=0, Total=992 [2018-06-24 21:16:26,519 INFO ]: Start difference. First operand 170 states and 200 transitions. Second operand 32 states. [2018-06-24 21:16:27,024 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:27,024 INFO ]: Finished difference Result 173 states and 203 transitions. [2018-06-24 21:16:27,024 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 38 states. [2018-06-24 21:16:27,024 INFO ]: Start accepts. Automaton has 32 states. Word has length 84 [2018-06-24 21:16:27,024 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:27,025 INFO ]: With dead ends: 173 [2018-06-24 21:16:27,025 INFO ]: Without dead ends: 173 [2018-06-24 21:16:27,026 INFO ]: 0 DeclaredPredicates, 121 GetRequests, 74 SyntacticMatches, 0 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 426 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=448, Invalid=1904, Unknown=0, NotChecked=0, Total=2352 [2018-06-24 21:16:27,026 INFO ]: Start minimizeSevpa. Operand 173 states. [2018-06-24 21:16:27,031 INFO ]: Finished minimizeSevpa. Reduced states from 173 to 173. [2018-06-24 21:16:27,031 INFO ]: Start removeUnreachable. Operand 173 states. [2018-06-24 21:16:27,032 INFO ]: Finished removeUnreachable. Reduced from 173 states to 173 states and 203 transitions. [2018-06-24 21:16:27,032 INFO ]: Start accepts. Automaton has 173 states and 203 transitions. Word has length 84 [2018-06-24 21:16:27,033 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:27,033 INFO ]: Abstraction has 173 states and 203 transitions. [2018-06-24 21:16:27,033 INFO ]: Interpolant automaton has 32 states. [2018-06-24 21:16:27,033 INFO ]: Start isEmpty. Operand 173 states and 203 transitions. [2018-06-24 21:16:27,034 INFO ]: Finished isEmpty. Found accepting run of length 86 [2018-06-24 21:16:27,034 INFO ]: Found error trace [2018-06-24 21:16:27,034 INFO ]: trace histogram [36, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1] [2018-06-24 21:16:27,034 INFO ]: === Iteration 28 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:27,034 INFO ]: Analyzing trace with hash -1684160423, now seen corresponding path program 21 times [2018-06-24 21:16:27,034 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:27,034 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:27,035 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:27,035 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:27,035 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:27,062 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:27,463 INFO ]: Checked inductivity of 1152 backedges. 9 proven. 986 refuted. 0 times theorem prover too weak. 157 trivial. 0 not checked. [2018-06-24 21:16:27,463 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:27,463 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 27 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:16:27,470 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:16:27,567 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 10 check-sat command(s) [2018-06-24 21:16:27,567 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:27,572 INFO ]: Computing forward predicates... [2018-06-24 21:16:28,382 INFO ]: Checked inductivity of 1152 backedges. 9 proven. 986 refuted. 0 times theorem prover too weak. 157 trivial. 0 not checked. [2018-06-24 21:16:28,401 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:28,401 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23] total 34 [2018-06-24 21:16:28,401 INFO ]: Interpolant automaton has 34 states [2018-06-24 21:16:28,401 INFO ]: Constructing interpolant automaton starting with 34 interpolants. [2018-06-24 21:16:28,401 INFO ]: CoverageRelationStatistics Valid=76, Invalid=1046, Unknown=0, NotChecked=0, Total=1122 [2018-06-24 21:16:28,402 INFO ]: Start difference. First operand 173 states and 203 transitions. Second operand 34 states. [2018-06-24 21:16:29,748 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:29,748 INFO ]: Finished difference Result 203 states and 235 transitions. [2018-06-24 21:16:29,749 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2018-06-24 21:16:29,749 INFO ]: Start accepts. Automaton has 34 states. Word has length 85 [2018-06-24 21:16:29,750 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:29,751 INFO ]: With dead ends: 203 [2018-06-24 21:16:29,751 INFO ]: Without dead ends: 203 [2018-06-24 21:16:29,752 INFO ]: 0 DeclaredPredicates, 144 GetRequests, 73 SyntacticMatches, 9 SemanticMatches, 62 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 733 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=291, Invalid=3741, Unknown=0, NotChecked=0, Total=4032 [2018-06-24 21:16:29,752 INFO ]: Start minimizeSevpa. Operand 203 states. [2018-06-24 21:16:29,758 INFO ]: Finished minimizeSevpa. Reduced states from 203 to 187. [2018-06-24 21:16:29,758 INFO ]: Start removeUnreachable. Operand 187 states. [2018-06-24 21:16:29,759 INFO ]: Finished removeUnreachable. Reduced from 187 states to 187 states and 219 transitions. [2018-06-24 21:16:29,760 INFO ]: Start accepts. Automaton has 187 states and 219 transitions. Word has length 85 [2018-06-24 21:16:29,760 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:29,760 INFO ]: Abstraction has 187 states and 219 transitions. [2018-06-24 21:16:29,760 INFO ]: Interpolant automaton has 34 states. [2018-06-24 21:16:29,760 INFO ]: Start isEmpty. Operand 187 states and 219 transitions. [2018-06-24 21:16:29,761 INFO ]: Finished isEmpty. Found accepting run of length 87 [2018-06-24 21:16:29,761 INFO ]: Found error trace [2018-06-24 21:16:29,761 INFO ]: trace histogram [37, 9, 9, 9, 9, 8, 1, 1, 1, 1, 1] [2018-06-24 21:16:29,761 INFO ]: === Iteration 29 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:29,761 INFO ]: Analyzing trace with hash -670277410, now seen corresponding path program 22 times [2018-06-24 21:16:29,761 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:29,761 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:29,762 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:29,762 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:29,762 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:29,786 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:30,184 INFO ]: Checked inductivity of 1197 backedges. 564 proven. 133 refuted. 0 times theorem prover too weak. 500 trivial. 0 not checked. [2018-06-24 21:16:30,184 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:30,184 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 28 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:16:30,190 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-24 21:16:30,270 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-24 21:16:30,270 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:30,275 INFO ]: Computing forward predicates... [2018-06-24 21:16:30,602 INFO ]: Checked inductivity of 1197 backedges. 581 proven. 116 refuted. 0 times theorem prover too weak. 500 trivial. 0 not checked. [2018-06-24 21:16:30,634 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:30,634 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23] total 34 [2018-06-24 21:16:30,634 INFO ]: Interpolant automaton has 34 states [2018-06-24 21:16:30,634 INFO ]: Constructing interpolant automaton starting with 34 interpolants. [2018-06-24 21:16:30,634 INFO ]: CoverageRelationStatistics Valid=214, Invalid=908, Unknown=0, NotChecked=0, Total=1122 [2018-06-24 21:16:30,634 INFO ]: Start difference. First operand 187 states and 219 transitions. Second operand 34 states. [2018-06-24 21:16:31,463 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:31,463 INFO ]: Finished difference Result 292 states and 330 transitions. [2018-06-24 21:16:31,463 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 51 states. [2018-06-24 21:16:31,463 INFO ]: Start accepts. Automaton has 34 states. Word has length 86 [2018-06-24 21:16:31,463 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:31,464 INFO ]: With dead ends: 292 [2018-06-24 21:16:31,464 INFO ]: Without dead ends: 269 [2018-06-24 21:16:31,465 INFO ]: 0 DeclaredPredicates, 136 GetRequests, 76 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 906 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=803, Invalid=2979, Unknown=0, NotChecked=0, Total=3782 [2018-06-24 21:16:31,466 INFO ]: Start minimizeSevpa. Operand 269 states. [2018-06-24 21:16:31,474 INFO ]: Finished minimizeSevpa. Reduced states from 269 to 199. [2018-06-24 21:16:31,474 INFO ]: Start removeUnreachable. Operand 199 states. [2018-06-24 21:16:31,475 INFO ]: Finished removeUnreachable. Reduced from 199 states to 199 states and 232 transitions. [2018-06-24 21:16:31,475 INFO ]: Start accepts. Automaton has 199 states and 232 transitions. Word has length 86 [2018-06-24 21:16:31,475 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:31,475 INFO ]: Abstraction has 199 states and 232 transitions. [2018-06-24 21:16:31,475 INFO ]: Interpolant automaton has 34 states. [2018-06-24 21:16:31,475 INFO ]: Start isEmpty. Operand 199 states and 232 transitions. [2018-06-24 21:16:31,476 INFO ]: Finished isEmpty. Found accepting run of length 99 [2018-06-24 21:16:31,476 INFO ]: Found error trace [2018-06-24 21:16:31,476 INFO ]: trace histogram [44, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1] [2018-06-24 21:16:31,476 INFO ]: === Iteration 30 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:31,476 INFO ]: Analyzing trace with hash 150415377, now seen corresponding path program 23 times [2018-06-24 21:16:31,476 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:31,477 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:31,477 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:31,477 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:31,477 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:31,503 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:31,818 INFO ]: Checked inductivity of 1631 backedges. 705 proven. 141 refuted. 0 times theorem prover too weak. 785 trivial. 0 not checked. [2018-06-24 21:16:31,818 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:31,818 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 29 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:16:31,825 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-24 21:16:31,941 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 15 check-sat command(s) [2018-06-24 21:16:31,941 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:31,946 INFO ]: Computing forward predicates... [2018-06-24 21:16:32,165 INFO ]: Checked inductivity of 1631 backedges. 720 proven. 126 refuted. 0 times theorem prover too weak. 785 trivial. 0 not checked. [2018-06-24 21:16:32,184 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:32,184 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [23, 23] total 35 [2018-06-24 21:16:32,185 INFO ]: Interpolant automaton has 35 states [2018-06-24 21:16:32,185 INFO ]: Constructing interpolant automaton starting with 35 interpolants. [2018-06-24 21:16:32,185 INFO ]: CoverageRelationStatistics Valid=216, Invalid=974, Unknown=0, NotChecked=0, Total=1190 [2018-06-24 21:16:32,185 INFO ]: Start difference. First operand 199 states and 232 transitions. Second operand 35 states. [2018-06-24 21:16:32,820 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:32,820 INFO ]: Finished difference Result 202 states and 235 transitions. [2018-06-24 21:16:32,820 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 42 states. [2018-06-24 21:16:32,820 INFO ]: Start accepts. Automaton has 35 states. Word has length 98 [2018-06-24 21:16:32,821 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:32,822 INFO ]: With dead ends: 202 [2018-06-24 21:16:32,822 INFO ]: Without dead ends: 202 [2018-06-24 21:16:32,823 INFO ]: 0 DeclaredPredicates, 139 GetRequests, 87 SyntacticMatches, 0 SemanticMatches, 52 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 530 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=550, Invalid=2312, Unknown=0, NotChecked=0, Total=2862 [2018-06-24 21:16:32,823 INFO ]: Start minimizeSevpa. Operand 202 states. [2018-06-24 21:16:32,829 INFO ]: Finished minimizeSevpa. Reduced states from 202 to 202. [2018-06-24 21:16:32,829 INFO ]: Start removeUnreachable. Operand 202 states. [2018-06-24 21:16:32,830 INFO ]: Finished removeUnreachable. Reduced from 202 states to 202 states and 235 transitions. [2018-06-24 21:16:32,830 INFO ]: Start accepts. Automaton has 202 states and 235 transitions. Word has length 98 [2018-06-24 21:16:32,831 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:32,831 INFO ]: Abstraction has 202 states and 235 transitions. [2018-06-24 21:16:32,831 INFO ]: Interpolant automaton has 35 states. [2018-06-24 21:16:32,831 INFO ]: Start isEmpty. Operand 202 states and 235 transitions. [2018-06-24 21:16:32,832 INFO ]: Finished isEmpty. Found accepting run of length 100 [2018-06-24 21:16:32,832 INFO ]: Found error trace [2018-06-24 21:16:32,832 INFO ]: trace histogram [45, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1] [2018-06-24 21:16:32,832 INFO ]: === Iteration 31 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:32,832 INFO ]: Analyzing trace with hash 366997542, now seen corresponding path program 24 times [2018-06-24 21:16:32,832 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:32,832 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:32,833 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:32,833 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:32,833 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:32,863 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:33,534 INFO ]: Checked inductivity of 1685 backedges. 10 proven. 1464 refuted. 0 times theorem prover too weak. 211 trivial. 0 not checked. [2018-06-24 21:16:33,534 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:33,534 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 30 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:16:33,540 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-24 21:16:33,711 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 16 check-sat command(s) [2018-06-24 21:16:33,711 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:33,718 INFO ]: Computing forward predicates... [2018-06-24 21:16:34,163 INFO ]: Checked inductivity of 1685 backedges. 10 proven. 1464 refuted. 0 times theorem prover too weak. 211 trivial. 0 not checked. [2018-06-24 21:16:34,183 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:34,191 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 37 [2018-06-24 21:16:34,191 INFO ]: Interpolant automaton has 37 states [2018-06-24 21:16:34,192 INFO ]: Constructing interpolant automaton starting with 37 interpolants. [2018-06-24 21:16:34,192 INFO ]: CoverageRelationStatistics Valid=83, Invalid=1249, Unknown=0, NotChecked=0, Total=1332 [2018-06-24 21:16:34,192 INFO ]: Start difference. First operand 202 states and 235 transitions. Second operand 37 states. [2018-06-24 21:16:35,789 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:35,789 INFO ]: Finished difference Result 235 states and 270 transitions. [2018-06-24 21:16:35,789 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-06-24 21:16:35,789 INFO ]: Start accepts. Automaton has 37 states. Word has length 99 [2018-06-24 21:16:35,789 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:35,790 INFO ]: With dead ends: 235 [2018-06-24 21:16:35,790 INFO ]: Without dead ends: 235 [2018-06-24 21:16:35,790 INFO ]: 0 DeclaredPredicates, 164 GetRequests, 86 SyntacticMatches, 10 SemanticMatches, 68 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 883 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=330, Invalid=4500, Unknown=0, NotChecked=0, Total=4830 [2018-06-24 21:16:35,790 INFO ]: Start minimizeSevpa. Operand 235 states. [2018-06-24 21:16:35,797 INFO ]: Finished minimizeSevpa. Reduced states from 235 to 217. [2018-06-24 21:16:35,797 INFO ]: Start removeUnreachable. Operand 217 states. [2018-06-24 21:16:35,798 INFO ]: Finished removeUnreachable. Reduced from 217 states to 217 states and 252 transitions. [2018-06-24 21:16:35,798 INFO ]: Start accepts. Automaton has 217 states and 252 transitions. Word has length 99 [2018-06-24 21:16:35,798 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:35,798 INFO ]: Abstraction has 217 states and 252 transitions. [2018-06-24 21:16:35,798 INFO ]: Interpolant automaton has 37 states. [2018-06-24 21:16:35,798 INFO ]: Start isEmpty. Operand 217 states and 252 transitions. [2018-06-24 21:16:35,799 INFO ]: Finished isEmpty. Found accepting run of length 101 [2018-06-24 21:16:35,799 INFO ]: Found error trace [2018-06-24 21:16:35,799 INFO ]: trace histogram [46, 10, 10, 10, 10, 9, 1, 1, 1, 1, 1] [2018-06-24 21:16:35,799 INFO ]: === Iteration 32 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:35,800 INFO ]: Analyzing trace with hash -1508889935, now seen corresponding path program 25 times [2018-06-24 21:16:35,800 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:35,800 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:35,800 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:35,800 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:35,800 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:35,827 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:36,687 INFO ]: Checked inductivity of 1740 backedges. 792 proven. 163 refuted. 0 times theorem prover too weak. 785 trivial. 0 not checked. [2018-06-24 21:16:36,687 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:36,687 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 31 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:16:36,692 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:36,798 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:36,802 INFO ]: Computing forward predicates... [2018-06-24 21:16:37,000 INFO ]: Checked inductivity of 1740 backedges. 811 proven. 144 refuted. 0 times theorem prover too weak. 785 trivial. 0 not checked. [2018-06-24 21:16:37,020 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:37,020 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [25, 25] total 37 [2018-06-24 21:16:37,020 INFO ]: Interpolant automaton has 37 states [2018-06-24 21:16:37,020 INFO ]: Constructing interpolant automaton starting with 37 interpolants. [2018-06-24 21:16:37,020 INFO ]: CoverageRelationStatistics Valid=256, Invalid=1076, Unknown=0, NotChecked=0, Total=1332 [2018-06-24 21:16:37,020 INFO ]: Start difference. First operand 217 states and 252 transitions. Second operand 37 states. [2018-06-24 21:16:38,550 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:38,550 INFO ]: Finished difference Result 343 states and 384 transitions. [2018-06-24 21:16:38,550 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 56 states. [2018-06-24 21:16:38,550 INFO ]: Start accepts. Automaton has 37 states. Word has length 100 [2018-06-24 21:16:38,550 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:38,552 INFO ]: With dead ends: 343 [2018-06-24 21:16:38,552 INFO ]: Without dead ends: 318 [2018-06-24 21:16:38,552 INFO ]: 0 DeclaredPredicates, 155 GetRequests, 89 SyntacticMatches, 0 SemanticMatches, 66 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1118 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=974, Invalid=3582, Unknown=0, NotChecked=0, Total=4556 [2018-06-24 21:16:38,553 INFO ]: Start minimizeSevpa. Operand 318 states. [2018-06-24 21:16:38,560 INFO ]: Finished minimizeSevpa. Reduced states from 318 to 230. [2018-06-24 21:16:38,560 INFO ]: Start removeUnreachable. Operand 230 states. [2018-06-24 21:16:38,562 INFO ]: Finished removeUnreachable. Reduced from 230 states to 230 states and 266 transitions. [2018-06-24 21:16:38,562 INFO ]: Start accepts. Automaton has 230 states and 266 transitions. Word has length 100 [2018-06-24 21:16:38,562 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:38,562 INFO ]: Abstraction has 230 states and 266 transitions. [2018-06-24 21:16:38,562 INFO ]: Interpolant automaton has 37 states. [2018-06-24 21:16:38,562 INFO ]: Start isEmpty. Operand 230 states and 266 transitions. [2018-06-24 21:16:38,564 INFO ]: Finished isEmpty. Found accepting run of length 114 [2018-06-24 21:16:38,564 INFO ]: Found error trace [2018-06-24 21:16:38,564 INFO ]: trace histogram [54, 11, 11, 11, 11, 10, 1, 1, 1, 1, 1] [2018-06-24 21:16:38,564 INFO ]: === Iteration 33 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:38,565 INFO ]: Analyzing trace with hash 1670711667, now seen corresponding path program 26 times [2018-06-24 21:16:38,565 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:38,565 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:38,565 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:38,565 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:16:38,565 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:38,593 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:39,289 INFO ]: Checked inductivity of 2322 backedges. 945 proven. 256 refuted. 0 times theorem prover too weak. 1121 trivial. 0 not checked. [2018-06-24 21:16:39,289 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:39,289 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 32 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:16:39,294 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:16:39,403 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:16:39,403 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:39,409 INFO ]: Computing forward predicates... [2018-06-24 21:16:40,702 INFO ]: Checked inductivity of 2322 backedges. 985 proven. 155 refuted. 0 times theorem prover too weak. 1182 trivial. 0 not checked. [2018-06-24 21:16:40,722 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:40,722 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 25] total 41 [2018-06-24 21:16:40,722 INFO ]: Interpolant automaton has 41 states [2018-06-24 21:16:40,722 INFO ]: Constructing interpolant automaton starting with 41 interpolants. [2018-06-24 21:16:40,723 INFO ]: CoverageRelationStatistics Valid=265, Invalid=1375, Unknown=0, NotChecked=0, Total=1640 [2018-06-24 21:16:40,723 INFO ]: Start difference. First operand 230 states and 266 transitions. Second operand 41 states. [2018-06-24 21:16:41,519 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:41,519 INFO ]: Finished difference Result 233 states and 269 transitions. [2018-06-24 21:16:41,519 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 60 states. [2018-06-24 21:16:41,519 INFO ]: Start accepts. Automaton has 41 states. Word has length 113 [2018-06-24 21:16:41,519 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:41,520 INFO ]: With dead ends: 233 [2018-06-24 21:16:41,520 INFO ]: Without dead ends: 233 [2018-06-24 21:16:41,521 INFO ]: 0 DeclaredPredicates, 175 GetRequests, 102 SyntacticMatches, 0 SemanticMatches, 73 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1264 ImplicationChecksByTransitivity, 2.3s TimeCoverageRelationStatistics Valid=806, Invalid=4744, Unknown=0, NotChecked=0, Total=5550 [2018-06-24 21:16:41,521 INFO ]: Start minimizeSevpa. Operand 233 states. [2018-06-24 21:16:41,528 INFO ]: Finished minimizeSevpa. Reduced states from 233 to 233. [2018-06-24 21:16:41,528 INFO ]: Start removeUnreachable. Operand 233 states. [2018-06-24 21:16:41,529 INFO ]: Finished removeUnreachable. Reduced from 233 states to 233 states and 269 transitions. [2018-06-24 21:16:41,529 INFO ]: Start accepts. Automaton has 233 states and 269 transitions. Word has length 113 [2018-06-24 21:16:41,530 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:41,530 INFO ]: Abstraction has 233 states and 269 transitions. [2018-06-24 21:16:41,530 INFO ]: Interpolant automaton has 41 states. [2018-06-24 21:16:41,530 INFO ]: Start isEmpty. Operand 233 states and 269 transitions. [2018-06-24 21:16:41,531 INFO ]: Finished isEmpty. Found accepting run of length 115 [2018-06-24 21:16:41,531 INFO ]: Found error trace [2018-06-24 21:16:41,531 INFO ]: trace histogram [55, 11, 11, 11, 11, 10, 1, 1, 1, 1, 1] [2018-06-24 21:16:41,531 INFO ]: === Iteration 34 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:41,531 INFO ]: Analyzing trace with hash 251542276, now seen corresponding path program 27 times [2018-06-24 21:16:41,531 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:41,531 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:41,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:41,532 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:41,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:41,564 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:42,064 INFO ]: Checked inductivity of 2387 backedges. 11 proven. 2100 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2018-06-24 21:16:42,064 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:42,064 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 33 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:16:42,070 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:16:42,230 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 12 check-sat command(s) [2018-06-24 21:16:42,230 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:42,236 INFO ]: Computing forward predicates... [2018-06-24 21:16:42,637 INFO ]: Checked inductivity of 2387 backedges. 11 proven. 2100 refuted. 0 times theorem prover too weak. 276 trivial. 0 not checked. [2018-06-24 21:16:42,656 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:42,656 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 27] total 40 [2018-06-24 21:16:42,657 INFO ]: Interpolant automaton has 40 states [2018-06-24 21:16:42,657 INFO ]: Constructing interpolant automaton starting with 40 interpolants. [2018-06-24 21:16:42,657 INFO ]: CoverageRelationStatistics Valid=90, Invalid=1470, Unknown=0, NotChecked=0, Total=1560 [2018-06-24 21:16:42,657 INFO ]: Start difference. First operand 233 states and 269 transitions. Second operand 40 states. [2018-06-24 21:16:44,566 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:44,566 INFO ]: Finished difference Result 269 states and 307 transitions. [2018-06-24 21:16:44,566 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 62 states. [2018-06-24 21:16:44,566 INFO ]: Start accepts. Automaton has 40 states. Word has length 114 [2018-06-24 21:16:44,566 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:44,568 INFO ]: With dead ends: 269 [2018-06-24 21:16:44,568 INFO ]: Without dead ends: 269 [2018-06-24 21:16:44,568 INFO ]: 0 DeclaredPredicates, 185 GetRequests, 100 SyntacticMatches, 11 SemanticMatches, 74 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1048 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=371, Invalid=5329, Unknown=0, NotChecked=0, Total=5700 [2018-06-24 21:16:44,569 INFO ]: Start minimizeSevpa. Operand 269 states. [2018-06-24 21:16:44,575 INFO ]: Finished minimizeSevpa. Reduced states from 269 to 249. [2018-06-24 21:16:44,575 INFO ]: Start removeUnreachable. Operand 249 states. [2018-06-24 21:16:44,576 INFO ]: Finished removeUnreachable. Reduced from 249 states to 249 states and 287 transitions. [2018-06-24 21:16:44,576 INFO ]: Start accepts. Automaton has 249 states and 287 transitions. Word has length 114 [2018-06-24 21:16:44,577 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:44,577 INFO ]: Abstraction has 249 states and 287 transitions. [2018-06-24 21:16:44,577 INFO ]: Interpolant automaton has 40 states. [2018-06-24 21:16:44,577 INFO ]: Start isEmpty. Operand 249 states and 287 transitions. [2018-06-24 21:16:44,578 INFO ]: Finished isEmpty. Found accepting run of length 116 [2018-06-24 21:16:44,578 INFO ]: Found error trace [2018-06-24 21:16:44,578 INFO ]: trace histogram [56, 11, 11, 11, 11, 10, 1, 1, 1, 1, 1] [2018-06-24 21:16:44,578 INFO ]: === Iteration 35 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:44,578 INFO ]: Analyzing trace with hash -793035885, now seen corresponding path program 28 times [2018-06-24 21:16:44,578 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:44,578 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:44,579 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:44,579 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:44,579 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:44,607 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:46,154 INFO ]: Checked inductivity of 2453 backedges. 1050 proven. 282 refuted. 0 times theorem prover too weak. 1121 trivial. 0 not checked. [2018-06-24 21:16:46,154 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:46,154 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 34 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 34 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:16:46,159 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-24 21:16:46,270 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-24 21:16:46,271 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:46,276 INFO ]: Computing forward predicates... [2018-06-24 21:16:46,874 INFO ]: Checked inductivity of 2453 backedges. 1096 proven. 175 refuted. 0 times theorem prover too weak. 1182 trivial. 0 not checked. [2018-06-24 21:16:46,894 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:46,894 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 27] total 43 [2018-06-24 21:16:46,894 INFO ]: Interpolant automaton has 43 states [2018-06-24 21:16:46,894 INFO ]: Constructing interpolant automaton starting with 43 interpolants. [2018-06-24 21:16:46,894 INFO ]: CoverageRelationStatistics Valid=308, Invalid=1498, Unknown=0, NotChecked=0, Total=1806 [2018-06-24 21:16:46,895 INFO ]: Start difference. First operand 249 states and 287 transitions. Second operand 43 states. [2018-06-24 21:16:48,008 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:48,009 INFO ]: Finished difference Result 398 states and 442 transitions. [2018-06-24 21:16:48,009 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 65 states. [2018-06-24 21:16:48,009 INFO ]: Start accepts. Automaton has 43 states. Word has length 115 [2018-06-24 21:16:48,009 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:48,011 INFO ]: With dead ends: 398 [2018-06-24 21:16:48,011 INFO ]: Without dead ends: 371 [2018-06-24 21:16:48,011 INFO ]: 0 DeclaredPredicates, 185 GetRequests, 105 SyntacticMatches, 0 SemanticMatches, 80 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1581 ImplicationChecksByTransitivity, 2.5s TimeCoverageRelationStatistics Valid=1188, Invalid=5454, Unknown=0, NotChecked=0, Total=6642 [2018-06-24 21:16:48,012 INFO ]: Start minimizeSevpa. Operand 371 states. [2018-06-24 21:16:48,023 INFO ]: Finished minimizeSevpa. Reduced states from 371 to 263. [2018-06-24 21:16:48,023 INFO ]: Start removeUnreachable. Operand 263 states. [2018-06-24 21:16:48,024 INFO ]: Finished removeUnreachable. Reduced from 263 states to 263 states and 302 transitions. [2018-06-24 21:16:48,024 INFO ]: Start accepts. Automaton has 263 states and 302 transitions. Word has length 115 [2018-06-24 21:16:48,024 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:48,024 INFO ]: Abstraction has 263 states and 302 transitions. [2018-06-24 21:16:48,024 INFO ]: Interpolant automaton has 43 states. [2018-06-24 21:16:48,024 INFO ]: Start isEmpty. Operand 263 states and 302 transitions. [2018-06-24 21:16:48,026 INFO ]: Finished isEmpty. Found accepting run of length 130 [2018-06-24 21:16:48,026 INFO ]: Found error trace [2018-06-24 21:16:48,026 INFO ]: trace histogram [65, 12, 12, 12, 12, 11, 1, 1, 1, 1, 1] [2018-06-24 21:16:48,026 INFO ]: === Iteration 36 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:48,026 INFO ]: Analyzing trace with hash 1314056654, now seen corresponding path program 29 times [2018-06-24 21:16:48,026 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:48,026 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:48,027 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:48,027 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:48,027 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:48,058 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:48,863 INFO ]: Checked inductivity of 3214 backedges. 1265 proven. 304 refuted. 0 times theorem prover too weak. 1645 trivial. 0 not checked. [2018-06-24 21:16:48,863 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:16:48,863 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 35 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 35 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:16:48,868 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-24 21:16:49,038 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 18 check-sat command(s) [2018-06-24 21:16:49,038 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:16:49,044 INFO ]: Computing forward predicates... [2018-06-24 21:16:49,575 INFO ]: Checked inductivity of 3214 backedges. 1309 proven. 187 refuted. 0 times theorem prover too weak. 1718 trivial. 0 not checked. [2018-06-24 21:16:49,595 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:16:49,595 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [30, 27] total 44 [2018-06-24 21:16:49,595 INFO ]: Interpolant automaton has 44 states [2018-06-24 21:16:49,596 INFO ]: Constructing interpolant automaton starting with 44 interpolants. [2018-06-24 21:16:49,596 INFO ]: CoverageRelationStatistics Valid=311, Invalid=1581, Unknown=0, NotChecked=0, Total=1892 [2018-06-24 21:16:49,596 INFO ]: Start difference. First operand 263 states and 302 transitions. Second operand 44 states. [2018-06-24 21:16:50,475 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:16:50,475 INFO ]: Finished difference Result 266 states and 305 transitions. [2018-06-24 21:16:50,475 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 65 states. [2018-06-24 21:16:50,475 INFO ]: Start accepts. Automaton has 44 states. Word has length 129 [2018-06-24 21:16:50,476 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:16:50,477 INFO ]: With dead ends: 266 [2018-06-24 21:16:50,477 INFO ]: Without dead ends: 266 [2018-06-24 21:16:50,478 INFO ]: 0 DeclaredPredicates, 196 GetRequests, 117 SyntacticMatches, 0 SemanticMatches, 79 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1506 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=948, Invalid=5532, Unknown=0, NotChecked=0, Total=6480 [2018-06-24 21:16:50,478 INFO ]: Start minimizeSevpa. Operand 266 states. [2018-06-24 21:16:50,484 INFO ]: Finished minimizeSevpa. Reduced states from 266 to 266. [2018-06-24 21:16:50,484 INFO ]: Start removeUnreachable. Operand 266 states. [2018-06-24 21:16:50,485 INFO ]: Finished removeUnreachable. Reduced from 266 states to 266 states and 305 transitions. [2018-06-24 21:16:50,485 INFO ]: Start accepts. Automaton has 266 states and 305 transitions. Word has length 129 [2018-06-24 21:16:50,485 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:16:50,485 INFO ]: Abstraction has 266 states and 305 transitions. [2018-06-24 21:16:50,485 INFO ]: Interpolant automaton has 44 states. [2018-06-24 21:16:50,486 INFO ]: Start isEmpty. Operand 266 states and 305 transitions. [2018-06-24 21:16:50,487 INFO ]: Finished isEmpty. Found accepting run of length 131 [2018-06-24 21:16:50,487 INFO ]: Found error trace [2018-06-24 21:16:50,487 INFO ]: trace histogram [66, 12, 12, 12, 12, 11, 1, 1, 1, 1, 1] [2018-06-24 21:16:50,487 INFO ]: === Iteration 37 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:16:50,487 INFO ]: Analyzing trace with hash 2080138761, now seen corresponding path program 30 times [2018-06-24 21:16:50,487 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:16:50,487 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:16:50,487 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:50,487 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:16:50,487 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:16:50,529 INFO ]: Conjunction of SSA is unsat Received shutdown request... [2018-06-24 21:16:51,541 WARN ]: Verification canceled [2018-06-24 21:16:51,543 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-24 21:16:51,544 WARN ]: Timeout [2018-06-24 21:16:51,544 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.06 09:16:51 BasicIcfg [2018-06-24 21:16:51,544 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-24 21:16:51,545 INFO ]: Toolchain (without parser) took 55512.31 ms. Allocated memory was 309.9 MB in the beginning and 919.1 MB in the end (delta: 609.2 MB). Free memory was 266.2 MB in the beginning and 252.8 MB in the end (delta: 13.4 MB). Peak memory consumption was 622.7 MB. Max. memory is 3.6 GB. [2018-06-24 21:16:51,546 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 309.9 MB. Free memory is still 275.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-24 21:16:51,546 INFO ]: ChcToBoogie took 57.87 ms. Allocated memory is still 309.9 MB. Free memory was 265.2 MB in the beginning and 263.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-24 21:16:51,546 INFO ]: Boogie Preprocessor took 34.00 ms. Allocated memory is still 309.9 MB. Free memory was 263.2 MB in the beginning and 262.1 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. [2018-06-24 21:16:51,547 INFO ]: RCFGBuilder took 301.02 ms. Allocated memory is still 309.9 MB. Free memory was 262.1 MB in the beginning and 253.1 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. [2018-06-24 21:16:51,547 INFO ]: BlockEncodingV2 took 134.07 ms. Allocated memory is still 309.9 MB. Free memory was 253.1 MB in the beginning and 249.1 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-24 21:16:51,547 INFO ]: TraceAbstraction took 54968.80 ms. Allocated memory was 309.9 MB in the beginning and 919.1 MB in the end (delta: 609.2 MB). Free memory was 248.1 MB in the beginning and 252.8 MB in the end (delta: -4.7 MB). Peak memory consumption was 604.5 MB. Max. memory is 3.6 GB. [2018-06-24 21:16:51,549 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.plugins.blockencoding: - StatisticsResult: Initial Icfg 16 locations, 22 edges - StatisticsResult: Encoded RCFG 10 locations, 15 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 309.9 MB. Free memory is still 275.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 57.87 ms. Allocated memory is still 309.9 MB. Free memory was 265.2 MB in the beginning and 263.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 34.00 ms. Allocated memory is still 309.9 MB. Free memory was 263.2 MB in the beginning and 262.1 MB in the end (delta: 1.1 MB). Peak memory consumption was 1.1 MB. Max. memory is 3.6 GB. * RCFGBuilder took 301.02 ms. Allocated memory is still 309.9 MB. Free memory was 262.1 MB in the beginning and 253.1 MB in the end (delta: 9.0 MB). Peak memory consumption was 9.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 134.07 ms. Allocated memory is still 309.9 MB. Free memory was 253.1 MB in the beginning and 249.1 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 54968.80 ms. Allocated memory was 309.9 MB in the beginning and 919.1 MB in the end (delta: 609.2 MB). Free memory was 248.1 MB in the beginning and 252.8 MB in the end (delta: -4.7 MB). Peak memory consumption was 604.5 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds Cancelled while BasicCegarLoop was analyzing trace of length 131 with TraceHistMax 66, while InterpolatingTraceCheckCraig was constructing Craig interpolants, while PredicateComparison was comparing new predicate (quantifier-free) to 14 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 54.9s OverallTime, 37 OverallIterations, 66 TraceHistogramMax, 25.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 461 SDtfs, 632 SDslu, 3423 SDs, 0 SdLazy, 18682 SolverSat, 1244 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 10.9s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 3180 GetRequests, 1657 SyntacticMatches, 65 SemanticMatches, 1458 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 16187 ImplicationChecksByTransitivity, 33.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=266occurred in iteration=36, 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.3s AutomataMinimizationTime, 36 MinimizatonAttempts, 545 StatesRemovedByMinimization, 21 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.5s SsaConstructionTime, 2.5s SatisfiabilityAnalysisTime, 23.9s InterpolantComputationTime, 3814 NumberOfCodeBlocks, 3758 NumberOfCodeBlocksAsserted, 196 NumberOfCheckSat, 3745 ConstructedInterpolants, 0 QuantifiedInterpolants, 1031826 SizeOfPredicates, 299 NumberOfNonLiveVariables, 17778 ConjunctsInSsa, 1721 ConjunctsInUnsatCore, 69 InterpolantComputations, 5 PerfectInterpolantSequences, 32917/48500 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/enc-rev_append.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-24_21-16-51-559.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/enc-rev_append.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-24_21-16-51-559.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/enc-rev_append.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-24_21-16-51-559.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/enc-rev_append.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-24_21-16-51-559.csv Completed graceful shutdown