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/012b-horn.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-24 21:03:14,619 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-24 21:03:14,622 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-24 21:03:14,633 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-24 21:03:14,634 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-24 21:03:14,634 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-24 21:03:14,636 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-24 21:03:14,640 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-24 21:03:14,641 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-24 21:03:14,642 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-24 21:03:14,643 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-24 21:03:14,644 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-24 21:03:14,644 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-24 21:03:14,645 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-24 21:03:14,649 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-24 21:03:14,650 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-24 21:03:14,651 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-24 21:03:14,660 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-24 21:03:14,661 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-24 21:03:14,662 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-24 21:03:14,663 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-24 21:03:14,668 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-24 21:03:14,668 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-24 21:03:14,668 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-24 21:03:14,669 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-24 21:03:14,673 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-24 21:03:14,673 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-24 21:03:14,675 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-24 21:03:14,676 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-24 21:03:14,676 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-24 21:03:14,676 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-24 21:03:14,677 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-24 21:03:14,677 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-24 21:03:14,682 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-24 21:03:14,683 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-24 21:03:14,683 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:14,703 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-24 21:03:14,703 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-24 21:03:14,704 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-24 21:03:14,704 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-24 21:03:14,705 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-24 21:03:14,705 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-24 21:03:14,705 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-24 21:03:14,705 INFO L133 SettingsManager]: * Use SBE=true [2018-06-24 21:03:14,706 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-24 21:03:14,707 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-24 21:03:14,707 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-24 21:03:14,707 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-24 21:03:14,707 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-24 21:03:14,707 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-24 21:03:14,708 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-24 21:03:14,708 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-24 21:03:14,708 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-24 21:03:14,708 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-24 21:03:14,708 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-24 21:03:14,708 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-24 21:03:14,709 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-24 21:03:14,711 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-24 21:03:14,711 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-24 21:03:14,748 INFO ]: Repository-Root is: /tmp [2018-06-24 21:03:14,760 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-24 21:03:14,764 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-24 21:03:14,765 INFO ]: Initializing SmtParser... [2018-06-24 21:03:14,765 INFO ]: SmtParser initialized [2018-06-24 21:03:14,766 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/eldarica-misc/LIA/reve/012b-horn.smt2 [2018-06-24 21:03:14,767 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:14,862 INFO ]: Executing SMT file /storage/chc-comp/eldarica-misc/LIA/reve/012b-horn.smt2 unknown [2018-06-24 21:03:15,030 INFO ]: Succesfully executed SMT file /storage/chc-comp/eldarica-misc/LIA/reve/012b-horn.smt2 [2018-06-24 21:03:15,034 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-24 21:03:15,041 INFO ]: Walking toolchain with 5 elements. [2018-06-24 21:03:15,042 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-24 21:03:15,042 INFO ]: Initializing ChcToBoogie... [2018-06-24 21:03:15,042 INFO ]: ChcToBoogie initialized [2018-06-24 21:03:15,046 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 24.06 09:03:15" (1/1) ... [2018-06-24 21:03:15,098 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:15 Unit [2018-06-24 21:03:15,098 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-24 21:03:15,099 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-24 21:03:15,099 INFO ]: Initializing Boogie Preprocessor... [2018-06-24 21:03:15,099 INFO ]: Boogie Preprocessor initialized [2018-06-24 21:03:15,119 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:15" (1/1) ... [2018-06-24 21:03:15,119 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:15" (1/1) ... [2018-06-24 21:03:15,126 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:15" (1/1) ... [2018-06-24 21:03:15,126 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:15" (1/1) ... [2018-06-24 21:03:15,130 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:15" (1/1) ... [2018-06-24 21:03:15,132 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:15" (1/1) ... [2018-06-24 21:03:15,132 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:15" (1/1) ... [2018-06-24 21:03:15,134 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-24 21:03:15,134 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-24 21:03:15,134 INFO ]: Initializing RCFGBuilder... [2018-06-24 21:03:15,134 INFO ]: RCFGBuilder initialized [2018-06-24 21:03:15,136 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:15" (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:15,151 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-24 21:03:15,151 INFO ]: Found specification of procedure gotoProc [2018-06-24 21:03:15,151 INFO ]: Found implementation of procedure gotoProc [2018-06-24 21:03:15,152 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-24 21:03:15,152 INFO ]: Found specification of procedure Ultimate.START [2018-06-24 21:03:15,152 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:15,401 INFO ]: Using library mode [2018-06-24 21:03:15,402 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:03:15 BoogieIcfgContainer [2018-06-24 21:03:15,402 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-24 21:03:15,402 INFO ]: ------------------------BlockEncodingV2---------------------------- [2018-06-24 21:03:15,402 INFO ]: Initializing BlockEncodingV2... [2018-06-24 21:03:15,403 INFO ]: BlockEncodingV2 initialized [2018-06-24 21:03:15,404 INFO ]: Executing the observer BlockEncodingObserver from plugin BlockEncodingV2 for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:03:15" (1/1) ... [2018-06-24 21:03:15,417 INFO ]: Initial Icfg 12 locations, 19 edges [2018-06-24 21:03:15,418 INFO ]: Using Remove infeasible edges [2018-06-24 21:03:15,419 INFO ]: Using Maximize final states [2018-06-24 21:03:15,419 INFO ]: Using Minimize states even if more edges are added than removed.=false [2018-06-24 21:03:15,419 INFO ]: Using Minimize states using LBE with the strategy=MULTI [2018-06-24 21:03:15,423 INFO ]: Using Remove sink states [2018-06-24 21:03:15,423 INFO ]: Using Apply optimizations until nothing changes=true [2018-06-24 21:03:15,423 INFO ]: Using Use SBE [2018-06-24 21:03:15,428 INFO ]: SBE split 0 edges [2018-06-24 21:03:15,439 INFO ]: Removed 5 edges and 2 locations because of local infeasibility [2018-06-24 21:03:15,440 INFO ]: 0 new accepting states [2018-06-24 21:03:15,471 INFO ]: Removed 6 edges and 2 locations by large block encoding [2018-06-24 21:03:15,472 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 21:03:15,476 INFO ]: Removed 0 edges and 0 locations because of local infeasibility [2018-06-24 21:03:15,476 INFO ]: 0 new accepting states [2018-06-24 21:03:15,476 INFO ]: Removed 0 edges and 0 locations by large block encoding [2018-06-24 21:03:15,476 INFO ]: Removed 0 edges and 0 locations by removing sink states [2018-06-24 21:03:15,476 INFO ]: Encoded RCFG 8 locations, 12 edges [2018-06-24 21:03:15,477 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 24.06 09:03:15 BasicIcfg [2018-06-24 21:03:15,477 INFO ]: ------------------------ END BlockEncodingV2---------------------------- [2018-06-24 21:03:15,478 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-24 21:03:15,478 INFO ]: Initializing TraceAbstraction... [2018-06-24 21:03:15,480 INFO ]: TraceAbstraction initialized [2018-06-24 21:03:15,480 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 24.06 09:03:15" (1/4) ... [2018-06-24 21:03:15,481 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@745c7d46 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 24.06 09:03:15, skipping insertion in model container [2018-06-24 21:03:15,481 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 24.06 09:03:15" (2/4) ... [2018-06-24 21:03:15,481 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@745c7d46 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 24.06 09:03:15, skipping insertion in model container [2018-06-24 21:03:15,481 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 24.06 09:03:15" (3/4) ... [2018-06-24 21:03:15,481 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@745c7d46 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.06 09:03:15, skipping insertion in model container [2018-06-24 21:03:15,481 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.blockencoding CFG 24.06 09:03:15" (4/4) ... [2018-06-24 21:03:15,482 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver_BEv2 [2018-06-24 21:03:15,490 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-24 21:03:15,499 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-24 21:03:15,544 INFO ]: Using default assertion order modulation [2018-06-24 21:03:15,544 INFO ]: Interprodecural is true [2018-06-24 21:03:15,544 INFO ]: Hoare is false [2018-06-24 21:03:15,544 INFO ]: Compute interpolants for FPandBP [2018-06-24 21:03:15,544 INFO ]: Backedges is TWOTRACK [2018-06-24 21:03:15,544 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-24 21:03:15,544 INFO ]: Difference is false [2018-06-24 21:03:15,544 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-24 21:03:15,544 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-24 21:03:15,553 INFO ]: Start isEmpty. Operand 8 states. [2018-06-24 21:03:15,563 INFO ]: Finished isEmpty. Found accepting run of length 6 [2018-06-24 21:03:15,563 INFO ]: Found error trace [2018-06-24 21:03:15,564 INFO ]: trace histogram [1, 1, 1, 1, 1] [2018-06-24 21:03:15,564 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:15,570 INFO ]: Analyzing trace with hash 37526653, now seen corresponding path program 1 times [2018-06-24 21:03:15,571 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:15,572 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:15,601 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:15,601 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:15,601 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:15,640 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:15,820 WARN ]: Spent 114.00 ms on a formula simplification. DAG size of input: 16 DAG size of output: 13 [2018-06-24 21:03:15,821 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:15,823 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:03:15,823 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:03:15,824 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:03:15,835 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:03:15,836 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:03:15,838 INFO ]: Start difference. First operand 8 states. Second operand 3 states. [2018-06-24 21:03:15,886 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:15,886 INFO ]: Finished difference Result 11 states and 18 transitions. [2018-06-24 21:03:15,887 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:03:15,887 INFO ]: Start accepts. Automaton has 3 states. Word has length 5 [2018-06-24 21:03:15,888 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:15,896 INFO ]: With dead ends: 11 [2018-06-24 21:03:15,896 INFO ]: Without dead ends: 11 [2018-06-24 21:03:15,898 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:03:15,910 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-24 21:03:15,924 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 9. [2018-06-24 21:03:15,925 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-24 21:03:15,925 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 15 transitions. [2018-06-24 21:03:15,926 INFO ]: Start accepts. Automaton has 9 states and 15 transitions. Word has length 5 [2018-06-24 21:03:15,926 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:15,926 INFO ]: Abstraction has 9 states and 15 transitions. [2018-06-24 21:03:15,926 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:03:15,926 INFO ]: Start isEmpty. Operand 9 states and 15 transitions. [2018-06-24 21:03:15,927 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-24 21:03:15,927 INFO ]: Found error trace [2018-06-24 21:03:15,927 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-24 21:03:15,927 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:15,927 INFO ]: Analyzing trace with hash 1163211301, now seen corresponding path program 1 times [2018-06-24 21:03:15,927 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:15,927 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:15,928 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:15,928 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:15,928 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:15,938 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:15,999 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:15,999 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:03:15,999 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-24 21:03:16,001 INFO ]: Interpolant automaton has 3 states [2018-06-24 21:03:16,001 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-24 21:03:16,001 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-24 21:03:16,001 INFO ]: Start difference. First operand 9 states and 15 transitions. Second operand 3 states. [2018-06-24 21:03:16,016 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:16,016 INFO ]: Finished difference Result 8 states and 11 transitions. [2018-06-24 21:03:16,017 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-24 21:03:16,017 INFO ]: Start accepts. Automaton has 3 states. Word has length 6 [2018-06-24 21:03:16,017 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:16,017 INFO ]: With dead ends: 8 [2018-06-24 21:03:16,017 INFO ]: Without dead ends: 8 [2018-06-24 21:03:16,018 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:16,018 INFO ]: Start minimizeSevpa. Operand 8 states. [2018-06-24 21:03:16,019 INFO ]: Finished minimizeSevpa. Reduced states from 8 to 8. [2018-06-24 21:03:16,019 INFO ]: Start removeUnreachable. Operand 8 states. [2018-06-24 21:03:16,019 INFO ]: Finished removeUnreachable. Reduced from 8 states to 8 states and 11 transitions. [2018-06-24 21:03:16,019 INFO ]: Start accepts. Automaton has 8 states and 11 transitions. Word has length 6 [2018-06-24 21:03:16,019 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:16,019 INFO ]: Abstraction has 8 states and 11 transitions. [2018-06-24 21:03:16,019 INFO ]: Interpolant automaton has 3 states. [2018-06-24 21:03:16,019 INFO ]: Start isEmpty. Operand 8 states and 11 transitions. [2018-06-24 21:03:16,019 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-24 21:03:16,019 INFO ]: Found error trace [2018-06-24 21:03:16,019 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-24 21:03:16,019 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:16,020 INFO ]: Analyzing trace with hash 1163150758, now seen corresponding path program 1 times [2018-06-24 21:03:16,020 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:16,020 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:16,021 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:16,021 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:16,021 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:16,032 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:16,096 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:16,096 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:03:16,096 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-24 21:03:16,096 INFO ]: Interpolant automaton has 4 states [2018-06-24 21:03:16,097 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-24 21:03:16,097 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-24 21:03:16,097 INFO ]: Start difference. First operand 8 states and 11 transitions. Second operand 4 states. [2018-06-24 21:03:16,223 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:16,223 INFO ]: Finished difference Result 11 states and 15 transitions. [2018-06-24 21:03:16,224 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-24 21:03:16,224 INFO ]: Start accepts. Automaton has 4 states. Word has length 6 [2018-06-24 21:03:16,224 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:16,224 INFO ]: With dead ends: 11 [2018-06-24 21:03:16,224 INFO ]: Without dead ends: 11 [2018-06-24 21:03:16,225 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:16,225 INFO ]: Start minimizeSevpa. Operand 11 states. [2018-06-24 21:03:16,226 INFO ]: Finished minimizeSevpa. Reduced states from 11 to 9. [2018-06-24 21:03:16,226 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-24 21:03:16,226 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 12 transitions. [2018-06-24 21:03:16,226 INFO ]: Start accepts. Automaton has 9 states and 12 transitions. Word has length 6 [2018-06-24 21:03:16,227 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:16,227 INFO ]: Abstraction has 9 states and 12 transitions. [2018-06-24 21:03:16,227 INFO ]: Interpolant automaton has 4 states. [2018-06-24 21:03:16,227 INFO ]: Start isEmpty. Operand 9 states and 12 transitions. [2018-06-24 21:03:16,227 INFO ]: Finished isEmpty. Found accepting run of length 7 [2018-06-24 21:03:16,227 INFO ]: Found error trace [2018-06-24 21:03:16,227 INFO ]: trace histogram [1, 1, 1, 1, 1, 1] [2018-06-24 21:03:16,227 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:16,227 INFO ]: Analyzing trace with hash 1163179588, now seen corresponding path program 1 times [2018-06-24 21:03:16,227 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:16,227 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:16,230 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:16,230 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:16,230 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:16,240 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:16,297 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:16,298 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:16,298 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:03:16,304 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:16,321 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:16,328 INFO ]: Computing forward predicates... [2018-06-24 21:03:16,361 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:16,395 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:16,395 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 4 [2018-06-24 21:03:16,395 INFO ]: Interpolant automaton has 4 states [2018-06-24 21:03:16,395 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-24 21:03:16,395 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-24 21:03:16,395 INFO ]: Start difference. First operand 9 states and 12 transitions. Second operand 4 states. [2018-06-24 21:03:16,517 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:16,517 INFO ]: Finished difference Result 9 states and 11 transitions. [2018-06-24 21:03:16,517 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-24 21:03:16,517 INFO ]: Start accepts. Automaton has 4 states. Word has length 6 [2018-06-24 21:03:16,517 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:16,517 INFO ]: With dead ends: 9 [2018-06-24 21:03:16,517 INFO ]: Without dead ends: 9 [2018-06-24 21:03:16,518 INFO ]: 0 DeclaredPredicates, 10 GetRequests, 7 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:16,518 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-24 21:03:16,519 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-24 21:03:16,519 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-24 21:03:16,519 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 11 transitions. [2018-06-24 21:03:16,519 INFO ]: Start accepts. Automaton has 9 states and 11 transitions. Word has length 6 [2018-06-24 21:03:16,519 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:16,519 INFO ]: Abstraction has 9 states and 11 transitions. [2018-06-24 21:03:16,519 INFO ]: Interpolant automaton has 4 states. [2018-06-24 21:03:16,520 INFO ]: Start isEmpty. Operand 9 states and 11 transitions. [2018-06-24 21:03:16,520 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-24 21:03:16,520 INFO ]: Found error trace [2018-06-24 21:03:16,520 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:16,520 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:16,520 INFO ]: Analyzing trace with hash 1697431944, now seen corresponding path program 1 times [2018-06-24 21:03:16,520 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:16,520 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:16,521 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:16,521 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:16,521 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:16,530 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:16,572 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:16,572 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-24 21:03:16,573 INFO ]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-06-24 21:03:16,573 INFO ]: Interpolant automaton has 4 states [2018-06-24 21:03:16,573 INFO ]: Constructing interpolant automaton starting with 4 interpolants. [2018-06-24 21:03:16,573 INFO ]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-06-24 21:03:16,573 INFO ]: Start difference. First operand 9 states and 11 transitions. Second operand 4 states. [2018-06-24 21:03:16,659 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:16,660 INFO ]: Finished difference Result 9 states and 10 transitions. [2018-06-24 21:03:16,660 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2018-06-24 21:03:16,660 INFO ]: Start accepts. Automaton has 4 states. Word has length 7 [2018-06-24 21:03:16,660 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:16,660 INFO ]: With dead ends: 9 [2018-06-24 21:03:16,660 INFO ]: Without dead ends: 8 [2018-06-24 21:03:16,660 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:16,660 INFO ]: Start minimizeSevpa. Operand 8 states. [2018-06-24 21:03:16,661 INFO ]: Finished minimizeSevpa. Reduced states from 8 to 8. [2018-06-24 21:03:16,661 INFO ]: Start removeUnreachable. Operand 8 states. [2018-06-24 21:03:16,661 INFO ]: Finished removeUnreachable. Reduced from 8 states to 8 states and 9 transitions. [2018-06-24 21:03:16,662 INFO ]: Start accepts. Automaton has 8 states and 9 transitions. Word has length 7 [2018-06-24 21:03:16,662 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:16,662 INFO ]: Abstraction has 8 states and 9 transitions. [2018-06-24 21:03:16,662 INFO ]: Interpolant automaton has 4 states. [2018-06-24 21:03:16,662 INFO ]: Start isEmpty. Operand 8 states and 9 transitions. [2018-06-24 21:03:16,662 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-24 21:03:16,662 INFO ]: Found error trace [2018-06-24 21:03:16,662 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:16,662 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:16,662 INFO ]: Analyzing trace with hash 1698653375, now seen corresponding path program 1 times [2018-06-24 21:03:16,662 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:16,662 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:16,663 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:16,663 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:16,663 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:16,685 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:16,850 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:16,851 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:16,851 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:16,857 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:16,878 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:16,880 INFO ]: Computing forward predicates... [2018-06-24 21:03:17,171 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:17,190 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:17,190 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 8 [2018-06-24 21:03:17,190 INFO ]: Interpolant automaton has 8 states [2018-06-24 21:03:17,191 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-24 21:03:17,191 INFO ]: CoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-06-24 21:03:17,191 INFO ]: Start difference. First operand 8 states and 9 transitions. Second operand 8 states. [2018-06-24 21:03:17,458 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:17,458 INFO ]: Finished difference Result 18 states and 24 transitions. [2018-06-24 21:03:17,458 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-24 21:03:17,458 INFO ]: Start accepts. Automaton has 8 states. Word has length 7 [2018-06-24 21:03:17,459 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:17,459 INFO ]: With dead ends: 18 [2018-06-24 21:03:17,459 INFO ]: Without dead ends: 18 [2018-06-24 21:03:17,459 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 8 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=46, Invalid=86, Unknown=0, NotChecked=0, Total=132 [2018-06-24 21:03:17,459 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-24 21:03:17,461 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 13. [2018-06-24 21:03:17,461 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-24 21:03:17,463 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 17 transitions. [2018-06-24 21:03:17,463 INFO ]: Start accepts. Automaton has 13 states and 17 transitions. Word has length 7 [2018-06-24 21:03:17,463 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:17,463 INFO ]: Abstraction has 13 states and 17 transitions. [2018-06-24 21:03:17,463 INFO ]: Interpolant automaton has 8 states. [2018-06-24 21:03:17,463 INFO ]: Start isEmpty. Operand 13 states and 17 transitions. [2018-06-24 21:03:17,463 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-24 21:03:17,463 INFO ]: Found error trace [2018-06-24 21:03:17,463 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:17,463 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:17,464 INFO ]: Analyzing trace with hash 302218943, now seen corresponding path program 1 times [2018-06-24 21:03:17,464 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:17,464 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:17,464 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:17,464 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:17,464 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:17,479 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:17,625 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:17,625 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:17,625 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-24 21:03:17,640 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-24 21:03:17,679 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:17,681 INFO ]: Computing forward predicates... [2018-06-24 21:03:17,702 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:17,735 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:17,735 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 6 [2018-06-24 21:03:17,735 INFO ]: Interpolant automaton has 6 states [2018-06-24 21:03:17,735 INFO ]: Constructing interpolant automaton starting with 6 interpolants. [2018-06-24 21:03:17,735 INFO ]: CoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2018-06-24 21:03:17,735 INFO ]: Start difference. First operand 13 states and 17 transitions. Second operand 6 states. [2018-06-24 21:03:17,934 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:17,934 INFO ]: Finished difference Result 14 states and 17 transitions. [2018-06-24 21:03:17,935 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-24 21:03:17,935 INFO ]: Start accepts. Automaton has 6 states. Word has length 9 [2018-06-24 21:03:17,935 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:17,935 INFO ]: With dead ends: 14 [2018-06-24 21:03:17,935 INFO ]: Without dead ends: 12 [2018-06-24 21:03:17,935 INFO ]: 0 DeclaredPredicates, 16 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=35, Unknown=0, NotChecked=0, Total=56 [2018-06-24 21:03:17,936 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-24 21:03:17,937 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-24 21:03:17,937 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-24 21:03:17,938 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 15 transitions. [2018-06-24 21:03:17,938 INFO ]: Start accepts. Automaton has 12 states and 15 transitions. Word has length 9 [2018-06-24 21:03:17,938 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:17,938 INFO ]: Abstraction has 12 states and 15 transitions. [2018-06-24 21:03:17,938 INFO ]: Interpolant automaton has 6 states. [2018-06-24 21:03:17,938 INFO ]: Start isEmpty. Operand 12 states and 15 transitions. [2018-06-24 21:03:17,938 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-24 21:03:17,938 INFO ]: Found error trace [2018-06-24 21:03:17,938 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:17,938 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:17,938 INFO ]: Analyzing trace with hash 340083304, now seen corresponding path program 2 times [2018-06-24 21:03:17,938 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:17,938 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:17,939 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:17,939 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:17,939 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:17,954 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:18,145 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:18,145 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:18,145 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:18,154 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:03:18,190 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:03:18,190 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:18,194 INFO ]: Computing forward predicates... [2018-06-24 21:03:18,533 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:18,553 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:18,553 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2018-06-24 21:03:18,554 INFO ]: Interpolant automaton has 12 states [2018-06-24 21:03:18,554 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-24 21:03:18,554 INFO ]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2018-06-24 21:03:18,554 INFO ]: Start difference. First operand 12 states and 15 transitions. Second operand 12 states. [2018-06-24 21:03:18,811 WARN ]: Spent 138.00 ms on a formula simplification that was a NOOP. DAG size: 50 [2018-06-24 21:03:18,830 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:18,830 INFO ]: Finished difference Result 14 states and 17 transitions. [2018-06-24 21:03:18,830 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-06-24 21:03:18,830 INFO ]: Start accepts. Automaton has 12 states. Word has length 9 [2018-06-24 21:03:18,831 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:18,831 INFO ]: With dead ends: 14 [2018-06-24 21:03:18,831 INFO ]: Without dead ends: 14 [2018-06-24 21:03:18,831 INFO ]: 0 DeclaredPredicates, 17 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=50, Invalid=132, Unknown=0, NotChecked=0, Total=182 [2018-06-24 21:03:18,831 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-24 21:03:18,833 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 11. [2018-06-24 21:03:18,833 INFO ]: Start removeUnreachable. Operand 11 states. [2018-06-24 21:03:18,833 INFO ]: Finished removeUnreachable. Reduced from 11 states to 11 states and 12 transitions. [2018-06-24 21:03:18,833 INFO ]: Start accepts. Automaton has 11 states and 12 transitions. Word has length 9 [2018-06-24 21:03:18,833 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:18,833 INFO ]: Abstraction has 11 states and 12 transitions. [2018-06-24 21:03:18,833 INFO ]: Interpolant automaton has 12 states. [2018-06-24 21:03:18,833 INFO ]: Start isEmpty. Operand 11 states and 12 transitions. [2018-06-24 21:03:18,833 INFO ]: Finished isEmpty. Found accepting run of length 11 [2018-06-24 21:03:18,833 INFO ]: Found error trace [2018-06-24 21:03:18,833 INFO ]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:18,833 INFO ]: === Iteration 9 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:18,834 INFO ]: Analyzing trace with hash 1952144646, now seen corresponding path program 3 times [2018-06-24 21:03:18,834 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:18,834 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:18,834 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:18,835 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:18,835 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:18,848 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:18,986 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:18,986 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:18,986 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:18,991 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:03:19,016 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2018-06-24 21:03:19,016 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:19,019 INFO ]: Computing forward predicates... [2018-06-24 21:03:19,139 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:19,157 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:19,157 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 11 [2018-06-24 21:03:19,157 INFO ]: Interpolant automaton has 11 states [2018-06-24 21:03:19,157 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-24 21:03:19,157 INFO ]: CoverageRelationStatistics Valid=22, Invalid=88, Unknown=0, NotChecked=0, Total=110 [2018-06-24 21:03:19,157 INFO ]: Start difference. First operand 11 states and 12 transitions. Second operand 11 states. [2018-06-24 21:03:19,259 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:19,259 INFO ]: Finished difference Result 17 states and 20 transitions. [2018-06-24 21:03:19,260 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-24 21:03:19,260 INFO ]: Start accepts. Automaton has 11 states. Word has length 10 [2018-06-24 21:03:19,260 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:19,260 INFO ]: With dead ends: 17 [2018-06-24 21:03:19,260 INFO ]: Without dead ends: 17 [2018-06-24 21:03:19,260 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:19,261 INFO ]: Start minimizeSevpa. Operand 17 states. [2018-06-24 21:03:19,262 INFO ]: Finished minimizeSevpa. Reduced states from 17 to 13. [2018-06-24 21:03:19,262 INFO ]: Start removeUnreachable. Operand 13 states. [2018-06-24 21:03:19,262 INFO ]: Finished removeUnreachable. Reduced from 13 states to 13 states and 15 transitions. [2018-06-24 21:03:19,262 INFO ]: Start accepts. Automaton has 13 states and 15 transitions. Word has length 10 [2018-06-24 21:03:19,263 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:19,263 INFO ]: Abstraction has 13 states and 15 transitions. [2018-06-24 21:03:19,263 INFO ]: Interpolant automaton has 11 states. [2018-06-24 21:03:19,263 INFO ]: Start isEmpty. Operand 13 states and 15 transitions. [2018-06-24 21:03:19,263 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-24 21:03:19,263 INFO ]: Found error trace [2018-06-24 21:03:19,263 INFO ]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:19,263 INFO ]: === Iteration 10 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:19,263 INFO ]: Analyzing trace with hash 386438696, now seen corresponding path program 4 times [2018-06-24 21:03:19,263 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:19,263 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:19,264 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:19,264 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:19,264 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:19,274 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:19,351 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:19,351 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:19,351 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:19,357 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-24 21:03:19,381 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-24 21:03:19,381 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:19,383 INFO ]: Computing forward predicates... [2018-06-24 21:03:19,392 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:19,417 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:19,417 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 8 [2018-06-24 21:03:19,417 INFO ]: Interpolant automaton has 8 states [2018-06-24 21:03:19,417 INFO ]: Constructing interpolant automaton starting with 8 interpolants. [2018-06-24 21:03:19,417 INFO ]: CoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-06-24 21:03:19,417 INFO ]: Start difference. First operand 13 states and 15 transitions. Second operand 8 states. [2018-06-24 21:03:19,448 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:19,448 INFO ]: Finished difference Result 15 states and 16 transitions. [2018-06-24 21:03:19,450 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-24 21:03:19,450 INFO ]: Start accepts. Automaton has 8 states. Word has length 11 [2018-06-24 21:03:19,450 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:19,450 INFO ]: With dead ends: 15 [2018-06-24 21:03:19,450 INFO ]: Without dead ends: 12 [2018-06-24 21:03:19,450 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:19,450 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-24 21:03:19,451 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-24 21:03:19,451 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-24 21:03:19,452 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 13 transitions. [2018-06-24 21:03:19,452 INFO ]: Start accepts. Automaton has 12 states and 13 transitions. Word has length 11 [2018-06-24 21:03:19,452 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:19,452 INFO ]: Abstraction has 12 states and 13 transitions. [2018-06-24 21:03:19,452 INFO ]: Interpolant automaton has 8 states. [2018-06-24 21:03:19,452 INFO ]: Start isEmpty. Operand 12 states and 13 transitions. [2018-06-24 21:03:19,452 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-24 21:03:19,452 INFO ]: Found error trace [2018-06-24 21:03:19,452 INFO ]: trace histogram [3, 2, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:19,452 INFO ]: === Iteration 11 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:19,452 INFO ]: Analyzing trace with hash 1560233887, now seen corresponding path program 5 times [2018-06-24 21:03:19,452 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:19,452 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:19,453 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:19,453 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:19,453 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:19,467 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:19,673 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:19,673 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:19,674 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:19,690 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-24 21:03:19,723 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 3 check-sat command(s) [2018-06-24 21:03:19,723 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:19,726 INFO ]: Computing forward predicates... [2018-06-24 21:03:20,019 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:20,043 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:20,043 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2018-06-24 21:03:20,043 INFO ]: Interpolant automaton has 16 states [2018-06-24 21:03:20,043 INFO ]: Constructing interpolant automaton starting with 16 interpolants. [2018-06-24 21:03:20,043 INFO ]: CoverageRelationStatistics Valid=48, Invalid=192, Unknown=0, NotChecked=0, Total=240 [2018-06-24 21:03:20,043 INFO ]: Start difference. First operand 12 states and 13 transitions. Second operand 16 states. [2018-06-24 21:03:21,077 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:21,077 INFO ]: Finished difference Result 42 states and 53 transitions. [2018-06-24 21:03:21,077 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-06-24 21:03:21,077 INFO ]: Start accepts. Automaton has 16 states. Word has length 11 [2018-06-24 21:03:21,077 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:21,078 INFO ]: With dead ends: 42 [2018-06-24 21:03:21,078 INFO ]: Without dead ends: 42 [2018-06-24 21:03:21,079 INFO ]: 0 DeclaredPredicates, 38 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 264 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=278, Invalid=912, Unknown=0, NotChecked=0, Total=1190 [2018-06-24 21:03:21,079 INFO ]: Start minimizeSevpa. Operand 42 states. [2018-06-24 21:03:21,083 INFO ]: Finished minimizeSevpa. Reduced states from 42 to 18. [2018-06-24 21:03:21,083 INFO ]: Start removeUnreachable. Operand 18 states. [2018-06-24 21:03:21,083 INFO ]: Finished removeUnreachable. Reduced from 18 states to 18 states and 24 transitions. [2018-06-24 21:03:21,083 INFO ]: Start accepts. Automaton has 18 states and 24 transitions. Word has length 11 [2018-06-24 21:03:21,084 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:21,084 INFO ]: Abstraction has 18 states and 24 transitions. [2018-06-24 21:03:21,084 INFO ]: Interpolant automaton has 16 states. [2018-06-24 21:03:21,084 INFO ]: Start isEmpty. Operand 18 states and 24 transitions. [2018-06-24 21:03:21,084 INFO ]: Finished isEmpty. Found accepting run of length 13 [2018-06-24 21:03:21,084 INFO ]: Found error trace [2018-06-24 21:03:21,084 INFO ]: trace histogram [3, 3, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:21,084 INFO ]: === Iteration 12 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:21,084 INFO ]: Analyzing trace with hash 1122107055, now seen corresponding path program 6 times [2018-06-24 21:03:21,084 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:21,084 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:21,085 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:21,085 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:21,085 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:21,113 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:21,510 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:21,510 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:21,510 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:21,516 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-24 21:03:21,544 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 3 check-sat command(s) [2018-06-24 21:03:21,544 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:21,546 INFO ]: Computing forward predicates... [2018-06-24 21:03:21,630 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:21,650 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:21,650 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2018-06-24 21:03:21,651 INFO ]: Interpolant automaton has 14 states [2018-06-24 21:03:21,651 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-24 21:03:21,651 INFO ]: CoverageRelationStatistics Valid=29, Invalid=153, Unknown=0, NotChecked=0, Total=182 [2018-06-24 21:03:21,651 INFO ]: Start difference. First operand 18 states and 24 transitions. Second operand 14 states. [2018-06-24 21:03:22,017 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:22,018 INFO ]: Finished difference Result 24 states and 31 transitions. [2018-06-24 21:03:22,018 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2018-06-24 21:03:22,018 INFO ]: Start accepts. Automaton has 14 states. Word has length 12 [2018-06-24 21:03:22,018 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:22,019 INFO ]: With dead ends: 24 [2018-06-24 21:03:22,019 INFO ]: Without dead ends: 24 [2018-06-24 21:03:22,019 INFO ]: 0 DeclaredPredicates, 27 GetRequests, 7 SyntacticMatches, 2 SemanticMatches, 18 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 46 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=62, Invalid=318, Unknown=0, NotChecked=0, Total=380 [2018-06-24 21:03:22,019 INFO ]: Start minimizeSevpa. Operand 24 states. [2018-06-24 21:03:22,022 INFO ]: Finished minimizeSevpa. Reduced states from 24 to 19. [2018-06-24 21:03:22,022 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-24 21:03:22,022 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 25 transitions. [2018-06-24 21:03:22,023 INFO ]: Start accepts. Automaton has 19 states and 25 transitions. Word has length 12 [2018-06-24 21:03:22,023 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:22,023 INFO ]: Abstraction has 19 states and 25 transitions. [2018-06-24 21:03:22,023 INFO ]: Interpolant automaton has 14 states. [2018-06-24 21:03:22,023 INFO ]: Start isEmpty. Operand 19 states and 25 transitions. [2018-06-24 21:03:22,023 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-24 21:03:22,023 INFO ]: Found error trace [2018-06-24 21:03:22,023 INFO ]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:22,023 INFO ]: === Iteration 13 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:22,023 INFO ]: Analyzing trace with hash 425077151, now seen corresponding path program 7 times [2018-06-24 21:03:22,023 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:22,023 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:22,024 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:22,024 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:22,024 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:22,034 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:22,126 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:22,126 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:22,126 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:22,133 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:22,163 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:22,165 INFO ]: Computing forward predicates... [2018-06-24 21:03:22,174 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:22,205 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:22,205 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 10 [2018-06-24 21:03:22,206 INFO ]: Interpolant automaton has 10 states [2018-06-24 21:03:22,206 INFO ]: Constructing interpolant automaton starting with 10 interpolants. [2018-06-24 21:03:22,206 INFO ]: CoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-06-24 21:03:22,206 INFO ]: Start difference. First operand 19 states and 25 transitions. Second operand 10 states. [2018-06-24 21:03:22,253 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:22,253 INFO ]: Finished difference Result 22 states and 27 transitions. [2018-06-24 21:03:22,255 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-24 21:03:22,255 INFO ]: Start accepts. Automaton has 10 states. Word has length 13 [2018-06-24 21:03:22,255 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:22,255 INFO ]: With dead ends: 22 [2018-06-24 21:03:22,255 INFO ]: Without dead ends: 18 [2018-06-24 21:03:22,256 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:22,256 INFO ]: Start minimizeSevpa. Operand 18 states. [2018-06-24 21:03:22,257 INFO ]: Finished minimizeSevpa. Reduced states from 18 to 18. [2018-06-24 21:03:22,257 INFO ]: Start removeUnreachable. Operand 18 states. [2018-06-24 21:03:22,258 INFO ]: Finished removeUnreachable. Reduced from 18 states to 18 states and 23 transitions. [2018-06-24 21:03:22,258 INFO ]: Start accepts. Automaton has 18 states and 23 transitions. Word has length 13 [2018-06-24 21:03:22,258 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:22,258 INFO ]: Abstraction has 18 states and 23 transitions. [2018-06-24 21:03:22,258 INFO ]: Interpolant automaton has 10 states. [2018-06-24 21:03:22,258 INFO ]: Start isEmpty. Operand 18 states and 23 transitions. [2018-06-24 21:03:22,258 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-24 21:03:22,258 INFO ]: Found error trace [2018-06-24 21:03:22,258 INFO ]: trace histogram [4, 3, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:22,258 INFO ]: === Iteration 14 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:22,258 INFO ]: Analyzing trace with hash -1841977592, now seen corresponding path program 8 times [2018-06-24 21:03:22,258 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:22,258 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:22,259 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:22,259 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-24 21:03:22,259 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:22,286 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:22,485 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:22,485 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:22,485 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:22,492 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-24 21:03:22,509 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-24 21:03:22,509 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:22,513 INFO ]: Computing forward predicates... [2018-06-24 21:03:23,540 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:23,559 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:23,559 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 20 [2018-06-24 21:03:23,560 INFO ]: Interpolant automaton has 20 states [2018-06-24 21:03:23,560 INFO ]: Constructing interpolant automaton starting with 20 interpolants. [2018-06-24 21:03:23,560 INFO ]: CoverageRelationStatistics Valid=66, Invalid=312, Unknown=2, NotChecked=0, Total=380 [2018-06-24 21:03:23,560 INFO ]: Start difference. First operand 18 states and 23 transitions. Second operand 20 states. [2018-06-24 21:03:26,928 WARN ]: Spent 312.00 ms on a formula simplification that was a NOOP. DAG size: 41 [2018-06-24 21:03:29,457 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:29,458 INFO ]: Finished difference Result 55 states and 68 transitions. [2018-06-24 21:03:29,458 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 43 states. [2018-06-24 21:03:29,458 INFO ]: Start accepts. Automaton has 20 states. Word has length 13 [2018-06-24 21:03:29,458 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:29,458 INFO ]: With dead ends: 55 [2018-06-24 21:03:29,458 INFO ]: Without dead ends: 55 [2018-06-24 21:03:29,460 INFO ]: 0 DeclaredPredicates, 58 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 838 ImplicationChecksByTransitivity, 5.2s TimeCoverageRelationStatistics Valid=581, Invalid=2384, Unknown=5, NotChecked=0, Total=2970 [2018-06-24 21:03:29,460 INFO ]: Start minimizeSevpa. Operand 55 states. [2018-06-24 21:03:29,463 INFO ]: Finished minimizeSevpa. Reduced states from 55 to 21. [2018-06-24 21:03:29,463 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-24 21:03:29,463 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 28 transitions. [2018-06-24 21:03:29,464 INFO ]: Start accepts. Automaton has 21 states and 28 transitions. Word has length 13 [2018-06-24 21:03:29,464 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:29,464 INFO ]: Abstraction has 21 states and 28 transitions. [2018-06-24 21:03:29,464 INFO ]: Interpolant automaton has 20 states. [2018-06-24 21:03:29,464 INFO ]: Start isEmpty. Operand 21 states and 28 transitions. [2018-06-24 21:03:29,464 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-24 21:03:29,464 INFO ]: Found error trace [2018-06-24 21:03:29,464 INFO ]: trace histogram [4, 4, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:29,464 INFO ]: === Iteration 15 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:29,464 INFO ]: Analyzing trace with hash -1267233690, now seen corresponding path program 9 times [2018-06-24 21:03:29,464 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:29,464 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:29,465 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:29,465 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:29,465 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:29,476 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:29,674 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:29,674 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:29,674 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:29,682 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-24 21:03:29,720 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-24 21:03:29,720 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:29,724 INFO ]: Computing forward predicates... [2018-06-24 21:03:30,185 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:30,204 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:30,204 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 17 [2018-06-24 21:03:30,204 INFO ]: Interpolant automaton has 17 states [2018-06-24 21:03:30,204 INFO ]: Constructing interpolant automaton starting with 17 interpolants. [2018-06-24 21:03:30,204 INFO ]: CoverageRelationStatistics Valid=36, Invalid=236, Unknown=0, NotChecked=0, Total=272 [2018-06-24 21:03:30,205 INFO ]: Start difference. First operand 21 states and 28 transitions. Second operand 17 states. [2018-06-24 21:03:30,458 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:30,458 INFO ]: Finished difference Result 28 states and 36 transitions. [2018-06-24 21:03:30,458 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-24 21:03:30,458 INFO ]: Start accepts. Automaton has 17 states. Word has length 14 [2018-06-24 21:03:30,458 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:30,458 INFO ]: With dead ends: 28 [2018-06-24 21:03:30,458 INFO ]: Without dead ends: 28 [2018-06-24 21:03:30,459 INFO ]: 0 DeclaredPredicates, 32 GetRequests, 8 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 67 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=77, Invalid=475, Unknown=0, NotChecked=0, Total=552 [2018-06-24 21:03:30,459 INFO ]: Start minimizeSevpa. Operand 28 states. [2018-06-24 21:03:30,460 INFO ]: Finished minimizeSevpa. Reduced states from 28 to 22. [2018-06-24 21:03:30,460 INFO ]: Start removeUnreachable. Operand 22 states. [2018-06-24 21:03:30,461 INFO ]: Finished removeUnreachable. Reduced from 22 states to 22 states and 29 transitions. [2018-06-24 21:03:30,461 INFO ]: Start accepts. Automaton has 22 states and 29 transitions. Word has length 14 [2018-06-24 21:03:30,461 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:30,462 INFO ]: Abstraction has 22 states and 29 transitions. [2018-06-24 21:03:30,462 INFO ]: Interpolant automaton has 17 states. [2018-06-24 21:03:30,462 INFO ]: Start isEmpty. Operand 22 states and 29 transitions. [2018-06-24 21:03:30,462 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-24 21:03:30,462 INFO ]: Found error trace [2018-06-24 21:03:30,462 INFO ]: trace histogram [5, 4, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:30,462 INFO ]: === Iteration 16 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:30,462 INFO ]: Analyzing trace with hash -630041912, now seen corresponding path program 10 times [2018-06-24 21:03:30,462 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:30,462 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:30,463 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:30,463 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:30,463 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:30,472 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:30,604 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:30,605 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:30,605 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 14 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-24 21:03:30,611 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-24 21:03:30,628 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-24 21:03:30,628 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:30,630 INFO ]: Computing forward predicates... [2018-06-24 21:03:30,640 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:30,664 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:30,664 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 12] total 12 [2018-06-24 21:03:30,664 INFO ]: Interpolant automaton has 12 states [2018-06-24 21:03:30,664 INFO ]: Constructing interpolant automaton starting with 12 interpolants. [2018-06-24 21:03:30,665 INFO ]: CoverageRelationStatistics Valid=41, Invalid=91, Unknown=0, NotChecked=0, Total=132 [2018-06-24 21:03:30,665 INFO ]: Start difference. First operand 22 states and 29 transitions. Second operand 12 states. [2018-06-24 21:03:30,723 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-24 21:03:30,723 INFO ]: Finished difference Result 26 states and 32 transitions. [2018-06-24 21:03:30,723 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 13 states. [2018-06-24 21:03:30,723 INFO ]: Start accepts. Automaton has 12 states. Word has length 15 [2018-06-24 21:03:30,723 INFO ]: Finished accepts. some prefix is accepted. [2018-06-24 21:03:30,724 INFO ]: With dead ends: 26 [2018-06-24 21:03:30,724 INFO ]: Without dead ends: 21 [2018-06-24 21:03:30,724 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:30,724 INFO ]: Start minimizeSevpa. Operand 21 states. [2018-06-24 21:03:30,725 INFO ]: Finished minimizeSevpa. Reduced states from 21 to 21. [2018-06-24 21:03:30,726 INFO ]: Start removeUnreachable. Operand 21 states. [2018-06-24 21:03:30,726 INFO ]: Finished removeUnreachable. Reduced from 21 states to 21 states and 27 transitions. [2018-06-24 21:03:30,726 INFO ]: Start accepts. Automaton has 21 states and 27 transitions. Word has length 15 [2018-06-24 21:03:30,726 INFO ]: Finished accepts. word is rejected. [2018-06-24 21:03:30,726 INFO ]: Abstraction has 21 states and 27 transitions. [2018-06-24 21:03:30,726 INFO ]: Interpolant automaton has 12 states. [2018-06-24 21:03:30,726 INFO ]: Start isEmpty. Operand 21 states and 27 transitions. [2018-06-24 21:03:30,727 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-24 21:03:30,727 INFO ]: Found error trace [2018-06-24 21:03:30,727 INFO ]: trace histogram [5, 4, 1, 1, 1, 1, 1, 1] [2018-06-24 21:03:30,727 INFO ]: === Iteration 17 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-24 21:03:30,727 INFO ]: Analyzing trace with hash 2105705087, now seen corresponding path program 11 times [2018-06-24 21:03:30,727 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-24 21:03:30,727 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-24 21:03:30,728 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:30,728 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-24 21:03:30,728 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-24 21:03:30,743 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:30,973 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:30,973 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-24 21:03:30,973 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:30,981 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-24 21:03:31,017 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 4 check-sat command(s) [2018-06-24 21:03:31,017 INFO ]: Conjunction of SSA is unsat [2018-06-24 21:03:31,021 INFO ]: Computing forward predicates... [2018-06-24 21:03:45,609 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:45,628 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-24 21:03:45,628 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 24 [2018-06-24 21:03:45,628 INFO ]: Interpolant automaton has 24 states [2018-06-24 21:03:45,628 INFO ]: Constructing interpolant automaton starting with 24 interpolants. [2018-06-24 21:03:45,628 INFO ]: CoverageRelationStatistics Valid=84, Invalid=459, Unknown=9, NotChecked=0, Total=552 [2018-06-24 21:03:45,628 INFO ]: Start difference. First operand 21 states and 27 transitions. Second operand 24 states. [2018-06-24 21:04:17,086 WARN ]: Spent 20.12 s on a formula simplification that was a NOOP. DAG size: 88 Received shutdown request... [2018-06-24 21:04:35,334 WARN ]: Removed 3 from assertion stack [2018-06-24 21:04:35,334 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-24 21:04:35,335 WARN ]: Verification canceled [2018-06-24 21:04:35,337 INFO ]: Did not count any witness invariants because Icfg is not BoogieIcfg [2018-06-24 21:04:35,338 WARN ]: Timeout [2018-06-24 21:04:35,339 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 24.06 09:04:35 BasicIcfg [2018-06-24 21:04:35,339 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-24 21:04:35,339 INFO ]: Toolchain (without parser) took 80304.44 ms. Allocated memory was 308.8 MB in the beginning and 407.4 MB in the end (delta: 98.6 MB). Free memory was 263.2 MB in the beginning and 192.7 MB in the end (delta: 70.5 MB). Peak memory consumption was 169.1 MB. Max. memory is 3.6 GB. [2018-06-24 21:04:35,340 INFO ]: SmtParser took 0.08 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-24 21:04:35,340 INFO ]: ChcToBoogie took 56.07 ms. Allocated memory is still 308.8 MB. Free memory was 263.2 MB in the beginning and 261.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-24 21:04:35,341 INFO ]: Boogie Preprocessor took 35.24 ms. Allocated memory is still 308.8 MB. Free memory is still 261.2 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-24 21:04:35,341 INFO ]: RCFGBuilder took 267.71 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 251.2 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:35,342 INFO ]: BlockEncodingV2 took 74.62 ms. Allocated memory is still 308.8 MB. Free memory was 251.2 MB in the beginning and 249.2 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:35,342 INFO ]: TraceAbstraction took 79861.06 ms. Allocated memory was 308.8 MB in the beginning and 407.4 MB in the end (delta: 98.6 MB). Free memory was 249.2 MB in the beginning and 192.7 MB in the end (delta: 56.5 MB). Peak memory consumption was 155.1 MB. Max. memory is 3.6 GB. [2018-06-24 21:04:35,345 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.08 ms. Allocated memory is still 308.8 MB. Free memory is still 273.3 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 56.07 ms. Allocated memory is still 308.8 MB. Free memory was 263.2 MB in the beginning and 261.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 35.24 ms. Allocated memory is still 308.8 MB. Free memory is still 261.2 MB. There was no memory consumed. Max. memory is 3.6 GB. * RCFGBuilder took 267.71 ms. Allocated memory is still 308.8 MB. Free memory was 261.2 MB in the beginning and 251.2 MB in the end (delta: 10.0 MB). Peak memory consumption was 10.0 MB. Max. memory is 3.6 GB. * BlockEncodingV2 took 74.62 ms. Allocated memory is still 308.8 MB. Free memory was 251.2 MB in the beginning and 249.2 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 79861.06 ms. Allocated memory was 308.8 MB in the beginning and 407.4 MB in the end (delta: 98.6 MB). Free memory was 249.2 MB in the beginning and 192.7 MB in the end (delta: 56.5 MB). Peak memory consumption was 155.1 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 10 states, 24 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 92. - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 8 locations, 1 error locations. TIMEOUT Result, 79.8s OverallTime, 17 OverallIterations, 5 TraceHistogramMax, 58.6s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 91 SDtfs, 155 SDslu, 417 SDs, 0 SdLazy, 793 SolverSat, 267 SolverUnsat, 4 SolverUnknown, 0 SolverNotchecked, 6.1s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 357 GetRequests, 113 SyntacticMatches, 6 SemanticMatches, 237 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1346 ImplicationChecksByTransitivity, 53.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, 19.8s 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/012b-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-0-2018-06-24_21-04-35-433.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/012b-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-GraphSizeCsvProvider-1-2018-06-24_21-04-35-433.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/012b-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-Benchmark-0-2018-06-24_21-04-35-433.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/012b-horn.smt2_AutomizerCHC_Goto.epf_AutomizerCHC_wBE.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-24_21-04-35-433.csv Completed graceful shutdown