java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC_wBE.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/hopv/lia/termination/Ackermann06.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-24 21:25:41,162 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-24 21:25:41,164 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-24 21:25:41,177 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-24 21:25:41,177 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-24 21:25:41,178 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-24 21:25:41,180 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-24 21:25:41,182 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-24 21:25:41,183 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-24 21:25:41,184 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-24 21:25:41,184 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-24 21:25:41,186 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-24 21:25:41,187 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-24 21:25:41,188 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-24 21:25:41,188 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-24 21:25:41,191 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-24 21:25:41,193 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-24 21:25:41,206 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-24 21:25:41,208 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-24 21:25:41,209 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-24 21:25:41,210 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-24 21:25:41,212 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-24 21:25:41,212 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-24 21:25:41,212 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-24 21:25:41,213 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-24 21:25:41,214 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-24 21:25:41,215 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-24 21:25:41,215 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-24 21:25:41,216 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-24 21:25:41,216 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-24 21:25:41,217 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-24 21:25:41,218 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-24 21:25:41,218 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-24 21:25:41,219 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-24 21:25:41,219 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-24 21:25:41,219 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-24 21:25:41,232 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-24 21:25:41,233 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-24 21:25:41,233 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-24 21:25:41,233 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-24 21:25:41,234 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-24 21:25:41,234 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-24 21:25:41,234 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-24 21:25:41,235 INFO L133 SettingsManager]: * Use SBE=true [2018-06-24 21:25:41,235 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-24 21:25:41,235 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-24 21:25:41,235 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-24 21:25:41,235 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-24 21:25:41,236 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-24 21:25:41,236 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-24 21:25:41,236 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-24 21:25:41,236 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-24 21:25:41,236 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-24 21:25:41,237 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-24 21:25:41,237 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-24 21:25:41,237 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-24 21:25:41,237 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-24 21:25:41,238 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-24 21:25:41,239 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-24 21:25:41,289 INFO ]: Repository-Root is: /tmp [2018-06-24 21:25:41,308 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-24 21:25:41,314 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-24 21:25:41,316 INFO ]: Initializing SmtParser... [2018-06-24 21:25:41,316 INFO ]: SmtParser initialized [2018-06-24 21:25:41,317 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/hopv/lia/termination/Ackermann06.smt2 [2018-06-24 21:25:41,318 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-24 21:25:41,404 INFO ]: Executing SMT file /storage/chc-comp/hopv/lia/termination/Ackermann06.smt2 unknown [2018-06-24 21:25:42,021 INFO ]: Succesfully executed SMT file /storage/chc-comp/hopv/lia/termination/Ackermann06.smt2 [2018-06-24 21:25:42,025 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-24 21:25:42,040 INFO ]: Walking toolchain with 5 elements. [2018-06-24 21:25:42,041 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-24 21:25:42,041 INFO ]: Initializing ChcToBoogie... [2018-06-24 21:25:42,041 INFO ]: ChcToBoogie initialized [2018-06-24 21:25:42,044 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 24.06 09:25:42" (1/1) ... [2018-06-24 21:25:42,157 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:25:42 Unit [2018-06-24 21:25:42,157 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-24 21:25:42,158 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-24 21:25:42,158 INFO ]: Initializing Boogie Preprocessor... [2018-06-24 21:25:42,158 INFO ]: Boogie Preprocessor initialized [2018-06-24 21:25:42,179 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:25:42" (1/1) ... [2018-06-24 21:25:42,179 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:25:42" (1/1) ... [2018-06-24 21:25:42,193 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:25:42" (1/1) ... [2018-06-24 21:25:42,193 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:25:42" (1/1) ... [2018-06-24 21:25:42,204 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:25:42" (1/1) ... [2018-06-24 21:25:42,207 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:25:42" (1/1) ... [2018-06-24 21:25:42,211 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:25:42" (1/1) ... [2018-06-24 21:25:42,215 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-24 21:25:42,216 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-24 21:25:42,216 INFO ]: Initializing RCFGBuilder... [2018-06-24 21:25:42,216 INFO ]: RCFGBuilder initialized [2018-06-24 21:25:42,217 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:25:42" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-24 21:25:42,240 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-24 21:25:42,240 INFO ]: Found specification of procedure gotoProc [2018-06-24 21:25:42,240 INFO ]: Found implementation of procedure gotoProc [2018-06-24 21:25:42,241 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-24 21:25:42,241 INFO ]: Found specification of procedure Ultimate.START [2018-06-24 21:25:42,241 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-24 21:25:43,180 INFO ]: Using library mode [2018-06-24 21:25:43,181 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:25:43 BoogieIcfgContainer [2018-06-24 21:25:43,181 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-24 21:25:43,181 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-24 21:25:43,181 INFO ]: Initializing BlockEncodingV2... [2018-06-24 21:25:43,182 INFO ]: BlockEncodingV2 initialized [2018-06-24 21:25:43,184 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:25:43" (1/1) ... [2018-06-24 21:25:43,212 INFO ]: Initial Icfg 48 locations, 77 edges [2018-06-24 21:25:43,213 INFO ]: Using Remove infeasible edges [2018-06-24 21:25:43,214 INFO ]: Using Maximize final states [2018-06-24 21:25:43,214 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-24 21:25:43,215 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-24 21:25:43,219 INFO ]: Using Remove sink states [2018-06-24 21:25:43,220 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-24 21:25:43,220 INFO ]: Using Use SBE [2018-06-24 21:25:43,230 WARN ]: expecting exponential blowup for input size 9 [2018-06-24 21:25:45,234 WARN ]: expecting exponential blowup for input size 9 [2018-06-24 21:25:47,033 WARN ]: expecting exponential blowup for input size 9 [2018-06-24 21:25:48,862 WARN ]: expecting exponential blowup for input size 9 [2018-06-24 21:25:50,540 WARN ]: expecting exponential blowup for input size 9 [2018-06-24 21:25:51,383 INFO ]: SBE split 5 edges [2018-06-24 21:25:51,389 INFO ]: Removed 4 edges and 2 locations because of local infeasibility [2018-06-24 21:25:51,390 INFO ]: 0 new accepting states [2018-06-24 21:25:53,803 INFO ]: Removed 201 edges and 13 locations by large block encoding [2018-06-24 21:25:53,805 INFO ]: Removed 4 edges and 3 locations by removing sink states [2018-06-24 21:25:53,808 INFO ]: Removed 54 edges and 0 locations because of local infeasibility [2018-06-24 21:25:53,808 INFO ]: 0 new accepting states [2018-06-24 21:25:53,809 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-24 21:25:53,809 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 21:25:53,809 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-24 21:25:53,809 INFO ]: 0 new accepting states [2018-06-24 21:25:53,810 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-24 21:25:53,810 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 21:25:53,810 INFO ]: Encoded RCFG 30 locations, 103 edges [2018-06-24 21:25:53,815 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 24.06 09:25:53 BasicIcfg [2018-06-24 21:25:53,815 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-24 21:25:53,816 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-24 21:25:53,816 INFO ]: Initializing TraceAbstraction... [2018-06-24 21:25:53,819 INFO ]: TraceAbstraction initialized [2018-06-24 21:25:53,820 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 24.06 09:25:42" (1/4) ... [2018-06-24 21:25:53,820 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@28ec38ee and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 24.06 09:25:53, skipping insertion in model container [2018-06-24 21:25:53,821 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:25:42" (2/4) ... [2018-06-24 21:25:53,821 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@28ec38ee and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.06 09:25:53, skipping insertion in model container [2018-06-24 21:25:53,821 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:25:43" (3/4) ... [2018-06-24 21:25:53,821 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@28ec38ee and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.06 09:25:53, skipping insertion in model container [2018-06-24 21:25:53,821 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 24.06 09:25:53" (4/4) ... [2018-06-24 21:25:53,831 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-24 21:25:53,842 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-24 21:25:53,849 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-24 21:25:53,895 INFO ]: Using default assertion order modulation [2018-06-24 21:25:53,896 INFO ]: Interprodecural is true [2018-06-24 21:25:53,896 INFO ]: Hoare is false [2018-06-24 21:25:53,896 INFO ]: Compute interpolants for FPandBP [2018-06-24 21:25:53,896 INFO ]: Backedges is TWOTRACK [2018-06-24 21:25:53,896 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-24 21:25:53,896 INFO ]: Difference is false [2018-06-24 21:25:53,896 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-24 21:25:53,896 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-24 21:25:53,909 INFO ]: Start isEmpty. Operand 30 states. [2018-06-24 21:25:53,922 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-24 21:25:53,922 INFO ]: Found error trace [2018-06-24 21:25:53,923 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-24 21:25:53,923 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:25:53,926 INFO ]: Analyzing trace with hash 50336521, now seen corresponding path program 1 times [2018-06-24 21:25:53,928 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:25:53,928 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:25:53,961 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:53,961 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:25:53,961 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:54,046 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:54,205 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:25:54,208 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:25:54,208 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:25:54,210 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:25:54,225 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:25:54,227 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:25:54,229 INFO ]: Start difference. First operand 30 states. Second operand 3 states. [2018-06-24 21:25:54,550 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:25:54,550 INFO ]: Finished difference Result 35 states and 108 transitions. [2018-06-24 21:25:54,552 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:25:54,553 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-24 21:25:54,553 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:25:54,563 INFO ]: With dead ends: 35 [2018-06-24 21:25:54,564 INFO ]: Without dead ends: 29 [2018-06-24 21:25:54,565 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:25:54,583 INFO ]: Start minimizeSevpa. Operand 29 states. [2018-06-24 21:25:54,610 INFO ]: Finished minimizeSevpa. Reduced states from 29 to 25. [2018-06-24 21:25:54,611 INFO ]: Start removeUnreachable. Operand 25 states. [2018-06-24 21:25:54,613 INFO ]: Finished removeUnreachable. Reduced from 25 states to 25 states and 52 transitions. [2018-06-24 21:25:54,614 INFO ]: Start accepts. Automaton has 25 states and 52 transitions. Word has length 5 [2018-06-24 21:25:54,615 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:25:54,615 INFO ]: Abstraction has 25 states and 52 transitions. [2018-06-24 21:25:54,615 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:25:54,615 INFO ]: Start isEmpty. Operand 25 states and 52 transitions. [2018-06-24 21:25:54,617 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-24 21:25:54,617 INFO ]: Found error trace [2018-06-24 21:25:54,617 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-24 21:25:54,617 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:25:54,617 INFO ]: Analyzing trace with hash 49949238, now seen corresponding path program 1 times [2018-06-24 21:25:54,617 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:25:54,617 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:25:54,618 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:54,618 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:25:54,618 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:54,627 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:54,691 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:25:54,691 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:25:54,691 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:25:54,692 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:25:54,692 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:25:54,692 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:25:54,693 INFO ]: Start difference. First operand 25 states and 52 transitions. Second operand 3 states. [2018-06-24 21:25:55,028 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:25:55,028 INFO ]: Finished difference Result 33 states and 70 transitions. [2018-06-24 21:25:55,029 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:25:55,029 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-24 21:25:55,029 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:25:55,031 INFO ]: With dead ends: 33 [2018-06-24 21:25:55,031 INFO ]: Without dead ends: 33 [2018-06-24 21:25:55,031 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:25:55,032 INFO ]: Start minimizeSevpa. Operand 33 states. [2018-06-24 21:25:55,037 INFO ]: Finished minimizeSevpa. Reduced states from 33 to 33. [2018-06-24 21:25:55,038 INFO ]: Start removeUnreachable. Operand 33 states. [2018-06-24 21:25:55,039 INFO ]: Finished removeUnreachable. Reduced from 33 states to 33 states and 70 transitions. [2018-06-24 21:25:55,039 INFO ]: Start accepts. Automaton has 33 states and 70 transitions. Word has length 5 [2018-06-24 21:25:55,039 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:25:55,039 INFO ]: Abstraction has 33 states and 70 transitions. [2018-06-24 21:25:55,039 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:25:55,039 INFO ]: Start isEmpty. Operand 33 states and 70 transitions. [2018-06-24 21:25:55,041 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-24 21:25:55,041 INFO ]: Found error trace [2018-06-24 21:25:55,041 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-24 21:25:55,041 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:25:55,041 INFO ]: Analyzing trace with hash 1552279577, now seen corresponding path program 1 times [2018-06-24 21:25:55,041 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:25:55,041 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:25:55,042 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:55,042 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:25:55,042 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:55,082 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:55,199 INFO ]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 21:25:55,200 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:25:55,200 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:25:55,200 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:25:55,200 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:25:55,200 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:25:55,200 INFO ]: Start difference. First operand 33 states and 70 transitions. Second operand 3 states. [2018-06-24 21:25:55,240 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:25:55,240 INFO ]: Finished difference Result 45 states and 94 transitions. [2018-06-24 21:25:55,241 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:25:55,241 INFO ]: Start accepts. Automaton has 3 states. Word has length 6 [2018-06-24 21:25:55,241 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:25:55,243 INFO ]: With dead ends: 45 [2018-06-24 21:25:55,243 INFO ]: Without dead ends: 45 [2018-06-24 21:25:55,243 INFO ]: 0 DeclaredPredicates, 4 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:25:55,243 INFO ]: Start minimizeSevpa. Operand 45 states. [2018-06-24 21:25:55,250 INFO ]: Finished minimizeSevpa. Reduced states from 45 to 35. [2018-06-24 21:25:55,250 INFO ]: Start removeUnreachable. Operand 35 states. [2018-06-24 21:25:55,251 INFO ]: Finished removeUnreachable. Reduced from 35 states to 35 states and 76 transitions. [2018-06-24 21:25:55,251 INFO ]: Start accepts. Automaton has 35 states and 76 transitions. Word has length 6 [2018-06-24 21:25:55,251 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:25:55,251 INFO ]: Abstraction has 35 states and 76 transitions. [2018-06-24 21:25:55,251 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:25:55,251 INFO ]: Start isEmpty. Operand 35 states and 76 transitions. [2018-06-24 21:25:55,253 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-24 21:25:55,253 INFO ]: Found error trace [2018-06-24 21:25:55,253 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-24 21:25:55,253 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:25:55,253 INFO ]: Analyzing trace with hash 1539350283, now seen corresponding path program 1 times [2018-06-24 21:25:55,253 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:25:55,253 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:25:55,254 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:55,254 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:25:55,254 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:55,264 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:55,300 INFO ]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 21:25:55,300 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:25:55,300 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:25:55,300 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:25:55,301 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:25:55,301 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:25:55,301 INFO ]: Start difference. First operand 35 states and 76 transitions. Second operand 3 states. [2018-06-24 21:25:55,449 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:25:55,449 INFO ]: Finished difference Result 41 states and 86 transitions. [2018-06-24 21:25:55,451 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:25:55,451 INFO ]: Start accepts. Automaton has 3 states. Word has length 6 [2018-06-24 21:25:55,451 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:25:55,452 INFO ]: With dead ends: 41 [2018-06-24 21:25:55,452 INFO ]: Without dead ends: 34 [2018-06-24 21:25:55,452 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:25:55,453 INFO ]: Start minimizeSevpa. Operand 34 states. [2018-06-24 21:25:55,457 INFO ]: Finished minimizeSevpa. Reduced states from 34 to 34. [2018-06-24 21:25:55,458 INFO ]: Start removeUnreachable. Operand 34 states. [2018-06-24 21:25:55,459 INFO ]: Finished removeUnreachable. Reduced from 34 states to 34 states and 72 transitions. [2018-06-24 21:25:55,459 INFO ]: Start accepts. Automaton has 34 states and 72 transitions. Word has length 6 [2018-06-24 21:25:55,459 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:25:55,459 INFO ]: Abstraction has 34 states and 72 transitions. [2018-06-24 21:25:55,459 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:25:55,459 INFO ]: Start isEmpty. Operand 34 states and 72 transitions. [2018-06-24 21:25:55,461 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-24 21:25:55,461 INFO ]: Found error trace [2018-06-24 21:25:55,461 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:25:55,461 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:25:55,462 INFO ]: Analyzing trace with hash 335257113, now seen corresponding path program 1 times [2018-06-24 21:25:55,462 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:25:55,462 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:25:55,462 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:55,462 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:25:55,462 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:55,497 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:55,570 INFO ]: Checked inductivity of 5 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-24 21:25:55,571 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:25:55,571 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:25:55,571 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:25:55,571 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:25:55,571 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:25:55,571 INFO ]: Start difference. First operand 34 states and 72 transitions. Second operand 3 states. [2018-06-24 21:25:55,719 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:25:55,719 INFO ]: Finished difference Result 42 states and 84 transitions. [2018-06-24 21:25:55,719 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:25:55,719 INFO ]: Start accepts. Automaton has 3 states. Word has length 11 [2018-06-24 21:25:55,720 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:25:55,721 INFO ]: With dead ends: 42 [2018-06-24 21:25:55,721 INFO ]: Without dead ends: 42 [2018-06-24 21:25:55,721 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:25:55,721 INFO ]: Start minimizeSevpa. Operand 42 states. [2018-06-24 21:25:55,727 INFO ]: Finished minimizeSevpa. Reduced states from 42 to 42. [2018-06-24 21:25:55,727 INFO ]: Start removeUnreachable. Operand 42 states. [2018-06-24 21:25:55,728 INFO ]: Finished removeUnreachable. Reduced from 42 states to 42 states and 84 transitions. [2018-06-24 21:25:55,728 INFO ]: Start accepts. Automaton has 42 states and 84 transitions. Word has length 11 [2018-06-24 21:25:55,728 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:25:55,728 INFO ]: Abstraction has 42 states and 84 transitions. [2018-06-24 21:25:55,728 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:25:55,728 INFO ]: Start isEmpty. Operand 42 states and 84 transitions. [2018-06-24 21:25:55,730 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-24 21:25:55,730 INFO ]: Found error trace [2018-06-24 21:25:55,730 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:25:55,730 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:25:55,731 INFO ]: Analyzing trace with hash 958866805, now seen corresponding path program 1 times [2018-06-24 21:25:55,731 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:25:55,731 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:25:55,731 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:55,731 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:25:55,731 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:55,759 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:55,925 INFO ]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-24 21:25:55,925 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:25:55,925 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-24 21:25:55,925 INFO ]: Interpolant automaton has 4 states [2018-06-24 21:25:55,925 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-24 21:25:55,925 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-24 21:25:55,925 INFO ]: Start difference. First operand 42 states and 84 transitions. Second operand 4 states. [2018-06-24 21:25:56,246 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:25:56,246 INFO ]: Finished difference Result 60 states and 120 transitions. [2018-06-24 21:25:56,246 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-24 21:25:56,246 INFO ]: Start accepts. Automaton has 4 states. Word has length 13 [2018-06-24 21:25:56,246 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:25:56,248 INFO ]: With dead ends: 60 [2018-06-24 21:25:56,248 INFO ]: Without dead ends: 60 [2018-06-24 21:25:56,248 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-24 21:25:56,248 INFO ]: Start minimizeSevpa. Operand 60 states. [2018-06-24 21:25:56,254 INFO ]: Finished minimizeSevpa. Reduced states from 60 to 44. [2018-06-24 21:25:56,254 INFO ]: Start removeUnreachable. Operand 44 states. [2018-06-24 21:25:56,256 INFO ]: Finished removeUnreachable. Reduced from 44 states to 44 states and 90 transitions. [2018-06-24 21:25:56,256 INFO ]: Start accepts. Automaton has 44 states and 90 transitions. Word has length 13 [2018-06-24 21:25:56,256 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:25:56,256 INFO ]: Abstraction has 44 states and 90 transitions. [2018-06-24 21:25:56,256 INFO ]: Interpolant automaton has 4 states. [2018-06-24 21:25:56,256 INFO ]: Start isEmpty. Operand 44 states and 90 transitions. [2018-06-24 21:25:56,258 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-24 21:25:56,258 INFO ]: Found error trace [2018-06-24 21:25:56,258 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:25:56,258 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:25:56,258 INFO ]: Analyzing trace with hash 593305670, now seen corresponding path program 1 times [2018-06-24 21:25:56,258 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:25:56,258 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:25:56,259 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:56,259 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:25:56,259 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:56,278 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:56,329 INFO ]: Checked inductivity of 8 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-06-24 21:25:56,329 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:25:56,329 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:25:56,330 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:25:56,330 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:25:56,330 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:25:56,330 INFO ]: Start difference. First operand 44 states and 90 transitions. Second operand 3 states. [2018-06-24 21:25:56,414 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:25:56,414 INFO ]: Finished difference Result 54 states and 109 transitions. [2018-06-24 21:25:56,422 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:25:56,422 INFO ]: Start accepts. Automaton has 3 states. Word has length 13 [2018-06-24 21:25:56,422 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:25:56,423 INFO ]: With dead ends: 54 [2018-06-24 21:25:56,423 INFO ]: Without dead ends: 54 [2018-06-24 21:25:56,424 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:25:56,424 INFO ]: Start minimizeSevpa. Operand 54 states. [2018-06-24 21:25:56,429 INFO ]: Finished minimizeSevpa. Reduced states from 54 to 54. [2018-06-24 21:25:56,429 INFO ]: Start removeUnreachable. Operand 54 states. [2018-06-24 21:25:56,430 INFO ]: Finished removeUnreachable. Reduced from 54 states to 54 states and 109 transitions. [2018-06-24 21:25:56,430 INFO ]: Start accepts. Automaton has 54 states and 109 transitions. Word has length 13 [2018-06-24 21:25:56,431 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:25:56,431 INFO ]: Abstraction has 54 states and 109 transitions. [2018-06-24 21:25:56,431 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:25:56,431 INFO ]: Start isEmpty. Operand 54 states and 109 transitions. [2018-06-24 21:25:56,432 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-24 21:25:56,432 INFO ]: Found error trace [2018-06-24 21:25:56,432 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:25:56,432 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:25:56,432 INFO ]: Analyzing trace with hash -348052691, now seen corresponding path program 2 times [2018-06-24 21:25:56,432 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:25:56,432 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:25:56,433 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:56,433 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:25:56,433 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:56,470 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:56,559 INFO ]: Checked inductivity of 12 backedges. 7 proven. 2 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-24 21:25:56,559 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:25:56,559 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:25:56,575 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:25:56,692 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:25:56,692 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:56,702 INFO ]: Computing forward predicates... [2018-06-24 21:25:56,761 INFO ]: Checked inductivity of 12 backedges. 7 proven. 2 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2018-06-24 21:25:56,797 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:25:56,797 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 5 [2018-06-24 21:25:56,797 INFO ]: Interpolant automaton has 5 states [2018-06-24 21:25:56,798 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-24 21:25:56,798 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-24 21:25:56,798 INFO ]: Start difference. First operand 54 states and 109 transitions. Second operand 5 states. [2018-06-24 21:25:57,219 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:25:57,220 INFO ]: Finished difference Result 87 states and 175 transitions. [2018-06-24 21:25:57,221 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-24 21:25:57,221 INFO ]: Start accepts. Automaton has 5 states. Word has length 14 [2018-06-24 21:25:57,221 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:25:57,224 INFO ]: With dead ends: 87 [2018-06-24 21:25:57,224 INFO ]: Without dead ends: 87 [2018-06-24 21:25:57,225 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=25, Unknown=0, NotChecked=0, Total=42 [2018-06-24 21:25:57,225 INFO ]: Start minimizeSevpa. Operand 87 states. [2018-06-24 21:25:57,237 INFO ]: Finished minimizeSevpa. Reduced states from 87 to 72. [2018-06-24 21:25:57,237 INFO ]: Start removeUnreachable. Operand 72 states. [2018-06-24 21:25:57,240 INFO ]: Finished removeUnreachable. Reduced from 72 states to 72 states and 155 transitions. [2018-06-24 21:25:57,240 INFO ]: Start accepts. Automaton has 72 states and 155 transitions. Word has length 14 [2018-06-24 21:25:57,240 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:25:57,240 INFO ]: Abstraction has 72 states and 155 transitions. [2018-06-24 21:25:57,240 INFO ]: Interpolant automaton has 5 states. [2018-06-24 21:25:57,240 INFO ]: Start isEmpty. Operand 72 states and 155 transitions. [2018-06-24 21:25:57,242 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-24 21:25:57,242 INFO ]: Found error trace [2018-06-24 21:25:57,242 INFO ]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:25:57,242 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:25:57,242 INFO ]: Analyzing trace with hash -686686179, now seen corresponding path program 3 times [2018-06-24 21:25:57,242 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:25:57,242 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:25:57,243 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:57,243 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:25:57,243 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:57,279 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:57,403 INFO ]: Checked inductivity of 17 backedges. 9 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-24 21:25:57,403 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:25:57,403 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:25:57,416 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:25:57,545 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-24 21:25:57,545 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:57,549 INFO ]: Computing forward predicates... [2018-06-24 21:25:57,787 INFO ]: Checked inductivity of 17 backedges. 9 proven. 4 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-24 21:25:57,818 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:25:57,819 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 7 [2018-06-24 21:25:57,819 INFO ]: Interpolant automaton has 7 states [2018-06-24 21:25:57,819 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-24 21:25:57,819 INFO ]: CoverageRelationStatistics Valid=12, Invalid=30, Unknown=0, NotChecked=0, Total=42 [2018-06-24 21:25:57,819 INFO ]: Start difference. First operand 72 states and 155 transitions. Second operand 7 states. [2018-06-24 21:25:58,421 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:25:58,421 INFO ]: Finished difference Result 114 states and 243 transitions. [2018-06-24 21:25:58,422 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-24 21:25:58,422 INFO ]: Start accepts. Automaton has 7 states. Word has length 15 [2018-06-24 21:25:58,422 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:25:58,425 INFO ]: With dead ends: 114 [2018-06-24 21:25:58,425 INFO ]: Without dead ends: 102 [2018-06-24 21:25:58,425 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 16 SyntacticMatches, 1 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=35, Invalid=75, Unknown=0, NotChecked=0, Total=110 [2018-06-24 21:25:58,425 INFO ]: Start minimizeSevpa. Operand 102 states. [2018-06-24 21:25:58,445 INFO ]: Finished minimizeSevpa. Reduced states from 102 to 69. [2018-06-24 21:25:58,445 INFO ]: Start removeUnreachable. Operand 69 states. [2018-06-24 21:25:58,446 INFO ]: Finished removeUnreachable. Reduced from 69 states to 69 states and 145 transitions. [2018-06-24 21:25:58,446 INFO ]: Start accepts. Automaton has 69 states and 145 transitions. Word has length 15 [2018-06-24 21:25:58,452 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:25:58,452 INFO ]: Abstraction has 69 states and 145 transitions. [2018-06-24 21:25:58,452 INFO ]: Interpolant automaton has 7 states. [2018-06-24 21:25:58,452 INFO ]: Start isEmpty. Operand 69 states and 145 transitions. [2018-06-24 21:25:58,453 INFO ]: Finished isEmpty. Found accepting run of length 22 [2018-06-24 21:25:58,453 INFO ]: Found error trace [2018-06-24 21:25:58,454 INFO ]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:25:58,454 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:25:58,454 INFO ]: Analyzing trace with hash -1377035852, now seen corresponding path program 1 times [2018-06-24 21:25:58,454 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:25:58,454 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:25:58,454 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:58,454 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:25:58,454 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:25:58,469 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:58,585 INFO ]: Checked inductivity of 27 backedges. 16 proven. 2 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2018-06-24 21:25:58,585 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:25:58,585 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:25:58,592 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:25:58,690 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:25:58,694 INFO ]: Computing forward predicates... [2018-06-24 21:25:59,058 INFO ]: Checked inductivity of 27 backedges. 13 proven. 9 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2018-06-24 21:25:59,079 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:25:59,079 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 8] total 11 [2018-06-24 21:25:59,079 INFO ]: Interpolant automaton has 11 states [2018-06-24 21:25:59,080 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-24 21:25:59,080 INFO ]: CoverageRelationStatistics Valid=20, Invalid=90, Unknown=0, NotChecked=0, Total=110 [2018-06-24 21:25:59,080 INFO ]: Start difference. First operand 69 states and 145 transitions. Second operand 11 states. [2018-06-24 21:26:00,441 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:26:00,442 INFO ]: Finished difference Result 169 states and 412 transitions. [2018-06-24 21:26:00,442 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-06-24 21:26:00,442 INFO ]: Start accepts. Automaton has 11 states. Word has length 21 [2018-06-24 21:26:00,442 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:26:00,449 INFO ]: With dead ends: 169 [2018-06-24 21:26:00,449 INFO ]: Without dead ends: 169 [2018-06-24 21:26:00,449 INFO ]: 0 DeclaredPredicates, 53 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 203 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=187, Invalid=805, Unknown=0, NotChecked=0, Total=992 [2018-06-24 21:26:00,450 INFO ]: Start minimizeSevpa. Operand 169 states. [2018-06-24 21:26:00,477 INFO ]: Finished minimizeSevpa. Reduced states from 169 to 91. [2018-06-24 21:26:00,477 INFO ]: Start removeUnreachable. Operand 91 states. [2018-06-24 21:26:00,479 INFO ]: Finished removeUnreachable. Reduced from 91 states to 91 states and 204 transitions. [2018-06-24 21:26:00,480 INFO ]: Start accepts. Automaton has 91 states and 204 transitions. Word has length 21 [2018-06-24 21:26:00,480 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:26:00,480 INFO ]: Abstraction has 91 states and 204 transitions. [2018-06-24 21:26:00,480 INFO ]: Interpolant automaton has 11 states. [2018-06-24 21:26:00,480 INFO ]: Start isEmpty. Operand 91 states and 204 transitions. [2018-06-24 21:26:00,485 INFO ]: Finished isEmpty. Found accepting run of length 33 [2018-06-24 21:26:00,485 INFO ]: Found error trace [2018-06-24 21:26:00,486 INFO ]: trace histogram [5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:26:00,486 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:26:00,486 INFO ]: Analyzing trace with hash -404379993, now seen corresponding path program 1 times [2018-06-24 21:26:00,486 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:26:00,486 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:26:00,486 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:00,486 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:26:00,486 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:00,506 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:00,673 INFO ]: Checked inductivity of 66 backedges. 31 proven. 0 refuted. 0 times theorem prover too weak. 35 trivial. 0 not checked. [2018-06-24 21:26:00,673 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:26:00,673 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:26:00,673 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:26:00,673 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:26:00,673 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:26:00,673 INFO ]: Start difference. First operand 91 states and 204 transitions. Second operand 3 states. [2018-06-24 21:26:00,755 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:26:00,756 INFO ]: Finished difference Result 102 states and 225 transitions. [2018-06-24 21:26:00,756 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:26:00,756 INFO ]: Start accepts. Automaton has 3 states. Word has length 32 [2018-06-24 21:26:00,756 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:26:00,759 INFO ]: With dead ends: 102 [2018-06-24 21:26:00,759 INFO ]: Without dead ends: 102 [2018-06-24 21:26:00,759 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:26:00,759 INFO ]: Start minimizeSevpa. Operand 102 states. [2018-06-24 21:26:00,772 INFO ]: Finished minimizeSevpa. Reduced states from 102 to 102. [2018-06-24 21:26:00,772 INFO ]: Start removeUnreachable. Operand 102 states. [2018-06-24 21:26:00,774 INFO ]: Finished removeUnreachable. Reduced from 102 states to 102 states and 225 transitions. [2018-06-24 21:26:00,774 INFO ]: Start accepts. Automaton has 102 states and 225 transitions. Word has length 32 [2018-06-24 21:26:00,774 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:26:00,774 INFO ]: Abstraction has 102 states and 225 transitions. [2018-06-24 21:26:00,774 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:26:00,774 INFO ]: Start isEmpty. Operand 102 states and 225 transitions. [2018-06-24 21:26:00,778 INFO ]: Finished isEmpty. Found accepting run of length 45 [2018-06-24 21:26:00,778 INFO ]: Found error trace [2018-06-24 21:26:00,778 INFO ]: trace histogram [7, 4, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:26:00,778 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:26:00,778 INFO ]: Analyzing trace with hash -330761154, now seen corresponding path program 1 times [2018-06-24 21:26:00,778 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:26:00,778 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:26:00,779 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:00,779 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:26:00,779 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:00,802 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:01,126 INFO ]: Checked inductivity of 122 backedges. 41 proven. 16 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2018-06-24 21:26:01,126 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:26:01,126 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) [2018-06-24 21:26:01,142 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:26:01,344 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:01,352 INFO ]: Computing forward predicates... [2018-06-24 21:26:01,940 INFO ]: Checked inductivity of 122 backedges. 42 proven. 0 refuted. 0 times theorem prover too weak. 80 trivial. 0 not checked. [2018-06-24 21:26:01,973 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-24 21:26:01,973 INFO ]: Number of different interpolants: perfect sequences [5] imperfect sequences [7] total 10 [2018-06-24 21:26:01,973 INFO ]: Interpolant automaton has 10 states [2018-06-24 21:26:01,973 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-24 21:26:01,973 INFO ]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-06-24 21:26:01,973 INFO ]: Start difference. First operand 102 states and 225 transitions. Second operand 10 states. [2018-06-24 21:26:03,456 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:26:03,456 INFO ]: Finished difference Result 307 states and 776 transitions. [2018-06-24 21:26:03,457 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-06-24 21:26:03,457 INFO ]: Start accepts. Automaton has 10 states. Word has length 44 [2018-06-24 21:26:03,457 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:26:03,465 INFO ]: With dead ends: 307 [2018-06-24 21:26:03,465 INFO ]: Without dead ends: 307 [2018-06-24 21:26:03,465 INFO ]: 0 DeclaredPredicates, 85 GetRequests, 57 SyntacticMatches, 0 SemanticMatches, 28 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 166 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=142, Invalid=728, Unknown=0, NotChecked=0, Total=870 [2018-06-24 21:26:03,466 INFO ]: Start minimizeSevpa. Operand 307 states. [2018-06-24 21:26:03,514 INFO ]: Finished minimizeSevpa. Reduced states from 307 to 186. [2018-06-24 21:26:03,514 INFO ]: Start removeUnreachable. Operand 186 states. [2018-06-24 21:26:03,519 INFO ]: Finished removeUnreachable. Reduced from 186 states to 186 states and 416 transitions. [2018-06-24 21:26:03,519 INFO ]: Start accepts. Automaton has 186 states and 416 transitions. Word has length 44 [2018-06-24 21:26:03,519 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:26:03,519 INFO ]: Abstraction has 186 states and 416 transitions. [2018-06-24 21:26:03,519 INFO ]: Interpolant automaton has 10 states. [2018-06-24 21:26:03,519 INFO ]: Start isEmpty. Operand 186 states and 416 transitions. [2018-06-24 21:26:03,523 INFO ]: Finished isEmpty. Found accepting run of length 46 [2018-06-24 21:26:03,523 INFO ]: Found error trace [2018-06-24 21:26:03,524 INFO ]: trace histogram [7, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:26:03,526 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:26:03,526 INFO ]: Analyzing trace with hash 261857268, now seen corresponding path program 1 times [2018-06-24 21:26:03,526 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:26:03,526 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:26:03,527 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:03,527 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:26:03,527 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:03,552 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:03,926 WARN ]: Spent 229.00 ms on a formula simplification. DAG size of input: 8 DAG size of output: 6 [2018-06-24 21:26:04,029 INFO ]: Checked inductivity of 135 backedges. 62 proven. 7 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-06-24 21:26:04,029 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:26:04,029 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-24 21:26:04,041 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:26:04,276 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:04,285 INFO ]: Computing forward predicates... [2018-06-24 21:26:04,487 INFO ]: Checked inductivity of 135 backedges. 52 proven. 0 refuted. 0 times theorem prover too weak. 83 trivial. 0 not checked. [2018-06-24 21:26:04,520 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-24 21:26:04,520 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [5] total 6 [2018-06-24 21:26:04,520 INFO ]: Interpolant automaton has 6 states [2018-06-24 21:26:04,521 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-24 21:26:04,521 INFO ]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-06-24 21:26:04,521 INFO ]: Start difference. First operand 186 states and 416 transitions. Second operand 6 states. [2018-06-24 21:26:04,643 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:26:04,643 INFO ]: Finished difference Result 234 states and 493 transitions. [2018-06-24 21:26:04,644 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-24 21:26:04,644 INFO ]: Start accepts. Automaton has 6 states. Word has length 45 [2018-06-24 21:26:04,644 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:26:04,649 INFO ]: With dead ends: 234 [2018-06-24 21:26:04,649 INFO ]: Without dead ends: 234 [2018-06-24 21:26:04,649 INFO ]: 0 DeclaredPredicates, 50 GetRequests, 45 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2018-06-24 21:26:04,649 INFO ]: Start minimizeSevpa. Operand 234 states. [2018-06-24 21:26:04,669 INFO ]: Finished minimizeSevpa. Reduced states from 234 to 186. [2018-06-24 21:26:04,669 INFO ]: Start removeUnreachable. Operand 186 states. [2018-06-24 21:26:04,675 INFO ]: Finished removeUnreachable. Reduced from 186 states to 186 states and 411 transitions. [2018-06-24 21:26:04,675 INFO ]: Start accepts. Automaton has 186 states and 411 transitions. Word has length 45 [2018-06-24 21:26:04,675 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:26:04,675 INFO ]: Abstraction has 186 states and 411 transitions. [2018-06-24 21:26:04,675 INFO ]: Interpolant automaton has 6 states. [2018-06-24 21:26:04,675 INFO ]: Start isEmpty. Operand 186 states and 411 transitions. [2018-06-24 21:26:04,681 INFO ]: Finished isEmpty. Found accepting run of length 47 [2018-06-24 21:26:04,681 INFO ]: Found error trace [2018-06-24 21:26:04,681 INFO ]: trace histogram [7, 6, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:26:04,681 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:26:04,681 INFO ]: Analyzing trace with hash -1433995608, now seen corresponding path program 1 times [2018-06-24 21:26:04,681 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:26:04,681 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:26:04,682 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:04,682 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:26:04,682 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:04,735 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:05,060 INFO ]: Checked inductivity of 149 backedges. 83 proven. 15 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2018-06-24 21:26:05,060 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:26:05,060 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:26:05,077 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:26:05,252 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:05,259 INFO ]: Computing forward predicates... [2018-06-24 21:26:05,423 INFO ]: Checked inductivity of 149 backedges. 71 proven. 27 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2018-06-24 21:26:05,445 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:26:05,445 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-06-24 21:26:05,445 INFO ]: Interpolant automaton has 15 states [2018-06-24 21:26:05,445 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-24 21:26:05,445 INFO ]: CoverageRelationStatistics Valid=34, Invalid=176, Unknown=0, NotChecked=0, Total=210 [2018-06-24 21:26:05,445 INFO ]: Start difference. First operand 186 states and 411 transitions. Second operand 15 states. [2018-06-24 21:26:06,470 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:26:06,470 INFO ]: Finished difference Result 331 states and 784 transitions. [2018-06-24 21:26:06,470 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 22 states. [2018-06-24 21:26:06,470 INFO ]: Start accepts. Automaton has 15 states. Word has length 46 [2018-06-24 21:26:06,470 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:26:06,477 INFO ]: With dead ends: 331 [2018-06-24 21:26:06,477 INFO ]: Without dead ends: 331 [2018-06-24 21:26:06,478 INFO ]: 0 DeclaredPredicates, 83 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 157 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=181, Invalid=811, Unknown=0, NotChecked=0, Total=992 [2018-06-24 21:26:06,478 INFO ]: Start minimizeSevpa. Operand 331 states. [2018-06-24 21:26:06,512 INFO ]: Finished minimizeSevpa. Reduced states from 331 to 251. [2018-06-24 21:26:06,512 INFO ]: Start removeUnreachable. Operand 251 states. [2018-06-24 21:26:06,520 INFO ]: Finished removeUnreachable. Reduced from 251 states to 251 states and 625 transitions. [2018-06-24 21:26:06,520 INFO ]: Start accepts. Automaton has 251 states and 625 transitions. Word has length 46 [2018-06-24 21:26:06,520 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:26:06,520 INFO ]: Abstraction has 251 states and 625 transitions. [2018-06-24 21:26:06,520 INFO ]: Interpolant automaton has 15 states. [2018-06-24 21:26:06,520 INFO ]: Start isEmpty. Operand 251 states and 625 transitions. [2018-06-24 21:26:06,529 INFO ]: Finished isEmpty. Found accepting run of length 48 [2018-06-24 21:26:06,529 INFO ]: Found error trace [2018-06-24 21:26:06,529 INFO ]: trace histogram [7, 7, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:26:06,529 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:26:06,529 INFO ]: Analyzing trace with hash -1238887528, now seen corresponding path program 2 times [2018-06-24 21:26:06,529 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:26:06,529 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:26:06,530 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:06,530 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:26:06,530 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:06,577 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:07,524 INFO ]: Checked inductivity of 164 backedges. 83 proven. 30 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2018-06-24 21:26:07,524 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:26:07,524 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:26:07,530 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:26:07,683 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:26:07,683 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:07,689 INFO ]: Computing forward predicates... [2018-06-24 21:26:07,798 INFO ]: Checked inductivity of 164 backedges. 72 proven. 41 refuted. 0 times theorem prover too weak. 51 trivial. 0 not checked. [2018-06-24 21:26:07,819 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:26:07,819 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 17 [2018-06-24 21:26:07,819 INFO ]: Interpolant automaton has 17 states [2018-06-24 21:26:07,819 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-24 21:26:07,819 INFO ]: CoverageRelationStatistics Valid=39, Invalid=233, Unknown=0, NotChecked=0, Total=272 [2018-06-24 21:26:07,819 INFO ]: Start difference. First operand 251 states and 625 transitions. Second operand 17 states. [2018-06-24 21:26:10,610 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:26:10,610 INFO ]: Finished difference Result 432 states and 1229 transitions. [2018-06-24 21:26:10,613 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 30 states. [2018-06-24 21:26:10,613 INFO ]: Start accepts. Automaton has 17 states. Word has length 47 [2018-06-24 21:26:10,613 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:26:10,622 INFO ]: With dead ends: 432 [2018-06-24 21:26:10,622 INFO ]: Without dead ends: 432 [2018-06-24 21:26:10,623 INFO ]: 0 DeclaredPredicates, 99 GetRequests, 60 SyntacticMatches, 0 SemanticMatches, 39 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 298 ImplicationChecksByTransitivity, 1.3s TimeCoverageRelationStatistics Valid=287, Invalid=1353, Unknown=0, NotChecked=0, Total=1640 [2018-06-24 21:26:10,623 INFO ]: Start minimizeSevpa. Operand 432 states. [2018-06-24 21:26:10,683 INFO ]: Finished minimizeSevpa. Reduced states from 432 to 268. [2018-06-24 21:26:10,683 INFO ]: Start removeUnreachable. Operand 268 states. [2018-06-24 21:26:10,689 INFO ]: Finished removeUnreachable. Reduced from 268 states to 268 states and 686 transitions. [2018-06-24 21:26:10,690 INFO ]: Start accepts. Automaton has 268 states and 686 transitions. Word has length 47 [2018-06-24 21:26:10,690 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:26:10,690 INFO ]: Abstraction has 268 states and 686 transitions. [2018-06-24 21:26:10,690 INFO ]: Interpolant automaton has 17 states. [2018-06-24 21:26:10,690 INFO ]: Start isEmpty. Operand 268 states and 686 transitions. [2018-06-24 21:26:10,703 INFO ]: Finished isEmpty. Found accepting run of length 49 [2018-06-24 21:26:10,703 INFO ]: Found error trace [2018-06-24 21:26:10,703 INFO ]: trace histogram [8, 7, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:26:10,703 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:26:10,703 INFO ]: Analyzing trace with hash 514495656, now seen corresponding path program 3 times [2018-06-24 21:26:10,703 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:26:10,704 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:26:10,704 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:10,704 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:26:10,704 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:10,758 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:10,941 INFO ]: Checked inductivity of 180 backedges. 44 proven. 70 refuted. 0 times theorem prover too weak. 66 trivial. 0 not checked. [2018-06-24 21:26:10,941 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:26:10,941 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:26:10,947 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:26:11,103 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 5 check-sat command(s) [2018-06-24 21:26:11,104 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:11,109 INFO ]: Computing forward predicates... [2018-06-24 21:26:11,149 INFO ]: Checked inductivity of 180 backedges. 19 proven. 42 refuted. 0 times theorem prover too weak. 119 trivial. 0 not checked. [2018-06-24 21:26:11,169 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:26:11,169 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 5] total 11 [2018-06-24 21:26:11,169 INFO ]: Interpolant automaton has 11 states [2018-06-24 21:26:11,169 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-24 21:26:11,169 INFO ]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2018-06-24 21:26:11,170 INFO ]: Start difference. First operand 268 states and 686 transitions. Second operand 11 states. [2018-06-24 21:26:11,822 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:26:11,822 INFO ]: Finished difference Result 517 states and 1508 transitions. [2018-06-24 21:26:11,822 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2018-06-24 21:26:11,822 INFO ]: Start accepts. Automaton has 11 states. Word has length 48 [2018-06-24 21:26:11,823 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:26:11,840 INFO ]: With dead ends: 517 [2018-06-24 21:26:11,840 INFO ]: Without dead ends: 517 [2018-06-24 21:26:11,841 INFO ]: 0 DeclaredPredicates, 78 GetRequests, 52 SyntacticMatches, 1 SemanticMatches, 25 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 128 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=121, Invalid=581, Unknown=0, NotChecked=0, Total=702 [2018-06-24 21:26:11,841 INFO ]: Start minimizeSevpa. Operand 517 states. [2018-06-24 21:26:11,931 INFO ]: Finished minimizeSevpa. Reduced states from 517 to 375. [2018-06-24 21:26:11,931 INFO ]: Start removeUnreachable. Operand 375 states. [2018-06-24 21:26:11,942 INFO ]: Finished removeUnreachable. Reduced from 375 states to 375 states and 1096 transitions. [2018-06-24 21:26:11,942 INFO ]: Start accepts. Automaton has 375 states and 1096 transitions. Word has length 48 [2018-06-24 21:26:11,942 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:26:11,942 INFO ]: Abstraction has 375 states and 1096 transitions. [2018-06-24 21:26:11,942 INFO ]: Interpolant automaton has 11 states. [2018-06-24 21:26:11,942 INFO ]: Start isEmpty. Operand 375 states and 1096 transitions. [2018-06-24 21:26:11,976 INFO ]: Finished isEmpty. Found accepting run of length 66 [2018-06-24 21:26:11,976 INFO ]: Found error trace [2018-06-24 21:26:11,977 INFO ]: trace histogram [11, 9, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:26:11,977 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:26:11,977 INFO ]: Analyzing trace with hash -990779174, now seen corresponding path program 4 times [2018-06-24 21:26:11,977 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:26:11,977 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:26:11,978 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:11,978 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:26:11,978 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:12,004 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:12,291 INFO ]: Checked inductivity of 361 backedges. 116 proven. 94 refuted. 0 times theorem prover too weak. 151 trivial. 0 not checked. [2018-06-24 21:26:12,291 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:26:12,291 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:26:12,299 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-24 21:26:12,526 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-24 21:26:12,526 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:12,535 INFO ]: Computing forward predicates... [2018-06-24 21:26:12,647 INFO ]: Checked inductivity of 361 backedges. 167 proven. 74 refuted. 0 times theorem prover too weak. 120 trivial. 0 not checked. [2018-06-24 21:26:12,668 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:26:12,668 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9] total 15 [2018-06-24 21:26:12,669 INFO ]: Interpolant automaton has 15 states [2018-06-24 21:26:12,669 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-24 21:26:12,669 INFO ]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2018-06-24 21:26:12,669 INFO ]: Start difference. First operand 375 states and 1096 transitions. Second operand 15 states. [2018-06-24 21:26:15,826 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:26:15,826 INFO ]: Finished difference Result 761 states and 2470 transitions. [2018-06-24 21:26:15,827 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-06-24 21:26:15,827 INFO ]: Start accepts. Automaton has 15 states. Word has length 65 [2018-06-24 21:26:15,827 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:26:15,856 INFO ]: With dead ends: 761 [2018-06-24 21:26:15,856 INFO ]: Without dead ends: 761 [2018-06-24 21:26:15,856 INFO ]: 0 DeclaredPredicates, 112 GetRequests, 69 SyntacticMatches, 0 SemanticMatches, 43 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 388 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=295, Invalid=1685, Unknown=0, NotChecked=0, Total=1980 [2018-06-24 21:26:15,857 INFO ]: Start minimizeSevpa. Operand 761 states. [2018-06-24 21:26:15,973 INFO ]: Finished minimizeSevpa. Reduced states from 761 to 425. [2018-06-24 21:26:15,974 INFO ]: Start removeUnreachable. Operand 425 states. [2018-06-24 21:26:15,987 INFO ]: Finished removeUnreachable. Reduced from 425 states to 425 states and 1283 transitions. [2018-06-24 21:26:15,987 INFO ]: Start accepts. Automaton has 425 states and 1283 transitions. Word has length 65 [2018-06-24 21:26:15,988 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:26:15,988 INFO ]: Abstraction has 425 states and 1283 transitions. [2018-06-24 21:26:15,988 INFO ]: Interpolant automaton has 15 states. [2018-06-24 21:26:15,988 INFO ]: Start isEmpty. Operand 425 states and 1283 transitions. [2018-06-24 21:26:16,026 INFO ]: Finished isEmpty. Found accepting run of length 67 [2018-06-24 21:26:16,026 INFO ]: Found error trace [2018-06-24 21:26:16,026 INFO ]: trace histogram [12, 9, 4, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:26:16,026 INFO ]: === Iteration 18 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:26:16,026 INFO ]: Analyzing trace with hash -670138766, now seen corresponding path program 5 times [2018-06-24 21:26:16,026 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:26:16,026 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:26:16,026 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:16,027 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:26:16,027 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:16,150 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:17,018 INFO ]: Checked inductivity of 385 backedges. 164 proven. 120 refuted. 0 times theorem prover too weak. 101 trivial. 0 not checked. [2018-06-24 21:26:17,018 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:26:17,018 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) [2018-06-24 21:26:17,032 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:26:17,252 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 10 check-sat command(s) [2018-06-24 21:26:17,252 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:17,262 INFO ]: Computing forward predicates... [2018-06-24 21:26:17,604 INFO ]: Checked inductivity of 385 backedges. 209 proven. 90 refuted. 0 times theorem prover too weak. 86 trivial. 0 not checked. [2018-06-24 21:26:17,626 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:26:17,626 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 14] total 26 [2018-06-24 21:26:17,626 INFO ]: Interpolant automaton has 26 states [2018-06-24 21:26:17,626 INFO ]: Constructing interpolant automaton starting with 26 interpolants. [2018-06-24 21:26:17,626 INFO ]: CoverageRelationStatistics Valid=54, Invalid=596, Unknown=0, NotChecked=0, Total=650 [2018-06-24 21:26:17,627 INFO ]: Start difference. First operand 425 states and 1283 transitions. Second operand 26 states. [2018-06-24 21:26:35,485 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:26:35,485 INFO ]: Finished difference Result 2896 states and 18725 transitions. [2018-06-24 21:26:35,485 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 286 states. [2018-06-24 21:26:35,485 INFO ]: Start accepts. Automaton has 26 states. Word has length 66 [2018-06-24 21:26:35,485 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:26:35,809 INFO ]: With dead ends: 2896 [2018-06-24 21:26:35,809 INFO ]: Without dead ends: 2728 [2018-06-24 21:26:35,820 INFO ]: 0 DeclaredPredicates, 443 GetRequests, 145 SyntacticMatches, 1 SemanticMatches, 297 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 36908 ImplicationChecksByTransitivity, 6.7s TimeCoverageRelationStatistics Valid=5393, Invalid=83709, Unknown=0, NotChecked=0, Total=89102 [2018-06-24 21:26:35,821 INFO ]: Start minimizeSevpa. Operand 2728 states. [2018-06-24 21:26:37,337 INFO ]: Finished minimizeSevpa. Reduced states from 2728 to 962. [2018-06-24 21:26:37,337 INFO ]: Start removeUnreachable. Operand 962 states. [2018-06-24 21:26:37,379 INFO ]: Finished removeUnreachable. Reduced from 962 states to 962 states and 3506 transitions. [2018-06-24 21:26:37,379 INFO ]: Start accepts. Automaton has 962 states and 3506 transitions. Word has length 66 [2018-06-24 21:26:37,379 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:26:37,379 INFO ]: Abstraction has 962 states and 3506 transitions. [2018-06-24 21:26:37,379 INFO ]: Interpolant automaton has 26 states. [2018-06-24 21:26:37,379 INFO ]: Start isEmpty. Operand 962 states and 3506 transitions. [2018-06-24 21:26:37,527 INFO ]: Finished isEmpty. Found accepting run of length 90 [2018-06-24 21:26:37,527 INFO ]: Found error trace [2018-06-24 21:26:37,527 INFO ]: trace histogram [14, 13, 5, 4, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:26:37,527 INFO ]: === Iteration 19 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:26:37,528 INFO ]: Analyzing trace with hash -1530764516, now seen corresponding path program 1 times [2018-06-24 21:26:37,528 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:26:37,528 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:26:37,529 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:37,529 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:26:37,529 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:26:37,558 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:37,746 INFO ]: Checked inductivity of 647 backedges. 150 proven. 10 refuted. 0 times theorem prover too weak. 487 trivial. 0 not checked. [2018-06-24 21:26:37,746 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:26:37,746 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:26:37,759 INFO ]: Keeping assertion order NOT_INCREMENTALLY Received shutdown request... [2018-06-24 21:26:38,060 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:26:38,068 INFO ]: Computing forward predicates... [2018-06-24 21:26:38,071 INFO ]: Timeout while computing interpolants [2018-06-24 21:26:38,271 WARN ]: Destroyed unattended storables created during the last iteration: 13 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:26:38,271 WARN ]: Verification canceled [2018-06-24 21:26:38,273 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-24 21:26:38,274 WARN ]: Timeout [2018-06-24 21:26:38,275 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.06 09:26:38 BasicIcfg [2018-06-24 21:26:38,275 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-24 21:26:38,275 INFO ]: Toolchain (without parser) took 56249.85 ms. Allocated memory was 303.0 MB in the beginning and 1.2 GB in the end (delta: 866.6 MB). Free memory was 229.5 MB in the beginning and 558.2 MB in the end (delta: -328.7 MB). Peak memory consumption was 537.9 MB. Max. memory is 3.6 GB. [2018-06-24 21:26:38,276 INFO ]: SmtParser took 0.09 ms. Allocated memory is still 303.0 MB. Free memory is still 266.5 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-24 21:26:38,276 INFO ]: ChcToBoogie took 116.70 ms. Allocated memory is still 303.0 MB. Free memory was 229.5 MB in the beginning and 225.5 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-24 21:26:38,277 INFO ]: Boogie Preprocessor took 57.28 ms. Allocated memory is still 303.0 MB. Free memory was 225.5 MB in the beginning and 224.5 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. [2018-06-24 21:26:38,277 INFO ]: RCFGBuilder took 965.27 ms. Allocated memory was 303.0 MB in the beginning and 322.4 MB in the end (delta: 19.4 MB). Free memory was 223.5 MB in the beginning and 288.2 MB in the end (delta: -64.7 MB). Peak memory consumption was 47.4 MB. Max. memory is 3.6 GB. [2018-06-24 21:26:38,278 INFO ]: BlockEncodingV2 took 10633.46 ms. Allocated memory was 322.4 MB in the beginning and 386.9 MB in the end (delta: 64.5 MB). Free memory was 288.2 MB in the beginning and 205.0 MB in the end (delta: 83.1 MB). Peak memory consumption was 151.6 MB. Max. memory is 3.6 GB. [2018-06-24 21:26:38,284 INFO ]: TraceAbstraction took 44458.77 ms. Allocated memory was 386.9 MB in the beginning and 1.2 GB in the end (delta: 782.8 MB). Free memory was 202.0 MB in the beginning and 558.2 MB in the end (delta: -356.2 MB). Peak memory consumption was 426.5 MB. Max. memory is 3.6 GB. [2018-06-24 21:26:38,287 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.plugins.blockencoding: - StatisticsResult: Initial Icfg 48 locations, 77 edges - StatisticsResult: Encoded RCFG 30 locations, 103 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.09 ms. Allocated memory is still 303.0 MB. Free memory is still 266.5 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 116.70 ms. Allocated memory is still 303.0 MB. Free memory was 229.5 MB in the beginning and 225.5 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 57.28 ms. Allocated memory is still 303.0 MB. Free memory was 225.5 MB in the beginning and 224.5 MB in the end (delta: 996.1 kB). Peak memory consumption was 996.1 kB. Max. memory is 3.6 GB. * RCFGBuilder took 965.27 ms. Allocated memory was 303.0 MB in the beginning and 322.4 MB in the end (delta: 19.4 MB). Free memory was 223.5 MB in the beginning and 288.2 MB in the end (delta: -64.7 MB). Peak memory consumption was 47.4 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 10633.46 ms. Allocated memory was 322.4 MB in the beginning and 386.9 MB in the end (delta: 64.5 MB). Free memory was 288.2 MB in the beginning and 205.0 MB in the end (delta: 83.1 MB). Peak memory consumption was 151.6 MB. Max. memory is 3.6 GB. * TraceAbstraction took 44458.77 ms. Allocated memory was 386.9 MB in the beginning and 1.2 GB in the end (delta: 782.8 MB). Free memory was 202.0 MB in the beginning and 558.2 MB in the end (delta: -356.2 MB). Peak memory consumption was 426.5 MB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds Cancelled while BasicCegarLoop was analyzing trace of length 90 with TraceHistMax 14, while TraceCheckSpWp was constructing forward predicates, while PredicateComparison was comparing new predicate (quantifier-free) to 4 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 30 locations, 1 error locations. TIMEOUT Result, 44.3s OverallTime, 19 OverallIterations, 14 TraceHistogramMax, 31.4s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 1436 SDtfs, 1555 SDslu, 5038 SDs, 0 SdLazy, 25211 SolverSat, 4973 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 19.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1076 GetRequests, 552 SyntacticMatches, 3 SemanticMatches, 521 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 38254 ImplicationChecksByTransitivity, 13.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=962occurred in iteration=18, 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: 2.1s AutomataMinimizationTime, 18 MinimizatonAttempts, 2813 StatesRemovedByMinimization, 13 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.5s SsaConstructionTime, 1.8s SatisfiabilityAnalysisTime, 6.8s InterpolantComputationTime, 913 NumberOfCodeBlocks, 884 NumberOfCodeBlocksAsserted, 45 NumberOfCheckSat, 885 ConstructedInterpolants, 0 QuantifiedInterpolants, 85167 SizeOfPredicates, 73 NumberOfNonLiveVariables, 12480 ConjunctsInSsa, 180 ConjunctsInUnsatCore, 28 InterpolantComputations, 10 PerfectInterpolantSequences, 2544/3193 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/Ackermann06.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-24_21-26-38-300.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/Ackermann06.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-24_21-26-38-300.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/Ackermann06.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-24_21-26-38-300.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/Ackermann06.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-24_21-26-38-300.csv Completed graceful shutdown