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/dillig03.c.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-62c3406-m [2018-06-26 21:20:22,154 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-26 21:20:22,156 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-26 21:20:22,168 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-26 21:20:22,168 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-26 21:20:22,169 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-26 21:20:22,170 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-26 21:20:22,172 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-26 21:20:22,173 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-26 21:20:22,174 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-26 21:20:22,175 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-26 21:20:22,175 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-26 21:20:22,176 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-26 21:20:22,177 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-26 21:20:22,178 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-26 21:20:22,178 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-26 21:20:22,179 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-26 21:20:22,181 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-26 21:20:22,183 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-26 21:20:22,184 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-26 21:20:22,185 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-26 21:20:22,187 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-26 21:20:22,189 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-26 21:20:22,190 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-26 21:20:22,190 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-26 21:20:22,191 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-26 21:20:22,192 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-26 21:20:22,192 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-26 21:20:22,193 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-26 21:20:22,194 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-26 21:20:22,195 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-26 21:20:22,195 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-26 21:20:22,195 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-06-26 21:20:22,196 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-26 21:20:22,197 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-26 21:20:22,197 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-26 21:20:22,198 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:20:22,212 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-26 21:20:22,213 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-26 21:20:22,213 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-26 21:20:22,213 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-26 21:20:22,214 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-26 21:20:22,215 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-26 21:20:22,215 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-26 21:20:22,215 INFO L133 SettingsManager]: * Use SBE=true [2018-06-26 21:20:22,215 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-26 21:20:22,215 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-26 21:20:22,216 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-26 21:20:22,216 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-26 21:20:22,216 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 21:20:22,216 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-26 21:20:22,216 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-26 21:20:22,217 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-26 21:20:22,217 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-26 21:20:22,217 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-26 21:20:22,217 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-26 21:20:22,217 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-26 21:20:22,218 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-26 21:20:22,219 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-26 21:20:22,220 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-26 21:20:22,260 INFO ]: Repository-Root is: /tmp [2018-06-26 21:20:22,272 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-26 21:20:22,275 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-26 21:20:22,277 INFO ]: Initializing SmtParser... [2018-06-26 21:20:22,277 INFO ]: SmtParser initialized [2018-06-26 21:20:22,281 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig03.c.smt2 [2018-06-26 21:20:22,282 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:20:22,376 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig03.c.smt2 unknown [2018-06-26 21:20:22,622 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/ctigar/dillig03.c.smt2 [2018-06-26 21:20:22,631 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-26 21:20:22,636 INFO ]: Walking toolchain with 5 elements. [2018-06-26 21:20:22,637 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-26 21:20:22,637 INFO ]: Initializing ChcToBoogie... [2018-06-26 21:20:22,637 INFO ]: ChcToBoogie initialized [2018-06-26 21:20:22,641 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 09:20:22" (1/1) ... [2018-06-26 21:20:22,697 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:20:22 Unit [2018-06-26 21:20:22,697 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-26 21:20:22,698 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-26 21:20:22,698 INFO ]: Initializing Boogie Preprocessor... [2018-06-26 21:20:22,698 INFO ]: Boogie Preprocessor initialized [2018-06-26 21:20:22,721 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:20:22" (1/1) ... [2018-06-26 21:20:22,721 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:20:22" (1/1) ... [2018-06-26 21:20:22,729 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:20:22" (1/1) ... [2018-06-26 21:20:22,729 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:20:22" (1/1) ... [2018-06-26 21:20:22,733 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:20:22" (1/1) ... [2018-06-26 21:20:22,734 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:20:22" (1/1) ... [2018-06-26 21:20:22,741 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:20:22" (1/1) ... [2018-06-26 21:20:22,742 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-26 21:20:22,743 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-26 21:20:22,743 INFO ]: Initializing RCFGBuilder... [2018-06-26 21:20:22,743 INFO ]: RCFGBuilder initialized [2018-06-26 21:20:22,745 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:20: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:20:22,763 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-26 21:20:22,763 INFO ]: Found specification of procedure gotoProc [2018-06-26 21:20:22,763 INFO ]: Found implementation of procedure gotoProc [2018-06-26 21:20:22,763 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-26 21:20:22,763 INFO ]: Found specification of procedure Ultimate.START [2018-06-26 21:20:22,763 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:20:22,976 INFO ]: Using library mode [2018-06-26 21:20:22,976 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 09:20:22 BoogieIcfgContainer [2018-06-26 21:20:22,977 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-26 21:20:22,977 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-26 21:20:22,977 INFO ]: Initializing BlockEncodingV2... [2018-06-26 21:20:22,978 INFO ]: BlockEncodingV2 initialized [2018-06-26 21:20:22,979 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 09:20:22" (1/1) ... [2018-06-26 21:20:23,002 INFO ]: Initial Icfg 10 locations, 10 edges [2018-06-26 21:20:23,004 INFO ]: Using Remove infeasible edges [2018-06-26 21:20:23,004 INFO ]: Using Maximize final states [2018-06-26 21:20:23,005 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-26 21:20:23,005 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-26 21:20:23,016 INFO ]: Using Remove sink states [2018-06-26 21:20:23,017 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-26 21:20:23,017 INFO ]: Using Use SBE [2018-06-26 21:20:23,025 WARN ]: expecting exponential blowup for input size 20 [2018-06-26 21:20:27,060 INFO ]: SBE split 1 edges [2018-06-26 21:20:27,075 INFO ]: Removed 2 edges and 2 locations because of local infeasibility [2018-06-26 21:20:27,083 INFO ]: 0 new accepting states [2018-06-26 21:20:27,116 INFO ]: Removed 4 edges and 2 locations by large block encoding [2018-06-26 21:20:27,118 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 21:20:27,131 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-26 21:20:27,131 INFO ]: 0 new accepting states [2018-06-26 21:20:27,131 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-26 21:20:27,132 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 21:20:27,146 INFO ]: Encoded RCFG 6 locations, 191 edges [2018-06-26 21:20:27,146 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 09:20:27 BasicIcfg [2018-06-26 21:20:27,146 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-26 21:20:27,148 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-26 21:20:27,148 INFO ]: Initializing TraceAbstraction... [2018-06-26 21:20:27,151 INFO ]: TraceAbstraction initialized [2018-06-26 21:20:27,151 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 09:20:22" (1/4) ... [2018-06-26 21:20:27,152 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@122b3fd5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 26.06 09:20:27, skipping insertion in model container [2018-06-26 21:20:27,152 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 09:20:22" (2/4) ... [2018-06-26 21:20:27,152 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@122b3fd5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.06 09:20:27, skipping insertion in model container [2018-06-26 21:20:27,152 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 09:20:22" (3/4) ... [2018-06-26 21:20:27,153 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@122b3fd5 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 09:20:27, skipping insertion in model container [2018-06-26 21:20:27,153 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 09:20:27" (4/4) ... [2018-06-26 21:20:27,154 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-26 21:20:27,162 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-26 21:20:27,168 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-26 21:20:27,202 INFO ]: Using default assertion order modulation [2018-06-26 21:20:27,202 INFO ]: Interprodecural is true [2018-06-26 21:20:27,202 INFO ]: Hoare is false [2018-06-26 21:20:27,202 INFO ]: Compute interpolants for FPandBP [2018-06-26 21:20:27,202 INFO ]: Backedges is TWOTRACK [2018-06-26 21:20:27,202 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-26 21:20:27,202 INFO ]: Difference is false [2018-06-26 21:20:27,203 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-26 21:20:27,203 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-26 21:20:27,212 INFO ]: Start isEmpty. Operand 6 states. [2018-06-26 21:20:27,223 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-26 21:20:27,223 INFO ]: Found error trace [2018-06-26 21:20:27,227 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-26 21:20:27,227 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:27,231 INFO ]: Analyzing trace with hash 41122434, now seen corresponding path program 1 times [2018-06-26 21:20:27,232 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:27,232 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:27,266 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:27,267 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:27,267 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:27,322 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:27,389 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:20:27,390 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:20:27,390 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:20:27,392 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:20:27,402 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:20:27,402 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:20:27,404 INFO ]: Start difference. First operand 6 states. Second operand 3 states. [2018-06-26 21:20:28,819 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:28,819 INFO ]: Finished difference Result 7 states and 311 transitions. [2018-06-26 21:20:28,819 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:20:28,820 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-26 21:20:28,820 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:28,831 INFO ]: With dead ends: 7 [2018-06-26 21:20:28,831 INFO ]: Without dead ends: 7 [2018-06-26 21:20:28,833 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:20:28,853 INFO ]: Start minimizeSevpa. Operand 7 states. [2018-06-26 21:20:28,876 INFO ]: Finished minimizeSevpa. Reduced states from 7 to 7. [2018-06-26 21:20:28,877 INFO ]: Start removeUnreachable. Operand 7 states. [2018-06-26 21:20:28,879 INFO ]: Finished removeUnreachable. Reduced from 7 states to 7 states and 311 transitions. [2018-06-26 21:20:28,880 INFO ]: Start accepts. Automaton has 7 states and 311 transitions. Word has length 5 [2018-06-26 21:20:28,881 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:28,881 INFO ]: Abstraction has 7 states and 311 transitions. [2018-06-26 21:20:28,881 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:20:28,881 INFO ]: Start isEmpty. Operand 7 states and 311 transitions. [2018-06-26 21:20:28,881 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 21:20:28,881 INFO ]: Found error trace [2018-06-26 21:20:28,882 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 21:20:28,882 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:28,882 INFO ]: Analyzing trace with hash 1269405364, now seen corresponding path program 1 times [2018-06-26 21:20:28,882 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:28,882 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:28,883 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:28,883 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:28,883 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:28,890 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:28,910 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:20:28,910 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:20:28,910 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:20:28,912 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:20:28,912 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:20:28,912 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:20:28,912 INFO ]: Start difference. First operand 7 states and 311 transitions. Second operand 3 states. [2018-06-26 21:20:29,453 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:29,453 INFO ]: Finished difference Result 9 states and 456 transitions. [2018-06-26 21:20:29,454 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:20:29,454 INFO ]: Start accepts. Automaton has 3 states. Word has length 6 [2018-06-26 21:20:29,454 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:29,455 INFO ]: With dead ends: 9 [2018-06-26 21:20:29,455 INFO ]: Without dead ends: 9 [2018-06-26 21:20:29,456 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:20:29,456 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-26 21:20:29,471 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-26 21:20:29,471 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-26 21:20:29,472 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 456 transitions. [2018-06-26 21:20:29,472 INFO ]: Start accepts. Automaton has 9 states and 456 transitions. Word has length 6 [2018-06-26 21:20:29,472 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:29,472 INFO ]: Abstraction has 9 states and 456 transitions. [2018-06-26 21:20:29,472 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:20:29,472 INFO ]: Start isEmpty. Operand 9 states and 456 transitions. [2018-06-26 21:20:29,477 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 21:20:29,477 INFO ]: Found error trace [2018-06-26 21:20:29,477 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 21:20:29,477 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:29,478 INFO ]: Analyzing trace with hash 1269584110, now seen corresponding path program 1 times [2018-06-26 21:20:29,478 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:29,478 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:29,478 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:29,478 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:29,478 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:29,488 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:29,503 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:20:29,504 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:20:29,504 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:20:29,504 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:20:29,504 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:20:29,504 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:20:29,504 INFO ]: Start difference. First operand 9 states and 456 transitions. Second operand 3 states. [2018-06-26 21:20:29,975 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:29,975 INFO ]: Finished difference Result 13 states and 658 transitions. [2018-06-26 21:20:29,975 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:20:29,976 INFO ]: Start accepts. Automaton has 3 states. Word has length 6 [2018-06-26 21:20:29,976 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:29,977 INFO ]: With dead ends: 13 [2018-06-26 21:20:29,977 INFO ]: Without dead ends: 13 [2018-06-26 21:20:29,977 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:20:29,977 INFO ]: Start minimizeSevpa. Operand 13 states. [2018-06-26 21:20:29,982 INFO ]: Finished minimizeSevpa. Reduced states from 13 to 13. [2018-06-26 21:20:29,983 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-26 21:20:29,984 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 658 transitions. [2018-06-26 21:20:29,984 INFO ]: Start accepts. Automaton has 13 states and 658 transitions. Word has length 6 [2018-06-26 21:20:29,984 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:29,984 INFO ]: Abstraction has 13 states and 658 transitions. [2018-06-26 21:20:29,984 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:20:29,984 INFO ]: Start isEmpty. Operand 13 states and 658 transitions. [2018-06-26 21:20:29,985 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-26 21:20:29,985 INFO ]: Found error trace [2018-06-26 21:20:29,985 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-26 21:20:29,985 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:29,985 INFO ]: Analyzing trace with hash 1274767744, now seen corresponding path program 1 times [2018-06-26 21:20:29,985 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:29,985 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:29,986 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:29,986 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:29,986 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:29,992 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:30,023 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 21:20:30,023 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:20:30,023 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:20:30,023 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:20:30,023 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:20:30,023 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:20:30,024 INFO ]: Start difference. First operand 13 states and 658 transitions. Second operand 3 states. [2018-06-26 21:20:30,517 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:30,517 INFO ]: Finished difference Result 21 states and 999 transitions. [2018-06-26 21:20:30,519 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:20:30,519 INFO ]: Start accepts. Automaton has 3 states. Word has length 6 [2018-06-26 21:20:30,519 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:30,521 INFO ]: With dead ends: 21 [2018-06-26 21:20:30,521 INFO ]: Without dead ends: 21 [2018-06-26 21:20:30,521 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:20:30,521 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-26 21:20:30,526 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 19. [2018-06-26 21:20:30,526 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-26 21:20:30,528 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 945 transitions. [2018-06-26 21:20:30,528 INFO ]: Start accepts. Automaton has 19 states and 945 transitions. Word has length 6 [2018-06-26 21:20:30,528 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:30,528 INFO ]: Abstraction has 19 states and 945 transitions. [2018-06-26 21:20:30,528 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:20:30,528 INFO ]: Start isEmpty. Operand 19 states and 945 transitions. [2018-06-26 21:20:30,529 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-26 21:20:30,529 INFO ]: Found error trace [2018-06-26 21:20:30,529 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:20:30,529 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:30,529 INFO ]: Analyzing trace with hash 1901903800, now seen corresponding path program 1 times [2018-06-26 21:20:30,529 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:30,529 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:30,530 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:30,530 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:30,530 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:30,546 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:30,617 INFO ]: Checked inductivity of 6 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 21:20:30,617 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:20:30,617 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:20:30,617 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:20:30,618 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:20:30,618 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:20:30,618 INFO ]: Start difference. First operand 19 states and 945 transitions. Second operand 3 states. [2018-06-26 21:20:31,344 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:31,344 INFO ]: Finished difference Result 34 states and 1867 transitions. [2018-06-26 21:20:31,344 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:20:31,344 INFO ]: Start accepts. Automaton has 3 states. Word has length 8 [2018-06-26 21:20:31,345 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:31,350 INFO ]: With dead ends: 34 [2018-06-26 21:20:31,350 INFO ]: Without dead ends: 34 [2018-06-26 21:20:31,351 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 1 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:20:31,351 INFO ]: Start minimizeSevpa. Operand 34 states. [2018-06-26 21:20:31,359 INFO ]: Finished minimizeSevpa. Reduced states from 34 to 31. [2018-06-26 21:20:31,359 INFO ]: Start removeUnreachable. Operand 31 states. [2018-06-26 21:20:31,361 INFO ]: Finished removeUnreachable. Reduced from 31 states to 31 states and 1812 transitions. [2018-06-26 21:20:31,361 INFO ]: Start accepts. Automaton has 31 states and 1812 transitions. Word has length 8 [2018-06-26 21:20:31,361 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:31,361 INFO ]: Abstraction has 31 states and 1812 transitions. [2018-06-26 21:20:31,361 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:20:31,361 INFO ]: Start isEmpty. Operand 31 states and 1812 transitions. [2018-06-26 21:20:31,363 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-26 21:20:31,363 INFO ]: Found error trace [2018-06-26 21:20:31,363 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:20:31,363 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:31,363 INFO ]: Analyzing trace with hash -713956004, now seen corresponding path program 1 times [2018-06-26 21:20:31,363 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:31,363 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:31,364 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:31,364 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:31,364 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:31,372 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:31,420 INFO ]: Checked inductivity of 15 backedges. 9 proven. 0 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2018-06-26 21:20:31,420 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:20:31,420 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:20:31,420 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:20:31,420 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:20:31,420 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:20:31,420 INFO ]: Start difference. First operand 31 states and 1812 transitions. Second operand 3 states. [2018-06-26 21:20:32,728 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:32,728 INFO ]: Finished difference Result 29 states and 1025 transitions. [2018-06-26 21:20:32,729 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:20:32,729 INFO ]: Start accepts. Automaton has 3 states. Word has length 10 [2018-06-26 21:20:32,729 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:32,730 INFO ]: With dead ends: 29 [2018-06-26 21:20:32,730 INFO ]: Without dead ends: 26 [2018-06-26 21:20:32,731 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:20:32,731 INFO ]: Start minimizeSevpa. Operand 26 states. [2018-06-26 21:20:32,733 INFO ]: Finished minimizeSevpa. Reduced states from 26 to 26. [2018-06-26 21:20:32,733 INFO ]: Start removeUnreachable. Operand 26 states. [2018-06-26 21:20:32,733 INFO ]: Finished removeUnreachable. Reduced from 26 states to 26 states and 330 transitions. [2018-06-26 21:20:32,733 INFO ]: Start accepts. Automaton has 26 states and 330 transitions. Word has length 10 [2018-06-26 21:20:32,733 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:32,733 INFO ]: Abstraction has 26 states and 330 transitions. [2018-06-26 21:20:32,733 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:20:32,733 INFO ]: Start isEmpty. Operand 26 states and 330 transitions. [2018-06-26 21:20:32,736 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-26 21:20:32,736 INFO ]: Found error trace [2018-06-26 21:20:32,736 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:20:32,736 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:32,736 INFO ]: Analyzing trace with hash 1610719246, now seen corresponding path program 1 times [2018-06-26 21:20:32,736 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:32,736 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:32,737 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:32,737 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:32,737 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:32,756 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:32,793 INFO ]: Checked inductivity of 36 backedges. 15 proven. 0 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-26 21:20:32,793 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:20:32,793 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:20:32,793 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:20:32,793 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:20:32,793 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:20:32,793 INFO ]: Start difference. First operand 26 states and 330 transitions. Second operand 3 states. [2018-06-26 21:20:32,944 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:32,944 INFO ]: Finished difference Result 48 states and 603 transitions. [2018-06-26 21:20:32,947 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:20:32,947 INFO ]: Start accepts. Automaton has 3 states. Word has length 13 [2018-06-26 21:20:32,947 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:32,949 INFO ]: With dead ends: 48 [2018-06-26 21:20:32,949 INFO ]: Without dead ends: 48 [2018-06-26 21:20:32,949 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:20:32,950 INFO ]: Start minimizeSevpa. Operand 48 states. [2018-06-26 21:20:32,957 INFO ]: Finished minimizeSevpa. Reduced states from 48 to 45. [2018-06-26 21:20:32,957 INFO ]: Start removeUnreachable. Operand 45 states. [2018-06-26 21:20:32,959 INFO ]: Finished removeUnreachable. Reduced from 45 states to 45 states and 572 transitions. [2018-06-26 21:20:32,959 INFO ]: Start accepts. Automaton has 45 states and 572 transitions. Word has length 13 [2018-06-26 21:20:32,959 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:32,959 INFO ]: Abstraction has 45 states and 572 transitions. [2018-06-26 21:20:32,959 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:20:32,959 INFO ]: Start isEmpty. Operand 45 states and 572 transitions. [2018-06-26 21:20:32,960 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-26 21:20:32,960 INFO ]: Found error trace [2018-06-26 21:20:32,960 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:20:32,960 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:32,960 INFO ]: Analyzing trace with hash 1611374648, now seen corresponding path program 1 times [2018-06-26 21:20:32,960 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:32,960 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:32,961 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:32,961 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:32,961 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:32,975 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:33,056 INFO ]: Checked inductivity of 36 backedges. 15 proven. 12 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-06-26 21:20:33,056 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:20:33,056 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:20:33,067 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:33,120 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:33,131 INFO ]: Computing forward predicates... [2018-06-26 21:20:33,260 INFO ]: Checked inductivity of 36 backedges. 15 proven. 12 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-06-26 21:20:33,287 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:20:33,287 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-26 21:20:33,288 INFO ]: Interpolant automaton has 5 states [2018-06-26 21:20:33,288 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 21:20:33,288 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-26 21:20:33,288 INFO ]: Start difference. First operand 45 states and 572 transitions. Second operand 5 states. [2018-06-26 21:20:35,233 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:35,233 INFO ]: Finished difference Result 103 states and 1237 transitions. [2018-06-26 21:20:35,235 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-26 21:20:35,235 INFO ]: Start accepts. Automaton has 5 states. Word has length 13 [2018-06-26 21:20:35,235 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:35,237 INFO ]: With dead ends: 103 [2018-06-26 21:20:35,238 INFO ]: Without dead ends: 99 [2018-06-26 21:20:35,239 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-26 21:20:35,239 INFO ]: Start minimizeSevpa. Operand 99 states. [2018-06-26 21:20:35,254 INFO ]: Finished minimizeSevpa. Reduced states from 99 to 73. [2018-06-26 21:20:35,254 INFO ]: Start removeUnreachable. Operand 73 states. [2018-06-26 21:20:35,256 INFO ]: Finished removeUnreachable. Reduced from 73 states to 73 states and 869 transitions. [2018-06-26 21:20:35,256 INFO ]: Start accepts. Automaton has 73 states and 869 transitions. Word has length 13 [2018-06-26 21:20:35,256 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:35,256 INFO ]: Abstraction has 73 states and 869 transitions. [2018-06-26 21:20:35,256 INFO ]: Interpolant automaton has 5 states. [2018-06-26 21:20:35,256 INFO ]: Start isEmpty. Operand 73 states and 869 transitions. [2018-06-26 21:20:35,259 INFO ]: Finished isEmpty. Found accepting run of length 21 [2018-06-26 21:20:35,259 INFO ]: Found error trace [2018-06-26 21:20:35,260 INFO ]: trace histogram [3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:20:35,260 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:35,260 INFO ]: Analyzing trace with hash -564616396, now seen corresponding path program 1 times [2018-06-26 21:20:35,260 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:35,260 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:35,261 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:35,261 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:35,261 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:35,297 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:35,347 INFO ]: Checked inductivity of 120 backedges. 65 proven. 0 refuted. 0 times theorem prover too weak. 55 trivial. 0 not checked. [2018-06-26 21:20:35,347 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 21:20:35,347 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 21:20:35,348 INFO ]: Interpolant automaton has 3 states [2018-06-26 21:20:35,348 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 21:20:35,348 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 21:20:35,348 INFO ]: Start difference. First operand 73 states and 869 transitions. Second operand 3 states. [2018-06-26 21:20:35,514 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:35,514 INFO ]: Finished difference Result 76 states and 698 transitions. [2018-06-26 21:20:35,514 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 21:20:35,515 INFO ]: Start accepts. Automaton has 3 states. Word has length 20 [2018-06-26 21:20:35,515 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:35,516 INFO ]: With dead ends: 76 [2018-06-26 21:20:35,516 INFO ]: Without dead ends: 70 [2018-06-26 21:20:35,516 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:20:35,517 INFO ]: Start minimizeSevpa. Operand 70 states. [2018-06-26 21:20:35,525 INFO ]: Finished minimizeSevpa. Reduced states from 70 to 68. [2018-06-26 21:20:35,525 INFO ]: Start removeUnreachable. Operand 68 states. [2018-06-26 21:20:35,529 INFO ]: Finished removeUnreachable. Reduced from 68 states to 68 states and 511 transitions. [2018-06-26 21:20:35,529 INFO ]: Start accepts. Automaton has 68 states and 511 transitions. Word has length 20 [2018-06-26 21:20:35,530 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:35,530 INFO ]: Abstraction has 68 states and 511 transitions. [2018-06-26 21:20:35,530 INFO ]: Interpolant automaton has 3 states. [2018-06-26 21:20:35,530 INFO ]: Start isEmpty. Operand 68 states and 511 transitions. [2018-06-26 21:20:35,531 INFO ]: Finished isEmpty. Found accepting run of length 21 [2018-06-26 21:20:35,531 INFO ]: Found error trace [2018-06-26 21:20:35,531 INFO ]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:20:35,531 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:35,531 INFO ]: Analyzing trace with hash -308662446, now seen corresponding path program 1 times [2018-06-26 21:20:35,531 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:35,531 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:35,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:35,532 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:35,532 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:35,553 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:35,961 INFO ]: Checked inductivity of 120 backedges. 29 proven. 71 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2018-06-26 21:20:35,962 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:20:35,962 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:20:35,970 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:36,025 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:36,029 INFO ]: Computing forward predicates... [2018-06-26 21:20:36,135 INFO ]: Checked inductivity of 120 backedges. 37 proven. 63 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2018-06-26 21:20:36,166 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:20:36,166 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 8 [2018-06-26 21:20:36,166 INFO ]: Interpolant automaton has 8 states [2018-06-26 21:20:36,166 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-26 21:20:36,166 INFO ]: CoverageRelationStatistics Valid=23, Invalid=33, Unknown=0, NotChecked=0, Total=56 [2018-06-26 21:20:36,166 INFO ]: Start difference. First operand 68 states and 511 transitions. Second operand 8 states. [2018-06-26 21:20:38,569 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:38,569 INFO ]: Finished difference Result 188 states and 1562 transitions. [2018-06-26 21:20:38,570 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-26 21:20:38,570 INFO ]: Start accepts. Automaton has 8 states. Word has length 20 [2018-06-26 21:20:38,570 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:38,576 INFO ]: With dead ends: 188 [2018-06-26 21:20:38,576 INFO ]: Without dead ends: 188 [2018-06-26 21:20:38,576 INFO ]: 0 DeclaredPredicates, 40 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=64, Invalid=92, Unknown=0, NotChecked=0, Total=156 [2018-06-26 21:20:38,578 INFO ]: Start minimizeSevpa. Operand 188 states. [2018-06-26 21:20:38,590 INFO ]: Finished minimizeSevpa. Reduced states from 188 to 87. [2018-06-26 21:20:38,590 INFO ]: Start removeUnreachable. Operand 87 states. [2018-06-26 21:20:38,597 INFO ]: Finished removeUnreachable. Reduced from 87 states to 87 states and 669 transitions. [2018-06-26 21:20:38,598 INFO ]: Start accepts. Automaton has 87 states and 669 transitions. Word has length 20 [2018-06-26 21:20:38,598 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:38,598 INFO ]: Abstraction has 87 states and 669 transitions. [2018-06-26 21:20:38,598 INFO ]: Interpolant automaton has 8 states. [2018-06-26 21:20:38,598 INFO ]: Start isEmpty. Operand 87 states and 669 transitions. [2018-06-26 21:20:38,599 INFO ]: Finished isEmpty. Found accepting run of length 29 [2018-06-26 21:20:38,599 INFO ]: Found error trace [2018-06-26 21:20:38,599 INFO ]: trace histogram [4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:20:38,599 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:38,599 INFO ]: Analyzing trace with hash 2100190561, now seen corresponding path program 2 times [2018-06-26 21:20:38,599 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:38,599 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:38,600 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:38,600 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 21:20:38,600 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:38,633 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:38,906 INFO ]: Checked inductivity of 276 backedges. 45 proven. 192 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2018-06-26 21:20:38,906 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:20:38,906 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:20:39,019 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 21:20:39,109 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 21:20:39,109 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:39,124 INFO ]: Computing forward predicates... [2018-06-26 21:20:39,742 INFO ]: Checked inductivity of 276 backedges. 45 proven. 192 refuted. 0 times theorem prover too weak. 39 trivial. 0 not checked. [2018-06-26 21:20:39,761 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:20:39,761 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 8 [2018-06-26 21:20:39,761 INFO ]: Interpolant automaton has 8 states [2018-06-26 21:20:39,761 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-26 21:20:39,761 INFO ]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-06-26 21:20:39,762 INFO ]: Start difference. First operand 87 states and 669 transitions. Second operand 8 states. [2018-06-26 21:20:41,447 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:41,447 INFO ]: Finished difference Result 292 states and 2502 transitions. [2018-06-26 21:20:41,447 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 18 states. [2018-06-26 21:20:41,448 INFO ]: Start accepts. Automaton has 8 states. Word has length 28 [2018-06-26 21:20:41,448 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:41,450 INFO ]: With dead ends: 292 [2018-06-26 21:20:41,450 INFO ]: Without dead ends: 292 [2018-06-26 21:20:41,451 INFO ]: 0 DeclaredPredicates, 61 GetRequests, 36 SyntacticMatches, 9 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 59 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=103, Invalid=203, Unknown=0, NotChecked=0, Total=306 [2018-06-26 21:20:41,451 INFO ]: Start minimizeSevpa. Operand 292 states. [2018-06-26 21:20:41,463 INFO ]: Finished minimizeSevpa. Reduced states from 292 to 116. [2018-06-26 21:20:41,463 INFO ]: Start removeUnreachable. Operand 116 states. [2018-06-26 21:20:41,465 INFO ]: Finished removeUnreachable. Reduced from 116 states to 116 states and 904 transitions. [2018-06-26 21:20:41,465 INFO ]: Start accepts. Automaton has 116 states and 904 transitions. Word has length 28 [2018-06-26 21:20:41,465 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:41,465 INFO ]: Abstraction has 116 states and 904 transitions. [2018-06-26 21:20:41,465 INFO ]: Interpolant automaton has 8 states. [2018-06-26 21:20:41,465 INFO ]: Start isEmpty. Operand 116 states and 904 transitions. [2018-06-26 21:20:41,467 INFO ]: Finished isEmpty. Found accepting run of length 36 [2018-06-26 21:20:41,467 INFO ]: Found error trace [2018-06-26 21:20:41,467 INFO ]: trace histogram [5, 5, 5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:20:41,467 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:41,467 INFO ]: Analyzing trace with hash 124322313, now seen corresponding path program 2 times [2018-06-26 21:20:41,467 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:41,467 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:41,468 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:41,468 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:20:41,468 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:41,502 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:41,755 INFO ]: Checked inductivity of 465 backedges. 59 proven. 356 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2018-06-26 21:20:41,755 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:20:41,755 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:20:41,761 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-26 21:20:41,848 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-26 21:20:41,848 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:41,855 INFO ]: Computing forward predicates... [2018-06-26 21:20:42,530 INFO ]: Checked inductivity of 465 backedges. 67 proven. 348 refuted. 0 times theorem prover too weak. 50 trivial. 0 not checked. [2018-06-26 21:20:42,556 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:20:42,556 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 11 [2018-06-26 21:20:42,556 INFO ]: Interpolant automaton has 11 states [2018-06-26 21:20:42,556 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-26 21:20:42,556 INFO ]: CoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2018-06-26 21:20:42,556 INFO ]: Start difference. First operand 116 states and 904 transitions. Second operand 11 states. [2018-06-26 21:20:44,236 WARN ]: Spent 164.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 9 [2018-06-26 21:20:45,904 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:45,905 INFO ]: Finished difference Result 476 states and 4094 transitions. [2018-06-26 21:20:45,905 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-06-26 21:20:45,905 INFO ]: Start accepts. Automaton has 11 states. Word has length 35 [2018-06-26 21:20:45,905 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:45,911 INFO ]: With dead ends: 476 [2018-06-26 21:20:45,911 INFO ]: Without dead ends: 476 [2018-06-26 21:20:45,911 INFO ]: 0 DeclaredPredicates, 85 GetRequests, 42 SyntacticMatches, 14 SemanticMatches, 29 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 271 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=290, Invalid=640, Unknown=0, NotChecked=0, Total=930 [2018-06-26 21:20:45,911 INFO ]: Start minimizeSevpa. Operand 476 states. [2018-06-26 21:20:45,938 INFO ]: Finished minimizeSevpa. Reduced states from 476 to 135. [2018-06-26 21:20:45,938 INFO ]: Start removeUnreachable. Operand 135 states. [2018-06-26 21:20:45,940 INFO ]: Finished removeUnreachable. Reduced from 135 states to 135 states and 1062 transitions. [2018-06-26 21:20:45,940 INFO ]: Start accepts. Automaton has 135 states and 1062 transitions. Word has length 35 [2018-06-26 21:20:45,940 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:45,940 INFO ]: Abstraction has 135 states and 1062 transitions. [2018-06-26 21:20:45,940 INFO ]: Interpolant automaton has 11 states. [2018-06-26 21:20:45,940 INFO ]: Start isEmpty. Operand 135 states and 1062 transitions. [2018-06-26 21:20:45,942 INFO ]: Finished isEmpty. Found accepting run of length 44 [2018-06-26 21:20:45,942 INFO ]: Found error trace [2018-06-26 21:20:45,943 INFO ]: trace histogram [7, 7, 7, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:20:45,943 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:45,943 INFO ]: Analyzing trace with hash 150374680, now seen corresponding path program 3 times [2018-06-26 21:20:45,943 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:45,943 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:45,943 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:45,944 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:20:45,944 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:45,979 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:46,681 INFO ]: Checked inductivity of 741 backedges. 75 proven. 597 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2018-06-26 21:20:46,681 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:20:46,681 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-26 21:20:46,699 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 21:20:46,880 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 20 check-sat command(s) [2018-06-26 21:20:46,880 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:46,886 INFO ]: Computing forward predicates... [2018-06-26 21:20:47,275 INFO ]: Checked inductivity of 741 backedges. 75 proven. 597 refuted. 0 times theorem prover too weak. 69 trivial. 0 not checked. [2018-06-26 21:20:47,296 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:20:47,296 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 11 [2018-06-26 21:20:47,297 INFO ]: Interpolant automaton has 11 states [2018-06-26 21:20:47,297 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-26 21:20:47,297 INFO ]: CoverageRelationStatistics Valid=27, Invalid=83, Unknown=0, NotChecked=0, Total=110 [2018-06-26 21:20:47,297 INFO ]: Start difference. First operand 135 states and 1062 transitions. Second operand 11 states. [2018-06-26 21:20:51,007 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:51,007 INFO ]: Finished difference Result 634 states and 5559 transitions. [2018-06-26 21:20:51,008 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-06-26 21:20:51,008 INFO ]: Start accepts. Automaton has 11 states. Word has length 43 [2018-06-26 21:20:51,008 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:51,015 INFO ]: With dead ends: 634 [2018-06-26 21:20:51,015 INFO ]: Without dead ends: 634 [2018-06-26 21:20:51,016 INFO ]: 0 DeclaredPredicates, 109 GetRequests, 48 SyntacticMatches, 24 SemanticMatches, 37 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 403 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=405, Invalid=1077, Unknown=0, NotChecked=0, Total=1482 [2018-06-26 21:20:51,016 INFO ]: Start minimizeSevpa. Operand 634 states. [2018-06-26 21:20:51,042 INFO ]: Finished minimizeSevpa. Reduced states from 634 to 164. [2018-06-26 21:20:51,042 INFO ]: Start removeUnreachable. Operand 164 states. [2018-06-26 21:20:51,044 INFO ]: Finished removeUnreachable. Reduced from 164 states to 164 states and 1297 transitions. [2018-06-26 21:20:51,044 INFO ]: Start accepts. Automaton has 164 states and 1297 transitions. Word has length 43 [2018-06-26 21:20:51,045 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:51,045 INFO ]: Abstraction has 164 states and 1297 transitions. [2018-06-26 21:20:51,045 INFO ]: Interpolant automaton has 11 states. [2018-06-26 21:20:51,045 INFO ]: Start isEmpty. Operand 164 states and 1297 transitions. [2018-06-26 21:20:51,048 INFO ]: Finished isEmpty. Found accepting run of length 51 [2018-06-26 21:20:51,048 INFO ]: Found error trace [2018-06-26 21:20:51,048 INFO ]: trace histogram [8, 8, 8, 7, 7, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:20:51,048 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:51,048 INFO ]: Analyzing trace with hash 1059162738, now seen corresponding path program 3 times [2018-06-26 21:20:51,048 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:51,048 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:51,049 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:51,049 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:20:51,049 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:51,090 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:51,297 INFO ]: Checked inductivity of 1035 backedges. 89 proven. 866 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2018-06-26 21:20:51,297 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:20:51,297 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:20:51,304 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-26 21:20:51,677 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 24 check-sat command(s) [2018-06-26 21:20:51,677 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:51,687 INFO ]: Computing forward predicates... [2018-06-26 21:20:52,315 INFO ]: Checked inductivity of 1035 backedges. 97 proven. 858 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2018-06-26 21:20:52,346 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:20:52,346 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 14 [2018-06-26 21:20:52,347 INFO ]: Interpolant automaton has 14 states [2018-06-26 21:20:52,347 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-26 21:20:52,347 INFO ]: CoverageRelationStatistics Valid=47, Invalid=135, Unknown=0, NotChecked=0, Total=182 [2018-06-26 21:20:52,347 INFO ]: Start difference. First operand 164 states and 1297 transitions. Second operand 14 states. [2018-06-26 21:20:57,668 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:20:57,668 INFO ]: Finished difference Result 908 states and 7931 transitions. [2018-06-26 21:20:57,668 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 57 states. [2018-06-26 21:20:57,668 INFO ]: Start accepts. Automaton has 14 states. Word has length 50 [2018-06-26 21:20:57,668 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:20:57,677 INFO ]: With dead ends: 908 [2018-06-26 21:20:57,677 INFO ]: Without dead ends: 908 [2018-06-26 21:20:57,678 INFO ]: 0 DeclaredPredicates, 139 GetRequests, 54 SyntacticMatches, 29 SemanticMatches, 56 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1153 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=873, Invalid=2433, Unknown=0, NotChecked=0, Total=3306 [2018-06-26 21:20:57,679 INFO ]: Start minimizeSevpa. Operand 908 states. [2018-06-26 21:20:57,696 INFO ]: Finished minimizeSevpa. Reduced states from 908 to 183. [2018-06-26 21:20:57,696 INFO ]: Start removeUnreachable. Operand 183 states. [2018-06-26 21:20:57,698 INFO ]: Finished removeUnreachable. Reduced from 183 states to 183 states and 1455 transitions. [2018-06-26 21:20:57,699 INFO ]: Start accepts. Automaton has 183 states and 1455 transitions. Word has length 50 [2018-06-26 21:20:57,699 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:20:57,699 INFO ]: Abstraction has 183 states and 1455 transitions. [2018-06-26 21:20:57,699 INFO ]: Interpolant automaton has 14 states. [2018-06-26 21:20:57,699 INFO ]: Start isEmpty. Operand 183 states and 1455 transitions. [2018-06-26 21:20:57,700 INFO ]: Finished isEmpty. Found accepting run of length 59 [2018-06-26 21:20:57,700 INFO ]: Found error trace [2018-06-26 21:20:57,700 INFO ]: trace histogram [10, 10, 10, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:20:57,700 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:20:57,701 INFO ]: Analyzing trace with hash 867735681, now seen corresponding path program 4 times [2018-06-26 21:20:57,701 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:20:57,701 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:20:57,701 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:57,701 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:20:57,701 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:20:57,733 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:58,234 INFO ]: Checked inductivity of 1431 backedges. 105 proven. 1227 refuted. 0 times theorem prover too weak. 99 trivial. 0 not checked. [2018-06-26 21:20:58,234 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:20:58,234 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:20:58,241 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 21:20:58,384 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 21:20:58,384 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:20:58,399 INFO ]: Computing forward predicates... [2018-06-26 21:20:59,407 INFO ]: Checked inductivity of 1431 backedges. 105 proven. 1227 refuted. 0 times theorem prover too weak. 99 trivial. 0 not checked. [2018-06-26 21:20:59,426 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:20:59,426 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 14 [2018-06-26 21:20:59,427 INFO ]: Interpolant automaton has 14 states [2018-06-26 21:20:59,427 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-26 21:20:59,427 INFO ]: CoverageRelationStatistics Valid=36, Invalid=146, Unknown=0, NotChecked=0, Total=182 [2018-06-26 21:20:59,427 INFO ]: Start difference. First operand 183 states and 1455 transitions. Second operand 14 states. [2018-06-26 21:21:06,043 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:21:06,043 INFO ]: Finished difference Result 1120 states and 9921 transitions. [2018-06-26 21:21:06,044 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 69 states. [2018-06-26 21:21:06,044 INFO ]: Start accepts. Automaton has 14 states. Word has length 58 [2018-06-26 21:21:06,044 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:21:06,057 INFO ]: With dead ends: 1120 [2018-06-26 21:21:06,057 INFO ]: Without dead ends: 1120 [2018-06-26 21:21:06,061 INFO ]: 0 DeclaredPredicates, 166 GetRequests, 60 SyntacticMatches, 39 SemanticMatches, 67 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1476 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=1136, Invalid=3556, Unknown=0, NotChecked=0, Total=4692 [2018-06-26 21:21:06,062 INFO ]: Start minimizeSevpa. Operand 1120 states. [2018-06-26 21:21:06,081 INFO ]: Finished minimizeSevpa. Reduced states from 1120 to 212. [2018-06-26 21:21:06,081 INFO ]: Start removeUnreachable. Operand 212 states. [2018-06-26 21:21:06,083 INFO ]: Finished removeUnreachable. Reduced from 212 states to 212 states and 1690 transitions. [2018-06-26 21:21:06,083 INFO ]: Start accepts. Automaton has 212 states and 1690 transitions. Word has length 58 [2018-06-26 21:21:06,083 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:21:06,083 INFO ]: Abstraction has 212 states and 1690 transitions. [2018-06-26 21:21:06,083 INFO ]: Interpolant automaton has 14 states. [2018-06-26 21:21:06,083 INFO ]: Start isEmpty. Operand 212 states and 1690 transitions. [2018-06-26 21:21:06,085 INFO ]: Finished isEmpty. Found accepting run of length 66 [2018-06-26 21:21:06,085 INFO ]: Found error trace [2018-06-26 21:21:06,085 INFO ]: trace histogram [11, 11, 11, 10, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:21:06,085 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:21:06,085 INFO ]: Analyzing trace with hash -1558445335, now seen corresponding path program 4 times [2018-06-26 21:21:06,085 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:21:06,085 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:21:06,086 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:21:06,086 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:21:06,086 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:21:06,121 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:21:06,860 INFO ]: Checked inductivity of 1830 backedges. 119 proven. 1601 refuted. 0 times theorem prover too weak. 110 trivial. 0 not checked. [2018-06-26 21:21:06,860 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:21:06,860 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:21:06,866 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-26 21:21:07,008 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-26 21:21:07,008 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:21:07,024 INFO ]: Computing forward predicates... [2018-06-26 21:21:07,820 INFO ]: Checked inductivity of 1830 backedges. 127 proven. 1593 refuted. 0 times theorem prover too weak. 110 trivial. 0 not checked. [2018-06-26 21:21:07,840 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:21:07,856 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 15] total 17 [2018-06-26 21:21:07,856 INFO ]: Interpolant automaton has 17 states [2018-06-26 21:21:07,856 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-26 21:21:07,856 INFO ]: CoverageRelationStatistics Valid=59, Invalid=213, Unknown=0, NotChecked=0, Total=272 [2018-06-26 21:21:07,856 INFO ]: Start difference. First operand 212 states and 1690 transitions. Second operand 17 states. [2018-06-26 21:21:15,428 WARN ]: Spent 170.00 ms on a formula simplification. DAG size of input: 23 DAG size of output: 16 [2018-06-26 21:21:17,058 WARN ]: Spent 186.00 ms on a formula simplification. DAG size of input: 24 DAG size of output: 12 [2018-06-26 21:21:18,721 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 21:21:18,721 INFO ]: Finished difference Result 1484 states and 13073 transitions. [2018-06-26 21:21:18,722 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 93 states. [2018-06-26 21:21:18,722 INFO ]: Start accepts. Automaton has 17 states. Word has length 65 [2018-06-26 21:21:18,722 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 21:21:18,736 INFO ]: With dead ends: 1484 [2018-06-26 21:21:18,737 INFO ]: Without dead ends: 1484 [2018-06-26 21:21:18,739 INFO ]: 0 DeclaredPredicates, 202 GetRequests, 66 SyntacticMatches, 44 SemanticMatches, 92 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3295 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=2083, Invalid=6659, Unknown=0, NotChecked=0, Total=8742 [2018-06-26 21:21:18,740 INFO ]: Start minimizeSevpa. Operand 1484 states. [2018-06-26 21:21:18,761 INFO ]: Finished minimizeSevpa. Reduced states from 1484 to 231. [2018-06-26 21:21:18,761 INFO ]: Start removeUnreachable. Operand 231 states. [2018-06-26 21:21:18,763 INFO ]: Finished removeUnreachable. Reduced from 231 states to 231 states and 1848 transitions. [2018-06-26 21:21:18,763 INFO ]: Start accepts. Automaton has 231 states and 1848 transitions. Word has length 65 [2018-06-26 21:21:18,764 INFO ]: Finished accepts. word is rejected. [2018-06-26 21:21:18,764 INFO ]: Abstraction has 231 states and 1848 transitions. [2018-06-26 21:21:18,764 INFO ]: Interpolant automaton has 17 states. [2018-06-26 21:21:18,764 INFO ]: Start isEmpty. Operand 231 states and 1848 transitions. [2018-06-26 21:21:18,766 INFO ]: Finished isEmpty. Found accepting run of length 74 [2018-06-26 21:21:18,766 INFO ]: Found error trace [2018-06-26 21:21:18,766 INFO ]: trace histogram [13, 13, 13, 13, 13, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 21:21:18,766 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 21:21:18,766 INFO ]: Analyzing trace with hash -41244168, now seen corresponding path program 5 times [2018-06-26 21:21:18,766 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 21:21:18,766 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 21:21:18,767 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:21:18,767 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-26 21:21:18,767 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 21:21:18,802 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:21:19,131 INFO ]: Checked inductivity of 2346 backedges. 135 proven. 2082 refuted. 0 times theorem prover too weak. 129 trivial. 0 not checked. [2018-06-26 21:21:19,131 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 21:21:19,131 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:21:19,137 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-26 21:21:19,484 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 34 check-sat command(s) [2018-06-26 21:21:19,484 INFO ]: Conjunction of SSA is unsat [2018-06-26 21:21:19,541 INFO ]: Computing forward predicates... [2018-06-26 21:21:20,361 INFO ]: Checked inductivity of 2346 backedges. 135 proven. 2082 refuted. 0 times theorem prover too weak. 129 trivial. 0 not checked. [2018-06-26 21:21:20,381 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 21:21:20,381 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 17 [2018-06-26 21:21:20,382 INFO ]: Interpolant automaton has 17 states [2018-06-26 21:21:20,382 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-26 21:21:20,382 INFO ]: CoverageRelationStatistics Valid=45, Invalid=227, Unknown=0, NotChecked=0, Total=272 [2018-06-26 21:21:20,382 INFO ]: Start difference. First operand 231 states and 1848 transitions. Second operand 17 states. Received shutdown request... [2018-06-26 21:21:22,434 WARN ]: Removed 3 from assertion stack [2018-06-26 21:21:22,434 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-26 21:21:22,434 WARN ]: Verification canceled [2018-06-26 21:21:22,436 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-26 21:21:22,438 WARN ]: Timeout [2018-06-26 21:21:22,438 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 09:21:22 BasicIcfg [2018-06-26 21:21:22,438 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-26 21:21:22,439 INFO ]: Toolchain (without parser) took 59807.29 ms. Allocated memory was 308.8 MB in the beginning and 1.6 GB in the end (delta: 1.2 GB). Free memory was 263.2 MB in the beginning and 818.6 MB in the end (delta: -555.5 MB). Peak memory consumption was 693.9 MB. Max. memory is 3.6 GB. [2018-06-26 21:21:22,440 INFO ]: SmtParser took 0.15 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-26 21:21:22,440 INFO ]: ChcToBoogie took 60.55 ms. Allocated memory is still 308.8 MB. Free memory was 263.2 MB in the beginning and 261.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:21:22,441 INFO ]: Boogie Preprocessor took 44.55 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 259.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:21:22,441 INFO ]: RCFGBuilder took 233.47 ms. Allocated memory is still 308.8 MB. Free memory was 259.2 MB in the beginning and 251.2 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. [2018-06-26 21:21:22,442 INFO ]: BlockEncodingV2 took 4169.33 ms. Allocated memory was 308.8 MB in the beginning and 1.1 GB in the end (delta: 748.7 MB). Free memory was 251.2 MB in the beginning and 826.7 MB in the end (delta: -575.5 MB). Peak memory consumption was 548.7 MB. Max. memory is 3.6 GB. [2018-06-26 21:21:22,444 INFO ]: TraceAbstraction took 55290.47 ms. Allocated memory was 1.1 GB in the beginning and 1.6 GB in the end (delta: 500.7 MB). Free memory was 826.7 MB in the beginning and 818.6 MB in the end (delta: 8.0 MB). Peak memory consumption was 508.7 MB. Max. memory is 3.6 GB. [2018-06-26 21:21:22,452 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, 191 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.15 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 60.55 ms. Allocated memory is still 308.8 MB. Free memory was 263.2 MB in the beginning and 261.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 44.55 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 259.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 233.47 ms. Allocated memory is still 308.8 MB. Free memory was 259.2 MB in the beginning and 251.2 MB in the end (delta: 8.0 MB). Peak memory consumption was 8.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 4169.33 ms. Allocated memory was 308.8 MB in the beginning and 1.1 GB in the end (delta: 748.7 MB). Free memory was 251.2 MB in the beginning and 826.7 MB in the end (delta: -575.5 MB). Peak memory consumption was 548.7 MB. Max. memory is 3.6 GB. * TraceAbstraction took 55290.47 ms. Allocated memory was 1.1 GB in the beginning and 1.6 GB in the end (delta: 500.7 MB). Free memory was 826.7 MB in the beginning and 818.6 MB in the end (delta: 8.0 MB). Peak memory consumption was 508.7 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds Cancelled while BasicCegarLoop was constructing difference of abstraction (231states) and interpolant automaton (currently 13 states, 17 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 12. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 6 locations, 1 error locations. TIMEOUT Result, 55.2s OverallTime, 17 OverallIterations, 13 TraceHistogramMax, 43.3s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 82 SDtfs, 14 SDslu, 275 SDs, 0 SdLazy, 28962 SolverSat, 27657 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 31.4s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 999 GetRequests, 440 SyntacticMatches, 215 SemanticMatches, 343 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6811 ImplicationChecksByTransitivity, 11.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=231occurred in iteration=16, 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.2s AutomataMinimizationTime, 16 MinimizatonAttempts, 4010 StatesRemovedByMinimization, 12 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.5s SatisfiabilityAnalysisTime, 9.1s InterpolantComputationTime, 844 NumberOfCodeBlocks, 839 NumberOfCodeBlocksAsserted, 103 NumberOfCheckSat, 818 ConstructedInterpolants, 38 QuantifiedInterpolants, 245375 SizeOfPredicates, 0 NumberOfNonLiveVariables, 8859 ConjunctsInSsa, 1279 ConjunctsInUnsatCore, 26 InterpolantComputations, 8 PerfectInterpolantSequences, 2764/16740 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/dillig03.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-26_21-21-22-470.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig03.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-26_21-21-22-470.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig03.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-26_21-21-22-470.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/dillig03.c.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-26_21-21-22-470.csv Completed graceful shutdown