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/eldarica-misc/LIA/reve/012-horn.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-24 21:03:25,307 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-24 21:03:25,309 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-24 21:03:25,320 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-24 21:03:25,320 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-24 21:03:25,321 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-24 21:03:25,322 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-24 21:03:25,324 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-24 21:03:25,326 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-24 21:03:25,326 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-24 21:03:25,327 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-24 21:03:25,328 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-24 21:03:25,328 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-24 21:03:25,330 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-24 21:03:25,330 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-24 21:03:25,331 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-24 21:03:25,333 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-24 21:03:25,335 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-24 21:03:25,336 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-24 21:03:25,337 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-24 21:03:25,338 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-24 21:03:25,341 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-24 21:03:25,341 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-24 21:03:25,341 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-24 21:03:25,342 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-24 21:03:25,343 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-24 21:03:25,344 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-24 21:03:25,345 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-24 21:03:25,346 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-24 21:03:25,346 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-24 21:03:25,347 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-24 21:03:25,347 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-24 21:03:25,348 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-24 21:03:25,349 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-24 21:03:25,349 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-24 21:03:25,350 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:03:25,364 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-24 21:03:25,364 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-24 21:03:25,364 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-24 21:03:25,365 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-24 21:03:25,366 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-24 21:03:25,366 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-24 21:03:25,366 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-24 21:03:25,367 INFO L133 SettingsManager]: * Use SBE=true [2018-06-24 21:03:25,367 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-24 21:03:25,367 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-24 21:03:25,367 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-24 21:03:25,368 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-24 21:03:25,368 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-24 21:03:25,368 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-24 21:03:25,368 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-24 21:03:25,369 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-24 21:03:25,369 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-24 21:03:25,369 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-24 21:03:25,369 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-24 21:03:25,369 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-24 21:03:25,370 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-24 21:03:25,371 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-24 21:03:25,371 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-24 21:03:25,414 INFO ]: Repository-Root is: /tmp [2018-06-24 21:03:25,429 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-24 21:03:25,433 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-24 21:03:25,436 INFO ]: Initializing SmtParser... [2018-06-24 21:03:25,436 INFO ]: SmtParser initialized [2018-06-24 21:03:25,437 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/eldarica-misc/LIA/reve/012-horn.smt2 [2018-06-24 21:03:25,438 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:03:25,528 INFO ]: Executing SMT file /storage/chc-comp/eldarica-misc/LIA/reve/012-horn.smt2 unknown [2018-06-24 21:03:25,738 INFO ]: Succesfully executed SMT file /storage/chc-comp/eldarica-misc/LIA/reve/012-horn.smt2 [2018-06-24 21:03:25,742 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-24 21:03:25,751 INFO ]: Walking toolchain with 5 elements. [2018-06-24 21:03:25,751 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-24 21:03:25,751 INFO ]: Initializing ChcToBoogie... [2018-06-24 21:03:25,752 INFO ]: ChcToBoogie initialized [2018-06-24 21:03:25,755 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 24.06 09:03:25" (1/1) ... [2018-06-24 21:03:25,807 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:25 Unit [2018-06-24 21:03:25,807 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-24 21:03:25,810 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-24 21:03:25,810 INFO ]: Initializing Boogie Preprocessor... [2018-06-24 21:03:25,810 INFO ]: Boogie Preprocessor initialized [2018-06-24 21:03:25,831 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:25" (1/1) ... [2018-06-24 21:03:25,831 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:25" (1/1) ... [2018-06-24 21:03:25,837 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:25" (1/1) ... [2018-06-24 21:03:25,837 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:25" (1/1) ... [2018-06-24 21:03:25,840 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:25" (1/1) ... [2018-06-24 21:03:25,843 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:25" (1/1) ... [2018-06-24 21:03:25,844 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:25" (1/1) ... [2018-06-24 21:03:25,846 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-24 21:03:25,847 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-24 21:03:25,847 INFO ]: Initializing RCFGBuilder... [2018-06-24 21:03:25,847 INFO ]: RCFGBuilder initialized [2018-06-24 21:03:25,848 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:25" (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:03:25,862 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-24 21:03:25,862 INFO ]: Found specification of procedure gotoProc [2018-06-24 21:03:25,862 INFO ]: Found implementation of procedure gotoProc [2018-06-24 21:03:25,862 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-24 21:03:25,862 INFO ]: Found specification of procedure Ultimate.START [2018-06-24 21:03:25,862 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:03:26,149 INFO ]: Using library mode [2018-06-24 21:03:26,149 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:03:26 BoogieIcfgContainer [2018-06-24 21:03:26,149 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-24 21:03:26,150 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-24 21:03:26,150 INFO ]: Initializing BlockEncodingV2... [2018-06-24 21:03:26,151 INFO ]: BlockEncodingV2 initialized [2018-06-24 21:03:26,152 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:03:26" (1/1) ... [2018-06-24 21:03:26,174 INFO ]: Initial Icfg 12 locations, 19 edges [2018-06-24 21:03:26,176 INFO ]: Using Remove infeasible edges [2018-06-24 21:03:26,176 INFO ]: Using Maximize final states [2018-06-24 21:03:26,177 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-24 21:03:26,177 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-24 21:03:26,179 INFO ]: Using Remove sink states [2018-06-24 21:03:26,182 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-24 21:03:26,182 INFO ]: Using Use SBE [2018-06-24 21:03:26,189 INFO ]: SBE split 0 edges [2018-06-24 21:03:26,194 INFO ]: Removed 5 edges and 2 locations because of local infeasibility [2018-06-24 21:03:26,197 INFO ]: 0 new accepting states [2018-06-24 21:03:26,231 INFO ]: Removed 6 edges and 2 locations by large block encoding [2018-06-24 21:03:26,233 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 21:03:26,237 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-24 21:03:26,237 INFO ]: 0 new accepting states [2018-06-24 21:03:26,237 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-24 21:03:26,237 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 21:03:26,238 INFO ]: Encoded RCFG 8 locations, 12 edges [2018-06-24 21:03:26,238 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 24.06 09:03:26 BasicIcfg [2018-06-24 21:03:26,238 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-24 21:03:26,239 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-24 21:03:26,239 INFO ]: Initializing TraceAbstraction... [2018-06-24 21:03:26,242 INFO ]: TraceAbstraction initialized [2018-06-24 21:03:26,242 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 24.06 09:03:25" (1/4) ... [2018-06-24 21:03:26,243 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@512a05fb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 24.06 09:03:26, skipping insertion in model container [2018-06-24 21:03:26,243 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:25" (2/4) ... [2018-06-24 21:03:26,243 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@512a05fb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.06 09:03:26, skipping insertion in model container [2018-06-24 21:03:26,243 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:03:26" (3/4) ... [2018-06-24 21:03:26,244 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@512a05fb and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.06 09:03:26, skipping insertion in model container [2018-06-24 21:03:26,244 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 24.06 09:03:26" (4/4) ... [2018-06-24 21:03:26,246 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-24 21:03:26,258 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-24 21:03:26,264 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-24 21:03:26,298 INFO ]: Using default assertion order modulation [2018-06-24 21:03:26,299 INFO ]: Interprodecural is true [2018-06-24 21:03:26,299 INFO ]: Hoare is false [2018-06-24 21:03:26,299 INFO ]: Compute interpolants for FPandBP [2018-06-24 21:03:26,299 INFO ]: Backedges is TWOTRACK [2018-06-24 21:03:26,299 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-24 21:03:26,299 INFO ]: Difference is false [2018-06-24 21:03:26,299 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-24 21:03:26,299 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-24 21:03:26,314 INFO ]: Start isEmpty. Operand 8 states. [2018-06-24 21:03:26,324 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-24 21:03:26,324 INFO ]: Found error trace [2018-06-24 21:03:26,325 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-24 21:03:26,325 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:26,330 INFO ]: Analyzing trace with hash 37528575, now seen corresponding path program 1 times [2018-06-24 21:03:26,332 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:26,333 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:26,371 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:26,371 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:26,371 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:26,414 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:26,564 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:03:26,566 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:03:26,566 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:03:26,567 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:03:26,577 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:03:26,577 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:03:26,579 INFO ]: Start difference. First operand 8 states. Second operand 3 states. [2018-06-24 21:03:26,633 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:26,633 INFO ]: Finished difference Result 11 states and 18 transitions. [2018-06-24 21:03:26,634 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:03:26,634 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-24 21:03:26,635 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:26,642 INFO ]: With dead ends: 11 [2018-06-24 21:03:26,642 INFO ]: Without dead ends: 11 [2018-06-24 21:03:26,644 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:03:26,657 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-24 21:03:26,686 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 9. [2018-06-24 21:03:26,687 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-24 21:03:26,688 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 15 transitions. [2018-06-24 21:03:26,689 INFO ]: Start accepts. Automaton has 9 states and 15 transitions. Word has length 5 [2018-06-24 21:03:26,689 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:26,689 INFO ]: Abstraction has 9 states and 15 transitions. [2018-06-24 21:03:26,689 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:03:26,689 INFO ]: Start isEmpty. Operand 9 states and 15 transitions. [2018-06-24 21:03:26,689 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-24 21:03:26,689 INFO ]: Found error trace [2018-06-24 21:03:26,690 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-24 21:03:26,690 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:26,690 INFO ]: Analyzing trace with hash 1163209379, now seen corresponding path program 1 times [2018-06-24 21:03:26,690 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:26,690 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:26,691 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:26,691 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:26,691 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:26,707 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:26,787 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:26,787 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:03:26,787 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:03:26,788 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:03:26,788 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:03:26,789 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:03:26,789 INFO ]: Start difference. First operand 9 states and 15 transitions. Second operand 3 states. [2018-06-24 21:03:26,845 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:26,845 INFO ]: Finished difference Result 8 states and 11 transitions. [2018-06-24 21:03:26,846 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:03:26,846 INFO ]: Start accepts. Automaton has 3 states. Word has length 6 [2018-06-24 21:03:26,846 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:26,846 INFO ]: With dead ends: 8 [2018-06-24 21:03:26,846 INFO ]: Without dead ends: 8 [2018-06-24 21:03:26,847 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:03:26,847 INFO ]: Start minimizeSevpa. Operand 8 states. [2018-06-24 21:03:26,848 INFO ]: Finished minimizeSevpa. Reduced states from 8 to 8. [2018-06-24 21:03:26,848 INFO ]: Start removeUnreachable. Operand 8 states. [2018-06-24 21:03:26,848 INFO ]: Finished removeUnreachable. Reduced from 8 states to 8 states and 11 transitions. [2018-06-24 21:03:26,849 INFO ]: Start accepts. Automaton has 8 states and 11 transitions. Word has length 6 [2018-06-24 21:03:26,849 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:26,849 INFO ]: Abstraction has 8 states and 11 transitions. [2018-06-24 21:03:26,849 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:03:26,849 INFO ]: Start isEmpty. Operand 8 states and 11 transitions. [2018-06-24 21:03:26,849 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-24 21:03:26,849 INFO ]: Found error trace [2018-06-24 21:03:26,849 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-24 21:03:26,849 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:26,849 INFO ]: Analyzing trace with hash 1163150758, now seen corresponding path program 1 times [2018-06-24 21:03:26,849 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:26,849 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:26,851 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:26,851 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:26,851 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:26,863 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:27,027 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:03:27,027 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:03:27,027 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-24 21:03:27,027 INFO ]: Interpolant automaton has 4 states [2018-06-24 21:03:27,027 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-24 21:03:27,027 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-24 21:03:27,027 INFO ]: Start difference. First operand 8 states and 11 transitions. Second operand 4 states. [2018-06-24 21:03:27,284 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:27,284 INFO ]: Finished difference Result 11 states and 15 transitions. [2018-06-24 21:03:27,285 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-24 21:03:27,285 INFO ]: Start accepts. Automaton has 4 states. Word has length 6 [2018-06-24 21:03:27,285 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:27,285 INFO ]: With dead ends: 11 [2018-06-24 21:03:27,285 INFO ]: Without dead ends: 11 [2018-06-24 21:03:27,285 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:03:27,286 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-24 21:03:27,287 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 9. [2018-06-24 21:03:27,287 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-24 21:03:27,287 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 12 transitions. [2018-06-24 21:03:27,287 INFO ]: Start accepts. Automaton has 9 states and 12 transitions. Word has length 6 [2018-06-24 21:03:27,287 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:27,287 INFO ]: Abstraction has 9 states and 12 transitions. [2018-06-24 21:03:27,287 INFO ]: Interpolant automaton has 4 states. [2018-06-24 21:03:27,288 INFO ]: Start isEmpty. Operand 9 states and 12 transitions. [2018-06-24 21:03:27,288 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-24 21:03:27,288 INFO ]: Found error trace [2018-06-24 21:03:27,288 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-24 21:03:27,288 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:27,288 INFO ]: Analyzing trace with hash 1163181510, now seen corresponding path program 1 times [2018-06-24 21:03:27,288 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:27,288 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:27,292 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:27,292 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:27,292 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:27,308 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:27,465 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:27,465 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:27,465 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-24 21:03:27,483 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:03:27,519 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:27,526 INFO ]: Computing forward predicates... [2018-06-24 21:03:27,547 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:27,578 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:27,578 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-24 21:03:27,579 INFO ]: Interpolant automaton has 4 states [2018-06-24 21:03:27,579 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-24 21:03:27,579 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-24 21:03:27,579 INFO ]: Start difference. First operand 9 states and 12 transitions. Second operand 4 states. [2018-06-24 21:03:27,718 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:27,718 INFO ]: Finished difference Result 9 states and 11 transitions. [2018-06-24 21:03:27,718 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-24 21:03:27,718 INFO ]: Start accepts. Automaton has 4 states. Word has length 6 [2018-06-24 21:03:27,718 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:27,719 INFO ]: With dead ends: 9 [2018-06-24 21:03:27,719 INFO ]: Without dead ends: 9 [2018-06-24 21:03:27,719 INFO ]: 0 DeclaredPredicates, 10 GetRequests, 7 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:03:27,719 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-24 21:03:27,720 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-24 21:03:27,720 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-24 21:03:27,720 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 11 transitions. [2018-06-24 21:03:27,720 INFO ]: Start accepts. Automaton has 9 states and 11 transitions. Word has length 6 [2018-06-24 21:03:27,721 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:27,721 INFO ]: Abstraction has 9 states and 11 transitions. [2018-06-24 21:03:27,721 INFO ]: Interpolant automaton has 4 states. [2018-06-24 21:03:27,721 INFO ]: Start isEmpty. Operand 9 states and 11 transitions. [2018-06-24 21:03:27,721 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-24 21:03:27,721 INFO ]: Found error trace [2018-06-24 21:03:27,721 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:27,721 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:27,721 INFO ]: Analyzing trace with hash 1697431944, now seen corresponding path program 1 times [2018-06-24 21:03:27,721 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:27,721 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:27,722 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:27,722 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:27,722 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:27,735 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:27,775 INFO ]: Checked inductivity of 1 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:27,775 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:03:27,775 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-24 21:03:27,775 INFO ]: Interpolant automaton has 4 states [2018-06-24 21:03:27,775 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-24 21:03:27,776 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-24 21:03:27,776 INFO ]: Start difference. First operand 9 states and 11 transitions. Second operand 4 states. [2018-06-24 21:03:27,818 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:27,818 INFO ]: Finished difference Result 9 states and 10 transitions. [2018-06-24 21:03:27,818 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-24 21:03:27,818 INFO ]: Start accepts. Automaton has 4 states. Word has length 7 [2018-06-24 21:03:27,818 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:27,819 INFO ]: With dead ends: 9 [2018-06-24 21:03:27,819 INFO ]: Without dead ends: 8 [2018-06-24 21:03:27,819 INFO ]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-24 21:03:27,819 INFO ]: Start minimizeSevpa. Operand 8 states. [2018-06-24 21:03:27,820 INFO ]: Finished minimizeSevpa. Reduced states from 8 to 8. [2018-06-24 21:03:27,820 INFO ]: Start removeUnreachable. Operand 8 states. [2018-06-24 21:03:27,820 INFO ]: Finished removeUnreachable. Reduced from 8 states to 8 states and 9 transitions. [2018-06-24 21:03:27,820 INFO ]: Start accepts. Automaton has 8 states and 9 transitions. Word has length 7 [2018-06-24 21:03:27,820 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:27,820 INFO ]: Abstraction has 8 states and 9 transitions. [2018-06-24 21:03:27,821 INFO ]: Interpolant automaton has 4 states. [2018-06-24 21:03:27,821 INFO ]: Start isEmpty. Operand 8 states and 9 transitions. [2018-06-24 21:03:27,821 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-24 21:03:27,821 INFO ]: Found error trace [2018-06-24 21:03:27,821 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:27,821 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:27,821 INFO ]: Analyzing trace with hash 1698653375, now seen corresponding path program 1 times [2018-06-24 21:03:27,821 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:27,821 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:27,822 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:27,822 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:27,822 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:27,836 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:27,986 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:27,986 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:27,986 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:03:27,993 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:28,023 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:28,025 INFO ]: Computing forward predicates... [2018-06-24 21:03:28,222 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:28,246 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:28,246 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-24 21:03:28,247 INFO ]: Interpolant automaton has 8 states [2018-06-24 21:03:28,247 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-24 21:03:28,247 INFO ]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-06-24 21:03:28,247 INFO ]: Start difference. First operand 8 states and 9 transitions. Second operand 8 states. [2018-06-24 21:03:28,481 WARN ]: Spent 103.00 ms on a formula simplification that was a NOOP. DAG size: 23 [2018-06-24 21:03:28,534 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:28,534 INFO ]: Finished difference Result 18 states and 24 transitions. [2018-06-24 21:03:28,534 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-24 21:03:28,534 INFO ]: Start accepts. Automaton has 8 states. Word has length 7 [2018-06-24 21:03:28,534 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:28,535 INFO ]: With dead ends: 18 [2018-06-24 21:03:28,535 INFO ]: Without dead ends: 18 [2018-06-24 21:03:28,536 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2018-06-24 21:03:28,536 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-24 21:03:28,538 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 13. [2018-06-24 21:03:28,538 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-24 21:03:28,538 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 17 transitions. [2018-06-24 21:03:28,538 INFO ]: Start accepts. Automaton has 13 states and 17 transitions. Word has length 7 [2018-06-24 21:03:28,538 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:28,538 INFO ]: Abstraction has 13 states and 17 transitions. [2018-06-24 21:03:28,538 INFO ]: Interpolant automaton has 8 states. [2018-06-24 21:03:28,538 INFO ]: Start isEmpty. Operand 13 states and 17 transitions. [2018-06-24 21:03:28,539 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-24 21:03:28,539 INFO ]: Found error trace [2018-06-24 21:03:28,539 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:28,539 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:28,539 INFO ]: Analyzing trace with hash 302218943, now seen corresponding path program 1 times [2018-06-24 21:03:28,539 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:28,539 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:28,540 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:28,540 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:28,540 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:28,552 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:28,855 INFO ]: Checked inductivity of 4 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:28,855 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:28,855 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:03:28,862 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:28,890 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:28,892 INFO ]: Computing forward predicates... [2018-06-24 21:03:28,905 INFO ]: Checked inductivity of 4 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:28,930 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:28,930 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-24 21:03:28,930 INFO ]: Interpolant automaton has 6 states [2018-06-24 21:03:28,930 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-24 21:03:28,930 INFO ]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-06-24 21:03:28,930 INFO ]: Start difference. First operand 13 states and 17 transitions. Second operand 6 states. [2018-06-24 21:03:28,961 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:28,961 INFO ]: Finished difference Result 14 states and 17 transitions. [2018-06-24 21:03:28,962 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-24 21:03:28,962 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-24 21:03:28,962 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:28,962 INFO ]: With dead ends: 14 [2018-06-24 21:03:28,962 INFO ]: Without dead ends: 12 [2018-06-24 21:03:28,963 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=21, Invalid=35, Unknown=0, NotChecked=0, Total=56 [2018-06-24 21:03:28,963 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-24 21:03:28,964 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-24 21:03:28,964 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-24 21:03:28,964 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 15 transitions. [2018-06-24 21:03:28,964 INFO ]: Start accepts. Automaton has 12 states and 15 transitions. Word has length 9 [2018-06-24 21:03:28,964 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:28,964 INFO ]: Abstraction has 12 states and 15 transitions. [2018-06-24 21:03:28,964 INFO ]: Interpolant automaton has 6 states. [2018-06-24 21:03:28,964 INFO ]: Start isEmpty. Operand 12 states and 15 transitions. [2018-06-24 21:03:28,965 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-24 21:03:28,965 INFO ]: Found error trace [2018-06-24 21:03:28,965 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:28,965 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:28,965 INFO ]: Analyzing trace with hash 340083304, now seen corresponding path program 2 times [2018-06-24 21:03:28,965 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:28,965 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:28,965 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:28,965 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:28,965 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:28,981 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:29,402 INFO ]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:29,402 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:29,402 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:03:29,410 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:03:29,447 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:03:29,447 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:29,450 INFO ]: Computing forward predicates... [2018-06-24 21:03:29,680 INFO ]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:29,711 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:29,711 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2018-06-24 21:03:29,712 INFO ]: Interpolant automaton has 12 states [2018-06-24 21:03:29,712 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-24 21:03:29,712 INFO ]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2018-06-24 21:03:29,712 INFO ]: Start difference. First operand 12 states and 15 transitions. Second operand 12 states. [2018-06-24 21:03:30,063 WARN ]: Spent 204.00 ms on a formula simplification that was a NOOP. DAG size: 50 [2018-06-24 21:03:30,083 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:30,083 INFO ]: Finished difference Result 14 states and 17 transitions. [2018-06-24 21:03:30,084 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-24 21:03:30,084 INFO ]: Start accepts. Automaton has 12 states. Word has length 9 [2018-06-24 21:03:30,085 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:30,085 INFO ]: With dead ends: 14 [2018-06-24 21:03:30,085 INFO ]: Without dead ends: 14 [2018-06-24 21:03:30,085 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.8s TimeCoverageRelationStatistics Valid=50, Invalid=132, Unknown=0, NotChecked=0, Total=182 [2018-06-24 21:03:30,085 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-24 21:03:30,087 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 11. [2018-06-24 21:03:30,087 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-24 21:03:30,087 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 12 transitions. [2018-06-24 21:03:30,087 INFO ]: Start accepts. Automaton has 11 states and 12 transitions. Word has length 9 [2018-06-24 21:03:30,087 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:30,087 INFO ]: Abstraction has 11 states and 12 transitions. [2018-06-24 21:03:30,087 INFO ]: Interpolant automaton has 12 states. [2018-06-24 21:03:30,087 INFO ]: Start isEmpty. Operand 11 states and 12 transitions. [2018-06-24 21:03:30,087 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-24 21:03:30,087 INFO ]: Found error trace [2018-06-24 21:03:30,088 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:30,088 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:30,088 INFO ]: Analyzing trace with hash 1952144646, now seen corresponding path program 3 times [2018-06-24 21:03:30,088 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:30,088 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:30,089 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:30,089 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:30,089 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:30,106 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:30,252 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:30,252 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:30,253 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:03:30,258 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:03:30,286 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2018-06-24 21:03:30,286 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:30,288 INFO ]: Computing forward predicates... [2018-06-24 21:03:30,426 INFO ]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:30,445 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:30,445 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-24 21:03:30,445 INFO ]: Interpolant automaton has 11 states [2018-06-24 21:03:30,445 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-24 21:03:30,445 INFO ]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2018-06-24 21:03:30,445 INFO ]: Start difference. First operand 11 states and 12 transitions. Second operand 11 states. [2018-06-24 21:03:30,557 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:30,557 INFO ]: Finished difference Result 17 states and 20 transitions. [2018-06-24 21:03:30,558 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-24 21:03:30,558 INFO ]: Start accepts. Automaton has 11 states. Word has length 10 [2018-06-24 21:03:30,558 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:30,558 INFO ]: With dead ends: 17 [2018-06-24 21:03:30,558 INFO ]: Without dead ends: 17 [2018-06-24 21:03:30,559 INFO ]: 0 DeclaredPredicates, 20 GetRequests, 6 SyntacticMatches, 2 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=37, Invalid=145, Unknown=0, NotChecked=0, Total=182 [2018-06-24 21:03:30,559 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-24 21:03:30,560 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 13. [2018-06-24 21:03:30,560 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-24 21:03:30,562 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 15 transitions. [2018-06-24 21:03:30,562 INFO ]: Start accepts. Automaton has 13 states and 15 transitions. Word has length 10 [2018-06-24 21:03:30,562 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:30,562 INFO ]: Abstraction has 13 states and 15 transitions. [2018-06-24 21:03:30,562 INFO ]: Interpolant automaton has 11 states. [2018-06-24 21:03:30,562 INFO ]: Start isEmpty. Operand 13 states and 15 transitions. [2018-06-24 21:03:30,562 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-24 21:03:30,562 INFO ]: Found error trace [2018-06-24 21:03:30,562 INFO ]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:30,562 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:30,563 INFO ]: Analyzing trace with hash 386438696, now seen corresponding path program 4 times [2018-06-24 21:03:30,563 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:30,563 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:30,563 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:30,563 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:30,563 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:30,574 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:30,651 INFO ]: Checked inductivity of 9 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:30,652 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:30,652 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:03:30,658 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-24 21:03:30,685 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-24 21:03:30,685 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:30,687 INFO ]: Computing forward predicates... [2018-06-24 21:03:30,698 INFO ]: Checked inductivity of 9 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:30,722 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:30,722 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-24 21:03:30,722 INFO ]: Interpolant automaton has 8 states [2018-06-24 21:03:30,722 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-24 21:03:30,722 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-24 21:03:30,722 INFO ]: Start difference. First operand 13 states and 15 transitions. Second operand 8 states. [2018-06-24 21:03:30,758 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:30,758 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-24 21:03:30,758 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-24 21:03:30,758 INFO ]: Start accepts. Automaton has 8 states. Word has length 11 [2018-06-24 21:03:30,758 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:30,758 INFO ]: With dead ends: 15 [2018-06-24 21:03:30,758 INFO ]: Without dead ends: 12 [2018-06-24 21:03:30,759 INFO ]: 0 DeclaredPredicates, 21 GetRequests, 12 SyntacticMatches, 0 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 7 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=37, Invalid=73, Unknown=0, NotChecked=0, Total=110 [2018-06-24 21:03:30,759 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-24 21:03:30,761 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-24 21:03:30,761 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-24 21:03:30,761 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 13 transitions. [2018-06-24 21:03:30,761 INFO ]: Start accepts. Automaton has 12 states and 13 transitions. Word has length 11 [2018-06-24 21:03:30,761 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:30,761 INFO ]: Abstraction has 12 states and 13 transitions. [2018-06-24 21:03:30,761 INFO ]: Interpolant automaton has 8 states. [2018-06-24 21:03:30,761 INFO ]: Start isEmpty. Operand 12 states and 13 transitions. [2018-06-24 21:03:30,761 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-24 21:03:30,761 INFO ]: Found error trace [2018-06-24 21:03:30,761 INFO ]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:30,761 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:30,762 INFO ]: Analyzing trace with hash 1560233887, now seen corresponding path program 5 times [2018-06-24 21:03:30,762 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:30,762 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:30,762 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:30,762 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:30,762 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:30,777 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:31,269 INFO ]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:31,270 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:31,303 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:03:31,310 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-24 21:03:31,329 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2018-06-24 21:03:31,329 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:31,332 INFO ]: Computing forward predicates... [2018-06-24 21:03:31,689 INFO ]: Checked inductivity of 9 backedges. 0 proven. 9 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:31,709 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:31,709 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2018-06-24 21:03:31,709 INFO ]: Interpolant automaton has 16 states [2018-06-24 21:03:31,709 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-24 21:03:31,709 INFO ]: CoverageRelationStatistics Valid=48, Invalid=192, Unknown=0, NotChecked=0, Total=240 [2018-06-24 21:03:31,709 INFO ]: Start difference. First operand 12 states and 13 transitions. Second operand 16 states. [2018-06-24 21:03:32,693 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:32,693 INFO ]: Finished difference Result 42 states and 53 transitions. [2018-06-24 21:03:32,693 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-06-24 21:03:32,693 INFO ]: Start accepts. Automaton has 16 states. Word has length 11 [2018-06-24 21:03:32,693 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:32,694 INFO ]: With dead ends: 42 [2018-06-24 21:03:32,694 INFO ]: Without dead ends: 42 [2018-06-24 21:03:32,695 INFO ]: 0 DeclaredPredicates, 38 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 264 ImplicationChecksByTransitivity, 1.4s TimeCoverageRelationStatistics Valid=278, Invalid=912, Unknown=0, NotChecked=0, Total=1190 [2018-06-24 21:03:32,695 INFO ]: Start minimizeSevpa. Operand 42 states. [2018-06-24 21:03:32,698 INFO ]: Finished minimizeSevpa. Reduced states from 42 to 18. [2018-06-24 21:03:32,698 INFO ]: Start removeUnreachable. Operand 18 states. [2018-06-24 21:03:32,698 INFO ]: Finished removeUnreachable. Reduced from 18 states to 18 states and 24 transitions. [2018-06-24 21:03:32,698 INFO ]: Start accepts. Automaton has 18 states and 24 transitions. Word has length 11 [2018-06-24 21:03:32,698 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:32,698 INFO ]: Abstraction has 18 states and 24 transitions. [2018-06-24 21:03:32,698 INFO ]: Interpolant automaton has 16 states. [2018-06-24 21:03:32,698 INFO ]: Start isEmpty. Operand 18 states and 24 transitions. [2018-06-24 21:03:32,699 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-24 21:03:32,699 INFO ]: Found error trace [2018-06-24 21:03:32,699 INFO ]: trace histogram [3, 3, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:32,699 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:32,699 INFO ]: Analyzing trace with hash 1122107055, now seen corresponding path program 6 times [2018-06-24 21:03:32,699 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:32,699 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:32,700 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:32,700 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:32,700 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:32,709 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:32,896 INFO ]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:32,896 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:32,896 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:03:32,909 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-24 21:03:32,939 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2018-06-24 21:03:32,939 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:32,942 INFO ]: Computing forward predicates... [2018-06-24 21:03:33,057 INFO ]: Checked inductivity of 12 backedges. 0 proven. 12 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:33,076 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:33,076 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2018-06-24 21:03:33,077 INFO ]: Interpolant automaton has 14 states [2018-06-24 21:03:33,077 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-24 21:03:33,077 INFO ]: CoverageRelationStatistics Valid=29, Invalid=153, Unknown=0, NotChecked=0, Total=182 [2018-06-24 21:03:33,077 INFO ]: Start difference. First operand 18 states and 24 transitions. Second operand 14 states. [2018-06-24 21:03:33,575 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:33,575 INFO ]: Finished difference Result 24 states and 31 transitions. [2018-06-24 21:03:33,575 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-24 21:03:33,575 INFO ]: Start accepts. Automaton has 14 states. Word has length 12 [2018-06-24 21:03:33,575 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:33,576 INFO ]: With dead ends: 24 [2018-06-24 21:03:33,576 INFO ]: Without dead ends: 24 [2018-06-24 21:03:33,576 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=62, Invalid=318, Unknown=0, NotChecked=0, Total=380 [2018-06-24 21:03:33,577 INFO ]: Start minimizeSevpa. Operand 24 states. [2018-06-24 21:03:33,579 INFO ]: Finished minimizeSevpa. Reduced states from 24 to 19. [2018-06-24 21:03:33,579 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-24 21:03:33,579 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 25 transitions. [2018-06-24 21:03:33,579 INFO ]: Start accepts. Automaton has 19 states and 25 transitions. Word has length 12 [2018-06-24 21:03:33,579 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:33,579 INFO ]: Abstraction has 19 states and 25 transitions. [2018-06-24 21:03:33,579 INFO ]: Interpolant automaton has 14 states. [2018-06-24 21:03:33,579 INFO ]: Start isEmpty. Operand 19 states and 25 transitions. [2018-06-24 21:03:33,580 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-24 21:03:33,580 INFO ]: Found error trace [2018-06-24 21:03:33,580 INFO ]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:33,580 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:33,580 INFO ]: Analyzing trace with hash 425077151, now seen corresponding path program 7 times [2018-06-24 21:03:33,580 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:33,580 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:33,581 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:33,581 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:33,581 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:33,592 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:33,653 INFO ]: Checked inductivity of 16 backedges. 10 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:33,653 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:33,653 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:03:33,659 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:33,689 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:33,691 INFO ]: Computing forward predicates... [2018-06-24 21:03:33,706 INFO ]: Checked inductivity of 16 backedges. 10 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:33,736 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:33,736 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 10 [2018-06-24 21:03:33,736 INFO ]: Interpolant automaton has 10 states [2018-06-24 21:03:33,737 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-24 21:03:33,737 INFO ]: CoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-06-24 21:03:33,737 INFO ]: Start difference. First operand 19 states and 25 transitions. Second operand 10 states. [2018-06-24 21:03:33,782 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:33,783 INFO ]: Finished difference Result 22 states and 27 transitions. [2018-06-24 21:03:33,783 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-24 21:03:33,783 INFO ]: Start accepts. Automaton has 10 states. Word has length 13 [2018-06-24 21:03:33,783 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:33,783 INFO ]: With dead ends: 22 [2018-06-24 21:03:33,783 INFO ]: Without dead ends: 18 [2018-06-24 21:03:33,783 INFO ]: 0 DeclaredPredicates, 26 GetRequests, 14 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 15 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=57, Invalid=125, Unknown=0, NotChecked=0, Total=182 [2018-06-24 21:03:33,783 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-24 21:03:33,785 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 18. [2018-06-24 21:03:33,785 INFO ]: Start removeUnreachable. Operand 18 states. [2018-06-24 21:03:33,785 INFO ]: Finished removeUnreachable. Reduced from 18 states to 18 states and 23 transitions. [2018-06-24 21:03:33,785 INFO ]: Start accepts. Automaton has 18 states and 23 transitions. Word has length 13 [2018-06-24 21:03:33,785 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:33,785 INFO ]: Abstraction has 18 states and 23 transitions. [2018-06-24 21:03:33,785 INFO ]: Interpolant automaton has 10 states. [2018-06-24 21:03:33,785 INFO ]: Start isEmpty. Operand 18 states and 23 transitions. [2018-06-24 21:03:33,786 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-24 21:03:33,786 INFO ]: Found error trace [2018-06-24 21:03:33,786 INFO ]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:33,786 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:33,786 INFO ]: Analyzing trace with hash -1841977592, now seen corresponding path program 8 times [2018-06-24 21:03:33,786 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:33,786 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:33,787 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:33,787 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:33,787 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:33,799 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:33,989 INFO ]: Checked inductivity of 16 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:33,989 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:33,989 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:03:33,995 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:03:34,015 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:03:34,015 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:34,019 INFO ]: Computing forward predicates... [2018-06-24 21:03:35,030 INFO ]: Checked inductivity of 16 backedges. 0 proven. 16 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:35,050 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:35,050 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 20 [2018-06-24 21:03:35,050 INFO ]: Interpolant automaton has 20 states [2018-06-24 21:03:35,050 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-24 21:03:35,051 INFO ]: CoverageRelationStatistics Valid=66, Invalid=312, Unknown=2, NotChecked=0, Total=380 [2018-06-24 21:03:35,051 INFO ]: Start difference. First operand 18 states and 23 transitions. Second operand 20 states. [2018-06-24 21:03:36,772 WARN ]: Spent 1.64 s on a formula simplification that was a NOOP. DAG size: 43 [2018-06-24 21:03:37,213 WARN ]: Spent 355.00 ms on a formula simplification that was a NOOP. DAG size: 41 [2018-06-24 21:03:38,550 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:38,550 INFO ]: Finished difference Result 55 states and 68 transitions. [2018-06-24 21:03:38,550 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-06-24 21:03:38,550 INFO ]: Start accepts. Automaton has 20 states. Word has length 13 [2018-06-24 21:03:38,550 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:38,551 INFO ]: With dead ends: 55 [2018-06-24 21:03:38,551 INFO ]: Without dead ends: 55 [2018-06-24 21:03:38,552 INFO ]: 0 DeclaredPredicates, 58 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 838 ImplicationChecksByTransitivity, 4.2s TimeCoverageRelationStatistics Valid=584, Invalid=2384, Unknown=2, NotChecked=0, Total=2970 [2018-06-24 21:03:38,552 INFO ]: Start minimizeSevpa. Operand 55 states. [2018-06-24 21:03:38,555 INFO ]: Finished minimizeSevpa. Reduced states from 55 to 21. [2018-06-24 21:03:38,555 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-24 21:03:38,555 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 28 transitions. [2018-06-24 21:03:38,555 INFO ]: Start accepts. Automaton has 21 states and 28 transitions. Word has length 13 [2018-06-24 21:03:38,556 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:38,556 INFO ]: Abstraction has 21 states and 28 transitions. [2018-06-24 21:03:38,556 INFO ]: Interpolant automaton has 20 states. [2018-06-24 21:03:38,556 INFO ]: Start isEmpty. Operand 21 states and 28 transitions. [2018-06-24 21:03:38,556 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-24 21:03:38,556 INFO ]: Found error trace [2018-06-24 21:03:38,556 INFO ]: trace histogram [4, 4, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:38,556 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:38,556 INFO ]: Analyzing trace with hash -1267233690, now seen corresponding path program 9 times [2018-06-24 21:03:38,556 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:38,556 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:38,557 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:38,557 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:38,557 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:38,567 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:38,725 INFO ]: Checked inductivity of 20 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:38,725 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:38,725 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:03:38,730 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:03:38,773 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-24 21:03:38,773 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:38,777 INFO ]: Computing forward predicates... [2018-06-24 21:03:38,892 INFO ]: Checked inductivity of 20 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:38,910 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:38,910 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 17 [2018-06-24 21:03:38,911 INFO ]: Interpolant automaton has 17 states [2018-06-24 21:03:38,911 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-24 21:03:38,911 INFO ]: CoverageRelationStatistics Valid=36, Invalid=236, Unknown=0, NotChecked=0, Total=272 [2018-06-24 21:03:38,911 INFO ]: Start difference. First operand 21 states and 28 transitions. Second operand 17 states. [2018-06-24 21:03:39,149 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:39,149 INFO ]: Finished difference Result 28 states and 36 transitions. [2018-06-24 21:03:39,149 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-24 21:03:39,149 INFO ]: Start accepts. Automaton has 17 states. Word has length 14 [2018-06-24 21:03:39,149 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:39,149 INFO ]: With dead ends: 28 [2018-06-24 21:03:39,150 INFO ]: Without dead ends: 28 [2018-06-24 21:03:39,150 INFO ]: 0 DeclaredPredicates, 32 GetRequests, 8 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=77, Invalid=475, Unknown=0, NotChecked=0, Total=552 [2018-06-24 21:03:39,150 INFO ]: Start minimizeSevpa. Operand 28 states. [2018-06-24 21:03:39,152 INFO ]: Finished minimizeSevpa. Reduced states from 28 to 22. [2018-06-24 21:03:39,152 INFO ]: Start removeUnreachable. Operand 22 states. [2018-06-24 21:03:39,152 INFO ]: Finished removeUnreachable. Reduced from 22 states to 22 states and 29 transitions. [2018-06-24 21:03:39,153 INFO ]: Start accepts. Automaton has 22 states and 29 transitions. Word has length 14 [2018-06-24 21:03:39,153 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:39,153 INFO ]: Abstraction has 22 states and 29 transitions. [2018-06-24 21:03:39,153 INFO ]: Interpolant automaton has 17 states. [2018-06-24 21:03:39,153 INFO ]: Start isEmpty. Operand 22 states and 29 transitions. [2018-06-24 21:03:39,153 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-24 21:03:39,153 INFO ]: Found error trace [2018-06-24 21:03:39,153 INFO ]: trace histogram [5, 4, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:39,153 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:39,153 INFO ]: Analyzing trace with hash -630041912, now seen corresponding path program 10 times [2018-06-24 21:03:39,153 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:39,153 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:39,154 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:39,154 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:39,154 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:39,164 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:39,318 INFO ]: Checked inductivity of 25 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:39,318 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:39,318 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-24 21:03:39,331 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:03:39,350 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-24 21:03:39,350 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:39,352 INFO ]: Computing forward predicates... [2018-06-24 21:03:39,362 INFO ]: Checked inductivity of 25 backedges. 15 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:39,383 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:39,383 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 12 [2018-06-24 21:03:39,383 INFO ]: Interpolant automaton has 12 states [2018-06-24 21:03:39,383 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-24 21:03:39,383 INFO ]: CoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2018-06-24 21:03:39,383 INFO ]: Start difference. First operand 22 states and 29 transitions. Second operand 12 states. [2018-06-24 21:03:39,437 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:39,437 INFO ]: Finished difference Result 26 states and 32 transitions. [2018-06-24 21:03:39,437 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-24 21:03:39,437 INFO ]: Start accepts. Automaton has 12 states. Word has length 15 [2018-06-24 21:03:39,437 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:39,438 INFO ]: With dead ends: 26 [2018-06-24 21:03:39,438 INFO ]: Without dead ends: 21 [2018-06-24 21:03:39,438 INFO ]: 0 DeclaredPredicates, 31 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 26 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=81, Invalid=191, Unknown=0, NotChecked=0, Total=272 [2018-06-24 21:03:39,438 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-24 21:03:39,439 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-24 21:03:39,439 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-24 21:03:39,440 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 27 transitions. [2018-06-24 21:03:39,440 INFO ]: Start accepts. Automaton has 21 states and 27 transitions. Word has length 15 [2018-06-24 21:03:39,440 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:39,440 INFO ]: Abstraction has 21 states and 27 transitions. [2018-06-24 21:03:39,440 INFO ]: Interpolant automaton has 12 states. [2018-06-24 21:03:39,440 INFO ]: Start isEmpty. Operand 21 states and 27 transitions. [2018-06-24 21:03:39,440 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-24 21:03:39,440 INFO ]: Found error trace [2018-06-24 21:03:39,440 INFO ]: trace histogram [5, 4, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:39,440 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:39,440 INFO ]: Analyzing trace with hash 2105705087, now seen corresponding path program 11 times [2018-06-24 21:03:39,440 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:39,440 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:39,441 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:39,441 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:39,441 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:39,454 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:39,701 INFO ]: Checked inductivity of 25 backedges. 0 proven. 25 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:39,701 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:39,701 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 15 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:03:39,707 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-24 21:03:39,748 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-24 21:03:39,748 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:39,754 INFO ]: Computing forward predicates... [2018-06-24 21:03:51,978 INFO ]: Checked inductivity of 25 backedges. 1 proven. 24 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-24 21:03:51,997 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:51,997 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 24 [2018-06-24 21:03:51,997 INFO ]: Interpolant automaton has 24 states [2018-06-24 21:03:51,997 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-24 21:03:51,998 INFO ]: CoverageRelationStatistics Valid=85, Invalid=460, Unknown=7, NotChecked=0, Total=552 [2018-06-24 21:03:51,998 INFO ]: Start difference. First operand 21 states and 27 transitions. Second operand 24 states. [2018-06-24 21:03:57,869 WARN ]: Spent 252.00 ms on a formula simplification that was a NOOP. DAG size: 44 [2018-06-24 21:04:09,997 WARN ]: Spent 6.08 s on a formula simplification that was a NOOP. DAG size: 74 [2018-06-24 21:04:30,789 WARN ]: Spent 16.65 s on a formula simplification that was a NOOP. DAG size: 92 [2018-06-24 21:04:42,992 WARN ]: Spent 8.23 s on a formula simplification that was a NOOP. DAG size: 76 Received shutdown request... [2018-06-24 21:04:45,018 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-24 21:04:45,018 WARN ]: Verification canceled [2018-06-24 21:04:45,020 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-24 21:04:45,021 WARN ]: Timeout [2018-06-24 21:04:45,021 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.06 09:04:45 BasicIcfg [2018-06-24 21:04:45,021 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-24 21:04:45,023 INFO ]: Toolchain (without parser) took 79279.72 ms. Allocated memory was 304.6 MB in the beginning and 406.3 MB in the end (delta: 101.7 MB). Free memory was 259.0 MB in the beginning and 195.3 MB in the end (delta: 63.7 MB). Peak memory consumption was 165.4 MB. Max. memory is 3.6 GB. [2018-06-24 21:04:45,023 INFO ]: SmtParser took 0.06 ms. Allocated memory is still 304.6 MB. Free memory is still 269.1 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-24 21:04:45,024 INFO ]: ChcToBoogie took 55.89 ms. Allocated memory is still 304.6 MB. Free memory was 259.0 MB in the beginning and 257.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-24 21:04:45,024 INFO ]: Boogie Preprocessor took 36.07 ms. Allocated memory is still 304.6 MB. Free memory is still 257.0 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-24 21:04:45,024 INFO ]: RCFGBuilder took 302.59 ms. Allocated memory is still 304.6 MB. Free memory was 257.0 MB in the beginning and 247.0 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. [2018-06-24 21:04:45,025 INFO ]: BlockEncodingV2 took 88.22 ms. Allocated memory is still 304.6 MB. Free memory was 247.0 MB in the beginning and 245.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-24 21:04:45,025 INFO ]: TraceAbstraction took 78782.23 ms. Allocated memory was 304.6 MB in the beginning and 406.3 MB in the end (delta: 101.7 MB). Free memory was 245.0 MB in the beginning and 195.3 MB in the end (delta: 49.7 MB). Peak memory consumption was 151.5 MB. Max. memory is 3.6 GB. [2018-06-24 21:04:45,029 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.plugins.blockencoding: - StatisticsResult: Initial Icfg 12 locations, 19 edges - StatisticsResult: Encoded RCFG 8 locations, 12 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.06 ms. Allocated memory is still 304.6 MB. Free memory is still 269.1 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 55.89 ms. Allocated memory is still 304.6 MB. Free memory was 259.0 MB in the beginning and 257.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 36.07 ms. Allocated memory is still 304.6 MB. Free memory is still 257.0 MB. There was no memory consumed. Max. memory is 3.6 GB. * RCFGBuilder took 302.59 ms. Allocated memory is still 304.6 MB. Free memory was 257.0 MB in the beginning and 247.0 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 88.22 ms. Allocated memory is still 304.6 MB. Free memory was 247.0 MB in the beginning and 245.0 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 78782.23 ms. Allocated memory was 304.6 MB in the beginning and 406.3 MB in the end (delta: 101.7 MB). Free memory was 245.0 MB in the beginning and 195.3 MB in the end (delta: 49.7 MB). Peak memory consumption was 151.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 constructing difference of abstraction (21states) and interpolant automaton (currently 12 states, 24 states before enhancement), while PredicateComparison was comparing new predicate (quantified with 0quantifier alternations) to 28 known predicates. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 8 locations, 1 error locations. TIMEOUT Result, 78.7s OverallTime, 17 OverallIterations, 5 TraceHistogramMax, 59.7s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 91 SDtfs, 155 SDslu, 417 SDs, 0 SdLazy, 795 SolverSat, 276 SolverUnsat, 3 SolverUnknown, 0 SolverNotchecked, 5.2s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 359 GetRequests, 113 SyntacticMatches, 6 SemanticMatches, 239 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1361 ImplicationChecksByTransitivity, 69.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=22occurred in iteration=15, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 16 MinimizatonAttempts, 85 StatesRemovedByMinimization, 9 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.0s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 17.6s InterpolantComputationTime, 314 NumberOfCodeBlocks, 314 NumberOfCodeBlocksAsserted, 42 NumberOfCheckSat, 284 ConstructedInterpolants, 16 QuantifiedInterpolants, 31557 SizeOfPredicates, 51 NumberOfNonLiveVariables, 1568 ConjunctsInSsa, 831 ConjunctsInUnsatCore, 30 InterpolantComputations, 4 PerfectInterpolantSequences, 70/297 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/012-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-24_21-04-45-042.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/012-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-24_21-04-45-042.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/012-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-24_21-04-45-042.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/012-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-24_21-04-45-042.csv Completed graceful shutdown