java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC_wBE.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/ctigar/barbr.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-62c3406-m [2018-06-26 21:16:21,070 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-26 21:16:21,072 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-26 21:16:21,087 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-26 21:16:21,087 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-26 21:16:21,088 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-26 21:16:21,092 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-26 21:16:21,094 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-26 21:16:21,096 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-26 21:16:21,097 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-26 21:16:21,099 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-26 21:16:21,099 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-26 21:16:21,100 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-26 21:16:21,100 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-26 21:16:21,102 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-26 21:16:21,106 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-26 21:16:21,107 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-26 21:16:21,108 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-26 21:16:21,122 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-26 21:16:21,123 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-26 21:16:21,124 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-26 21:16:21,125 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-26 21:16:21,127 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-26 21:16:21,127 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-26 21:16:21,128 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-26 21:16:21,128 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-26 21:16:21,133 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-26 21:16:21,134 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-26 21:16:21,135 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-26 21:16:21,136 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-26 21:16:21,136 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-26 21:16:21,137 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-26 21:16:21,141 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-06-26 21:16:21,141 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-26 21:16:21,142 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-26 21:16:21,143 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-26 21:16:21,143 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-26 21:16:21,167 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-26 21:16:21,167 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-26 21:16:21,167 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-26 21:16:21,167 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-26 21:16:21,168 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-26 21:16:21,169 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-26 21:16:21,171 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-26 21:16:21,172 INFO L133 SettingsManager]: * Use SBE=true [2018-06-26 21:16:21,172 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-26 21:16:21,172 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-26 21:16:21,172 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-26 21:16:21,172 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-26 21:16:21,173 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 21:16:21,173 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-26 21:16:21,173 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-26 21:16:21,173 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-26 21:16:21,173 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-26 21:16:21,174 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-26 21:16:21,174 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-26 21:16:21,174 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-26 21:16:21,174 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-26 21:16:21,177 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-26 21:16:21,177 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-26 21:16:21,224 INFO ]: Repository-Root is: /tmp [2018-06-26 21:16:21,240 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-26 21:16:21,245 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-26 21:16:21,247 INFO ]: Initializing SmtParser... [2018-06-26 21:16:21,247 INFO ]: SmtParser initialized [2018-06-26 21:16:21,248 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/barbr.c.smt2 [2018-06-26 21:16:21,249 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-26 21:16:21,336 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/barbr.c.smt2 unknown [2018-06-26 21:16:21,953 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/barbr.c.smt2 [2018-06-26 21:16:21,959 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-26 21:16:21,966 INFO ]: Walking toolchain with 5 elements. [2018-06-26 21:16:21,967 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-26 21:16:21,967 INFO ]: Initializing ChcToBoogie... [2018-06-26 21:16:21,967 INFO ]: ChcToBoogie initialized [2018-06-26 21:16:21,971 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 09:16:21" (1/1) ... [2018-06-26 21:16:22,046 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:16:22 Unit [2018-06-26 21:16:22,047 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-26 21:16:22,047 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-26 21:16:22,047 INFO ]: Initializing Boogie Preprocessor... [2018-06-26 21:16:22,047 INFO ]: Boogie Preprocessor initialized [2018-06-26 21:16:22,065 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:16:22" (1/1) ... [2018-06-26 21:16:22,065 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:16:22" (1/1) ... [2018-06-26 21:16:22,081 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:16:22" (1/1) ... [2018-06-26 21:16:22,081 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:16:22" (1/1) ... [2018-06-26 21:16:22,105 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:16:22" (1/1) ... [2018-06-26 21:16:22,107 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:16:22" (1/1) ... [2018-06-26 21:16:22,113 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:16:22" (1/1) ... [2018-06-26 21:16:22,121 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-26 21:16:22,121 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-26 21:16:22,121 INFO ]: Initializing RCFGBuilder... [2018-06-26 21:16:22,121 INFO ]: RCFGBuilder initialized [2018-06-26 21:16:22,122 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:16:22" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-26 21:16:22,132 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-26 21:16:22,132 INFO ]: Found specification of procedure gotoProc [2018-06-26 21:16:22,132 INFO ]: Found implementation of procedure gotoProc [2018-06-26 21:16:22,132 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-26 21:16:22,132 INFO ]: Found specification of procedure Ultimate.START [2018-06-26 21:16:22,132 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 21:16:22,673 INFO ]: Using library mode [2018-06-26 21:16:22,673 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 09:16:22 BoogieIcfgContainer [2018-06-26 21:16:22,673 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-26 21:16:22,674 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-26 21:16:22,674 INFO ]: Initializing BlockEncodingV2... [2018-06-26 21:16:22,675 INFO ]: BlockEncodingV2 initialized [2018-06-26 21:16:22,675 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 09:16:22" (1/1) ... [2018-06-26 21:16:22,694 INFO ]: Initial Icfg 10 locations, 10 edges [2018-06-26 21:16:22,695 INFO ]: Using Remove infeasible edges [2018-06-26 21:16:22,696 INFO ]: Using Maximize final states [2018-06-26 21:16:22,696 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-26 21:16:22,696 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-26 21:16:22,698 INFO ]: Using Remove sink states [2018-06-26 21:16:22,699 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-26 21:16:22,699 INFO ]: Using Use SBE [2018-06-26 21:16:22,707 WARN ]: expecting exponential blowup for input size 9 [2018-06-26 21:16:22,867 WARN ]: aborting because of expected exponential blowup for input size 235 [2018-06-26 21:16:22,889 WARN ]: aborting because of expected exponential blowup for input size 235 [2018-06-26 21:16:22,890 INFO ]: SBE split 1 edges [2018-06-26 21:16:22,896 INFO ]: Removed 2 edges and 2 locations because of local infeasibility [2018-06-26 21:16:22,898 INFO ]: 0 new accepting states [2018-06-26 21:16:23,160 INFO ]: Removed 16 edges and 2 locations by large block encoding [2018-06-26 21:16:23,162 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 21:16:23,163 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-26 21:16:23,163 INFO ]: 0 new accepting states [2018-06-26 21:16:23,163 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-26 21:16:23,164 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 21:16:23,164 INFO ]: Encoded RCFG 6 locations, 18 edges [2018-06-26 21:16:23,164 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 09:16:23 BasicIcfg [2018-06-26 21:16:23,164 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-26 21:16:23,165 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-26 21:16:23,165 INFO ]: Initializing TraceAbstraction... [2018-06-26 21:16:23,170 INFO ]: TraceAbstraction initialized [2018-06-26 21:16:23,170 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 09:16:21" (1/4) ... [2018-06-26 21:16:23,171 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7d1d5240 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 26.06 09:16:23, skipping insertion in model container [2018-06-26 21:16:23,171 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:16:22" (2/4) ... [2018-06-26 21:16:23,171 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7d1d5240 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.06 09:16:23, skipping insertion in model container [2018-06-26 21:16:23,172 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 09:16:22" (3/4) ... [2018-06-26 21:16:23,172 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7d1d5240 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 09:16:23, skipping insertion in model container [2018-06-26 21:16:23,172 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 09:16:23" (4/4) ... [2018-06-26 21:16:23,174 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-26 21:16:23,185 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-26 21:16:23,193 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-26 21:16:23,246 INFO ]: Using default assertion order modulation [2018-06-26 21:16:23,247 INFO ]: Interprodecural is true [2018-06-26 21:16:23,247 INFO ]: Hoare is false [2018-06-26 21:16:23,247 INFO ]: Compute interpolants for FPandBP [2018-06-26 21:16:23,247 INFO ]: Backedges is TWOTRACK [2018-06-26 21:16:23,247 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-26 21:16:23,247 INFO ]: Difference is false [2018-06-26 21:16:23,247 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-26 21:16:23,247 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-26 21:16:23,255 INFO ]: Start isEmpty. Operand 6 states. [2018-06-26 21:16:23,264 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-26 21:16:23,264 INFO ]: Found error trace [2018-06-26 21:16:23,265 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-26 21:16:23,265 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:16:23,271 INFO ]: Analyzing trace with hash 36081989, now seen corresponding path program 1 times [2018-06-26 21:16:23,272 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:16:23,272 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:16:23,303 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:23,303 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:16:23,303 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:23,340 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:23,423 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:23,424 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:16:23,425 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:16:23,426 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:16:23,436 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:16:23,436 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:16:23,438 INFO ]: Start difference. First operand 6 states. Second operand 3 states. [2018-06-26 21:16:23,643 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:16:23,643 INFO ]: Finished difference Result 7 states and 19 transitions. [2018-06-26 21:16:23,643 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:16:23,644 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-26 21:16:23,645 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:16:23,656 INFO ]: With dead ends: 7 [2018-06-26 21:16:23,656 INFO ]: Without dead ends: 7 [2018-06-26 21:16:23,662 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:16:23,680 INFO ]: Start minimizeSevpa. Operand 7 states. [2018-06-26 21:16:23,699 INFO ]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-06-26 21:16:23,700 INFO ]: Start removeUnreachable. Operand 7 states. [2018-06-26 21:16:23,700 INFO ]: Finished removeUnreachable. Reduced from 7 states to 7 states and 19 transitions. [2018-06-26 21:16:23,702 INFO ]: Start accepts. Automaton has 7 states and 19 transitions. Word has length 5 [2018-06-26 21:16:23,703 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:16:23,703 INFO ]: Abstraction has 7 states and 19 transitions. [2018-06-26 21:16:23,703 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:16:23,703 INFO ]: Start isEmpty. Operand 7 states and 19 transitions. [2018-06-26 21:16:23,703 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 21:16:23,703 INFO ]: Found error trace [2018-06-26 21:16:23,703 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 21:16:23,703 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:16:23,703 INFO ]: Analyzing trace with hash 1117554871, now seen corresponding path program 1 times [2018-06-26 21:16:23,703 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:16:23,703 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:16:23,704 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:23,704 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:16:23,704 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:23,886 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:24,174 WARN ]: Spent 124.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-26 21:16:24,174 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:24,175 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:16:24,175 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) [2018-06-26 21:16:24,190 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:16:24,331 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:24,340 INFO ]: Computing forward predicates... [2018-06-26 21:16:24,835 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:24,856 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:16:24,857 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-26 21:16:24,857 INFO ]: Interpolant automaton has 5 states [2018-06-26 21:16:24,857 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 21:16:24,857 INFO ]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2018-06-26 21:16:24,857 INFO ]: Start difference. First operand 7 states and 19 transitions. Second operand 5 states. [2018-06-26 21:16:25,017 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:16:25,017 INFO ]: Finished difference Result 11 states and 23 transitions. [2018-06-26 21:16:25,018 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-26 21:16:25,018 INFO ]: Start accepts. Automaton has 5 states. Word has length 6 [2018-06-26 21:16:25,018 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:16:25,018 INFO ]: With dead ends: 11 [2018-06-26 21:16:25,018 INFO ]: Without dead ends: 11 [2018-06-26 21:16:25,019 INFO ]: 0 DeclaredPredicates, 11 GetRequests, 5 SyntacticMatches, 1 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=18, Invalid=24, Unknown=0, NotChecked=0, Total=42 [2018-06-26 21:16:25,019 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-26 21:16:25,020 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 8. [2018-06-26 21:16:25,020 INFO ]: Start removeUnreachable. Operand 8 states. [2018-06-26 21:16:25,021 INFO ]: Finished removeUnreachable. Reduced from 8 states to 8 states and 20 transitions. [2018-06-26 21:16:25,021 INFO ]: Start accepts. Automaton has 8 states and 20 transitions. Word has length 6 [2018-06-26 21:16:25,021 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:16:25,021 INFO ]: Abstraction has 8 states and 20 transitions. [2018-06-26 21:16:25,021 INFO ]: Interpolant automaton has 5 states. [2018-06-26 21:16:25,021 INFO ]: Start isEmpty. Operand 8 states and 20 transitions. [2018-06-26 21:16:25,021 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 21:16:25,021 INFO ]: Found error trace [2018-06-26 21:16:25,021 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 21:16:25,021 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:16:25,021 INFO ]: Analyzing trace with hash 1110166703, now seen corresponding path program 1 times [2018-06-26 21:16:25,021 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:16:25,022 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:16:25,022 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:25,022 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:16:25,022 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:25,091 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:25,263 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:25,263 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:16:25,263 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:16:25,282 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:16:25,385 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:25,391 INFO ]: Computing forward predicates... [2018-06-26 21:16:25,652 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:25,672 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:16:25,672 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-26 21:16:25,672 INFO ]: Interpolant automaton has 5 states [2018-06-26 21:16:25,672 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 21:16:25,672 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-26 21:16:25,672 INFO ]: Start difference. First operand 8 states and 20 transitions. Second operand 5 states. [2018-06-26 21:16:25,746 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:16:25,747 INFO ]: Finished difference Result 13 states and 25 transitions. [2018-06-26 21:16:25,747 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-26 21:16:25,747 INFO ]: Start accepts. Automaton has 5 states. Word has length 6 [2018-06-26 21:16:25,747 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:16:25,748 INFO ]: With dead ends: 13 [2018-06-26 21:16:25,748 INFO ]: Without dead ends: 13 [2018-06-26 21:16:25,748 INFO ]: 0 DeclaredPredicates, 10 GetRequests, 5 SyntacticMatches, 1 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-26 21:16:25,748 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-26 21:16:25,750 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 9. [2018-06-26 21:16:25,750 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-26 21:16:25,750 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 21 transitions. [2018-06-26 21:16:25,750 INFO ]: Start accepts. Automaton has 9 states and 21 transitions. Word has length 6 [2018-06-26 21:16:25,750 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:16:25,750 INFO ]: Abstraction has 9 states and 21 transitions. [2018-06-26 21:16:25,750 INFO ]: Interpolant automaton has 5 states. [2018-06-26 21:16:25,750 INFO ]: Start isEmpty. Operand 9 states and 21 transitions. [2018-06-26 21:16:25,750 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-26 21:16:25,751 INFO ]: Found error trace [2018-06-26 21:16:25,751 INFO ]: trace histogram [2, 1, 1, 1, 1, 1] [2018-06-26 21:16:25,751 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:16:25,751 INFO ]: Analyzing trace with hash 283475845, now seen corresponding path program 2 times [2018-06-26 21:16:25,751 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:16:25,751 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:16:25,752 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:25,752 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:16:25,752 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:25,864 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:26,330 WARN ]: Spent 208.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-26 21:16:26,401 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:26,401 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:16:26,401 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:16:26,409 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 21:16:26,560 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 21:16:26,560 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:26,565 INFO ]: Computing forward predicates... [2018-06-26 21:16:27,669 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:27,701 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:16:27,701 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 6 [2018-06-26 21:16:27,701 INFO ]: Interpolant automaton has 6 states [2018-06-26 21:16:27,702 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-26 21:16:27,702 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-26 21:16:27,702 INFO ]: Start difference. First operand 9 states and 21 transitions. Second operand 6 states. [2018-06-26 21:16:28,454 WARN ]: Spent 506.00 ms on a formula simplification. DAG size of input: 12 DAG size of output: 12 [2018-06-26 21:16:28,701 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:16:28,701 INFO ]: Finished difference Result 16 states and 28 transitions. [2018-06-26 21:16:28,702 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-26 21:16:28,702 INFO ]: Start accepts. Automaton has 6 states. Word has length 7 [2018-06-26 21:16:28,702 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:16:28,702 INFO ]: With dead ends: 16 [2018-06-26 21:16:28,702 INFO ]: Without dead ends: 16 [2018-06-26 21:16:28,703 INFO ]: 0 DeclaredPredicates, 14 GetRequests, 5 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=31, Invalid=41, Unknown=0, NotChecked=0, Total=72 [2018-06-26 21:16:28,703 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-26 21:16:28,704 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 9. [2018-06-26 21:16:28,705 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-26 21:16:28,705 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 21 transitions. [2018-06-26 21:16:28,705 INFO ]: Start accepts. Automaton has 9 states and 21 transitions. Word has length 7 [2018-06-26 21:16:28,705 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:16:28,705 INFO ]: Abstraction has 9 states and 21 transitions. [2018-06-26 21:16:28,705 INFO ]: Interpolant automaton has 6 states. [2018-06-26 21:16:28,705 INFO ]: Start isEmpty. Operand 9 states and 21 transitions. [2018-06-26 21:16:28,705 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-26 21:16:28,705 INFO ]: Found error trace [2018-06-26 21:16:28,705 INFO ]: trace histogram [3, 1, 1, 1, 1, 1] [2018-06-26 21:16:28,706 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:16:28,707 INFO ]: Analyzing trace with hash 196829815, now seen corresponding path program 3 times [2018-06-26 21:16:28,707 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:16:28,707 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:16:28,708 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:28,708 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:16:28,708 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:28,851 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:29,204 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:29,204 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:16:29,204 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:16:29,211 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 21:16:29,430 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-26 21:16:29,430 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:29,436 INFO ]: Computing forward predicates... [2018-06-26 21:16:30,896 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:30,929 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:16:30,929 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2018-06-26 21:16:30,929 INFO ]: Interpolant automaton has 7 states [2018-06-26 21:16:30,930 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-26 21:16:30,930 INFO ]: CoverageRelationStatistics Valid=14, Invalid=28, Unknown=0, NotChecked=0, Total=42 [2018-06-26 21:16:30,930 INFO ]: Start difference. First operand 9 states and 21 transitions. Second operand 7 states. [2018-06-26 21:16:31,587 WARN ]: Spent 386.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 13 [2018-06-26 21:16:31,815 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:16:31,815 INFO ]: Finished difference Result 15 states and 27 transitions. [2018-06-26 21:16:31,815 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-26 21:16:31,815 INFO ]: Start accepts. Automaton has 7 states. Word has length 8 [2018-06-26 21:16:31,815 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:16:31,815 INFO ]: With dead ends: 15 [2018-06-26 21:16:31,816 INFO ]: Without dead ends: 15 [2018-06-26 21:16:31,816 INFO ]: 0 DeclaredPredicates, 18 GetRequests, 5 SyntacticMatches, 3 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=51, Invalid=81, Unknown=0, NotChecked=0, Total=132 [2018-06-26 21:16:31,816 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-26 21:16:31,817 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 10. [2018-06-26 21:16:31,817 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-26 21:16:31,818 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 22 transitions. [2018-06-26 21:16:31,818 INFO ]: Start accepts. Automaton has 10 states and 22 transitions. Word has length 8 [2018-06-26 21:16:31,818 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:16:31,818 INFO ]: Abstraction has 10 states and 22 transitions. [2018-06-26 21:16:31,818 INFO ]: Interpolant automaton has 7 states. [2018-06-26 21:16:31,818 INFO ]: Start isEmpty. Operand 10 states and 22 transitions. [2018-06-26 21:16:31,818 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-26 21:16:31,818 INFO ]: Found error trace [2018-06-26 21:16:31,818 INFO ]: trace histogram [3, 1, 1, 1, 1, 1] [2018-06-26 21:16:31,818 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:16:31,819 INFO ]: Analyzing trace with hash 1971837177, now seen corresponding path program 1 times [2018-06-26 21:16:31,819 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:16:31,819 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:16:31,819 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:31,819 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:16:31,819 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:31,927 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:32,231 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:32,232 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:16:32,232 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:16:32,239 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:16:32,408 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:32,413 INFO ]: Computing forward predicates... [2018-06-26 21:16:45,493 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:45,515 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:16:45,515 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-26 21:16:45,515 INFO ]: Interpolant automaton has 6 states [2018-06-26 21:16:45,515 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-26 21:16:45,515 INFO ]: CoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2018-06-26 21:16:45,516 INFO ]: Start difference. First operand 10 states and 22 transitions. Second operand 6 states. [2018-06-26 21:16:45,724 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:16:45,724 INFO ]: Finished difference Result 18 states and 30 transitions. [2018-06-26 21:16:45,724 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-26 21:16:45,724 INFO ]: Start accepts. Automaton has 6 states. Word has length 8 [2018-06-26 21:16:45,724 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:16:45,724 INFO ]: With dead ends: 18 [2018-06-26 21:16:45,724 INFO ]: Without dead ends: 18 [2018-06-26 21:16:45,725 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 6 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2018-06-26 21:16:45,725 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-26 21:16:45,726 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 10. [2018-06-26 21:16:45,726 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-26 21:16:45,727 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 22 transitions. [2018-06-26 21:16:45,727 INFO ]: Start accepts. Automaton has 10 states and 22 transitions. Word has length 8 [2018-06-26 21:16:45,727 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:16:45,727 INFO ]: Abstraction has 10 states and 22 transitions. [2018-06-26 21:16:45,727 INFO ]: Interpolant automaton has 6 states. [2018-06-26 21:16:45,727 INFO ]: Start isEmpty. Operand 10 states and 22 transitions. [2018-06-26 21:16:45,727 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-26 21:16:45,727 INFO ]: Found error trace [2018-06-26 21:16:45,727 INFO ]: trace histogram [4, 1, 1, 1, 1, 1] [2018-06-26 21:16:45,727 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:16:45,727 INFO ]: Analyzing trace with hash 1805770181, now seen corresponding path program 4 times [2018-06-26 21:16:45,727 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:16:45,727 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:16:45,728 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:45,728 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:16:45,728 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:45,849 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:46,258 WARN ]: Spent 131.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-26 21:16:46,294 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:46,294 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:16:46,294 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:16:46,300 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 21:16:46,495 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 21:16:46,495 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:46,502 INFO ]: Computing forward predicates... [2018-06-26 21:16:49,080 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:49,100 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:16:49,100 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-06-26 21:16:49,101 INFO ]: Interpolant automaton has 8 states [2018-06-26 21:16:49,101 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-26 21:16:49,101 INFO ]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-06-26 21:16:49,101 INFO ]: Start difference. First operand 10 states and 22 transitions. Second operand 8 states. [2018-06-26 21:16:49,471 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:16:49,471 INFO ]: Finished difference Result 17 states and 29 transitions. [2018-06-26 21:16:49,471 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-26 21:16:49,471 INFO ]: Start accepts. Automaton has 8 states. Word has length 9 [2018-06-26 21:16:49,471 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:16:49,471 INFO ]: With dead ends: 17 [2018-06-26 21:16:49,471 INFO ]: Without dead ends: 17 [2018-06-26 21:16:49,472 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 5 SyntacticMatches, 4 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 29 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=69, Invalid=113, Unknown=0, NotChecked=0, Total=182 [2018-06-26 21:16:49,472 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-26 21:16:49,473 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 11. [2018-06-26 21:16:49,473 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-26 21:16:49,474 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 23 transitions. [2018-06-26 21:16:49,474 INFO ]: Start accepts. Automaton has 11 states and 23 transitions. Word has length 9 [2018-06-26 21:16:49,474 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:16:49,474 INFO ]: Abstraction has 11 states and 23 transitions. [2018-06-26 21:16:49,474 INFO ]: Interpolant automaton has 8 states. [2018-06-26 21:16:49,474 INFO ]: Start isEmpty. Operand 11 states and 23 transitions. [2018-06-26 21:16:49,474 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-26 21:16:49,474 INFO ]: Found error trace [2018-06-26 21:16:49,474 INFO ]: trace histogram [4, 1, 1, 1, 1, 1] [2018-06-26 21:16:49,474 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:16:49,474 INFO ]: Analyzing trace with hash 996423555, now seen corresponding path program 2 times [2018-06-26 21:16:49,474 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:16:49,475 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:16:49,475 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:49,475 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:16:49,475 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:49,584 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:50,106 WARN ]: Spent 220.00 ms on a formula simplification that was a NOOP. DAG size: 10 [2018-06-26 21:16:50,261 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:50,261 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:16:50,261 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:16:50,268 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 21:16:50,545 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 21:16:50,545 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:50,553 INFO ]: Computing forward predicates... [2018-06-26 21:16:51,086 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:51,108 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:16:51,108 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2018-06-26 21:16:51,108 INFO ]: Interpolant automaton has 7 states [2018-06-26 21:16:51,108 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-26 21:16:51,108 INFO ]: CoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2018-06-26 21:16:51,108 INFO ]: Start difference. First operand 11 states and 23 transitions. Second operand 7 states. [2018-06-26 21:16:51,360 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:16:51,360 INFO ]: Finished difference Result 21 states and 33 transitions. [2018-06-26 21:16:51,360 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-06-26 21:16:51,360 INFO ]: Start accepts. Automaton has 7 states. Word has length 9 [2018-06-26 21:16:51,360 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:16:51,361 INFO ]: With dead ends: 21 [2018-06-26 21:16:51,361 INFO ]: Without dead ends: 21 [2018-06-26 21:16:51,361 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 6 SyntacticMatches, 4 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=43, Invalid=67, Unknown=0, NotChecked=0, Total=110 [2018-06-26 21:16:51,361 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-26 21:16:51,362 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 11. [2018-06-26 21:16:51,362 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-26 21:16:51,363 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 23 transitions. [2018-06-26 21:16:51,363 INFO ]: Start accepts. Automaton has 11 states and 23 transitions. Word has length 9 [2018-06-26 21:16:51,363 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:16:51,363 INFO ]: Abstraction has 11 states and 23 transitions. [2018-06-26 21:16:51,363 INFO ]: Interpolant automaton has 7 states. [2018-06-26 21:16:51,363 INFO ]: Start isEmpty. Operand 11 states and 23 transitions. [2018-06-26 21:16:51,363 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-26 21:16:51,363 INFO ]: Found error trace [2018-06-26 21:16:51,364 INFO ]: trace histogram [5, 1, 1, 1, 1, 1] [2018-06-26 21:16:51,364 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:16:51,365 INFO ]: Analyzing trace with hash 143313975, now seen corresponding path program 5 times [2018-06-26 21:16:51,365 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:16:51,365 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:16:51,365 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:51,365 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:16:51,365 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:51,466 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:51,776 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:51,776 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:16:51,776 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:16:51,782 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-26 21:16:52,061 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-26 21:16:52,061 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:52,070 INFO ]: Computing forward predicates... [2018-06-26 21:16:53,071 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:53,091 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:16:53,091 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 9 [2018-06-26 21:16:53,092 INFO ]: Interpolant automaton has 9 states [2018-06-26 21:16:53,092 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-26 21:16:53,092 INFO ]: CoverageRelationStatistics Valid=22, Invalid=50, Unknown=0, NotChecked=0, Total=72 [2018-06-26 21:16:53,092 INFO ]: Start difference. First operand 11 states and 23 transitions. Second operand 9 states. [2018-06-26 21:16:53,472 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:16:53,472 INFO ]: Finished difference Result 19 states and 31 transitions. [2018-06-26 21:16:53,472 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-26 21:16:53,472 INFO ]: Start accepts. Automaton has 9 states. Word has length 10 [2018-06-26 21:16:53,473 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:16:53,473 INFO ]: With dead ends: 19 [2018-06-26 21:16:53,473 INFO ]: Without dead ends: 19 [2018-06-26 21:16:53,473 INFO ]: 0 DeclaredPredicates, 24 GetRequests, 5 SyntacticMatches, 5 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=89, Invalid=151, Unknown=0, NotChecked=0, Total=240 [2018-06-26 21:16:53,473 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-26 21:16:53,475 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 12. [2018-06-26 21:16:53,475 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-26 21:16:53,475 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 24 transitions. [2018-06-26 21:16:53,475 INFO ]: Start accepts. Automaton has 12 states and 24 transitions. Word has length 10 [2018-06-26 21:16:53,476 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:16:53,476 INFO ]: Abstraction has 12 states and 24 transitions. [2018-06-26 21:16:53,476 INFO ]: Interpolant automaton has 9 states. [2018-06-26 21:16:53,476 INFO ]: Start isEmpty. Operand 12 states and 24 transitions. [2018-06-26 21:16:53,476 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-26 21:16:53,476 INFO ]: Found error trace [2018-06-26 21:16:53,476 INFO ]: trace histogram [5, 1, 1, 1, 1, 1] [2018-06-26 21:16:53,476 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:16:53,476 INFO ]: Analyzing trace with hash 823372345, now seen corresponding path program 3 times [2018-06-26 21:16:53,476 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:16:53,476 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:16:53,477 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:53,477 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:16:53,477 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:53,571 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:53,776 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:53,776 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:16:53,776 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:16:53,782 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 21:16:54,036 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2018-06-26 21:16:54,036 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:54,045 INFO ]: Computing forward predicates... [2018-06-26 21:16:55,040 INFO ]: Checked inductivity of 15 backedges. 0 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:55,061 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:16:55,061 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-26 21:16:55,061 INFO ]: Interpolant automaton has 8 states [2018-06-26 21:16:55,061 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-26 21:16:55,061 INFO ]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-06-26 21:16:55,061 INFO ]: Start difference. First operand 12 states and 24 transitions. Second operand 8 states. [2018-06-26 21:16:55,456 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:16:55,456 INFO ]: Finished difference Result 24 states and 36 transitions. [2018-06-26 21:16:55,456 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-26 21:16:55,456 INFO ]: Start accepts. Automaton has 8 states. Word has length 10 [2018-06-26 21:16:55,456 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:16:55,457 INFO ]: With dead ends: 24 [2018-06-26 21:16:55,457 INFO ]: Without dead ends: 24 [2018-06-26 21:16:55,457 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 7 SyntacticMatches, 4 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 10 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=58, Invalid=98, Unknown=0, NotChecked=0, Total=156 [2018-06-26 21:16:55,457 INFO ]: Start minimizeSevpa. Operand 24 states. [2018-06-26 21:16:55,459 INFO ]: Finished minimizeSevpa. Reduced states from 24 to 12. [2018-06-26 21:16:55,459 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-26 21:16:55,459 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 24 transitions. [2018-06-26 21:16:55,459 INFO ]: Start accepts. Automaton has 12 states and 24 transitions. Word has length 10 [2018-06-26 21:16:55,459 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:16:55,459 INFO ]: Abstraction has 12 states and 24 transitions. [2018-06-26 21:16:55,459 INFO ]: Interpolant automaton has 8 states. [2018-06-26 21:16:55,459 INFO ]: Start isEmpty. Operand 12 states and 24 transitions. [2018-06-26 21:16:55,460 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-26 21:16:55,460 INFO ]: Found error trace [2018-06-26 21:16:55,460 INFO ]: trace histogram [6, 1, 1, 1, 1, 1] [2018-06-26 21:16:55,460 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:16:55,460 INFO ]: Analyzing trace with hash 146779141, now seen corresponding path program 6 times [2018-06-26 21:16:55,460 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:16:55,460 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:16:55,460 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:55,460 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:16:55,460 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:16:55,569 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:55,876 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:55,876 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:16:55,876 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:16:55,890 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-26 21:16:56,191 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 4 check-sat command(s) [2018-06-26 21:16:56,191 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:16:56,200 INFO ]: Computing forward predicates... [2018-06-26 21:16:59,697 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:16:59,717 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:16:59,717 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 10 [2018-06-26 21:16:59,717 INFO ]: Interpolant automaton has 10 states [2018-06-26 21:16:59,718 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-26 21:16:59,718 INFO ]: CoverageRelationStatistics Valid=26, Invalid=64, Unknown=0, NotChecked=0, Total=90 [2018-06-26 21:16:59,718 INFO ]: Start difference. First operand 12 states and 24 transitions. Second operand 10 states. [2018-06-26 21:17:00,182 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:17:00,182 INFO ]: Finished difference Result 21 states and 33 transitions. [2018-06-26 21:17:00,182 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-26 21:17:00,182 INFO ]: Start accepts. Automaton has 10 states. Word has length 11 [2018-06-26 21:17:00,182 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:17:00,183 INFO ]: With dead ends: 21 [2018-06-26 21:17:00,183 INFO ]: Without dead ends: 21 [2018-06-26 21:17:00,183 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 6 SyntacticMatches, 5 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 53 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=111, Invalid=195, Unknown=0, NotChecked=0, Total=306 [2018-06-26 21:17:00,183 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-26 21:17:00,185 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 13. [2018-06-26 21:17:00,185 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-26 21:17:00,185 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 25 transitions. [2018-06-26 21:17:00,185 INFO ]: Start accepts. Automaton has 13 states and 25 transitions. Word has length 11 [2018-06-26 21:17:00,185 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:17:00,185 INFO ]: Abstraction has 13 states and 25 transitions. [2018-06-26 21:17:00,185 INFO ]: Interpolant automaton has 10 states. [2018-06-26 21:17:00,185 INFO ]: Start isEmpty. Operand 13 states and 25 transitions. [2018-06-26 21:17:00,185 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-26 21:17:00,185 INFO ]: Found error trace [2018-06-26 21:17:00,185 INFO ]: trace histogram [6, 1, 1, 1, 1, 1] [2018-06-26 21:17:00,186 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:17:00,186 INFO ]: Analyzing trace with hash -246247869, now seen corresponding path program 4 times [2018-06-26 21:17:00,186 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:17:00,187 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:17:00,187 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:17:00,187 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:17:00,187 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:17:00,293 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:17:00,528 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:17:00,528 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:17:00,528 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:17:00,534 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 21:17:00,816 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 21:17:00,816 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:17:00,824 INFO ]: Computing forward predicates... [2018-06-26 21:17:13,236 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:17:13,257 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:17:13,257 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 9 [2018-06-26 21:17:13,257 INFO ]: Interpolant automaton has 9 states [2018-06-26 21:17:13,257 INFO ]: Constructing interpolant automaton starting with 9 interpolants. [2018-06-26 21:17:13,257 INFO ]: CoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2018-06-26 21:17:13,257 INFO ]: Start difference. First operand 13 states and 25 transitions. Second operand 9 states. [2018-06-26 21:17:13,756 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:17:13,756 INFO ]: Finished difference Result 27 states and 39 transitions. [2018-06-26 21:17:13,756 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-26 21:17:13,756 INFO ]: Start accepts. Automaton has 9 states. Word has length 11 [2018-06-26 21:17:13,756 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:17:13,757 INFO ]: With dead ends: 27 [2018-06-26 21:17:13,757 INFO ]: Without dead ends: 27 [2018-06-26 21:17:13,757 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 6 SyntacticMatches, 6 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=75, Invalid=135, Unknown=0, NotChecked=0, Total=210 [2018-06-26 21:17:13,757 INFO ]: Start minimizeSevpa. Operand 27 states. [2018-06-26 21:17:13,759 INFO ]: Finished minimizeSevpa. Reduced states from 27 to 13. [2018-06-26 21:17:13,759 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-26 21:17:13,759 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 25 transitions. [2018-06-26 21:17:13,759 INFO ]: Start accepts. Automaton has 13 states and 25 transitions. Word has length 11 [2018-06-26 21:17:13,759 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:17:13,759 INFO ]: Abstraction has 13 states and 25 transitions. [2018-06-26 21:17:13,759 INFO ]: Interpolant automaton has 9 states. [2018-06-26 21:17:13,759 INFO ]: Start isEmpty. Operand 13 states and 25 transitions. [2018-06-26 21:17:13,760 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-26 21:17:13,760 INFO ]: Found error trace [2018-06-26 21:17:13,760 INFO ]: trace histogram [7, 1, 1, 1, 1, 1] [2018-06-26 21:17:13,761 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:17:13,761 INFO ]: Analyzing trace with hash 254199287, now seen corresponding path program 7 times [2018-06-26 21:17:13,761 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:17:13,761 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:17:13,762 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:17:13,762 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:17:13,762 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:17:13,859 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:17:14,126 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:17:14,126 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:17:14,126 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:17:14,131 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:17:14,442 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:17:14,452 INFO ]: Computing forward predicates... Received shutdown request... [2018-06-26 21:17:25,497 INFO ]: Timeout while computing interpolants [2018-06-26 21:17:25,698 WARN ]: Destroyed unattended storables created during the last iteration: 14 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:17:25,698 WARN ]: Verification canceled [2018-06-26 21:17:25,700 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-26 21:17:25,701 WARN ]: Timeout [2018-06-26 21:17:25,701 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 09:17:25 BasicIcfg [2018-06-26 21:17:25,701 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-26 21:17:25,702 INFO ]: Toolchain (without parser) took 63742.86 ms. Allocated memory was 297.8 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 201.3 MB in the beginning and 248.8 MB in the end (delta: -47.5 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-26 21:17:25,703 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 297.8 MB. Free memory is still 263.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-26 21:17:25,703 INFO ]: ChcToBoogie took 80.14 ms. Allocated memory is still 297.8 MB. Free memory was 201.3 MB in the beginning and 196.3 MB in the end (delta: 5.0 MB). Peak memory consumption was 5.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:17:25,704 INFO ]: Boogie Preprocessor took 73.49 ms. Allocated memory is still 297.8 MB. Free memory was 196.3 MB in the beginning and 193.3 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:17:25,704 INFO ]: RCFGBuilder took 552.39 ms. Allocated memory was 297.8 MB in the beginning and 326.6 MB in the end (delta: 28.8 MB). Free memory was 193.3 MB in the beginning and 266.9 MB in the end (delta: -73.6 MB). Peak memory consumption was 21.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:17:25,704 INFO ]: BlockEncodingV2 took 490.32 ms. Allocated memory is still 326.6 MB. Free memory was 266.9 MB in the beginning and 212.8 MB in the end (delta: 54.0 MB). Peak memory consumption was 54.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:17:25,705 INFO ]: TraceAbstraction took 62536.16 ms. Allocated memory was 326.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 212.8 MB in the beginning and 248.8 MB in the end (delta: -35.9 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-26 21:17:25,709 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.plugins.blockencoding: - StatisticsResult: Initial Icfg 10 locations, 10 edges - StatisticsResult: Encoded RCFG 6 locations, 18 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.06 ms. Allocated memory is still 297.8 MB. Free memory is still 263.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 80.14 ms. Allocated memory is still 297.8 MB. Free memory was 201.3 MB in the beginning and 196.3 MB in the end (delta: 5.0 MB). Peak memory consumption was 5.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 73.49 ms. Allocated memory is still 297.8 MB. Free memory was 196.3 MB in the beginning and 193.3 MB in the end (delta: 3.0 MB). Peak memory consumption was 3.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 552.39 ms. Allocated memory was 297.8 MB in the beginning and 326.6 MB in the end (delta: 28.8 MB). Free memory was 193.3 MB in the beginning and 266.9 MB in the end (delta: -73.6 MB). Peak memory consumption was 21.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 490.32 ms. Allocated memory is still 326.6 MB. Free memory was 266.9 MB in the beginning and 212.8 MB in the end (delta: 54.0 MB). Peak memory consumption was 54.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 62536.16 ms. Allocated memory was 326.6 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 212.8 MB in the beginning and 248.8 MB in the end (delta: -35.9 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds Cancelled while BasicCegarLoop was analyzing trace of length 13 with TraceHistMax 7, while TraceCheckSpWp was constructing forward predicates, while XnfDer was eliminating 31 quantified variables from 10 xjuncts. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 6 locations, 1 error locations. TIMEOUT Result, 62.4s OverallTime, 13 OverallIterations, 7 TraceHistogramMax, 4.9s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 204 SDtfs, 0 SDslu, 168 SDs, 0 SdLazy, 219 SolverSat, 445 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 1.3s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 210 GetRequests, 63 SyntacticMatches, 38 SemanticMatches, 109 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 184 ImplicationChecksByTransitivity, 6.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=13occurred in iteration=11, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 12 MinimizatonAttempts, 84 StatesRemovedByMinimization, 11 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.2s SsaConstructionTime, 3.3s SatisfiabilityAnalysisTime, 41.4s InterpolantComputationTime, 195 NumberOfCodeBlocks, 195 NumberOfCodeBlocksAsserted, 36 NumberOfCheckSat, 172 ConstructedInterpolants, 0 QuantifiedInterpolants, 7745 SizeOfPredicates, 88 NumberOfNonLiveVariables, 10854 ConjunctsInSsa, 459 ConjunctsInUnsatCore, 23 InterpolantComputations, 1 PerfectInterpolantSequences, 0/218 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/barbr.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-26_21-17-25-719.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/barbr.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-26_21-17-25-719.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/barbr.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-26_21-17-25-719.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/barbr.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-26_21-17-25-719.csv Completed graceful shutdown