java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC_wBE.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/hopv/lia/termination/Ackermann02.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-62c3406-m [2018-06-26 18:27:25,563 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-26 18:27:25,565 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-26 18:27:25,577 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-26 18:27:25,577 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-26 18:27:25,578 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-26 18:27:25,579 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-26 18:27:25,585 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-26 18:27:25,587 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-26 18:27:25,588 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-26 18:27:25,588 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-26 18:27:25,589 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-26 18:27:25,589 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-26 18:27:25,590 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-26 18:27:25,591 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-26 18:27:25,594 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-26 18:27:25,595 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-26 18:27:25,596 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-26 18:27:25,606 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-26 18:27:25,607 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-26 18:27:25,608 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-26 18:27:25,609 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-26 18:27:25,611 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-26 18:27:25,611 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-26 18:27:25,611 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-26 18:27:25,614 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-26 18:27:25,615 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-26 18:27:25,615 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-26 18:27:25,616 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-26 18:27:25,619 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-26 18:27:25,620 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-26 18:27:25,620 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-26 18:27:25,620 INFO L177 SettingsManager]: ReqParser provides no preferences, ignoring... [2018-06-26 18:27:25,621 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-26 18:27:25,621 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-26 18:27:25,622 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-26 18:27:25,622 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-26 18:27:25,643 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-26 18:27:25,643 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-26 18:27:25,644 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-26 18:27:25,644 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-26 18:27:25,645 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-26 18:27:25,645 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-26 18:27:25,645 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-26 18:27:25,645 INFO L133 SettingsManager]: * Use SBE=true [2018-06-26 18:27:25,646 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-26 18:27:25,646 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-26 18:27:25,646 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-26 18:27:25,646 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-26 18:27:25,646 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 18:27:25,646 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-26 18:27:25,647 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-26 18:27:25,647 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-26 18:27:25,647 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-26 18:27:25,647 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-26 18:27:25,647 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-26 18:27:25,647 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-26 18:27:25,648 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-26 18:27:25,649 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-26 18:27:25,649 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-26 18:27:25,696 INFO ]: Repository-Root is: /tmp [2018-06-26 18:27:25,709 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-26 18:27:25,713 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-26 18:27:25,714 INFO ]: Initializing SmtParser... [2018-06-26 18:27:25,714 INFO ]: SmtParser initialized [2018-06-26 18:27:25,715 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/hopv/lia/termination/Ackermann02.smt2 [2018-06-26 18:27:25,716 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-26 18:27:25,807 INFO ]: Executing SMT file /storage/chc-comp/hopv/lia/termination/Ackermann02.smt2 unknown [2018-06-26 18:27:26,307 INFO ]: Succesfully executed SMT file /storage/chc-comp/hopv/lia/termination/Ackermann02.smt2 [2018-06-26 18:27:26,312 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-26 18:27:26,327 INFO ]: Walking toolchain with 5 elements. [2018-06-26 18:27:26,327 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-26 18:27:26,327 INFO ]: Initializing ChcToBoogie... [2018-06-26 18:27:26,327 INFO ]: ChcToBoogie initialized [2018-06-26 18:27:26,339 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 06:27:26" (1/1) ... [2018-06-26 18:27:26,434 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:27:26 Unit [2018-06-26 18:27:26,434 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-26 18:27:26,435 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-26 18:27:26,435 INFO ]: Initializing Boogie Preprocessor... [2018-06-26 18:27:26,435 INFO ]: Boogie Preprocessor initialized [2018-06-26 18:27:26,479 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:27:26" (1/1) ... [2018-06-26 18:27:26,479 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:27:26" (1/1) ... [2018-06-26 18:27:26,496 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:27:26" (1/1) ... [2018-06-26 18:27:26,496 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:27:26" (1/1) ... [2018-06-26 18:27:26,511 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:27:26" (1/1) ... [2018-06-26 18:27:26,514 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:27:26" (1/1) ... [2018-06-26 18:27:26,516 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:27:26" (1/1) ... [2018-06-26 18:27:26,519 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-26 18:27:26,520 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-26 18:27:26,520 INFO ]: Initializing RCFGBuilder... [2018-06-26 18:27:26,520 INFO ]: RCFGBuilder initialized [2018-06-26 18:27:26,521 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:27:26" (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) Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-26 18:27:26,537 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-26 18:27:26,537 INFO ]: Found specification of procedure gotoProc [2018-06-26 18:27:26,537 INFO ]: Found implementation of procedure gotoProc [2018-06-26 18:27:26,537 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-26 18:27:26,537 INFO ]: Found specification of procedure Ultimate.START [2018-06-26 18:27:26,537 INFO ]: Found implementation of procedure Ultimate.START [2018-06-26 18:27:27,225 INFO ]: Using library mode [2018-06-26 18:27:27,225 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 06:27:27 BoogieIcfgContainer [2018-06-26 18:27:27,225 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-26 18:27:27,226 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-26 18:27:27,227 INFO ]: Initializing BlockEncodingV2... [2018-06-26 18:27:27,228 INFO ]: BlockEncodingV2 initialized [2018-06-26 18:27:27,228 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 06:27:27" (1/1) ... [2018-06-26 18:27:27,256 INFO ]: Initial Icfg 48 locations, 77 edges [2018-06-26 18:27:27,257 INFO ]: Using Remove infeasible edges [2018-06-26 18:27:27,258 INFO ]: Using Maximize final states [2018-06-26 18:27:27,258 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-26 18:27:27,259 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-26 18:27:27,262 INFO ]: Using Remove sink states [2018-06-26 18:27:27,263 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-26 18:27:27,263 INFO ]: Using Use SBE [2018-06-26 18:27:27,326 INFO ]: SBE split 3 edges [2018-06-26 18:27:27,331 INFO ]: Removed 4 edges and 2 locations because of local infeasibility [2018-06-26 18:27:27,333 INFO ]: 0 new accepting states [2018-06-26 18:27:27,929 INFO ]: Removed 51 edges and 13 locations by large block encoding [2018-06-26 18:27:27,931 INFO ]: Removed 1 edges and 1 locations by removing sink states [2018-06-26 18:27:27,933 INFO ]: Removed 3 edges and 0 locations because of local infeasibility [2018-06-26 18:27:27,933 INFO ]: 0 new accepting states [2018-06-26 18:27:27,934 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-26 18:27:27,934 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 18:27:27,935 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-26 18:27:27,935 INFO ]: 0 new accepting states [2018-06-26 18:27:27,935 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-26 18:27:27,936 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-26 18:27:27,936 INFO ]: Encoded RCFG 32 locations, 62 edges [2018-06-26 18:27:27,937 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 06:27:27 BasicIcfg [2018-06-26 18:27:27,937 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-26 18:27:27,939 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-26 18:27:27,939 INFO ]: Initializing TraceAbstraction... [2018-06-26 18:27:27,942 INFO ]: TraceAbstraction initialized [2018-06-26 18:27:27,942 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 26.06 06:27:26" (1/4) ... [2018-06-26 18:27:27,943 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b35c2c1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 26.06 06:27:27, skipping insertion in model container [2018-06-26 18:27:27,943 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 26.06 06:27:26" (2/4) ... [2018-06-26 18:27:27,943 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b35c2c1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 26.06 06:27:27, skipping insertion in model container [2018-06-26 18:27:27,943 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 26.06 06:27:27" (3/4) ... [2018-06-26 18:27:27,943 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@7b35c2c1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 06:27:27, skipping insertion in model container [2018-06-26 18:27:27,943 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 26.06 06:27:27" (4/4) ... [2018-06-26 18:27:27,945 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-26 18:27:27,960 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-26 18:27:27,973 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-26 18:27:28,020 INFO ]: Using default assertion order modulation [2018-06-26 18:27:28,021 INFO ]: Interprodecural is true [2018-06-26 18:27:28,021 INFO ]: Hoare is false [2018-06-26 18:27:28,021 INFO ]: Compute interpolants for FPandBP [2018-06-26 18:27:28,021 INFO ]: Backedges is TWOTRACK [2018-06-26 18:27:28,021 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-26 18:27:28,021 INFO ]: Difference is false [2018-06-26 18:27:28,021 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-26 18:27:28,021 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-26 18:27:28,036 INFO ]: Start isEmpty. Operand 32 states. [2018-06-26 18:27:28,050 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-26 18:27:28,050 INFO ]: Found error trace [2018-06-26 18:27:28,051 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-26 18:27:28,052 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:27:28,056 INFO ]: Analyzing trace with hash 43341403, now seen corresponding path program 1 times [2018-06-26 18:27:28,057 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:27:28,057 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:27:28,090 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:28,090 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:28,090 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:28,166 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:28,308 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:27:28,310 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:27:28,310 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 18:27:28,312 INFO ]: Interpolant automaton has 3 states [2018-06-26 18:27:28,326 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 18:27:28,326 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:27:28,329 INFO ]: Start difference. First operand 32 states. Second operand 3 states. [2018-06-26 18:27:28,821 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:27:28,821 INFO ]: Finished difference Result 46 states and 88 transitions. [2018-06-26 18:27:28,821 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 18:27:28,823 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-26 18:27:28,823 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:27:28,845 INFO ]: With dead ends: 46 [2018-06-26 18:27:28,845 INFO ]: Without dead ends: 45 [2018-06-26 18:27:28,846 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:27:28,864 INFO ]: Start minimizeSevpa. Operand 45 states. [2018-06-26 18:27:28,899 INFO ]: Finished minimizeSevpa. Reduced states from 45 to 32. [2018-06-26 18:27:28,900 INFO ]: Start removeUnreachable. Operand 32 states. [2018-06-26 18:27:28,902 INFO ]: Finished removeUnreachable. Reduced from 32 states to 32 states and 62 transitions. [2018-06-26 18:27:28,903 INFO ]: Start accepts. Automaton has 32 states and 62 transitions. Word has length 5 [2018-06-26 18:27:28,903 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:27:28,903 INFO ]: Abstraction has 32 states and 62 transitions. [2018-06-26 18:27:28,903 INFO ]: Interpolant automaton has 3 states. [2018-06-26 18:27:28,903 INFO ]: Start isEmpty. Operand 32 states and 62 transitions. [2018-06-26 18:27:28,905 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-26 18:27:28,905 INFO ]: Found error trace [2018-06-26 18:27:28,905 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-26 18:27:28,905 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:27:28,906 INFO ]: Analyzing trace with hash 43400985, now seen corresponding path program 1 times [2018-06-26 18:27:28,906 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:27:28,906 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:27:28,907 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:28,907 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:28,907 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:28,931 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:29,011 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-26 18:27:29,011 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:27:29,011 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 18:27:29,013 INFO ]: Interpolant automaton has 3 states [2018-06-26 18:27:29,013 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 18:27:29,013 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:27:29,013 INFO ]: Start difference. First operand 32 states and 62 transitions. Second operand 3 states. [2018-06-26 18:27:29,776 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:27:29,777 INFO ]: Finished difference Result 49 states and 99 transitions. [2018-06-26 18:27:29,777 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 18:27:29,777 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-26 18:27:29,777 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:27:29,780 INFO ]: With dead ends: 49 [2018-06-26 18:27:29,780 INFO ]: Without dead ends: 49 [2018-06-26 18:27:29,781 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:27:29,781 INFO ]: Start minimizeSevpa. Operand 49 states. [2018-06-26 18:27:29,794 INFO ]: Finished minimizeSevpa. Reduced states from 49 to 49. [2018-06-26 18:27:29,794 INFO ]: Start removeUnreachable. Operand 49 states. [2018-06-26 18:27:29,798 INFO ]: Finished removeUnreachable. Reduced from 49 states to 49 states and 99 transitions. [2018-06-26 18:27:29,798 INFO ]: Start accepts. Automaton has 49 states and 99 transitions. Word has length 5 [2018-06-26 18:27:29,798 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:27:29,798 INFO ]: Abstraction has 49 states and 99 transitions. [2018-06-26 18:27:29,798 INFO ]: Interpolant automaton has 3 states. [2018-06-26 18:27:29,798 INFO ]: Start isEmpty. Operand 49 states and 99 transitions. [2018-06-26 18:27:29,805 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-26 18:27:29,805 INFO ]: Found error trace [2018-06-26 18:27:29,805 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:27:29,805 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:27:29,805 INFO ]: Analyzing trace with hash -1590547262, now seen corresponding path program 1 times [2018-06-26 18:27:29,805 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:27:29,805 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:27:29,806 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:29,806 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:29,806 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:29,855 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:29,909 INFO ]: Checked inductivity of 5 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:27:29,909 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:27:29,909 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 18:27:29,909 INFO ]: Interpolant automaton has 3 states [2018-06-26 18:27:29,909 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 18:27:29,909 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:27:29,910 INFO ]: Start difference. First operand 49 states and 99 transitions. Second operand 3 states. [2018-06-26 18:27:30,335 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:27:30,335 INFO ]: Finished difference Result 66 states and 126 transitions. [2018-06-26 18:27:30,336 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 18:27:30,336 INFO ]: Start accepts. Automaton has 3 states. Word has length 11 [2018-06-26 18:27:30,336 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:27:30,339 INFO ]: With dead ends: 66 [2018-06-26 18:27:30,339 INFO ]: Without dead ends: 66 [2018-06-26 18:27:30,339 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:27:30,340 INFO ]: Start minimizeSevpa. Operand 66 states. [2018-06-26 18:27:30,349 INFO ]: Finished minimizeSevpa. Reduced states from 66 to 66. [2018-06-26 18:27:30,349 INFO ]: Start removeUnreachable. Operand 66 states. [2018-06-26 18:27:30,353 INFO ]: Finished removeUnreachable. Reduced from 66 states to 66 states and 126 transitions. [2018-06-26 18:27:30,353 INFO ]: Start accepts. Automaton has 66 states and 126 transitions. Word has length 11 [2018-06-26 18:27:30,353 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:27:30,353 INFO ]: Abstraction has 66 states and 126 transitions. [2018-06-26 18:27:30,353 INFO ]: Interpolant automaton has 3 states. [2018-06-26 18:27:30,353 INFO ]: Start isEmpty. Operand 66 states and 126 transitions. [2018-06-26 18:27:30,357 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-26 18:27:30,357 INFO ]: Found error trace [2018-06-26 18:27:30,357 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:27:30,357 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:27:30,357 INFO ]: Analyzing trace with hash -243193227, now seen corresponding path program 1 times [2018-06-26 18:27:30,357 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:27:30,357 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:27:30,358 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:30,358 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:30,358 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:30,389 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:30,466 INFO ]: Checked inductivity of 5 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:27:30,466 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:27:30,466 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 18:27:30,466 INFO ]: Interpolant automaton has 3 states [2018-06-26 18:27:30,466 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 18:27:30,466 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:27:30,467 INFO ]: Start difference. First operand 66 states and 126 transitions. Second operand 3 states. [2018-06-26 18:27:30,802 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:27:30,802 INFO ]: Finished difference Result 87 states and 171 transitions. [2018-06-26 18:27:30,802 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 18:27:30,803 INFO ]: Start accepts. Automaton has 3 states. Word has length 11 [2018-06-26 18:27:30,803 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:27:30,806 INFO ]: With dead ends: 87 [2018-06-26 18:27:30,806 INFO ]: Without dead ends: 87 [2018-06-26 18:27:30,806 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:27:30,806 INFO ]: Start minimizeSevpa. Operand 87 states. [2018-06-26 18:27:30,826 INFO ]: Finished minimizeSevpa. Reduced states from 87 to 87. [2018-06-26 18:27:30,826 INFO ]: Start removeUnreachable. Operand 87 states. [2018-06-26 18:27:30,833 INFO ]: Finished removeUnreachable. Reduced from 87 states to 87 states and 171 transitions. [2018-06-26 18:27:30,833 INFO ]: Start accepts. Automaton has 87 states and 171 transitions. Word has length 11 [2018-06-26 18:27:30,833 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:27:30,833 INFO ]: Abstraction has 87 states and 171 transitions. [2018-06-26 18:27:30,833 INFO ]: Interpolant automaton has 3 states. [2018-06-26 18:27:30,833 INFO ]: Start isEmpty. Operand 87 states and 171 transitions. [2018-06-26 18:27:30,837 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-26 18:27:30,837 INFO ]: Found error trace [2018-06-26 18:27:30,837 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:27:30,837 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:27:30,837 INFO ]: Analyzing trace with hash 391828563, now seen corresponding path program 1 times [2018-06-26 18:27:30,837 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:27:30,837 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:27:30,838 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:30,838 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:30,838 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:30,905 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:31,197 WARN ]: Spent 107.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 13 [2018-06-26 18:27:31,206 INFO ]: Checked inductivity of 5 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:27:31,207 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:27:31,207 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:27:31,216 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:31,282 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:31,289 INFO ]: Computing forward predicates... [2018-06-26 18:27:31,410 INFO ]: Checked inductivity of 5 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2018-06-26 18:27:31,445 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:27:31,445 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 5] total 7 [2018-06-26 18:27:31,446 INFO ]: Interpolant automaton has 7 states [2018-06-26 18:27:31,446 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-26 18:27:31,446 INFO ]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2018-06-26 18:27:31,446 INFO ]: Start difference. First operand 87 states and 171 transitions. Second operand 7 states. [2018-06-26 18:27:33,209 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:27:33,209 INFO ]: Finished difference Result 288 states and 655 transitions. [2018-06-26 18:27:33,209 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-26 18:27:33,209 INFO ]: Start accepts. Automaton has 7 states. Word has length 12 [2018-06-26 18:27:33,209 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:27:33,227 INFO ]: With dead ends: 288 [2018-06-26 18:27:33,227 INFO ]: Without dead ends: 259 [2018-06-26 18:27:33,228 INFO ]: 0 DeclaredPredicates, 22 GetRequests, 10 SyntacticMatches, 2 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 14 ImplicationChecksByTransitivity, 0.4s TimeCoverageRelationStatistics Valid=42, Invalid=90, Unknown=0, NotChecked=0, Total=132 [2018-06-26 18:27:33,228 INFO ]: Start minimizeSevpa. Operand 259 states. [2018-06-26 18:27:33,279 INFO ]: Finished minimizeSevpa. Reduced states from 259 to 115. [2018-06-26 18:27:33,279 INFO ]: Start removeUnreachable. Operand 115 states. [2018-06-26 18:27:33,282 INFO ]: Finished removeUnreachable. Reduced from 115 states to 115 states and 238 transitions. [2018-06-26 18:27:33,283 INFO ]: Start accepts. Automaton has 115 states and 238 transitions. Word has length 12 [2018-06-26 18:27:33,283 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:27:33,283 INFO ]: Abstraction has 115 states and 238 transitions. [2018-06-26 18:27:33,283 INFO ]: Interpolant automaton has 7 states. [2018-06-26 18:27:33,283 INFO ]: Start isEmpty. Operand 115 states and 238 transitions. [2018-06-26 18:27:33,289 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-26 18:27:33,289 INFO ]: Found error trace [2018-06-26 18:27:33,289 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:27:33,289 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:27:33,290 INFO ]: Analyzing trace with hash -1855195911, now seen corresponding path program 1 times [2018-06-26 18:27:33,290 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:27:33,290 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:27:33,290 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:33,290 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:33,290 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:33,305 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:33,399 INFO ]: Checked inductivity of 12 backedges. 5 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-06-26 18:27:33,399 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:27:33,399 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-26 18:27:33,399 INFO ]: Interpolant automaton has 4 states [2018-06-26 18:27:33,400 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-26 18:27:33,400 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-26 18:27:33,400 INFO ]: Start difference. First operand 115 states and 238 transitions. Second operand 4 states. [2018-06-26 18:27:33,518 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:27:33,518 INFO ]: Finished difference Result 149 states and 382 transitions. [2018-06-26 18:27:33,520 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-26 18:27:33,520 INFO ]: Start accepts. Automaton has 4 states. Word has length 17 [2018-06-26 18:27:33,520 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:27:33,526 INFO ]: With dead ends: 149 [2018-06-26 18:27:33,526 INFO ]: Without dead ends: 149 [2018-06-26 18:27:33,526 INFO ]: 0 DeclaredPredicates, 6 GetRequests, 3 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-26 18:27:33,526 INFO ]: Start minimizeSevpa. Operand 149 states. [2018-06-26 18:27:33,549 INFO ]: Finished minimizeSevpa. Reduced states from 149 to 108. [2018-06-26 18:27:33,549 INFO ]: Start removeUnreachable. Operand 108 states. [2018-06-26 18:27:33,551 INFO ]: Finished removeUnreachable. Reduced from 108 states to 108 states and 226 transitions. [2018-06-26 18:27:33,551 INFO ]: Start accepts. Automaton has 108 states and 226 transitions. Word has length 17 [2018-06-26 18:27:33,551 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:27:33,551 INFO ]: Abstraction has 108 states and 226 transitions. [2018-06-26 18:27:33,551 INFO ]: Interpolant automaton has 4 states. [2018-06-26 18:27:33,552 INFO ]: Start isEmpty. Operand 108 states and 226 transitions. [2018-06-26 18:27:33,556 INFO ]: Finished isEmpty. Found accepting run of length 18 [2018-06-26 18:27:33,556 INFO ]: Found error trace [2018-06-26 18:27:33,556 INFO ]: trace histogram [3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:27:33,556 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:27:33,557 INFO ]: Analyzing trace with hash 758983570, now seen corresponding path program 1 times [2018-06-26 18:27:33,557 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:27:33,557 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:27:33,557 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:33,557 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:33,557 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:33,576 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:33,649 INFO ]: Checked inductivity of 12 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2018-06-26 18:27:33,649 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:27:33,650 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-26 18:27:33,650 INFO ]: Interpolant automaton has 3 states [2018-06-26 18:27:33,650 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-26 18:27:33,650 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:27:33,650 INFO ]: Start difference. First operand 108 states and 226 transitions. Second operand 3 states. [2018-06-26 18:27:33,814 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:27:33,814 INFO ]: Finished difference Result 125 states and 260 transitions. [2018-06-26 18:27:33,815 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-26 18:27:33,815 INFO ]: Start accepts. Automaton has 3 states. Word has length 17 [2018-06-26 18:27:33,815 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:27:33,817 INFO ]: With dead ends: 125 [2018-06-26 18:27:33,817 INFO ]: Without dead ends: 125 [2018-06-26 18:27:33,818 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-26 18:27:33,818 INFO ]: Start minimizeSevpa. Operand 125 states. [2018-06-26 18:27:33,842 INFO ]: Finished minimizeSevpa. Reduced states from 125 to 125. [2018-06-26 18:27:33,842 INFO ]: Start removeUnreachable. Operand 125 states. [2018-06-26 18:27:33,844 INFO ]: Finished removeUnreachable. Reduced from 125 states to 125 states and 260 transitions. [2018-06-26 18:27:33,845 INFO ]: Start accepts. Automaton has 125 states and 260 transitions. Word has length 17 [2018-06-26 18:27:33,845 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:27:33,845 INFO ]: Abstraction has 125 states and 260 transitions. [2018-06-26 18:27:33,845 INFO ]: Interpolant automaton has 3 states. [2018-06-26 18:27:33,845 INFO ]: Start isEmpty. Operand 125 states and 260 transitions. [2018-06-26 18:27:33,852 INFO ]: Finished isEmpty. Found accepting run of length 28 [2018-06-26 18:27:33,852 INFO ]: Found error trace [2018-06-26 18:27:33,852 INFO ]: trace histogram [5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:27:33,852 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:27:33,852 INFO ]: Analyzing trace with hash -386896589, now seen corresponding path program 1 times [2018-06-26 18:27:33,852 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:27:33,852 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:27:33,853 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:33,853 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:33,853 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:33,879 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:33,984 INFO ]: Checked inductivity of 35 backedges. 19 proven. 1 refuted. 0 times theorem prover too weak. 15 trivial. 0 not checked. [2018-06-26 18:27:33,984 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:27:33,984 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:27:33,990 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:34,100 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:34,105 INFO ]: Computing forward predicates... [2018-06-26 18:27:34,193 INFO ]: Checked inductivity of 35 backedges. 16 proven. 6 refuted. 0 times theorem prover too weak. 13 trivial. 0 not checked. [2018-06-26 18:27:34,213 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:27:34,214 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 8] total 13 [2018-06-26 18:27:34,214 INFO ]: Interpolant automaton has 13 states [2018-06-26 18:27:34,214 INFO ]: Constructing interpolant automaton starting with 13 interpolants. [2018-06-26 18:27:34,214 INFO ]: CoverageRelationStatistics Valid=23, Invalid=133, Unknown=0, NotChecked=0, Total=156 [2018-06-26 18:27:34,214 INFO ]: Start difference. First operand 125 states and 260 transitions. Second operand 13 states. [2018-06-26 18:27:41,311 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:27:41,311 INFO ]: Finished difference Result 789 states and 3061 transitions. [2018-06-26 18:27:41,311 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 90 states. [2018-06-26 18:27:41,311 INFO ]: Start accepts. Automaton has 13 states. Word has length 27 [2018-06-26 18:27:41,311 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:27:41,357 INFO ]: With dead ends: 789 [2018-06-26 18:27:41,357 INFO ]: Without dead ends: 712 [2018-06-26 18:27:41,360 INFO ]: 0 DeclaredPredicates, 152 GetRequests, 58 SyntacticMatches, 0 SemanticMatches, 94 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3182 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=1258, Invalid=7862, Unknown=0, NotChecked=0, Total=9120 [2018-06-26 18:27:41,360 INFO ]: Start minimizeSevpa. Operand 712 states. [2018-06-26 18:27:41,515 INFO ]: Finished minimizeSevpa. Reduced states from 712 to 329. [2018-06-26 18:27:41,515 INFO ]: Start removeUnreachable. Operand 329 states. [2018-06-26 18:27:41,525 INFO ]: Finished removeUnreachable. Reduced from 329 states to 329 states and 754 transitions. [2018-06-26 18:27:41,526 INFO ]: Start accepts. Automaton has 329 states and 754 transitions. Word has length 27 [2018-06-26 18:27:41,526 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:27:41,526 INFO ]: Abstraction has 329 states and 754 transitions. [2018-06-26 18:27:41,526 INFO ]: Interpolant automaton has 13 states. [2018-06-26 18:27:41,526 INFO ]: Start isEmpty. Operand 329 states and 754 transitions. [2018-06-26 18:27:41,555 INFO ]: Finished isEmpty. Found accepting run of length 33 [2018-06-26 18:27:41,555 INFO ]: Found error trace [2018-06-26 18:27:41,555 INFO ]: trace histogram [6, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:27:41,555 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:27:41,555 INFO ]: Analyzing trace with hash -460785466, now seen corresponding path program 1 times [2018-06-26 18:27:41,555 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:27:41,555 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:27:41,557 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:41,557 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:41,557 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:41,587 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:41,899 INFO ]: Checked inductivity of 51 backedges. 26 proven. 4 refuted. 0 times theorem prover too weak. 21 trivial. 0 not checked. [2018-06-26 18:27:41,899 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:27:41,899 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) [2018-06-26 18:27:41,913 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:27:42,016 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:42,021 INFO ]: Computing forward predicates... [2018-06-26 18:27:42,037 INFO ]: Checked inductivity of 51 backedges. 23 proven. 0 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2018-06-26 18:27:42,057 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 18:27:42,057 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [9] total 10 [2018-06-26 18:27:42,057 INFO ]: Interpolant automaton has 10 states [2018-06-26 18:27:42,057 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-26 18:27:42,057 INFO ]: CoverageRelationStatistics Valid=17, Invalid=73, Unknown=0, NotChecked=0, Total=90 [2018-06-26 18:27:42,058 INFO ]: Start difference. First operand 329 states and 754 transitions. Second operand 10 states. [2018-06-26 18:27:44,431 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:27:44,431 INFO ]: Finished difference Result 563 states and 1646 transitions. [2018-06-26 18:27:44,463 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 47 states. [2018-06-26 18:27:44,464 INFO ]: Start accepts. Automaton has 10 states. Word has length 32 [2018-06-26 18:27:44,464 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:27:44,482 INFO ]: With dead ends: 563 [2018-06-26 18:27:44,482 INFO ]: Without dead ends: 533 [2018-06-26 18:27:44,483 INFO ]: 0 DeclaredPredicates, 100 GetRequests, 52 SyntacticMatches, 0 SemanticMatches, 48 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 711 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=413, Invalid=2037, Unknown=0, NotChecked=0, Total=2450 [2018-06-26 18:27:44,483 INFO ]: Start minimizeSevpa. Operand 533 states. [2018-06-26 18:27:44,539 INFO ]: Finished minimizeSevpa. Reduced states from 533 to 260. [2018-06-26 18:27:44,539 INFO ]: Start removeUnreachable. Operand 260 states. [2018-06-26 18:27:44,543 INFO ]: Finished removeUnreachable. Reduced from 260 states to 260 states and 529 transitions. [2018-06-26 18:27:44,543 INFO ]: Start accepts. Automaton has 260 states and 529 transitions. Word has length 32 [2018-06-26 18:27:44,543 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:27:44,544 INFO ]: Abstraction has 260 states and 529 transitions. [2018-06-26 18:27:44,544 INFO ]: Interpolant automaton has 10 states. [2018-06-26 18:27:44,544 INFO ]: Start isEmpty. Operand 260 states and 529 transitions. [2018-06-26 18:27:44,554 INFO ]: Finished isEmpty. Found accepting run of length 41 [2018-06-26 18:27:44,554 INFO ]: Found error trace [2018-06-26 18:27:44,555 INFO ]: trace histogram [7, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:27:44,555 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:27:44,555 INFO ]: Analyzing trace with hash 801475312, now seen corresponding path program 1 times [2018-06-26 18:27:44,555 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:27:44,555 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:27:44,555 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:44,555 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:44,555 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:44,594 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:44,799 INFO ]: Checked inductivity of 88 backedges. 38 proven. 1 refuted. 0 times theorem prover too weak. 49 trivial. 0 not checked. [2018-06-26 18:27:44,799 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:27:44,799 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-26 18:27:44,814 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:27:44,934 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:44,940 INFO ]: Computing forward predicates... [2018-06-26 18:27:45,168 INFO ]: Checked inductivity of 88 backedges. 38 proven. 18 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2018-06-26 18:27:45,187 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:27:45,187 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 9] total 15 [2018-06-26 18:27:45,188 INFO ]: Interpolant automaton has 15 states [2018-06-26 18:27:45,188 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-26 18:27:45,188 INFO ]: CoverageRelationStatistics Valid=27, Invalid=183, Unknown=0, NotChecked=0, Total=210 [2018-06-26 18:27:45,188 INFO ]: Start difference. First operand 260 states and 529 transitions. Second operand 15 states. [2018-06-26 18:27:48,530 WARN ]: Spent 186.00 ms on a formula simplification that was a NOOP. DAG size: 18 [2018-06-26 18:27:51,307 WARN ]: Spent 137.00 ms on a formula simplification that was a NOOP. DAG size: 15 [2018-06-26 18:27:57,937 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:27:57,937 INFO ]: Finished difference Result 1170 states and 4278 transitions. [2018-06-26 18:27:57,937 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 203 states. [2018-06-26 18:27:57,937 INFO ]: Start accepts. Automaton has 15 states. Word has length 40 [2018-06-26 18:27:57,937 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:27:58,012 INFO ]: With dead ends: 1170 [2018-06-26 18:27:58,012 INFO ]: Without dead ends: 1170 [2018-06-26 18:27:58,019 INFO ]: 0 DeclaredPredicates, 273 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 209 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 18704 ImplicationChecksByTransitivity, 4.9s TimeCoverageRelationStatistics Valid=3895, Invalid=40415, Unknown=0, NotChecked=0, Total=44310 [2018-06-26 18:27:58,020 INFO ]: Start minimizeSevpa. Operand 1170 states. [2018-06-26 18:27:58,386 INFO ]: Finished minimizeSevpa. Reduced states from 1170 to 392. [2018-06-26 18:27:58,386 INFO ]: Start removeUnreachable. Operand 392 states. [2018-06-26 18:27:58,394 INFO ]: Finished removeUnreachable. Reduced from 392 states to 392 states and 856 transitions. [2018-06-26 18:27:58,394 INFO ]: Start accepts. Automaton has 392 states and 856 transitions. Word has length 40 [2018-06-26 18:27:58,394 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:27:58,394 INFO ]: Abstraction has 392 states and 856 transitions. [2018-06-26 18:27:58,394 INFO ]: Interpolant automaton has 15 states. [2018-06-26 18:27:58,394 INFO ]: Start isEmpty. Operand 392 states and 856 transitions. [2018-06-26 18:27:58,422 INFO ]: Finished isEmpty. Found accepting run of length 74 [2018-06-26 18:27:58,422 INFO ]: Found error trace [2018-06-26 18:27:58,422 INFO ]: trace histogram [13, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:27:58,422 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:27:58,423 INFO ]: Analyzing trace with hash -2000026167, now seen corresponding path program 1 times [2018-06-26 18:27:58,423 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:27:58,423 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:27:58,426 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:58,426 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:58,426 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:27:58,460 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:58,910 INFO ]: Checked inductivity of 321 backedges. 90 proven. 19 refuted. 0 times theorem prover too weak. 212 trivial. 0 not checked. [2018-06-26 18:27:58,910 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:27:58,910 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:27:58,924 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:27:59,185 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:27:59,197 INFO ]: Computing forward predicates... [2018-06-26 18:27:59,337 INFO ]: Checked inductivity of 321 backedges. 83 proven. 57 refuted. 0 times theorem prover too weak. 181 trivial. 0 not checked. [2018-06-26 18:27:59,357 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:27:59,357 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2018-06-26 18:27:59,357 INFO ]: Interpolant automaton has 16 states [2018-06-26 18:27:59,358 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-26 18:27:59,358 INFO ]: CoverageRelationStatistics Valid=29, Invalid=211, Unknown=0, NotChecked=0, Total=240 [2018-06-26 18:27:59,358 INFO ]: Start difference. First operand 392 states and 856 transitions. Second operand 16 states. [2018-06-26 18:28:11,532 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:28:11,532 INFO ]: Finished difference Result 1644 states and 7365 transitions. [2018-06-26 18:28:11,532 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 213 states. [2018-06-26 18:28:11,532 INFO ]: Start accepts. Automaton has 16 states. Word has length 73 [2018-06-26 18:28:11,532 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:28:11,641 INFO ]: With dead ends: 1644 [2018-06-26 18:28:11,641 INFO ]: Without dead ends: 1644 [2018-06-26 18:28:11,645 INFO ]: 0 DeclaredPredicates, 318 GetRequests, 100 SyntacticMatches, 0 SemanticMatches, 218 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19825 ImplicationChecksByTransitivity, 4.0s TimeCoverageRelationStatistics Valid=3804, Invalid=44376, Unknown=0, NotChecked=0, Total=48180 [2018-06-26 18:28:11,646 INFO ]: Start minimizeSevpa. Operand 1644 states. [2018-06-26 18:28:12,098 INFO ]: Finished minimizeSevpa. Reduced states from 1644 to 475. [2018-06-26 18:28:12,098 INFO ]: Start removeUnreachable. Operand 475 states. [2018-06-26 18:28:12,109 INFO ]: Finished removeUnreachable. Reduced from 475 states to 475 states and 1112 transitions. [2018-06-26 18:28:12,110 INFO ]: Start accepts. Automaton has 475 states and 1112 transitions. Word has length 73 [2018-06-26 18:28:12,110 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:28:12,110 INFO ]: Abstraction has 475 states and 1112 transitions. [2018-06-26 18:28:12,110 INFO ]: Interpolant automaton has 16 states. [2018-06-26 18:28:12,110 INFO ]: Start isEmpty. Operand 475 states and 1112 transitions. [2018-06-26 18:28:12,160 INFO ]: Finished isEmpty. Found accepting run of length 74 [2018-06-26 18:28:12,160 INFO ]: Found error trace [2018-06-26 18:28:12,160 INFO ]: trace histogram [13, 6, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:28:12,160 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:28:12,160 INFO ]: Analyzing trace with hash 312379231, now seen corresponding path program 1 times [2018-06-26 18:28:12,160 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:28:12,160 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:28:12,161 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:28:12,161 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:28:12,161 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:28:12,184 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:28:12,297 INFO ]: Checked inductivity of 333 backedges. 32 proven. 29 refuted. 0 times theorem prover too weak. 272 trivial. 0 not checked. [2018-06-26 18:28:12,297 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:28:12,297 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) [2018-06-26 18:28:12,312 INFO ]: Keeping assertion order NOT_INCREMENTALLY Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:28:12,567 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:28:12,576 INFO ]: Computing forward predicates... [2018-06-26 18:28:12,639 INFO ]: Checked inductivity of 333 backedges. 66 proven. 0 refuted. 0 times theorem prover too weak. 267 trivial. 0 not checked. [2018-06-26 18:28:12,665 INFO ]: Constructing automaton from 1 perfect and 1 imperfect interpolant sequences. [2018-06-26 18:28:12,665 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [3] total 5 [2018-06-26 18:28:12,665 INFO ]: Interpolant automaton has 5 states [2018-06-26 18:28:12,665 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-26 18:28:12,665 INFO ]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2018-06-26 18:28:12,665 INFO ]: Start difference. First operand 475 states and 1112 transitions. Second operand 5 states. [2018-06-26 18:28:12,833 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:28:12,833 INFO ]: Finished difference Result 680 states and 1974 transitions. [2018-06-26 18:28:12,833 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-26 18:28:12,833 INFO ]: Start accepts. Automaton has 5 states. Word has length 73 [2018-06-26 18:28:12,833 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:28:12,847 INFO ]: With dead ends: 680 [2018-06-26 18:28:12,847 INFO ]: Without dead ends: 649 [2018-06-26 18:28:12,847 INFO ]: 0 DeclaredPredicates, 80 GetRequests, 73 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2018-06-26 18:28:12,848 INFO ]: Start minimizeSevpa. Operand 649 states. [2018-06-26 18:28:12,917 INFO ]: Finished minimizeSevpa. Reduced states from 649 to 471. [2018-06-26 18:28:12,917 INFO ]: Start removeUnreachable. Operand 471 states. [2018-06-26 18:28:12,928 INFO ]: Finished removeUnreachable. Reduced from 471 states to 471 states and 1019 transitions. [2018-06-26 18:28:12,928 INFO ]: Start accepts. Automaton has 471 states and 1019 transitions. Word has length 73 [2018-06-26 18:28:12,929 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:28:12,929 INFO ]: Abstraction has 471 states and 1019 transitions. [2018-06-26 18:28:12,929 INFO ]: Interpolant automaton has 5 states. [2018-06-26 18:28:12,929 INFO ]: Start isEmpty. Operand 471 states and 1019 transitions. [2018-06-26 18:28:12,944 INFO ]: Finished isEmpty. Found accepting run of length 74 [2018-06-26 18:28:12,944 INFO ]: Found error trace [2018-06-26 18:28:12,944 INFO ]: trace histogram [13, 5, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:28:12,944 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:28:12,944 INFO ]: Analyzing trace with hash 1193257882, now seen corresponding path program 1 times [2018-06-26 18:28:12,944 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:28:12,944 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:28:12,946 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:28:12,946 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:28:12,946 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:28:12,987 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:28:13,179 INFO ]: Checked inductivity of 312 backedges. 78 proven. 0 refuted. 0 times theorem prover too weak. 234 trivial. 0 not checked. [2018-06-26 18:28:13,179 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-26 18:28:13,179 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-26 18:28:13,179 INFO ]: Interpolant automaton has 4 states [2018-06-26 18:28:13,179 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-26 18:28:13,179 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-26 18:28:13,180 INFO ]: Start difference. First operand 471 states and 1019 transitions. Second operand 4 states. [2018-06-26 18:28:13,574 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-26 18:28:13,574 INFO ]: Finished difference Result 637 states and 1801 transitions. [2018-06-26 18:28:13,574 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-26 18:28:13,574 INFO ]: Start accepts. Automaton has 4 states. Word has length 73 [2018-06-26 18:28:13,574 INFO ]: Finished accepts. some prefix is accepted. [2018-06-26 18:28:13,589 INFO ]: With dead ends: 637 [2018-06-26 18:28:13,589 INFO ]: Without dead ends: 637 [2018-06-26 18:28:13,589 INFO ]: 0 DeclaredPredicates, 6 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-26 18:28:13,589 INFO ]: Start minimizeSevpa. Operand 637 states. [2018-06-26 18:28:13,649 INFO ]: Finished minimizeSevpa. Reduced states from 637 to 463. [2018-06-26 18:28:13,649 INFO ]: Start removeUnreachable. Operand 463 states. [2018-06-26 18:28:13,658 INFO ]: Finished removeUnreachable. Reduced from 463 states to 463 states and 991 transitions. [2018-06-26 18:28:13,658 INFO ]: Start accepts. Automaton has 463 states and 991 transitions. Word has length 73 [2018-06-26 18:28:13,659 INFO ]: Finished accepts. word is rejected. [2018-06-26 18:28:13,659 INFO ]: Abstraction has 463 states and 991 transitions. [2018-06-26 18:28:13,659 INFO ]: Interpolant automaton has 4 states. [2018-06-26 18:28:13,659 INFO ]: Start isEmpty. Operand 463 states and 991 transitions. [2018-06-26 18:28:13,670 INFO ]: Finished isEmpty. Found accepting run of length 86 [2018-06-26 18:28:13,670 INFO ]: Found error trace [2018-06-26 18:28:13,670 INFO ]: trace histogram [15, 6, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-06-26 18:28:13,670 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-26 18:28:13,670 INFO ]: Analyzing trace with hash 1212067944, now seen corresponding path program 1 times [2018-06-26 18:28:13,670 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-26 18:28:13,670 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-26 18:28:13,671 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:28:13,671 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:28:13,671 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-26 18:28:13,709 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:28:14,020 INFO ]: Checked inductivity of 433 backedges. 100 proven. 78 refuted. 0 times theorem prover too weak. 255 trivial. 0 not checked. [2018-06-26 18:28:14,020 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-26 18:28:14,020 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-26 18:28:14,026 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-26 18:28:14,265 INFO ]: Conjunction of SSA is unsat [2018-06-26 18:28:14,277 INFO ]: Computing forward predicates... [2018-06-26 18:28:15,024 INFO ]: Checked inductivity of 433 backedges. 92 proven. 108 refuted. 0 times theorem prover too weak. 233 trivial. 0 not checked. [2018-06-26 18:28:15,057 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-26 18:28:15,057 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 13] total 22 [2018-06-26 18:28:15,058 INFO ]: Interpolant automaton has 22 states [2018-06-26 18:28:15,058 INFO ]: Constructing interpolant automaton starting with 22 interpolants. [2018-06-26 18:28:15,058 INFO ]: CoverageRelationStatistics Valid=46, Invalid=416, Unknown=0, NotChecked=0, Total=462 [2018-06-26 18:28:15,058 INFO ]: Start difference. First operand 463 states and 991 transitions. Second operand 22 states. [2018-06-26 18:28:15,728 WARN ]: Spent 168.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 16 Received shutdown request... [2018-06-26 18:28:23,884 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 124 states. [2018-06-26 18:28:23,884 WARN ]: Verification canceled [2018-06-26 18:28:23,886 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-26 18:28:23,887 WARN ]: Timeout [2018-06-26 18:28:23,887 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 26.06 06:28:23 BasicIcfg [2018-06-26 18:28:23,887 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-26 18:28:23,888 INFO ]: Toolchain (without parser) took 57567.15 ms. Allocated memory was 304.6 MB in the beginning and 1.2 GB in the end (delta: 871.9 MB). Free memory was 243.2 MB in the beginning and 560.6 MB in the end (delta: -317.4 MB). Peak memory consumption was 554.4 MB. Max. memory is 3.6 GB. [2018-06-26 18:28:23,889 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 304.6 MB. Free memory is still 269.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-26 18:28:23,889 INFO ]: ChcToBoogie took 107.40 ms. Allocated memory is still 304.6 MB. Free memory was 243.2 MB in the beginning and 239.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. [2018-06-26 18:28:23,889 INFO ]: Boogie Preprocessor took 84.49 ms. Allocated memory is still 304.6 MB. Free memory was 239.2 MB in the beginning and 237.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-26 18:28:23,890 INFO ]: RCFGBuilder took 705.46 ms. Allocated memory is still 304.6 MB. Free memory was 237.2 MB in the beginning and 205.2 MB in the end (delta: 32.0 MB). Peak memory consumption was 32.0 MB. Max. memory is 3.6 GB. [2018-06-26 18:28:23,890 INFO ]: BlockEncodingV2 took 712.07 ms. Allocated memory was 304.6 MB in the beginning and 323.0 MB in the end (delta: 18.4 MB). Free memory was 205.2 MB in the beginning and 279.3 MB in the end (delta: -74.1 MB). Peak memory consumption was 28.1 MB. Max. memory is 3.6 GB. [2018-06-26 18:28:23,890 INFO ]: TraceAbstraction took 55948.89 ms. Allocated memory was 323.0 MB in the beginning and 1.2 GB in the end (delta: 853.5 MB). Free memory was 279.3 MB in the beginning and 560.6 MB in the end (delta: -281.3 MB). Peak memory consumption was 572.2 MB. Max. memory is 3.6 GB. [2018-06-26 18:28:23,899 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.plugins.blockencoding: - StatisticsResult: Initial Icfg 48 locations, 77 edges - StatisticsResult: Encoded RCFG 32 locations, 62 edges * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 304.6 MB. Free memory is still 269.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 107.40 ms. Allocated memory is still 304.6 MB. Free memory was 243.2 MB in the beginning and 239.2 MB in the end (delta: 4.0 MB). Peak memory consumption was 4.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 84.49 ms. Allocated memory is still 304.6 MB. Free memory was 239.2 MB in the beginning and 237.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 705.46 ms. Allocated memory is still 304.6 MB. Free memory was 237.2 MB in the beginning and 205.2 MB in the end (delta: 32.0 MB). Peak memory consumption was 32.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 712.07 ms. Allocated memory was 304.6 MB in the beginning and 323.0 MB in the end (delta: 18.4 MB). Free memory was 205.2 MB in the beginning and 279.3 MB in the end (delta: -74.1 MB). Peak memory consumption was 28.1 MB. Max. memory is 3.6 GB. * TraceAbstraction took 55948.89 ms. Allocated memory was 323.0 MB in the beginning and 1.2 GB in the end (delta: 853.5 MB). Free memory was 279.3 MB in the beginning and 560.6 MB in the end (delta: -281.3 MB). Peak memory consumption was 572.2 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 (463states) and interpolant automaton (currently 124 states, 22 states before enhancement), while ReachableStatesComputation was computing reachable states (1780 states constructedinput type IntersectNwa). - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 32 locations, 1 error locations. TIMEOUT Result, 55.8s OverallTime, 14 OverallIterations, 15 TraceHistogramMax, 48.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 3004 SDtfs, 1880 SDslu, 13978 SDs, 0 SdLazy, 43953 SolverSat, 6490 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 30.0s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1244 GetRequests, 513 SyntacticMatches, 2 SemanticMatches, 729 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48592 ImplicationChecksByTransitivity, 15.0s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=475occurred in iteration=11, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 1.4s AutomataMinimizationTime, 13 MinimizatonAttempts, 3153 StatesRemovedByMinimization, 9 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.4s SsaConstructionTime, 1.2s SatisfiabilityAnalysisTime, 3.9s InterpolantComputationTime, 823 NumberOfCodeBlocks, 823 NumberOfCodeBlocksAsserted, 21 NumberOfCheckSat, 802 ConstructedInterpolants, 0 QuantifiedInterpolants, 74515 SizeOfPredicates, 58 NumberOfNonLiveVariables, 9014 ConjunctsInSsa, 120 ConjunctsInUnsatCore, 21 InterpolantComputations, 9 PerfectInterpolantSequences, 2555/2878 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/Ackermann02.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-26_18-28-23-913.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/Ackermann02.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-26_18-28-23-913.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/Ackermann02.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-26_18-28-23-913.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/Ackermann02.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-26_18-28-23-913.csv Completed graceful shutdown